Back to Search
Start Over
Two-Sided Random Matching Markets: Ex-Ante Equivalence of the Deferred Acceptance Procedures.
- Source :
- EC: Economics & Computation; 2020, p13-17, 13p
- Publication Year :
- 2020
-
Abstract
- Stable matching in a community consisting of N men and N women is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley. When the input preference profile is generated from a distribution, we study the output distribution of two stable matching procedures: women-proposing-deferred-acceptance and men-proposing-deferred-acceptance. We show that the two procedures are ex-ante equivalent: that is, under certain conditions on the input distribution, their output distributions are identical. In terms of technical contributions, we generalize (to the non-uniform case) an integral formula, due to Knuth and Pittel, which gives the probability that a fixed matching is stable. Using an inclusion-exclusion principle on the set of rotations, we give a new formula which gives the probability that a fixed matching is the women/men-optimal stable matching. We show that those two probabilities are equal with an integration by substitution. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- Database :
- Complementary Index
- Journal :
- EC: Economics & Computation
- Publication Type :
- Conference
- Accession number :
- 155539997
- Full Text :
- https://doi.org/10.1145/3391403.3399448