Size Versus Truthfulness in the House Allocation Problem
- 16:00 7th March 2014 ( week 7, Hilary Term 2014 )Room 278, Oxford e-Research Centre, 7 Keble Road
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 the first explicit extensions of the classical Random Serial Dictatorship Mechanism (RSDM) to the case where preference lists can include ties. We thus obtain a universally truthful randomized mechanism for finding a Pareto optimal matchingand 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.
Speaker bio
Baharak Rastegari is a Research Associate at the School of Computing Science, University of Glasgow. She received a Ph.D. in Computer Science from the University of British Columbia, Canada, in 2013, and an M.Sc. in Computer Science from the same institution in 2004. Prior to that, she received a B.Sc. in Computer Engineering from Sharif University of Technology, Iran, in 2002. She enjoys solving mathematical problems, and in particular, designing efficient algorithms for various problems, or proving that none exists. Her main areas of interest are Game Theory and Bioinformatics. For the past few years she has been focused on solving problems concerning two-sided matching markets; before that, she worked on Combinatorial Auctions and the prediction of RNA secondary structures.Share this:
