In mathematics,

economics Economics () is the social science that studies the production, distribution, and consumption of goods and services. Economics focuses on the behaviour and interactions of economic agents and how economies work. Microeconomics analy ...

, and

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...

, the stable matching polytope or stable marriage polytope is a convex polytope derived from the solutions to an instance of the

stable matching problem In mathematics, economics, and computer science, the stable marriage problem (also stable matching problem or SMP) is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each ele ...

Description

The stable matching polytope is the convex hull of the

indicator vector In mathematics, the indicator vector or characteristic vector or incidence vector of a subset ''T'' of a set ''S'' is the vector x_T := (x_s)_ such that x_s = 1 if s \in T and x_s = 0 if s \notin T. If ''S'' is countable and its elements are numbe ...

s of the stable matchings of the given problem. It has a dimension for each pair of elements that can be matched, and a

vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...

for each stable matchings. For each vertex, the

Cartesian coordinate A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured i ...

s are one for pairs that are matched in the corresponding matching, and zero for pairs that are not matched. The stable matching polytope has a polynomial number of

facets A facet is a flat surface of a geometric shape, e.g., of a cut gemstone. Facet may also refer to: Arts, entertainment, and media * ''Facets'' (album), an album by Jim Croce * ''Facets'', a 1980 album by jazz pianist Monty Alexander and his tri ...

. 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 In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable. For example, in a 0–1 integer program, all constraints are of the form :x_i\in\. The relax ...

of the stable matching problem.

Integrality

It is a theorem of that the polytope described by the facet constraints listed above has only the vertices described above. In particular it is an

integral polytope 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 als ...

. This can be seen as an analogue of the theorem of

Garrett Birkhoff Garrett Birkhoff (January 19, 1911 – November 22, 1996) was an American mathematician. He is best known for his work in lattice theory. The mathematician George Birkhoff (1884–1944) was his father. Life The son of the mathematician G ...

that an analogous polytope, the

Birkhoff polytope The Birkhoff polytope ''B'n'' (also called the assignment polytope, the polytope of doubly stochastic matrices, or the perfect matching polytope of the complete bipartite graph K_) is the convex polytope in R''N'' (where ''N'' = ''n''2) wh ...

describing the set of all fractional matchings between two sets, is integral. An equivalent way of stating the same theorem is that every fractional matching can be expressed as a

convex combination In convex geometry and vector algebra, a convex combination is a linear combination of points (which can be vectors, scalars, or more generally points in an affine space) where all coefficients are non-negative and sum to 1. In other ...

of integral matchings. prove this by constructing a probability distribution on integral matchings whose

expected value In probability theory, the expected value (also called expectation, expectancy, mathematical expectation, mean, average, or first moment) is a generalization of the weighted average. Informally, the expected value is the arithmetic mean of a ...

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 In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomeno ...

over stable matchings constructed in this way provides a representation of the given fractional matching as a convex combination of integral stable matchings.

Lattice of fractional matchings

The family of all stable matchings forms a

distributive lattice 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 ...

, the lattice of stable matchings, in which the

join Join may refer to: * Join (law), to include additional counts or additional defendants on an indictment *In mathematics: ** Join (mathematics), a least upper bound of sets orders in lattice theory ** Join (topology), an operation combining two topo ...

of two matchings gives all doctors their preference among their assigned hospitals in the two matchings, and the meet gives all hospitals their preference. The same is true of the family of all fractional stable matchings, the points of the stable matching polytope. 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 In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...

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 mathematics, economics, and computer science, the Gale–Shapley algorithm (also known as the deferred acceptance algorithm or propose-and-reject algorithm) is an algorithm for finding a solution to the stable matching problem, named for David ...

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. 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.

Applications

By applying

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...

to the stable matching polytope, one can find the minimum or maximum weight stable matching. Alternative methods for the same problem include applying the

closure problem In graph theory and combinatorial optimization, a closure of a directed graph is a set of vertices ''C'', such that no edges leave ''C''. The closure problem is the task of finding the maximum-weight or minimum-weight closure in a vertex-weighted di ...

to a

partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binar ...

