Stable matching polytope

Last updated

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]

Contents

Description

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

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:

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

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

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

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]

Related Research Articles

<span class="mw-page-title-main">Linear programming</span> Method to solve some optimization problems

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming.

In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is—up to isomorphism—given as such a lattice of sets.

In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures in a one-to-one fashion, often by means of an involution operation: if the dual of A is B, then the dual of B is A. Such involutions sometimes have fixed points, so that the dual of A is A itself. For example, Desargues' theorem is self-dual in this sense under the standard duality in projective geometry.

<span class="mw-page-title-main">Antimatroid</span> Mathematical system of orderings or sets

In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included. Antimatroids are commonly axiomatized in two equivalent ways, either as a set system modeling the possible states of such a process, or as a formal language modeling the different sequences in which elements may be included. Dilworth (1940) was the first to study antimatroids, using yet another axiomatization based on lattice theory, and they have been frequently rediscovered in other contexts.

In mathematics, economics, and computer science, the stable marriage problem is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a bijection from the elements of one set to the elements of the other set. A matching is not stable if:

<span class="mw-page-title-main">Convex polytope</span> Convex hull of a finite set of points in a Euclidean space

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.

<span class="mw-page-title-main">Linear programming relaxation</span>

In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.

The Birkhoff polytopeBn is the convex polytope in RN whose points are the doubly stochastic matrices, i.e., the n × n matrices whose entries are non-negative real numbers and whose rows and columns each add up to 1. It is named after Garrett Birkhoff.

<span class="mw-page-title-main">Dedekind–MacNeille completion</span> Smallest complete lattice containing a partial order

In mathematics, specifically order theory, the Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains it. It is named after Holbrook Mann MacNeille whose 1937 paper first defined and constructed it, and after Richard Dedekind because its construction generalizes the Dedekind cuts used by Dedekind to construct the real numbers from the rational numbers. It is also called the completion by cuts or normal completion.

<span class="mw-page-title-main">Median graph</span> Graph with a median for each three vertices

In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest paths between each pair of a, b, and c.

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets. The theorem can be interpreted as providing a one-to-one correspondence between distributive lattices and partial orders, between quasi-ordinal knowledge spaces and preorders, or between finite topological spaces and preorders. It is named after Garrett Birkhoff, who published a proof of it in 1937.

<span class="mw-page-title-main">Integral polytope</span> A convex polytope whose vertices all have integer Cartesian coordinates

In geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it is a polytope that equals the convex hull of its integer points. Integral polytopes are also called lattice polytopes or Z-polytopes. The special cases of two- and three-dimensional integral polytopes may be called polygons or polyhedra instead of polytopes, respectively.

In the study of algorithms, an LP-type problem is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems include many important optimization problems that are not themselves linear programs, such as the problem of finding the smallest circle containing a given set of planar points. They may be solved by a combination of randomized algorithms in an amount of time that is linear in the number of elements defining the problem, and subexponential in the dimension of the problem.

In the geometry of convex polytopes, a distributive polytope is a convex polytope for which coordinatewise minima and maxima of pairs of points remain within the polytope. For example, this property is true of the unit cube, so the unit cube is a distributive polytope. It is called a distributive polytope because the coordinatewise minimum and coordinatewise maximum operations form the meet and join operations of a continuous distributive lattice on the points of the polytope.

In mathematics, the order polytope of a finite partially ordered set is a convex polytope defined from the set. The points of the order polytope are the monotonic functions from the given set to the unit interval, its vertices correspond to the upper sets of the partial order, and its dimension is the number of elements in the partial order. The order polytope is a distributive polytope, meaning that coordinatewise minima and maxima of pairs of its points remain within the polytope.

In mathematics, economics, and computer science, the lattice of stable matchings is a distributive lattice whose elements are stable matchings. For a given instance of the stable matching problem, this lattice provides an algebraic description of the family of all solutions to the problem. It was originally described in the 1970s by John Horton Conway and Donald Knuth.

In graph theory, a fractional matching is a generalization of a matching in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices.

In graph theory, the matching polytope of a given graph is a geometric object representing the possible matchings in the graph. It is a convex polytope each of whose corners corresponds to a matching. It has great theoretical importance in the theory of matching.

References

  1. 1 2 3 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
  2. ↑ 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
  3. 1 2 3 4 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
  4. ↑ 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
  5. ↑ 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.
  6. ↑ 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
  7. ↑ 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 .
  8. ↑ 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
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.