【Team】Computational Social Choice Team Seminar()
【Date】2026/January/9(Friday) 14:00-15:00(JST)
【Speaker】Talk by VishwaPrakash HV, Chennai Mathematical Institute
Title: Existence Guarantees and Algorithms in Discrete Fair Division
Abstract: The problem of discrete fair division arises whenever indivisible goods must be allocated among agents with competing preferences. A university seat, a house, or a domain name cannot be split. Whether the agents are people, algorithms, or robots, the same fundamental question arises: how do we divide what cannot be divided, fairly?
Three central notions of fairness dominate the literature. Envy-freeness requires that no agent prefer another agent’s allocation to their own. Proportionality demands that each agent receive a fair share of the overall bundle. And Equitability requires that all agents derive equal value from their allocations. While conceptually appealing, these ideals are often unattainable in the presence of indivisible goods. With a single good and two interested agents, envy, disproportionality, and inequity are inevitable. This impossibility has motivated the study of relaxed fairness notions, typically formalized as “fairness up to one good” or “fairness up to any good.” For example, EFX (Envy-Freeness up to Any Good) requires that no agent envy another after the removal of any single item from the latter’s bundle. Understanding whether such relaxed notions always admit feasible allocations, and how to compute them, remains one of the central challenges in discrete fair division.
In this talk, I will present my contributions to existence guarantees and algorithms for relaxed fairness notions, based on joint works carried out during my PhD. In particular, I will highlight results on EFX and approximate EFX for settings with few agent types, proportional allocation of chores under heterogeneous entitlements, and equitable allocations for broad classes of valuation functions.
