34 citations · 142 across the 43 of their papers we have counts for
45 papers · 1 filter
Equilibrium Pricing in Oligopolistic Data Markets
Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma +1
We study equilibrium pricing in oligopolistic data markets with budget-constrained buyers (e.g., machine learning companies purchasing data to improve model accuracy) and strategic…
Efficiently Restructuring Sovereign Debt via Arctic Auctions with Convex Costs
Jugal Garg, Edwin Lock, Vijay V. Vazirani
We study the problem of computing competitive equilibria in the Arctic product-mix auction, originally developed for the Icelandic government for exchanging blocked financial accou…
A Strongly Polynomial Algorithm for Arctic Auctions
Jugal Garg, Shayan Taherijam, Vijay V Vazirani
Our main contribution is a strongly polynomial algorithm for computing an equilibrium for the Arctic Auction, which is the quasi-linear extension of the linear Fisher market model.…
Existence of 2-EFX Allocations of Chores
Jugal Garg, Aniket Murhekar
We study the fair division of indivisible chores among agents with additive disutility functions. We investigate the existence of allocations satisfying the popular fairness notion…
Improved MMS Approximations for Few Agent Types
Jugal Garg, Parnian Shahkar
We study fair division of indivisible goods under the maximin share (MMS) fairness criterion in settings where agents are grouped into a small number of types, with agents within e…
Matching Markets with Chores
Jugal Garg, Thorben Tröbst, Vijay V. Vazirani
The fair division of chores, as well as mixed manna (goods and chores), has received substantial recent attention in the fair division literature; however, ours is the first paper…
On the Theoretical Foundations of Data Exchange Economies
Hannaneh Akrami, Bhaskar Ray Chaudhury, Jugal Garg +1
The immense success of ML systems relies heavily on large-scale, high-quality data. The high demand for data has led to many paradigms that involve selling, exchanging, and sharing…
Improved Maximin Share Approximations for Chores by Bin Packing
Jugal Garg, Xin Huang, Erel Segal-Halevi
We study fair division of indivisible chores among agents with additive cost functions using the popular fairness notion of maximin share (MMS). Since MMS allocations do not al…
Best-of-Both-Worlds Fairness of the Envy-Cycle-Elimination Algorithm
Jugal Garg, Eklavya Sharma
We consider the problem of fairly dividing indivisible goods among agents with additive valuations. It is known that an Epistemic EFX and -MMS allocation can be obtained using…
Constant-Factor EFX Exists for Chores
Jugal Garg, Aniket Murhekar, John Qin
We study the problem of fair allocation of chores to agents with additive preferences. In the discrete setting, envy-freeness up to any chore (EFX) has emerged as a compelling fair…
Weighted EF1 and PO Allocations with Few Types of Agents or Chores
Jugal Garg, Aniket Murhekar, John Qin
We investigate the existence of fair and efficient allocations of indivisible chores to asymmetric agents who have unequal entitlements or weights. We consider the fairness notion…
Approximating Competitive Equilibrium by Nash Welfare
Jugal Garg, Yixin Tao, László A. Végh
We study the relationship between two central concepts in the allocation of divisible goods: competitive equilibrium (CE) and allocations that maximize Nash welfare, i.e., allocati…
Breaking the Barrier for Approximate Maximin Share
Hannaneh Akrami, Jugal Garg
We study the fundamental problem of fairly allocating a set of indivisible goods among agents with additive valuations using the desirable fairness notion of maximin share (MMS…
Improving Approximation Guarantees for Maximin Share
Hannaneh Akrami, Jugal Garg, Eklavya Sharma +1
We consider fair division of a set of indivisible goods among agents with additive valuations using the fairness notion of maximin share (MMS). MMS is the most popular share-ba…
Fair and Efficient Allocation of Indivisible Chores with Surplus
Hannaneh Akrami, Bhaskar Ray Chaudhury, Jugal Garg +2
We study fair division of indivisible chores among agents with additive disutility functions. Two well-studied fairness notions for indivisible items are envy-freeness up to on…
Simplification and Improvement of MMS Approximation
Hannaneh Akrami, Jugal Garg, Eklavya Sharma +1
We consider the problem of fairly allocating a set of indivisible goods among agents with additive valuations, using the popular fairness notion of maximin share (MMS). Since M…
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…
Tractable Fragments of the Maximum Nash Welfare Problem
Jugal Garg, Edin Husić, Aniket Murhekar +1
We study the problem of maximizing Nash welfare (MNW) while allocating indivisible goods to asymmetric agents. The Nash welfare of an allocation is the weighted geometric mean of a…
Fair and Efficient Allocations of Chores under Bivalued Preferences
Jugal Garg, Aniket Murhekar, John Qin
We study the problem of fair and efficient allocation of a set of indivisible chores to agents with additive cost functions. We consider the popular fairness notion of envy-freenes…