CATS-May-2-2014
Title[edit]
One-Sided Matching with Limited Complementarities
Speaker[edit]
Professor Vohra is a leading global expert in mechanism design, an innovative area of game theory that brings together economics, engineering and computer science. His economics research in mechanism design focuses on the best ways to allocate scarce resources when the information required to make the allocation is dispersed and privately held, an increasingly common condition in present-day environments. His work has been critical to the development of game, auction and pricing theory — for example, the keyword auctions central to online search engines — and spans such areas as operations research, market systems and optimal pricing mechanisms.
He formerly taught at Northwestern University, where he was the John L. and Helen Kellogg Professor of Managerial Economics and Decision Sciences in the Kellogg School of Management, with additional appointments in the Department of Economics and the Department of Electrical Engineering and Computer Science. He taught from 1985 to 1998 in the Fisher College of Business at Ohio State University. He earned a Ph.D. in mathematics in 1985 from the University of Maryland, an M.Sc. in operational research in 1981 from the London School of Economics and a B.Sc. (Hon.) in mathematics in 1980 from University College London.
He joined Penn as part as of the Penn Integrates Knowledge program that President Amy Guttmann established in 2005 as a University-wide initiative to recruit exceptional faculty members whose research and teaching exemplify the integration of knowledge across disciplines. His appointment is shared with the Department of Electrical and Systems Engineering in the School of Engineering and Applied Science.
Abstract[edit]
The problem of allocating bundles of indivisible objects without transfers arises in the assignment of courses to students, the assignment of computing resources like CPU time, memory and disk space to computing tasks and the assignment of truck loads of food to food banks. In these settings the complementarities in preferences are small compared with the size of the market. We exploit this to design mechanisms satisfying efficiency, envyfreeness and asymptotic strategy-proofness.
Informally, we assume that agents do not want bundles that are too large. There will be a parameter k such that the marginal utility of any item relative to a bundle of size k or larger is zero. We call such preferences k-demand preferences. Given this parameter we show how to represent probability shares over bundles as lotteries over approximately deterministic feasible integer allocations. The degree of infeasibility in these integer allocations will be controlled by the parameter k. In particular, ex-post, no good is over allocated by at most k-1 units.
Based on joint work with Thanh Nguyen and Ahmad Peivandi.
