Finding Approximate Competitive Equilibria: Efficient and Fair Course Allocation

Coauthors: Abraham Othman and Tuomas Sandholm
Proc. of 9th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010), (2010): 1, 873-880. [PDF]

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 mixed-integer 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.