Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)
Date and Time
Location
Aviad Rubinstein (Stanford)
Friday, May 5, in-person SEC 1.413
Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)
Abstract:
Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is an equilibrium-based solution concept for fair division of discrete items to agents with combinatorial demands. We developed a new heuristic A-CEEI algorithm that significantly outperforms the (previous) commercial state-of-the-art and is now in production on real course allocation problems.
In theory, it is known that on asymptotically large markets:
- For incentives, the A-CEEI mechanism is Envy-Free-but-for-Tie-Breaking (EF-TB), which implies that it is Strategyproof-in-the-Large (SP-L).
- From a computational perspective, computing the equilibrium solution is unfortunately a computationally intractable problem (in the worst-case, assuming PPAD != FP).
In this talk I will share insights from our empirical work studying what happens to incentives and computational complexity beyond asymptotic analysis.
Based on joint work with Eric Budish, Ruiquan Gao, Abraham Othman, and Qianfan Zhang