16 February 2023, Computational Social Choice Seminar, Mayesha Tasnim

Abstract

In the one-sided matching problem of school allocation, where students are assigned to schools based on ordered preference lists, applying combinatorial optimization can yield matchings that have better collective welfare than matchings obtained by Deferred Acceptance. However, these matchings are subject to strategic preference submissions. The tradeoff between welfare loss in strategy-proof mechanisms versus non-strategy-proof mechanisms in real-world settings is an understudied problem. In this work the optimal strategy for a single student is derived for combinatorial optimization based allocation. Based on this derivation, a suite of strategies is introduced, ranging from truthful to optimal, varying several strategy parameters. An empirical study is then conducted on the impact of applying these strategies in order to enhance allocation to the top-ranked schools, using real-world school-data from Amsterdam. The welfare loss due to strategic preference submission is observed and contrasted against welfare loss due to indifferent preferences over students in Deferred Acceptance.

For more information on the Computational Social Choice Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/.