Abstract
We study dynamic matching problems in graphs among agents with preferences. Agents and/or edges of the graph arrive and depart iteratively over time. The goal is to maintain matchings that are favorable to the agent population and stable over time. More formally, we strive to keep a small unpopularity factor by making only a small amortized number of changes to the matching per round. Our main result is an algorithm to maintain matchings with unpopularity factor \((\Delta +k)\) by making an amortized number of \(O(\Delta + \Delta ^2/k)\) changes per round, for any \(k > 0\). Here \(\Delta \) 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 that might be of independent interest. First, our algorithm implies existence of matchings with small unpopularity factors in graphs with bounded degree. Second, given any matching M and any value \(\alpha \ge 1\), we provide an efficient algorithm to compute a matching \(M'\) with unpopularity factor \(\alpha \) over M if it exists. Finally, our results show the absence of voting paths in two-sided instances, even if we restrict to sequences of matchings with larger unpopularity factors (below \(\Delta )\).
Supported by DFG Cluster of Excellence MMCI at Saarland University.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abraham, D., Irving, R., Kavitha, T., Mehlhorn, K.: Popular matchings. SIAM J. Comput. 37(4), 1030–1045 (2007)
Abraham, D., Kavitha, T.: Voting paths. SIAM J. Disc. Math. 24(2), 520–537 (2010)
Ackermann, H., Goldberg, P., Mirrokni, V., Röglin, H., Vöcking, B.: Uncoordinated two-sided matching markets. SIAM J. Comput. 40(1), 92–106 (2011)
Baswana, S., Gupta, M., Sen, S.: Fully dynamic maximal matching in \(O(\log n)\) update time. In: Proc. 52nd Symp. Foundations of Computer Science (FOCS), pp. 383–392 (2011)
Bhattacharya, S., Henzinger, M., Italiano, G.: Deterministic fully dynamic data structures for vertex cover and matching. In: Proc. 25th Symp. Discrete Algorithms (SODA), pp. 785–804 (2015)
Biró, P., Irving, R.W., Manlove, D.F.: Popular matchings in the marriage and roommates problems. In: Calamoneri, T., Diaz, J. (eds.) CIAC 2010. LNCS, vol. 6078, pp. 97–108. Springer, Heidelberg (2010)
Diamantoudi, E., Miyagawa, E., Xue, L.: Random paths to stability in the roommates problem. Games Econom. Behav. 48(1), 18–28 (2004)
Gärdenfors, P.: Match making: Assignments based on bilateral preferences. Behavioural Sciences 20, 166–173 (1975)
Gupta, M., Peng, R.: Fully dynamic (1+\(\varepsilon \))-approximate matchings. In: Proc. 54th Symp. Foundations of Computer Science (FOCS), pp. 548–557 (2013)
Gusfield, D., Irving, R.: The Stable Marriage Problem: Structure and Algorithms. MIT Press (1989)
Hoefer, M.: Local matching dynamics in social networks. Inf. Comput. 222, 20–35 (2013)
Hoefer, M., Wagner, L.: Locally stable marriage with strict preferences. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 620–631. Springer, Heidelberg (2013)
Hoefer, M., Wagner, L.: Matching dynamics with constraints. In: Liu, T.-Y., Qi, Q., Ye, Y. (eds.) WINE 2014. LNCS, vol. 8877, pp. 161–174. Springer, Heidelberg (2014)
Huang, C., Kavitha, T.: Near-popular matchings in the roommates problem. SIAM J. Disc. Math. 27(1), 43–62 (2013)
Knuth, D.: Marriages stables et leurs relations avec d’autres problemes combinatoires. Les Presses de l’Université de Montréal (1976)
Manlove, D.: Algorithmics of Matching Under Preferences. World Scientific (2013)
McCutchen, R.M.: The least-unpopularity-factor and least-unpopularity-margin criteria for matching problems with one-sided preferences. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 593–604. Springer, Heidelberg (2008)
Onak, K., Rubinfeld, R.: Maintaining a large matching and a small vertex cover. In: Proc. 42nd Symp. Theory of Computing (STOC), pp. 457–464 (2010)
Roth, A., Sotomayor, M.O.: Two-sided Matching: A study in game-theoretic modeling and analysis. Cambridge University Press (1990)
Roth, A., Vate, J.V.: Random paths to stability in two-sided matching. Econometrica 58(6), 1475–1480 (1990)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bhattacharya, S., Hoefer, M., Huang, CC., Kavitha, T., Wagner, L. (2015). Maintaining Near-Popular Matchings. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9135. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47666-6_40
Download citation
DOI: https://doi.org/10.1007/978-3-662-47666-6_40
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47665-9
Online ISBN: 978-3-662-47666-6
eBook Packages: Computer ScienceComputer Science (R0)