derived from the lattice of stable matchings, or applying linear programming to the

order 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 upp ...

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 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 d ...

, a polytope in which coordinatewise maximization and minimization form the meet and join operations of a lattice. However, the meet and join operations for the stable matching polytope are defined in a different way than coordinatewise maximization and minimization. Instead, the

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 In Euclidean geometry, an affine transformation or affinity (from the Latin, ''affinis'', "connected with") is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles. More generall ...

of the other.

References

{{reflist, refs= {{citation , last1 = Aprile , first1 = Manuel , last2 = Cevallos , first2 = Alfonso , last3 = Faenza , first3 = Yuri , doi = 10.1137/17M1116684 , issue = 3 , journal =

SIAM Journal on Discrete Mathematics '' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was esta ...

, mr = 3835234 , pages = 1857–1886 , title = On 2-level polytopes arising in combinatorial settings , volume = 32 , year = 2018, arxiv = 1702.03187 {{citation , last1 = Felsner , first1 = Stefan , last2 = Knauer , first2 = Kolja , doi = 10.1016/j.ejc.2010.07.011 , issue = 1 , journal =

European Journal of Combinatorics European, or Europeans, or Europeneans, may refer to: In general * ''European'', an adjective referring to something of, from, or related to Europe ** Ethnic groups in Europe ** Demographics of Europe ** European cuisine European cuisine co ...

, mr = 2727459 , pages = 45–59 , title = Distributive lattices, polyhedra, and generalized flows , volume = 32 , year = 2011, doi-access = free . {{citation , last = Knuth , first = Donald E. , authorlink = Donald Knuth , isbn = 0-8405-0342-3 , language = French , mr = 0488980 , publisher = Les Presses de l'Université de Montréal , location = Montréal, Quebec , title = Mariages stables et leurs relations avec d'autres problèmes combinatoires , url = https://www-cs-faculty.stanford.edu/~knuth/mariages-stables.pdf , year = 1976. See in particular Problem 6, pp. 87–94. {{citation , last1 = Irving , first1 = Robert W. , last2 = Leather , first2 = Paul , last3 = Gusfield , first3 = Dan , author3-link = Dan Gusfield , doi = 10.1145/28869.28871 , issue = 3 , journal =

Journal of the ACM The ''Journal of the ACM'' is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief An editor-in-c ...

, mr = 904192 , pages = 532–543 , title = An efficient algorithm for the "optimal" stable marriage , volume = 34 , year = 1987 {{citation , last = Ratier , first = Guillaume , doi = 10.1016/0012-365X(94)00237-D , issue = 1–3 , journal =

Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continu ...

, mr = 1368286 , pages = 141–159 , title = On the stable marriage polytope , url = https://core.ac.uk/download/pdf/82824876.pdf , volume = 148 , year = 1996, doi-access = free {{citation , last1 = Roth , first1 = Alvin E. , authorlink = Alvin E. Roth , last2 = Rothblum , first2 = Uriel G. , authorlink2 = Uriel Rothblum , last3 = Vande Vate , first3 = John H. , doi = 10.1287/moor.18.4.803 , issue = 4 , journal =

Mathematics of Operations Research ''Mathematics of Operations Research'' is a quarterly peer-reviewed scientific journal established in February 1976. It focuses on areas of mathematics relevant to the field of operations research such as continuous optimization, discrete optimi ...

, jstor = 3690124 , mr = 1251681 , pages = 803–828 , title = Stable matchings, optimal assignments, and linear programming , volume = 18 , year = 1993 {{citation , last1 = Teo , first1 = Chung-Piaw , last2 = Sethuraman , first2 = Jay , doi = 10.1287/moor.23.4.874 , issue = 4 , journal =

, mr = 1662426 , pages = 874–891 , title = The geometry of fractional stable matchings and its applications , volume = 23 , year = 1998 {{citation , last = Vande Vate , first = John H. , doi = 10.1016/0167-6377(89)90041-2 , issue = 3 , journal = Operations Research Letters , mr = 1007271 , pages = 147–153 , title = Linear programming brings marital bliss , volume = 8 , year = 1989 Stable matching Polyhedral combinatorics