Two-Sided Random Matching Markets: Ex-Ante Equivalence of the Deferred Acceptance Procedures
| Autor: | Simon Mauras |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Statistics and Probability Economics and Econometrics Matching (statistics) Discrete Mathematics (cs.DM) Distributive lattice 02 engineering and technology FOS: Economics and business Combinatorics Empirical research Computer Science - Computer Science and Game Theory Computer Science - Data Structures and Algorithms 0502 economics and business Subject (grammar) 0202 electrical engineering electronic engineering information engineering Economics - Theoretical Economics Computer Science (miscellaneous) Data Structures and Algorithms (cs.DS) 050207 economics Equivalence (measure theory) 050205 econometrics Mathematics Marketing Ex-ante 05 social sciences Integration by substitution Random matching Computational Mathematics Theoretical Economics (econ.TH) 020201 artificial intelligence & image processing Integral formula Mathematical economics Computer Science and Game Theory (cs.GT) Computer Science - Discrete Mathematics |
| Zdroj: | EC |
| ISSN: | 2167-8383 2167-8375 |
| DOI: | 10.1145/3485010 |
| Popis: | 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. Accepted for publication in the 21st ACM Conference on Economics and Computation (EC'20) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|