6 papers · 1 filter
Best of Both Worlds Guarantees for Equitable Allocations
Umang Bhaskar, Vishwa Prakash HV, Aditi Sethia +1
Equitability is a well-studied fairness notion in fair division, where an allocation is equitable if all agents receive equal utility from their allocation. For indivisible items,…
Connected Equitable Cake Division via Sperner's Lemma
Umang Bhaskar, A. R. Sricharan, Rohit Vaish
We study the problem of fair cake-cutting where each agent receives a connected piece of the cake. A division of the cake is deemed fair if it is equitable, which means that all ag…
Equilibrium Computation in the Hotelling-Downs Model of Spatial Competition
Umang Bhaskar, Soumyajit Pyne
The Hotelling-Downs model is a natural and appealing model for understanding strategic positioning by candidates in elections. In this model, voters are distributed on a line, repr…
EFX Allocations on Some Multi-graph Classes
Umang Bhaskar, Yeshwant Pandit
The existence of EFX allocations is one of the most significant open questions in fair division. Recent work by Christodolou, Fiat, Koutsoupias, and Sgouritsa ("Fair allocation in…
EF1 Allocations for Identical Trilean and Separable Single-Peaked Valuations
Umang Bhaskar, Gunjan Kumar, Yeshwant Pandit +1
In the fair division of items among interested agents, envy-freeness is possibly the most favoured and widely studied formalisation of fairness. For indivisible items, envy-free al…
Nearly Tight Bounds on Approximate Equilibria in Spatial Competition on the Line
Umang Bhaskar, Soumyajit Pyne
In Hotelling's model of spatial competition, a unit mass of voters is distributed in the interval (with their location corresponding to their political persuasion), and eac…