Author name cluster

Aniket Murhekar

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.

14 papers

2 author rows

AAAI Conference 2026 Conference Paper

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 of envy-freeness up to any chore (EFX), and its multiplicative approximations. The existence of 4-EFX allocations was recently established by Garg, Murhekar, and Qin (2025). We improve this guarantee by proving the existence of 2-EFX allocations for all instances with additive disutilities. This approximation was previously known only for restricted instances such as bivalued disutilities (Lin, Wu, and Zhou (2025)) or three agents (Afshinmehr, Ansaripour, Danaei, and Mehlhorn (2024)). We obtain our result by providing a general framework for achieving approximate-EFX allocations. The approach begins with a suitable initial allocation and performs a sequence of local swaps between the bundles of envious and envied agents. For our main result, we begin with an initial allocation that satisfies envy-freeness up to one chore (EF1) and Pareto-optimality (PO); the existence of such an allocation was recently established in a major breakthrough by Mahara (2025). We further demonstrate the strength and generality of our framework by giving simple and unified proofs of existing results, namely (i) 2-EFX for bivalued instances, (ii) 2-EFX for three agents, (iii) EFX when the number of chores is at most twice the number of agents, and (iv) 4-EFX for all instances. We expect this framework to have broader applications in approximate-EFX due to its simplicity and generality.

PDF Details DOI

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

ICML Conference 2025 Conference Paper

You Get What You Give: Reciprocally Fair Federated Learning

Aniket Murhekar
Jiaxin Song
Parnian Shahkar
Bhaskar Ray Chaudhury
Ruta Mehta

Federated learning (FL) is a popular collaborative learning paradigm, whereby agents with individual datasets can jointly train an ML model. While higher data sharing improves model accuracy and leads to higher payoffs, it also raises costs associated with data acquisition or loss of privacy, causing agents to be strategic about their data contribution. This leads to undesirable behavior at a Nash equilibrium (NE) such as free-riding, resulting in sub-optimal fairness, data sharing, and welfare. To address this, we design $\mathcal{M}^{Shap}$, a budget-balanced payment mechanism for FL, that admits Nash equilibria under mild conditions, and achieves reciprocal fairness: where each agent’s payoff equals her contribution to the collaboration, as measured by the Shapley share. In addition to fairness, we show that the NE under $\mathcal{M}^{Shap}$ has desirable guarantees in terms of accuracy, welfare, and total data collected. We validate our theoretical results through experiments, demonstrating that $\mathcal{M}^{Shap}$ outperforms baselines in terms of fairness and efficiency.

Details

JAIR Journal 2024 Journal Article

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 good (EF1) and equitability up to one good (EQ1) in conjunction with Pareto-optimality (PO). There exists a pseudo-polynomial time algorithm to compute an EF1+PO allocation and a non-constructive proof of the existence of allocations that are both EF1 and fractionally Pareto-optimal (fPO), which is a stronger notion than PO. We present a pseudopolynomial time algorithm to compute an EF1+fPO allocation, thereby improving the earlier results. Our techniques also enable us to show that an EQ1+fPO allocation always exists when the values are positive and that it can be computed in pseudo-polynomial time. We also consider the class of k-ary instances where k is a constant, i.e., each agent has at most k different values for the goods. For such instances, we show that an EF1+fPO allocation can be computed in strongly polynomial time. When all values are positive, we show that an EQ1+fPO allocation for such instances can be computed in strongly polynomial time. Next, we consider instances where the number of agents is constant and show that an EF1+PO (likewise, an EQ1+PO) allocation can be computed in polynomial time. These results significantly extend the polynomial-time computability beyond the known cases of binary or identical valuations. We also design a polynomial-time algorithm that computes a Nash welfare maximizing allocation when there are constantly many agents with constant many different values for the goods. Finally, on the complexity side, we show that the problem of computing an EF1+fPO allocation lies in the complexity class PLS.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Fair and Efficient Chore Allocation: Existence and Computation

Aniket Murhekar

