9 papers
Non-Linear Pricing Restores Tractability for a Data Seller
Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma +1
We consider a data seller who designs pricing mechanisms over multiple datasets to maximize revenue from budget-constrained buyers. The seller offers multiple datasets and assigns…
Tight Subsidy Bounds for Weighted Proportional Allocation of Mixed Manna
Jugal Garg, Eklavya Sharma, Xiaowei Wu
We study the problem of fairly allocating m indivisible items among n agents with possibly unequal entitlements in the mixed manna setting, where each item may be perceived as a go…
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…
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,…
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…
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…
EF1 for Mixed Manna with Unequal Entitlements
Jugal Garg, Eklavya Sharma
We study fair division of indivisible mixed manna when agents have unequal entitlements, with weighted envy-freeness up to one item (WEF1) as our primary notion of fairness. We ide…