Stable Matching with Evolving Preferences
Add this Pith Number to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{QB2O2WXO}
Prints a linked pith:QB2O2WXO badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
We consider the problem of stable matching with dynamic preference lists. At each time step, the preference list of some player may change by swapping random adjacent members. The goal of a central agency (algorithm) is to maintain an approximately stable matching (in terms of number of blocking pairs) at all times. The changes in the preference lists are not reported to the algorithm, but must instead be probed explicitly by the algorithm. We design an algorithm that in expectation and with high probability maintains a matching that has at most $O((log (n))^2)$ blocking pairs.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.