Computational Social Choice Team Seminar(Talk by Max DuprélaTour, McGill University).

【Team】Computational Social Choice Team Seminar
【Date】2026/January/15(Thursday) 10:00-11:00(JST)
【Speaker】Talk by Max DuprélaTour, McGill University

Title: Applications of Combinatorial Discrepancy to the Fair Division of Indivisible Items

Abstract:
Fair division of indivisible items has been an active area of research in recent years. In the classical model with individual agents, strong fairness notions such as envy-freeness up to one item (EF1) can often be guaranteed and achieved efficiently. However, this landscape changes when one considers allocations to groups or the design of truthful mechanisms. In these settings, the best known approximation guarantees are closely linked to techniques from combinatorial discrepancy theory.
In this talk, I will describe how discrepancy theory provides a unifying framework for establishing both upper bounds, via constructive allocation procedures, and lower bounds, via impossibility results. I will present recent advances, including new lower bounds for fair division in the presence of couples, and discuss ongoing efforts to extend discrepancy-based approaches beyond additive valuations, highlighting the associated challenges and open problems.