Date/Time
Date(s) - 04/07/2023
2:00 pm - 3:00 pm
Location
School of Computing Science, Sir Alwyn Williams Building, Lilybank Gardens, University of Glasgow
SICSA DVF Dr Alexandros Hollender, EPFL is giving a talk on 4th July at the School of Computing Science, Lilybank Gardens, University of Glasgow
Title: Envy-Free Cake-Cutting for Four Agents
Abstract: In the envy-free cake-cutting problem we are given a resource, usually called a cake and represented as the [0,1] interval, and a set of n agents with heterogeneous preferences over pieces of the cake. The goal is to divide the cake among the n agents such that no agent is envious of any other agent. Even under a very general preferences model, this fundamental fair division problem is known to always admit an exact solution where each agent obtains a connected piece of the cake; we study the complexity of finding an approximate solution, i.e., a connected ε-envy-free allocation.
For monotone valuations of cake pieces, Deng, Qi, and Saberi (2012) gave an efficient algorithm for three agents, and it was conjectured by Brânzei and Nisan (2022) that the problem for four agents is hard. We present an efficient algorithm for the case of four agents. We also prove that as soon as the valuations are allowed to be non-monotone, the problem becomes hard, even in the communication model. This constitutes, to the best of our knowledge, the first intractability result for any version of the cake-cutting problem in the communication complexity model.
Based on joint work with Aviad Rubinstein.
Short Bio: Alexandros Hollender is currently a postdoctoral researcher at the École Polytechnique Fédérale de Lausanne (EPFL). Last year, he was a postdoctoral research fellow at All Souls College, University of Oxford. He obtained his PhD from the University of Oxford under the supervision of Paul Goldberg.
His research interests lie mainly in algorithms and computational complexity, including applications in various fields such as game theory, fair division and optimization. His work focuses on total search problems and the various complexity classes that arise in their study. In 2021 he received the best paper award in the ACM Symposium on Theory of Computing (STOC) for his work on the computational complexity of the gradient descent method. In 2022, he received the European Association for Theoretical Computer Science (EATCS) distinguished dissertation award for his doctoral thesis “Structural Results for Total Search Complexity Classes with Applications to Game Theory and Optimisation”
The host of Dr Hollender for the University of Glasgow is Professor David Manlove
