Title: ECCS: Finding Approximate Competitive Equilibria:Efficient and Fair Course Alloc
Speaker: Yicheng Liu Tsinghua University
Time: 2014-10-10 14:00-2014-10-10 16:00
Venue: FIT 1-203-5


In the course allocation problem, a university administrator seeks to efficiently and fairly allocate schedules of over-demanded courses to students with heterogeneous preferences. We investigate how to computationally implement a recently-proposed theoretical solution to this problem (Budish, 2009) which uses approximate competitive equilibria to balance notions of efficiency, fairness, and incentives. Despite the apparent similarity to the well-known combinatorial auction problem we show that no polynomial-size mixedinteger program (MIP) can solve our problem. Instead, we develop a two-level search process: at the master level, the center uses tabu search over the union of two distinct neighborhoods to suggest prices; at the agent level, we use MIPs to solve for student demands in parallel at the current prices. Our method scales near-optimally in the number of processors used and is able to solve realistic-size problems fast enough to be usable in practice.

Short Bio: