Skip to main content.
Advanced search >
<< Back to previous page Print

<< Tuesday, October 01, 2013 >>


Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare


Seminar EconCS: "Intractability of Course Match"

Seminar | October 1 | 12:30-1:30 p.m. | 531 Cory Hall


Aviad Rubinstein, UC Berkeley (CS)

Department of Economics, Electrical Engineering and Computer Sciences (EECS)


Course Match is a course allocation mechanism based on the concept of Approximate Competitive Equilibrium from Equal Incomes (A-CEEI), and it is currently used by Wharton's MBA Program. Course Match uses a heuristic to search for an A-CEEI, and the plausibility of finding an algorithm remained unsettled.
We prove that finding an A-CEEI is computationally intractable. In particular, we prove that: (1) it is PPAD-Complete to find an A-CEEI; and (2) it is NP-Complete to decide whether there exists an exact CEEI.

Joint work with Abe Othman.


Faculty, Students - Graduate

lunch will be served!


alexpsomi@cs.berkeley.edu, 510-517-8185