Abstract
We study two-sided matching markets with locality of information and control. Each male (female) agent has an arbitrary strict preference list over all female (male) agents. In addition, each agent is a node in a fixed network. Agents learn about possible partners dynamically based on their current network neighborhood. We consider convergence of dynamics to locally stable matchings that are stable with respect to their imposed information structure in the network. While existence of such states is guaranteed, we show that reachability becomes NP-hard to decide. This holds even when the network exists only among one side. In contrast, if only one side has no network and agents remember a previous match every round, reachability is guaranteed and random dynamics converge with probability 1. We characterize this positive result in various ways. For instance, it holds for random memory and for memory with the most recent partner, but not for memory with the best partner. Also, it is crucial which partition of the agents has memory. Finally, we conclude with results on approximating maximum locally stable matchings.
Supported by DFG Cluster of Excellence MMCI and grant Ho 3831/3-1. An extended full version of this paper can be found at http://arxiv.org/abs/1207.1265
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
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)
Arcaute, E., Vassilvitskii, S.: Social networks and stable matchings in the job market. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 220–231. Springer, Heidelberg (2009)
Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. Theory of Computing 7(1), 27–43 (2011)
Biró, P., Cechlárová, K., Fleiner, T.: The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems. Int. J. Game Theory 36(3-4), 333–352 (2008)
Blum, Y., Roth, A., Rothblum, U.: Vacancy chains and equilibration in senior-level labor markets. J. Econom. Theory 76, 362–411 (1997)
Blum, Y., Rothblum, U.: “Timing is everything” and martial bliss. J. Econom. Theory 103, 429–442 (2002)
Cheng, C., McDermid, E.: Maximum locally stable matchings. In: Proc. 2nd Intl. Workshop Matching under Preferences (MATCH-UP), pp. 51–62 (2012)
Diamantoudi, E., Miyagawa, E., Xue, L.: Random paths to stability in the roommates problem. Games Econom. Behav. 48(1), 18–28 (2004)
Goemans, M., Li, L., Mirrokni, V., Thottan, M.: Market sharing games applied to content distribution in ad-hoc networks. IEEE J. Sel. Area Comm. 24(5), 1020–1033 (2006)
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)
Inarra, E., Larrea, C., Moris, E.: Random paths to P-stability in the roommates problem. Int. J. Game Theory 36(3-4), 461–471 (2008)
Inarra, E., Larrea, C., Moris, E.: The stability of the roommate problem revisited. Core Discussion Paper 2010/7 (2010)
Irving, R.: An efficient algorithm for the ”stable roommates” problem. J. Algorithms 6(4), 577–595 (1985)
Klaus, B., Klijn, F., Walzl, M.: Stochastic stability for rommate markets. J. Econom. Theory 145, 2218–2240 (2010)
Knuth, D.: Marriages stables et leurs relations avec d’autres problemes combinatoires. Les Presses de l’Université de Montréal (1976)
McDermid, E.: A 3/2-approximation algorithm for general stable marriage. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 689–700. Springer, Heidelberg (2009)
Roth, A., Sönmezc, T., Ünver, M.U.: Pairwise kidney exchange. J. Econom. Theory 125(2), 151–188 (2005)
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)
Yanagisawa, H.: Approximation algorithms for stable marriage problems. PhD thesis, Kyoto University, Graduate School of Informatics (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hoefer, M., Wagner, L. (2013). Locally Stable Marriage with Strict Preferences. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds) Automata, Languages, and Programming. ICALP 2013. Lecture Notes in Computer Science, vol 7966. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39212-2_54
Download citation
DOI: https://doi.org/10.1007/978-3-642-39212-2_54
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39211-5
Online ISBN: 978-3-642-39212-2
eBook Packages: Computer ScienceComputer Science (R0)