14 citations · 35 across the 11 of their papers we have counts for
13 papers
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…
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…
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…
Nash Equilibria of Two-Player Matrix Games Repeated Until Collision
Aniket Murhekar, Eklavya Sharma
We introduce and initiate the study of a natural class of repeated two-player matrix games, called Repeated-Until-Collision (RUC) games. In each round, both players simultaneously…
Dynamic Vector Bin Packing for Online Resource Allocation in the Cloud
Aniket Murhekar, David Arbour, Tung Mai +1
Several cloud-based applications, such as cloud gaming, rent servers to execute jobs which arrive in an online fashion. Each job has a resource demand and must be dispatched to a c…
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…
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…
(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna
Vasilis Livanos, Ruta Mehta, Aniket Murhekar
We study the problem of finding fair and efficient allocations of a set of indivisible items to a set of agents, where each item may be a good (positively valued) for some agents a…
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…
On Fair and Efficient Allocations of Indivisible Public Goods
Jugal Garg, Pooja Kulkarni, Aniket Murhekar
We study fair allocation of indivisible public goods subject to cardinality (budget) constraints. In this model, we have n agents and m available public goods, and we want to selec…
Automated Recurrence Analysis for Almost-Linear Expected-Runtime Bounds
Krishnendu Chatterjee, Hongfei Fu, Aniket Murhekar
We consider the problem of developing automated techniques for solving recurrence relations to aid the expected-runtime analysis of programs. Several classical textbook algorithms…