- Constantinos Daskalakis, Massachusetts Institute of Technology
Title: Reductions from Mechanism to Algorithm Design
Abstract: Algorithmic mechanism design centers around the following question: How much harder is optimizing an objective over inputs that are furnished by rational agents compared to when the inputs are known? We present computationally efficient reductions from mechanism design (i.e. optimizing over rational inputs) to algorithm design (i.e. optimizing over known inputs) in general Bayesian settings. We also explore whether structural properties about optimal mechanisms can be inferred from these reductions. As an application, we present extensions of Myerson's celebrated single-item auction to multi-item settings.
- Bettina Klaus, Department of Economics, Faculty of Business and Economics (HEC), University of Lausanne
Title: Strategy-Proofness makes the Difference: Deferred-Acceptance with Responsive Priorities
(based on joint work with Lars Ehlers)
Abstract: In college admissions and student placements at public schools, the admission decision can be thought of as assigning indivisible objects with capacity constraints to a set of students such that each student receives at most one object and monetary compensations are not allowed. In these important market design problems, the agent-proposing deferred-acceptance (DA) mechanism with responsive strict priorities performs well and economists have successfully implemented DA-mechanisms or slight variants thereof. We show that almost all real-life mechanisms used in such environments - including the large classes of priority mechanisms and linear programming mechanisms - satisfy a set of simple and intuitive properties. Once we add strategy-proofness to these properties, DA-mechanisms are the only ones surviving. In market design problems that are based on weak priorities (like school choice), generally multiple tie-breaking (MTB) procedures are used and then a mechanism is implemented with the obtained strict priorities. By adding stability with respect to the weak priorities, we establish the first normative foundation for MTB-DA-mechanisms that are used in NYC.
- Rakesh Vohra, Kellogg School of Management
Title: The Allocation of Indivisible Objects via Rounding
(based on joint work with Thanh Nguyen, Krannert School of Business, Purdue University)
Abstract: The problem of allocating indivisible objects arises in the allocation of courses, spectrum licenses, airport landing slots and assigning students to schools. This paper proposes a technique for making such allocations that is based on rounding a fractional allocation. Under the assumption that no agent wants to consume more than $k$ items, the rounding technique can be interpreted as giving agents lotteries over approximately feasible integral allocations that preserve the ex-ante efficiency and fairness and asymptotically strategy-proof properties of the initial fractional allocation. The integral allocations are only approximately feasible in the sense that upto $k-1$ more units than the available supply of any good is allocated.