Krysta, Piotr, Manlove, David, Rastegari, Baharak and Zhang, Jinshan
(2014)
Size versus truthfulness in the house allocation problem.
In: 15th ACM Conference on Economics and Computation (EC 2014), 2014-6-8 - 2014-6-12, Stanford , CA, USA.
Text
main.pdf - Submitted version Download (455kB) |
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 agent has ordinal preferences (possibly involving ties) over a subset of the objects. We focus on truthful mechanisms without monetary transfers for finding large Pareto optimal matchings. It is straightforward to show that no deterministic truthful mechanism can approximate a maximum cardinality Pareto optimal matching with ratio better than 2. We thus consider randomized mechanisms. We give a natural and explicit extension of the classical Random Serial Dictatorship Mechanism (RSDM) specifically for the House Allocation problem where preference lists can include ties. We thus obtain a universally truthful randomized mechanism for finding a Pareto optimal matching and show that it achieves an approximation ratio of e/e-1. The same bound holds even when agents have priorities (weights) and our goal is to find a maximum weight (as opposed to maximum cardinality) Pareto optimal matching. On the other hand we give a lower bound of 18/13 on the approximation ratio of any universally truthful Pareto optimal mechanism in settings with strict preferences. In the case that the mechanism must additionally be non-bossy, an improved lower bound of e/e-1 holds. This lower bound is tight given that RSDM for strict preference lists is non-bossy. We moreover interpret our problem in terms of the classical secretary problem and prove that our mechanism provides the best randomized strategy of the administrator who interviews the applicants. © 2014 ACM.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Depositing User: | Symplectic Admin |
Date Deposited: | 26 Sep 2016 08:41 |
Last Modified: | 19 Jan 2023 07:36 |
DOI: | 10.1145/2600057.2602868 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3001461 |