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

Tohya Sugano

Papers from arXiv.org

Abstract: In this paper we address the design of matching mechanisms that are strategy-proof and simultaneously as stable as possible. Building on the impossibility result by \cite{Roth1982-cl} for one-to-one matching problems, we formulate an optimization problem that maximizes stability under the constraint of strategy-proofness. In our model the objective is to minimize the degree of instability measured as the sum (or worst-case maximum) of stability violations over all preference profiles. We further introduce the socially important properties of anonymity and symmetry into the formulation. Our computational results show that, for small markets, our optimization approach leads to mechanisms with substantially lower stability violations than RSD. In particular, the optimal mechanism under our formulation exhibits roughly one-third the stability violation of RSD. For deterministic mechanisms in the three-agent case, we also find that any strategy-proof mechanism hvae at least two blocking pairs at the worst case, and we propose an algorithm that attains this lower bound. Finally, we discuss extensions to larger markets and present simulation evidence that our mechanism yields a reduction of approximately $0.25$ blocking pairs on average compared to SD mechanism.

Date: 2025-02
New Economics Papers: this item is included in nep-des
References: Add references at 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 ().