On the stable marriage polytope

✍ Scribed by Guillaume Ratier

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 727 KB
• Volume: 148
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00237-d

✦ Synopsis

The stable marriage problem is a game theoretic model introduced by Gale and Shapley (1962). It involves two sets of players referred to as men and women. A marriage is a set of disjoint pairs, where each pair consists of a woman and a man. Each individual has a strict linear order of preference over the set of opposite sex. A marriage is called stable if there is no man and woman who both prefer being matched to each other over the outcome they obtained in the marriage.

Conway showed 'that the set of stable marriages can be ordered as a lattice. Vande Vate (1989) described the polytope whose extreme points are the set of stable marriages. Rothblum simplified and extended this result.

In this paper the marriage problem is reformulated in terms of a marriage market graph. A stable marriage is characterized as a kernel of the graph. Equivalent marriage graphs are those having the same sets of stable marriages, and it is shown how a "simplest" such graph can be obtained. The faces of the polytope are characterized in terms of the lattice of stable marriages.

Elsevier Science B.V.