BEGIN:VCALENDAR
VERSION:2.0
X-WR-CALNAME;VALUE=TEXT:Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)
PRODID:-//Harvard events data//EN
BEGIN:VEVENT
UID:event_1687416_0
SUMMARY:Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)
DESCRIPTION:<p>	Aviad Rubinstein (Stanford)</p><p>	Friday, May 5, in-person SEC 1.413</p><p>	<em>Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)</em></p><p>	Abstract:</p><p>	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.</p><p>	 </p><p>	In theory, it is known that on asymptotically large markets:</p><ul>	<li>		<span style="tab-stops:list.5in">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).</span>	</li>	<li>		<span style="tab-stops:list.5in">From a computational perspective, computing the equilibrium solution is unfortunately a computationally intractable problem (in the worst-case, assuming PPAD != FP).</span>	</li></ul><p>	In this talk I will share insights from our empirical work studying what happens to incentives and computational complexity beyond asymptotic analysis.</p><p>	Based on joint work with Eric Budish, Ruiquan Gao, Abraham Othman, and Qianfan Zhang</p>
LOCATION:SEC 1.413
STATUS:CONFIRMED
DTSTART:20230505T170000Z
DTEND:20230505T170000Z
END:VEVENT
END:VCALENDAR