Seminar | October 1 | 12:30-1:30 p.m. | 531 Cory Hall
Aviad Rubinstein, UC Berkeley (CS)
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!