We investigate the existence and computation of fair and efficient allocations of indivisible chores to agents with additive preferences. We consider the popular envy-based fairness notions of envy-freeness up to one chore (EF1) and the efficiency notion of Pareto-optimality (PO). The existence of an allocation of chores that is simultaneously EF1 and PO is regarded a major open problem in discrete fair division. We show that an EF1 and PO allocation can be computed in polynomial time for certain structured instances. These results comprise the first non-trivial positive results for the problem and reveal insights towards settling the problem in its full generality.

PDF Details DOI

ICML Conference 2024 Conference Paper

Fair Federated Learning via the Proportional Veto Core

Bhaskar Ray Chaudhury
Aniket Murhekar
Zhuowen Yuan
Bo Li 0026
Ruta Mehta
Ariel D. Procaccia

Previous work on fairness in federated learning introduced the notion of core stability, which provides utility-based fairness guarantees to any subset of participating agents. However, these guarantees require strong assumptions on agent utilities that render them impractical. To address this shortcoming, we measure the quality of output models in terms of their ordinal rank instead of their cardinal utility, and use this insight to adapt the classical notion of proportional veto core (PVC) from social choice theory to the federated learning setting. We prove that models that are PVC-stable exist in very general learning paradigms, even allowing non-convex model sets, as well as non-convex and non-concave loss functions. We also design Rank-Core-Fed, a distributed federated learning algorithm, to train a PVC-stable model. Finally, we demonstrate that Rank-Core-Fed outperforms baselines in terms of fairness on different datasets.

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

TCS Journal 2023 Journal Article

Computing fair and efficient allocations with few utility values

Jugal Garg
Aniket Murhekar

We study the problem of allocating indivisible goods among agents with additive valuations in a fair and efficient manner, when agents have few utility values for the goods. We consider the compelling fairness notion of envy-freeness up to any good (EFX) in conjunction with Pareto-optimality (PO). Amanatidis et al. [1] showed that when there are at most two utility values, an EFX allocation can be computed in polynomial-time. We improve this result by showing that for such instances an allocation that is EFX and PO can be computed in polynomial-time. This is the first class apart from identical or binary valuations, for which EFX+PO allocations are shown to exist and are polynomial-time computable. In contrast, we show that when there are three utility values, EFX+PO allocations need not exist, and even deciding if EFX+PO allocations exist is NP-hard. Our techniques allow us to obtain similar results for the fairness notion of equitability up to any good (EQX) together with PO. We show that for instances with two positive values an EQX+PO allocation can be computed in polynomial-time, and deciding if an EQX+PO allocation exists is NP-hard when there are three utility values. We also study the problem of maximizing Nash welfare (MNW), and show that our EFX+PO algorithm returns an allocation that approximates the MNW to a factor of 1. 061 for two valued instances, in addition to being EFX+PO. In contrast, we show that for three valued instances, computing an MNW allocation is APX-hard. Finally, we give a polynomial-time algorithm for computing an MNW allocation for two-valued instances where the ratio of the two values is greater than a certain threshold.

Details DOI

NeurIPS Conference 2023 Conference Paper

Incentives in Federated Learning: Equilibria, Dynamics, and Mechanisms for Welfare Maximization

Aniket Murhekar
Zhuowen Yuan
Bhaskar Ray Chaudhury
Bo Li
Ruta Mehta

Federated learning (FL) has emerged as a powerful scheme to facilitate the collaborative learning of models amongst a set of agents holding their own private data. Although the agents benefit from the global model trained on shared data, by participating in federated learning, they may also incur costs (related to privacy and communication) due to data sharing. In this paper, we model a collaborative FL framework, where every agent attempts to achieve an optimal trade-off between her learning payoff and data sharing cost. We show the existence of Nash equilibrium (NE) under mild assumptions on agents' payoff and costs. Furthermore, we show that agents can discover the NE via best response dynamics. However, some of the NE may be bad in terms of overall welfare for the agents, implying little incentive for some fraction of the agents to participate in the learning. To remedy this, we design a budget-balanced mechanism involving payments to the agents, that ensures that any $p$-mean welfare function of the agents' utilities is maximized at NE. In addition, we introduce a FL protocol FedBR-BG that incorporates our budget-balanced mechanism, utilizing best response dynamics. Our empirical validation on MNIST and CIFAR-10 substantiates our theoretical analysis. We show that FedBR-BG outperforms the basic best-response-based protocol without additional incentivization, the standard federated learning protocol FedAvg, as well as a recent baseline MWFed in terms of achieving superior $p$-mean welfare.

