Motivated by the social distancing rules, this talk considers the task of fairly sharing a divisible good among several agents in a setting where every two agents’ shares must be separated. The case where the good is the [0, 1] segment (usually referred to as “cake”) is first looked at. In this model, the separation constraint is captured by specifying a parameter s such that for every pair of agents i, j their shares are separated by a segment of length at least s. Intuitively, the cake is cut by a blunt knife of width s. The focus is on the recently introduced fairness concept of maximin fair share, and it turns out that each agent can be guaranteed its maximin fair share. However, computing the agents’ fair shares is computationally hard. Elkind then extends the analysis to richer models, such as a 2-dimensional cake (where additional restrictions on the shapes of agents’ pieces apply) and graphical cake (where agents need to share edges of a graph), and obtains positive results for an ordinal relaxation of the maximin fair share solution concept.

This talk is based on joint work with Erel Segal-Halevi and Warut Suksompong.

Edith Elkind is a Professor of Computer Science at the University of Oxford. Her primary research interests are algorithmic game theory and preference aggregation, and she has published over 100 papers in these research areas. She obtained her PhD from Princeton in 2005, and held positions in the UK, Israel and Singapore before joining Oxford. Prof. Elkind is a fellow of EurAI and ELLIS, and will serve as a program chair of the International Joint Conference on Artificial Intelligence (IJCAI) in 2021.

Download the poster here