[Intelligence Seminar] Talk by Abe Othman, Jan 20 at 3pm @ GHC 4405

[Ariel Procaccia]

Speaker: Abe Othman

Title: Course Match: Large-Scale Equilibrium Approximation for Fair
Combinatorial Allocation

Time and place: Jan 20, 2014, 3pm, GHC 4405

Abstract:

In the combinatorial allocation problem, agents have combinatorial
preferences over bundles of possible allocations. The example I will
discuss in detail is business school course allocation, where students
may have complex preferences over schedules of courses (e.g., two
desirable courses could meet at the same time). Other examples of
combinatorial allocation include scheduling workers to shifts and
scheduling airlines to landing slots.

I will begin by giving the intuition why conventional approaches to
this problem fail. I will then introduce Course Match, a mechanism
that implements a fair allocation while being approximately truthful
and efficient. Unfortunately, Course Match requires minimizing a
highly discontinuous function in ~400-dimensional space; the overall
search problem was recently shown to be PPAD-complete. I will detail
the three-stage search technique we used to solve this difficult
problem. Crucially, Course Match was designed to be parallelized and
scales linearly in the number of processors used.

The Wharton school uses Course Match to allocate courses to their MBA
students; a recent production run solved seven billion Mixed-Integer
Programs to determine schedules. I'll conclude with a discussion of
some of the properties of the mechanism that have emerged in practice.

Joint work over various papers with Eric Budish (Chicago Booth),
Gerard Cachon (Wharton), Judd Kessler (Wharton), Christos
Papadimitriou (Berkeley), Aviad Rubinstein (Berkeley), and Tuomas
Sandholm (CMU).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.srv.cs.cmu.edu/pipermail/intelligence-seminar-announce/attachments/20140109/3c33acd6/attachment.html>