Matching Dynamics with Constraints

DOI10.1007/978-3-319-13129-0_12MaRDI QIDQ2936983zbMATH OpenOpenAlexFDO

Authors Martin Hoefer, Lisa Wagner

Publication date 7 January 2015

Published in Web and Internet Economics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.4304

zbMATH Keywords

hedonic coalition formation gameslocal constraintsmatching gamesmatching marketsNP-hardness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Cooperative games (91A12) Matching models (91B68)

Abstract: We study uncoordinated matching markets with additional local constraints that capture, e.g., restricted information, visibility, or externalities in markets. Each agent is a node in a fixed matching network and strives to be matched to another agent. Each agent has a complete preference list over all other agents it can be matched with. However, depending on the constraints and the current state of the game, not all possible partners are available for matching at all times. For correlated preferences, we propose and study a general class of hedonic coalition formation games that we call coalition formation games with constraints. This class includes and extends many recently studied variants of stable matching, such as locally stable matching, socially stable matching, or friendship matching. Perhaps surprisingly, we show that all these variants are encompassed in a class of "consistent" instances that always allow a polynomial improvement sequence to a stable state. In addition, we show that for consistent instances there always exists a polynomial sequence to every reachable state. Our characterization is tight in the sense that we provide exponential lower bounds when each of the requirements for consistency is violated. We also analyze matching with uncorrelated preferences, where we obtain a larger variety of results. While socially stable matching always allows a polynomial sequence to a stable state, for other classes different additional assumptions are sufficient to guarantee the same results. For the problem of reaching a given stable state, we show NP-hardness in almost all considered classes of matching games.

Recommendations

• The problem of realizing constraints in dynamics
• Dynamics of constrained systems
• scientific article; zbMATH DE number 1014978
• Stable constrained dynamics
• Dynamics of Constrained Multibody Systems
• Constrained integration of rigid body dynamics
• Constructing equations of constrained dynamical systems
• Matching with Regular Constraints

Cited in

(9)

• Dynamics in matching and coalition formation games with structural constraints
• Local matching dynamics in social networks
• Paths to stable allocations
• Stable matching with network externalities
• Local matching dynamics in social networks
• Maintaining Near-Popular Matchings
• scientific article; zbMATH DE number 1787124 (Why is no real title available?)
• Preference-constrained oriented matching
• Matching with Regular Constraints

This page was built for publication: Matching Dynamics with Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2936983)