(New) 26 May 2026, Computational Social Choice Seminar, Rupert Freeman

Abstract

The classical cake cutting setting is concerned with dividing a resource, modeled by the [0,1] interval, and allocating subintervals to different agents. A recent result shows that there does not exist a deterministic cake cutting mechanism that is both incentive compatible and even only one of proportional or envy-free (the latter is restricted to non-wasteful mechanisms). In principle, randomization can circumvent this impossibility, but known solutions either require restrictive assumptions on the valuation functions or only provide non-constructive existence arguments. In this work, leveraging proper scoring rules, we design a class of randomized mechanisms that are ex ante incentive compatible, ex ante proportional, and ex ante envy-free. Moreover, within this class, we identify the Seeded Probabilistic Allocation mechanism, which is ex ante strictly incentive compatible, ex post strongly proportional and ex post strongly envy-free. This result is tight in the sense that additionally achieving ex post incentive compatibility is impossible as it would violate the aforementioned impossibility result. This is joint work with Jens Witkowski.
For more information on the Computational Social Choice Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/.