Stable matching polytope
In mathematics, economics, and computer science, the stable matching polytope or stable marriage polytope is a convex polytope derived from the solutions to an instance of the stable matching problem.[1][2]
Description
[edit]The stable matching polytope is the convex hull of the indicator vectors of the stable matchings of the given problem. It has a dimension for each pair of elements that can be matched, and a vertex for each stable matchings. For each vertex, the Cartesian coordinates are one for pairs that are matched in the corresponding matching, and zero for pairs that are not matched.[1]
The stable matching polytope has a polynomial number of facets. These include the conventional inequalities describing matchings without the requirement of stability (each coordinate must be between 0 and 1, and for each element to be matched the sum of coordinates for the pairs involving that element must be exactly one), together with inequalities constraining the resulting matching to be stable (for each potential matched pair elements, the sum of coordinates for matches that are at least as good for one of the two elements must be at least one). The points satisfying all of these constraints can be thought of as the fractional solutions of a linear programming relaxation of the stable matching problem.
Integrality
[edit]It is a theorem of Vande Vate (1989) that the polytope described by the facet constraints listed above has only the vertices described above. In particular it is an integral polytope. This can be seen as an analogue of the theorem of Garrett Birkhoff that an analogous polytope, the Birkhoff polytope describing the set of all fractional matchings between two sets, is integral.[3]
An equivalent way of stating the same theorem is that every fractional matching can be expressed as a convex combination of integral matchings. Teo & Sethuraman (1998) prove this by constructing a probability distribution on integral matchings whose expected value can be set equal to any given fractional matching. To do so, they perform the following steps:
- Consider for each element on one side of the stable matching problem (the doctors, say, in a problem matching doctors to hospitals) the fractional values assigned to pairings with the elements on the other side (the hospitals), and sort these values in decreasing order by that doctor's preferences.
- Partition the unit interval into subintervals, of lengths equal to these fractional values, in the sorted order. Choosing a random number in the unit interval will give a random match for the selected doctor, with probability equal to the fractional weight of that match.
- Symmetrically, consider for each element on the other side of the stable matching (the hospitals), sort the fractional values for pairings involving that element in increasing order by preference, and construct a partition of the unit interval whose subintervals have these fractional values in the sorted order.
- It can be proven that, for each matched pair, the subintervals associated with that pair are the same in both the partition for the doctor and the partition for the hospital in that pair. Therefore, choosing a single random number in the unit interval, and using that choice to simultaneously select a hospital for each doctor and a doctor for each hospital, gives a matching. Moreover, this matching can be shown to be stable.
The resulting randomly chosen stable matching chooses any particular matched pair with probability equal to the fractional coordinate value of that pair. Therefore, the probability distribution over stable matchings constructed in this way provides a representation of the given fractional matching as a convex combination of integral stable matchings.[4]
Lattice of fractional matchings
[edit]The family of all stable matchings forms a distributive lattice, the lattice of stable matchings, in which the join of two matchings gives all doctors their preference among their assigned hospitals in the two matchings, and the meet gives all hospitals their preference.[5] The same is true of the family of all fractional stable matchings, the points of the stable matching polytope.[3]
In the stable matching polytope, one can define one matching to dominate another if, for every doctor and hospital, the total fractional value assigned to matches for that doctor that are at least as good (for the doctor) as that hospital are at least as large in the first matching as in the second. This defines a partial order on the fractional matchings. This partial order has a unique largest element, the integer stable matching found by a version of the Gale–Shapley algorithm in which the doctors propose matches and the hospitals respond to the proposals. It also has a unique smallest element, the integer stable matching found by a version of the Gale–Shapley algorithm in which the hospitals make the proposals.[3]
Consistently with this partial order, one can define the meet of two fractional matchings to be a fractional matching that is as low as possible in the partial order while dominating the two matchings. For each doctor and hospital, it assigns to that potential matched pair a weight that makes the total weight of that pair and all better pairs for the same doctor equal to the larger of the corresponding totals from the two given matchings. The join is defined symmetrically.[3]
Applications
[edit]By applying linear programming to the stable matching polytope, one can find the minimum or maximum weight stable matching.[1] Alternative methods for the same problem include applying the closure problem to a partially ordered set derived from the lattice of stable matchings,[6] or applying linear programming to the order polytope of this partial order.
Relation to order polytope
[edit]The property of the stable matching polytope, of defining a continuous distributive lattice is analogous to the defining property of a distributive polytope, a polytope in which coordinatewise maximization and minimization form the meet and join operations of a lattice.[7] However, the meet and join operations for the stable matching polytope are defined in a different way than coordinatewise maximization and minimization. Instead, the order polytope of the underlying partial order of the lattice of stable matchings provides a distributive polytope associated with the set of stable matchings, but one for which it is more difficult to read off the fractional value associated with each matched pair. In fact, the stable matching polytope and the order polytope of the underlying partial order are very closely related to each other: each is an affine transformation of the other.[8]
References
[edit]- ^ a b c Vande Vate, John H. (1989), "Linear programming brings marital bliss", Operations Research Letters, 8 (3): 147–153, doi:10.1016/0167-6377(89)90041-2, MR 1007271
- ^ Ratier, Guillaume (1996), "On the stable marriage polytope" (PDF), Discrete Mathematics, 148 (1–3): 141–159, doi:10.1016/0012-365X(94)00237-D, MR 1368286
- ^ a b c d Roth, Alvin E.; Rothblum, Uriel G.; Vande Vate, John H. (1993), "Stable matchings, optimal assignments, and linear programming", Mathematics of Operations Research, 18 (4): 803–828, doi:10.1287/moor.18.4.803, JSTOR 3690124, MR 1251681
- ^ Teo, Chung-Piaw; Sethuraman, Jay (1998), "The geometry of fractional stable matchings and its applications", Mathematics of Operations Research, 23 (4): 874–891, doi:10.1287/moor.23.4.874, MR 1662426
- ^ Knuth, Donald E. (1976), Mariages stables et leurs relations avec d'autres problèmes combinatoires (PDF) (in French), Montréal, Quebec: Les Presses de l'Université de Montréal, ISBN 0-8405-0342-3, MR 0488980. See in particular Problem 6, pp. 87–94.
- ^ Irving, Robert W.; Leather, Paul; Gusfield, Dan (1987), "An efficient algorithm for the "optimal" stable marriage", Journal of the ACM, 34 (3): 532–543, doi:10.1145/28869.28871, MR 0904192
- ^ Felsner, Stefan; Knauer, Kolja (2011), "Distributive lattices, polyhedra, and generalized flows", European Journal of Combinatorics, 32 (1): 45–59, doi:10.1016/j.ejc.2010.07.011, MR 2727459.
- ^ Aprile, Manuel; Cevallos, Alfonso; Faenza, Yuri (2018), "On 2-level polytopes arising in combinatorial settings", SIAM Journal on Discrete Mathematics, 32 (3): 1857–1886, arXiv:1702.03187, doi:10.1137/17M1116684, MR 3835234