
arXiv: 1104.5474
The school choice mechanism design problem focuses on assignment mechanisms matching students to public schools in a given school district. The well-known Gale Shapley Student Optimal Stable Matching Mechanism (SOSM) is the most efficient stable mechanism proposed so far as a solution to this problem. However its inefficiency is well-documented, and recently the Efficiency Adjusted Deferred Acceptance Mechanism (EADAM) was proposed as a remedy for this weakness. In this note we describe two related adjustments to SOSM with the intention to address the same inefficiency issue. In one we create possibly artificial coalitions among students where some students modify their preference profiles in order to improve the outcome for some other students. Our second approach involves trading cliques among students where those involved improve their assignments by waiving some of their priorities. The coalition method yields the EADAM outcome among other Pareto dominations of the SOSM outcome, while the clique method yields all possible Pareto optimal Pareto dominations of SOSM. The clique method furthermore incorporates a natural solution to the problem of breaking possible ties within preference and priority profiles. We discuss the practical implications and limitations of our approach in the final section of the article.
Social and Information Networks (cs.SI), FOS: Computer and information sciences, Physics - Physics and Society, matching, FOS: Physical sciences, Computer Science - Social and Information Networks, 90C27, 91A40, Physics and Society (physics.soc-ph), mechanism design, 91B68, 91B14, assignment, 90B80, Optimization and Control (math.OC), FOS: Mathematics, Mathematics - Combinatorics, school choice, Combinatorics (math.CO), Mathematics - Optimization and Control
Social and Information Networks (cs.SI), FOS: Computer and information sciences, Physics - Physics and Society, matching, FOS: Physical sciences, Computer Science - Social and Information Networks, 90C27, 91A40, Physics and Society (physics.soc-ph), mechanism design, 91B68, 91B14, assignment, 90B80, Optimization and Control (math.OC), FOS: Mathematics, Mathematics - Combinatorics, school choice, Combinatorics (math.CO), Mathematics - Optimization and Control
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
