7 papers
Exploring Relations among Fairness Notions in Discrete Fair Division
Jugal Garg, Eklavya Sharma
Fair allocation of indivisible items among agents is a fundamental and extensively studied problem. However, fairness does not have a single universally accepted definition, leadin…
Proportionally Fair Makespan Approximation
Michal Feldman, Jugal Garg, Vishnu V. Narayan +1
We study fair mechanisms for the classic job scheduling problem on unrelated machines with the objective of minimizing the makespan. This problem is equivalent to minimizing the eg…
Revenue-Optimal Pricing for Budget-Constrained Buyers in Data Markets
Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma +1
We study revenue-optimal pricing in data markets with rational, budget-constrained buyers. Such a market offers multiple datasets for sale, and buyers aim to improve the accuracy o…
Tight Efficiency Bounds for the Probabilistic Serial and Related Mechanisms
Jugal Garg, Yixin Tao, László A. Végh
The Probabilistic Serial (PS) mechanism -- also known as the simultaneous eating algorithm -- is a canonical solution for the random assignment problem under ordinal preferences. I…
Designing Truthful Mechanisms for Asymptotic Fair Division
Jugal Garg, Vishnu V. Narayan, Yuang Eric Shen
We study the problem of fairly allocating a set of goods among agents in the asymptotic setting, where each item's value for each agent is drawn from an underlying joint di…
Proportional and Pareto-Optimal Allocation of Chores with Subsidy
Jugal Garg, Eklavya Sharma, Xiaowei Wu
We consider the problem of allocating indivisible chores among agents with possibly different weights, aiming for a solution that is both fair and efficient. Specifically,…