Paper Info
Title
The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems
Abstract
We study the dynamics of stable marriage and stable roommates markets. Our main tool is the incremental algorithm of Roth and Vande Vate and its generalization by Tan and Hsueh. Beyond proposing alternative proofs for known results, we also generalize some of them to the nonbipartite case. In particular, we show that the lastcomer gets his best stable partner in both incremental algorithms. Consequently, we confirm that it is better to arrive later than earlier to a stable roommates market. We also prove that when the equilibrium is restored after the arrival of a new agent, some agents will be better off under any stable solution for the new market than at any stable solution for the original market. We also propose a procedure to find these agents.
Year
DOI
Venue
2008
10.1007/s00182-007-0084-3
Int. J. Game Theory
Keywords
Field
DocType
stable marriage problem · stable roommates problem · matching mechanism,stable marriage,stable roommates problem,stable matching,stable marriage problem
Welfare economics,Stable roommates problem,Mathematical economics,Stable marriage problem,Mathematical proof,Mathematics
Journal
Volume
Issue
ISSN
36
3
1432-1270
Citations 
PageRank 
References 
8
0.57
16
Authors
3
Name
Order
Citations
PageRank
Péter Biró123719.83
Katarína Cechlárová222628.02
Tamás Fleiner324127.45