Size versus truthfulness in the house allocation problem

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:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3001461