[Intelligence Seminar] Reminder: Talk by Abe Othman, today at 3pm @ GHC 4405

[Ariel Procaccia]

Reminder: Abe will give a talk today at 3pm...

Ariel


On Thu, Jan 9, 2014 at 12:13 AM, Ariel Procaccia <arielpro at cs.cmu.edu>wrote:

> 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/20140120/e0783f58/attachment.html>