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