Minimizing Instability in Strategy-Proof Matching Mechanism Using A Linear Programming Approach

Tohya Sugano

Papers from arXiv.org

Abstract: We study the design of one-to-one matching mechanisms that are strategy-proof for both sides and as stable as possible. Motivated by the impossibility result of Roth (1982), we formulate the mechanism design problem as a linear program that minimizes stability violations subject to exact strategy-proofness constraints. We consider both an average-case objective (summing violations over all preference profiles) and a worst-case objective (minimizing the maximum violation across profiles), and we show that imposing anonymity and symmetry when the number of agents in both sides are the same can be done without loss of optimality. Computationally, for small markets our approach yields randomized mechanisms with substantially lower stability violations than randomized sequential dictatorship (RSD); in the $3\times 3$ case the optimum reduces average instability to roughly one third of RSD. For deterministic mechanisms with three students and three schools, we find that any two-sided strategy-proof mechanism has at least two blocking pairs in the worst case and we provide a simple algorithm that attains this bound. Finally, we propose an extension to larger markets and present simulation evidence that, relative to sequential dictatorship (SD), it reduces the number of blocking pairs by about $0.25$ on average.

Date: 2025-02, Revised 2026-02
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2502.12431 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2502.12431

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().