Maintaining Near-Popular Matchings

In dynamic matching, vertices and/or edges of the graph arrive and depart iteratively over time. The goal is to maintain good matchings by making only a small amortized number of changes to the matching. We present the first algorithmic study of dynamic matching under preferences, where we strive to maintain matchings that are favorable to the agent population and stable over time. Our main result is an algorithm to maintain matchings with unpopularity factor (D+k) by making an amortized number of O(D + D^2/k)) changes per round, for any k>0. Here D denotes the maximum degree of any agent in any round. We complement this result by a variety of lower bounds indicating that matchings with smaller factor do not exist or cannot be maintained using our algorithm. As a byproduct, we obtain several additional results on (un-)popular matchings that might be of independent interest.