Strategyproof and fair matching mechanism for ratio constraints
| Autor: | Nathanaël Barrot, Kentaro Yahiro, Yuzhe Zhang, Makoto Yokoo |
|---|---|
| Přispěvatelé: | Artificial Intelligence |
| Rok vydání: | 2020 |
| Předmět: |
Class (set theory)
Mathematical optimization Matching (statistics) PROOFNESS STABILITY Computer science BOUNDS 05 social sciences SCHOOL CHOICE 02 engineering and technology Strategyproof Set (abstract data type) Mechanism (engineering) Reduction (complexity) MINIMUM Artificial Intelligence 0502 economics and business 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 050207 economics Baseline (configuration management) PARETO-OPTIMAL MATCHINGS |
| Zdroj: | AAMAS Autonomous Agents and Multi-Agent Systems, 34(1):23. SPRINGER |
| ISSN: | 1573-7454 1387-2532 |
| DOI: | 10.1007/s10458-020-09448-9 |
| Popis: | We introduce a new type of distributional constraints called ratio constraints, which explicitly specify the required balance among schools in two-sided matching. Since ratio constraints do not belong to the known well-behaved class of constraints called M-convex set, developing a fair and strategyproof mechanism that can handle them is challenging. We develop a novel mechanism called quota reduction deferred acceptance (QRDA), which repeatedly applies the standard DA by sequentially reducing artificially introduced maximum quotas. As well as being fair and strategyproof, QRDA always yields a weakly better matching for students compared to a baseline mechanism called artificial cap deferred acceptance (ACDA), which uses predetermined artificial maximum quotas. Finally, we experimentally show that, in terms of student welfare and nonwastefulness, QRDA outperforms ACDA and another fair and strategyproof mechanism called Extended Seat Deferred Acceptance (ESDA), in which ratio constraints are transformed into minimum and maximum quotas. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink