A market design collaboration between an economist and computer scientists

I've written earlier about the work on course allocation by Eric Budish. The new mechanism he proposed is by no means computationally trivial to implement, and together with Abe Othman, a computer science grad student at CMU (who took my Market Design class when he was an undergraduate at Harvard), he has been working on making this a practical too. A report of their work has now appeared:

Finding Approximate Competitive Equilibria: Efficient and Fair
Course Allocation, Abraham Othman, Eric Budish, and Tuomas Sandholm, Proc. of 9th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010), van der Hoek, Kaminka, Lespérance, Luck and Sen (eds.), May, 10–14, 2010, Toronto, Canada, pp. 873-880


Abstract: 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.