We consider the setting of fair division of indivisible items and focus on the fairness notion known as "envy-freeness up to any item (EFX)". The input to the problem is a set of n agents and m items, where each agent has a valuation function defined for each subset of items. The goal is to partition the items among the agents so that the allocation satisfies the EFX requirement. Such an allocation is called an EFX allocation. When two or more agents have the same valuation function, the agents are said to have the same "type".
Existence of EFX allocations is one of the central problems in fair division. The problem has turned out to be difficult, and the existence of EFX allocations is known for only restricted cases. In particular, EFX allocations are known to exist for three agents, for the case when there are at most two types of agents, and (partial EFX allocations) for an arbitrary number of agents, say n, with at most n-2 items left unallocated.
We make progress on these three fronts and show the following:
1. EFX allocations exist when agents have at most three types.
2. EFX allocations with at most k-2 items left unallocated, when agents have at most k types.
In this talk, I will highlight some techniques and challenges that arise in extending the results on EFX for agents to EFX for types of agents.
Short Bio:
Prajakta Nimbhorkar is an Associate Professor at Chennai Mathematical Institute. Her research interests are broadly in design and analysis of algorithms. She has completed her Ph.D at The Institute of Mathematical Sciences, Chennai under the supervision of Prof. Meena Mahajan.
