Author name cluster

John Qin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

STOC Conference 2025 Conference Paper

Constant-Factor EFX Exists for Chores

Jugal Garg
Aniket Murhekar
John Qin

We study the problem of fair allocation of chores among agents with additive preferences. In the discrete setting, envy-freeness up to any chore (EFX) has emerged as a compelling fairness criterion. However, establishing its (non-)existence or achieving a meaningful approximation remains a major open question in fair division. The current best guarantee is the existence of O ( n 2 )-EFX allocations, where n denotes the number of agents, obtained through a sophisticated algorithm. In this paper, we show the existence of 4-EFX allocations, providing the first constant-factor approximation of EFX. We further investigate the existence of allocations that are both fair and efficient , using Pareto optimality (PO) as our efficiency criterion. For the special case of bivalued instances, we establish the existence of allocations that are both 3-EFX and PO, thereby improving upon the current best factor of O ( n )-EFX without any efficiency guarantees. For general additive instances, the existence of allocations that are α-EF k and PO has remained open for any constant values of α and k , where EF k denotes envy-freeness up to k chores. We provide the first positive result in this direction by showing the existence of allocations that are 2-EF2 and PO. Our results are obtained via a novel economic framework called earning restricted (ER) competitive equilibrium for fractional allocations, which imposes limits on the earnings of agents from each chore. We show the existence of ER equilibria by carefully formulating a linear complementarity problem (LCP) that captures all ER equilibria, and then prove that the classic complementary pivot algorithm applied to this LCP terminates at an ER equilibrium. By carefully setting earning limits and leveraging the properties of ER equilibria, we design algorithms that involve rounding the fractional solutions and then performing swaps and merges of bundles to meet the desired fairness and efficiency criteria. We expect that the concept of ER equilibrium will play a crucial role in deriving further results on related problems.

Details

IJCAI Conference 2024 Conference Paper

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 of weighted envy-freeness up to one chore (wEF1) and the efficiency notion of Pareto-optimality (PO). The existence of EF1 and PO allocations of chores to symmetric agents is a major open problem in discrete fair division, and positive results are known only for certain structured instances. In this paper, we study this problem for a more general setting of asymmetric agents and show that an allocation that is wEF1 and PO exists and can be computed in polynomial time for instances with: - Three types of agents where agents with the same type have identical preferences but can have different weights. - Two types of chores For symmetric agents, our results establish that EF1 and PO allocations exist for three types of agents and also generalize known results for three agents, two types of agents, and two types of chores. Our algorithms use a weighted picking sequence algorithm as a subroutine; we expect this idea and our analysis to be of independent interest.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

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 properties of EF1 and EFX in conjunction with the efficiency property of fractional Pareto-optimality (fPO). Existence (and computation) of an allocation that is simultaneously EF1/EFX and fPO are challenging open problems, and we make progress on both of them. We show the existence of an allocation that is - EF1 + fPO, when there are three agents, - EF1 + fPO, when there are at most two disutility functions, - EFX + fPO, for three agents with bivalued disutility functions. These results are constructive, based on strongly polynomial-time algorithms. We also investigate non-existence and show that an allocation that is EFX+fPO need not exist, even for two agents.

PDF Details DOI

AAAI Conference 2022 Conference Paper

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-freeness up to one good (EF1) with the efficiency notion of Paretooptimality (PO). While it is known that an EF1+PO allocation exists and can be computed in pseudo-polynomial time in the case of goods, the same problem is open for chores. Our first result is a strongly polynomial-time algorithm for computing an EF1+PO allocation for bivalued instances, where agents have (at most) two disutility values for the chores. To the best of our knowledge, this is the first nontrivial class of indivisible chores to admit an EF1+PO allocation and an efficient algorithm for its computation. We also study the problem of computing an envy-free (EF) and PO allocation for the case of divisible chores. While the existence of EF+PO allocation is known via competitive equilibrium with equal incomes, its efficient computation is open. Our second result shows that for bivalued instances, an EF+PO allocation can be computed in strongly polynomialtime.

PDF Details