Given a set of indivisible goods that are to be allocated among agents with differing preferences, EFX fairness requires that no agent prefers any strict subset of another agent's bundle. Do such allocations always exist? This question has emerged as one of the most challenging open problems in discrete fair division.
Due to the difficulty of this problem, several restricted and relaxed variants have been studied. EFX allocations are known to exist in structured settings, such as for three agents, and under relaxations including multiplicative approximations, most notably that a 0.618-EFX allocation always exists. Another prominent relaxation is EFX with charity, which seeks a large partial EFX allocation while leaving a small number of goods unallocated.
In this talk, I will present new results on the existence of EFX and approximate EFX when agents can be partitioned into a small number of types, with agents of the same type having identical valuations. We show that EFX allocations exist for three types of agents, and that a 2/3-EFX allocation exists for four types. Additionally, we strengthen guarantees for EFX with charity by establishing bounds that depend explicitly on the number of distinct agent types.
The results presented in this talk are drawn from three papers (
Paper1,
Paper2,
Paper3), coauthored with Pratik Ghosal, Ruta Mehta, Prajakta Nimbhorkar, and Nithin Varma.
Short Bio: Vishwa Prakash is a PhD student at the Chennai Mathematical Institute, working under the supervision of Prof. Prajakta Nimbhorkar. He works on Discrete Fair Division, and more broadly on Algorithmic Game Theory.