PDF Details

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

AAMAS Conference 2022 Conference Paper

(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 and a bad (negatively valued) for others, i. e. , a mixed manna. As fairness notions, we consider arguably the strongest possible relaxations of envy-freeness and proportionality, namely envy-free up to any item (EFX and EFX0), and proportional up to the maximin good or any bad (PropMX and PropMX0). Our efficiency notion is Pareto-optimality (PO). We study two types of instances: (i) Separable, where the item set can be partitioned into goods and bads, and (ii) Restricted mixed goods (RMG), where for each item j, every agent has either a nonpositive value for j, or values j at the same vj > 0. We obtain polynomial-time algorithms for the following: • Separable instances: PropMX0 allocation. • RMG instances: Let pure bads be the set of items that everyone values negatively. – PropMX allocation for general pure bads. – EFX+PropMX allocation for identically-ordered pure bads. – EFX+PropMX+PO allocation for identical pure bads. Finally, if the RMG instances are further restricted to binary mixed goods where all the vj ’s are the same, we strengthen the results to guarantee EFX0 and PropMX0 respectively.

PDF

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

Highlights Conference 2021 Conference Abstract

Near-optimal complexity bounds for fragments of the Skolem Problem

Aniket Murhekar

Given a linear recurrence sequence (LRS), specified using the initial conditions and the recurrence relation, the Skolem problem asks if zero ever occurs in the infinite sequence generated by the LRS. Despite active research over last few decades, its decidability is known only for a few restricted subclasses, by either restricting the order of the LRS (upto 4) or by restricting the structure of the LRS (e. g. , roots of its characteristic polynomial). In this paper, we identify a subclass of LRS of arbitrary order for which the Skolem problem is easy, namely LRS all of whose characteristic roots are (possibly complex) roots of real algebraic numbers, i. e. , roots satisfying x^d = r for r real algebraic. We show that for this subclass, the Skolem problem can be solved in \NP^\RP. As a byproduct, we implicitly obtain effective bounds on the zero set of the LRS for this subclass. While prior works in this area often exploit deep results from algebraic and transcendental number theory to get such effective results, our techniques are primarily algorithmic and use linear algebra and Galois theory. We also complement our upper bounds with a \NP lower bound for the Skolem problem via a new direct reduction from 3-CNF-SAT, matching the best known lower bounds. This is joint work with S. Akshay, Nikhil Balaji, Rohith Varma, and Nikhil Vyas, and was accepted for publication at STACS 2020.

Details

AAAI Conference 2021 Conference Paper

On Fair and Efficient Allocations of Indivisible Goods

Aniket Murhekar
Jugal Garg

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 good (EF1) and equitability up to one good (EQ1) in conjunction with Pareto-optimality (PO). There exists a pseudopolynomial time algorithm to compute an EF1+PO allocation, and a non-constructive proof of existence of allocations that are both EF1 and fractionally Pareto-optimal (fPO). We present a pseudo-polynomial time algorithm to compute an EF1+fPO allocation, thereby improving the earlier results. Our techniques also enable us to show that an EQ1+fPO allocation always exists when the values are positive, and that it can be computed in pseudo-polynomial time. We also consider the class of k-ary instances where k is a constant, i. e. , each agent has at most k different values for the goods. We show that for such instances an EF1+fPO allocation can be computed in polynomial time. When all values are positive, we show that an EQ1+fPO allocation for such instances can be computed in polynomial time. Next, we consider instances where the number of agents is constant, and show that an EF1+PO (also EQ1+PO) allocation can be computed in polynomial time. These results significantly extend the polynomial-time computability beyond the known cases of binary or identical valuations. Further, we show that the problem of computing an EF1+PO allocation polynomial-time reduces to a problem in the complexity class PLS. We also design a polynomial-time algorithm that computes Nash welfare maximizing allocations when there are constantly many agents with constant many different values for the goods.

PDF Details