2017/03/30 by Nevzat Onur Domaniç, Domaniç, Nevzat Onur, Chi-Kit Lam +3
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
paper · pdf · doi:10.48550/arxiv.1703.10598
openalex publication_date 2017/03/30 · openalex created_date 2022/09/01 · openalex updated_date 2026/07/28
We study variants of the stable marriage and college admissions models in\nwhich the agents are allowed to express weak preferences over the set of agents\non the other side of the market and the option of remaining unmatched. For the\nproblems that we address, previous authors have presented polynomial-time\nalgorithms for computing a "Pareto-stable" matching. In the case of college\nadmissions, these algorithms require the preferences of the colleges over\ngroups of students to satisfy a technical condition related to responsiveness.\nWe design new polynomial-time Pareto-stable algorithms for stable marriage and\ncollege admissions that correspond to strategyproof mechanisms. For stable\nmarriage, it is known that no Pareto-stable mechanism is strategyproof for all\nof the agents; our algorithm provides a mechanism that is strategyproof for the\nagents on one side of the market. For college admissions, it is known that no\nPareto-stable mechanism can be strategyproof for the colleges; our algorithm\nprovides a mechanism that is strategyproof for the students.\n