2017/03/30 by Nevzat Onur Domaniç, Domaniç, Nevzat Onur, Chi-Kit Lam +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #cs.GT
paper · pdf · doi:10.48550/arxiv.1703.10598
An earlier version of this work appears as a UTCS technical report
arxiv created 2017/03/30 · openalex publication_date 2017/03/30 · arxiv updated 2017/03/31 · openalex created_date 2022/09/01 · openalex updated_date 2026/07/28
We study variants of the stable marriage and college admissions models in which the agents are allowed to express weak preferences over the set of agents on the other side of the market and the option of remaining unmatched. For the problems that we address, previous authors have presented polynomial-time algorithms for computing a "Pareto-stable" matching. In the case of college admissions, these algorithms require the preferences of the colleges over groups of students to satisfy a technical condition related to responsiveness. We design new polynomial-time Pareto-stable algorithms for stable marriage and college admissions that correspond to strategyproof mechanisms. For stable marriage, it is known that no Pareto-stable mechanism is strategyproof for all of the agents; our algorithm provides a mechanism that is strategyproof for the agents on one side of the market. For college admissions, it is known that no Pareto-stable mechanism can be strategyproof for the colleges; our algorithm provides a mechanism that is strategyproof for the students.