Krysta, Piotr, Manlove, David, Rastegari, Baharak and Zhang, Jinshan
(2019)
Size versus truthfulness in the House Allocation problem.
Algorithmica: an international journal in computer science, 81 (9).
pp. 3422-3463.
|
Text
Size_versus_truthfulness_journal_version (1).pdf - Author Accepted Manuscript Download (442kB) | Preview |
Abstract
We study the House Allocation problem (also known as the Assignment problem),i.e., the problem of allocating a set of objects among a set of agents, where each agenthas ordinal preferences (possibly involving ties) over a subset of the objects. We focuson truthful mechanisms without monetary transfers for finding large Pareto optimalmatchings. It is straightforward to show that no deterministic truthful mechanism canapproximate a maximum cardinality Pareto optimal matching with ratio better than 2.We thus consider randomised mechanisms. We give a natural and explicit extensionof the classical Random Serial Dictatorship Mechanism (RSDM) specifically for theHouse Allocation problem where preference lists can include ties. We thus obtaina universally truthful randomised mechanism for finding a Pareto optimal matchingand show that it achieves an approximation ratio ofee−1. The same bound holds evenwhen agents have priorities (weights) and our goal is to find a maximum weight (asopposed to maximum cardinality) Pareto optimal matching. On the other hand wegive a lower bound of1813on the approximation ratio of any universally truthful Paretooptimal mechanism in settings with strict preferences. By using a characterisationresult of Bade, we show that any randomised mechanism that is a symmetrisation ofa truthful, non-bossy and Pareto optimal mechanism has an improved lower bound ofee−1. Since our new mechanism is a symmetrisation of RSDM for strict preferences,it follows that this lower bound is tight. We moreover interpret our problem in termsof the classical secretary problem and prove that our mechanism provides the bestrandomised strategy of the administrator who interviews the applicants.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | House allocation problem, Assignment problem, Pareto optimal matching, Randomised mechanisms, Truthfulness |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 08 May 2019 08:19 |
| Last Modified: | 19 Jan 2023 00:49 |
| DOI: | 10.1007/s00453-019-00584-7 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3040127 |
Dimensions
Dimensions
