Related papers: The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items

The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items

URL: http://arxiv.org/abs/2601.12849v1
Date: Mon, 19 Jan 2026 09:02:32 GMT
Title: The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items
Authors: Eugene Lim, Tzeh Yuan Neoh, Nicholas Teh,
Abstract summary: Envy-freeness up any good (EFX) is a central fairness notion for allocating indivisible goods, yet its existence is unresolved in general.<n>We study how EFX interacts with generalized dichotomies-mean-mean welfare, which subsumes commonly-studied utilitarian ($p=1), Nash ($p-mean) welfare, and egalitarian ($p rightarrow -infty$) objectives.
Score: 13.603504120117016
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Envy-freeness up to any good (EFX) is a central fairness notion for allocating indivisible goods, yet its existence is unresolved in general. In the setting with few surplus items, where the number of goods exceeds the number of agents by a small constant (at most three), EFX allocations are guaranteed to exist, shifting the focus from existence to efficiency and computation. We study how EFX interacts with generalized-mean ($p$-mean) welfare, which subsumes commonly-studied utilitarian ($p=1$), Nash ($p=0$), and egalitarian ($p \rightarrow -\infty$) objectives. We establish sharp complexity dichotomies at $p=0$: for any fixed $p \in (0,1]$, both deciding whether EFX can attain the global $p$-mean optimum and computing an EFX allocation maximizing $p$-mean welfare are NP-hard, even with at most three surplus goods; in contrast, for any fixed $p \leq 0$, we give polynomial-time algorithms that optimize $p$-mean welfare within the space of EFX allocations and efficiently certify when EFX attains the global optimum. We further quantify the welfare loss of enforcing EFX via the price of fairness framework, showing that for $p > 0$, the loss can grow linearly with the number of agents, whereas for $p \leq 0$, it is bounded by a constant depending on the surplus (and for Nash welfare it vanishes asymptotically). Finally we show that requiring Pareto-optimality alongside EFX is NP-hard (and becomes $Σ_2^P$-complete for a stronger variant of EFX). Overall, our results delineate when EFX is computationally costly versus structurally aligned with welfare maximization in the setting with few surplus items.

Related papers

Trade-off in Estimating the Number of Byzantine Clients in Federated Learning [51.015234193544636]
Federated learning is vulnerable to Byzantine clients that can send any erroneous signals.<n>We show that underestimation ($hatfge f$) can lead to arbitrarily poor performance for both aggregators and federated learning.<n>All these optimal bounds are proportional to $hatf/(n-f-hatf)$ with $n$ clients, which monotonically increases with larger $hatf$.
arXiv Detail & Related papers (2025-10-06T02:01:56Z)
Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
We consider a centralized distributed learning setup where all workers jointly find an unbiased bound LDeltaepsilon2,$ better poly-logarithmically in $n$, even in the homogeneous (i.i.d.) case, where all workers access the same distribution.
arXiv Detail & Related papers (2025-06-30T13:27:39Z)
Understanding EFX Allocations: Counting and Variants [0.8287206589886881]
Envy-freeness up to any good (EFX) is a popular and important fairness property in the fair allocation of indivisible goods.<n>We argue that this approach may yield valuable insights into the existence and computation of EFX allocations.
arXiv Detail & Related papers (2025-04-04T21:36:09Z)
Resource Allocation under the Latin Square Constraint [3.8028747063484585]
We introduce a problem of allocating $n$ indivisible items among $n$ agents over $n$ rounds.<n>This constraint ensures that each agent receives no more than one item per round and receives each item at most once.<n>Real-world applications like scheduling, resource management, and experimental design require the Latin square constraint to satisfy fairness or balancedness in allocation.
arXiv Detail & Related papers (2025-01-11T10:53:48Z)
Pushing the Frontier on Approximate EFX Allocations [14.101164748526159]
We study the problem of allocating a set of indivisible goods to a set of agents with additive valuation functions.<n>We get existence results for strict generalizations of the settings for which exact EFX allocations are known to exist.<n>Our results push the emphfrontier of existence and computation of approximate EFX allocations.
arXiv Detail & Related papers (2024-06-18T09:01:37Z)
Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations [20.774185319381985]
We study the problem of fairly allocating a set of indivisible goods among agents with bivalued submodular valuations. We show that neither the leximin nor the MNW allocation is guaranteed to be envy free up to one good.
arXiv Detail & Related papers (2023-02-06T19:41:28Z)
Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
We propose a novel offline reinforcement learning algorithm called Pessimistic vAlue iteRaTion with rEward Decomposition (PARTED) PARTED decomposes the trajectory return into per-step proxy rewards via least-squares-based reward redistribution, and then performs pessimistic value based on the learned proxy reward. To the best of our knowledge, PARTED is the first offline RL algorithm that is provably efficient in general MDP with trajectory-wise reward.
arXiv Detail & Related papers (2022-06-13T19:11:22Z)
(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna [10.933894827834825]
We study the problem of finding fair and efficient allocations of a set of indivisible items to a set of agents. As fairness notions, we consider arguably the strongest possible relaxations of envy-freeness and proportionality.
arXiv Detail & Related papers (2022-02-06T01:29:50Z)
Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
arXiv Detail & Related papers (2021-06-02T22:03:36Z)
Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
We study the statistical limits of Imitation Learning in episodic Markov Decision Processes (MDPs) with a state space $mathcalS$. We establish an upper bound $O(|mathcalS|H3/2/N)$ for the suboptimality using the Mimic-MD algorithm in Rajaraman et al ( 2020) We show the minimax suboptimality grows as $Omega( H3/2/N)$ when $mathcalS|geq 3$ while the unknown-transition setting suffers from a larger sharp rate
arXiv Detail & Related papers (2021-02-25T15:50:19Z)
Safe Learning under Uncertain Objectives and Constraints [66.05180398174286]
We consider non-textitunknown yet safety-critical optimization problems under textitunknown yet safety-critical constraints. Such problems naturally arise in a variety of domains including robotics, manufacturing, and medical procedures. A crucial component of our analysis is to introduce and apply a technique called shrinkage in the context of safe optimization.
arXiv Detail & Related papers (2020-06-23T20:51:00Z)
Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
We study the Safe Reinforcement Learning (SRL) problem using the Constrained Markov Decision Process (CMDP) formulation. We present an provably efficient online policy optimization algorithm for CMDP with safe exploration in the function approximation setting.
arXiv Detail & Related papers (2020-03-01T17:47:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.