This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Fleiner, T. Search for Related Content

A Fixed-Point Approach to Stable Matchings and Some Applications

Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, POB 127, H-1364 Budapest, Hungary
fleiner{at}renyi.hu

We describe a fixed-point based approach to the theory of bipartite stable matchings. By this, we provide a common framework that links together seemingly distant results, like the stable marriage theorem of Gale and Shapley, the Mendelsohn-Dulmage theorem, the Kundu-Lawler theorem, Tarski's fixed-point theorem, the Cantor-Bernstein theorem, Pym's linking theorem, or the monochromatic path theorem of Sands et al. In this framework, we formulate a matroidgeneralization of the stable marriage theorem and study the lattice structure of generalized stable matchings. Based on the theory of lattice polyhedra and blocking polyhedra, we extend results of Vande Vate and Rothblum on the bipartite stable matching polytope.

Key Words: Stable marriage problem; stable matching; fixed point theorem; lattice polyhedron
History: Received: June 21, 1999; revision received: November 22, 1999;revision received: June 4, 2002;

This article has been cited by other articles:

				S. Fujishige and A. Tamura A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis Mathematics of Operations Research, February 1, 2007; 32(1): 136 - 155. [Abstract] [PDF]

				J. Sethuraman, C.-P. Teo, and L. Qian Many-to-One Stable Matching: Geometry and Fairness Mathematics of Operations Research, August 1, 2006; 31(3): 581 - 596. [Abstract] [PDF]