34 citations · 142 across the 43 of their papers we have counts for
6 papers · 1 filter
New Algorithms for the Fair and Efficient Allocation of Indivisible Chores
Jugal Garg, Aniket Murhekar, John Qin
We study the problem of fairly and efficiently allocating indivisible chores among agents with additive disutility functions. We consider the widely-used envy-based fairness proper…
Approximating Nash Social Welfare by Matching and Local Search
Jugal Garg, Edin Husić, Wenzheng Li +2
For any , we give a simple, deterministic -approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also co…
New Fairness Concepts for Allocating Indivisible Items
Ioannis Caragiannis, Jugal Garg, Nidhi Rathi +2
For the fundamental problem of fairly dividing a set of indivisible items among agents, envy-freeness up to any item (EFX) and maximin fairness (MMS) are arguably the most compelli…
Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness
Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin +1
We study the computational complexity of finding a competitive equilibrium (CE) with chores when agents have linear preferences. CE is one of the most preferred mechanisms for allo…
EFX Allocations: Simplifications and Improvements
Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury +3
The existence of EFX allocations is a fundamental open problem in discrete fair division. Given a set of agents and indivisible goods, the goal is to determine the existence of an…
Computing Pareto-Optimal and Almost Envy-Free Allocations of Indivisible Goods
Jugal Garg, Aniket Murhekar
We study the problem of fair and efficient allocation of a set of indivisible goods to agents with additive valuations using the popular fairness notions of envy-freeness up to one…