Penn Arts & Sciences Logo

AMCS/PICS Colloquium

Friday, November 8, 2013 - 2:00pm

Rakesh Vohra

Penn

Location

University of Pennsylvania

Towne 337

The problem of allocating indivisible objects arises in the allocation of courses, spectrum licenses, landing slots at airports and assigning students to schools. Here I describe 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 up to k-1 more units than the available supply of any good is allocated. (Based on joint work with Thanh Nguyen) --