Pushing the Frontier on Approximate EFX Allocations

• URL: http://arxiv.org/abs/2406.12413v1
• Date: Tue, 18 Jun 2024 09:01:37 GMT
• Title: Pushing the Frontier on Approximate EFX Allocations
• Authors: Georgios Amanatidis, Aris Filos-Ratsikas, Alkmini Sgouritsa,
• Abstract summary: We study the problem of allocating a set of indivisible goods to a set of agents with additive valuation functions. We get existence results for strict generalizations of the settings for which exact EFX allocations are known to exist. Our results push the emphfrontier of existence and computation of approximate EFX allocations.
• Score: 14.101164748526159
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of allocating a set of indivisible goods to a set of agents with additive valuation functions, aiming to achieve approximate envy-freeness up to any good ($\alpha$-EFX). The state-of-the-art results on the problem include that (exact) EFX allocations exist when (a) there are at most three agents, or (b) the agents' valuation functions can take at most two values, or (c) the agents' valuation functions can be represented via a graph. For $\alpha$-EFX, it is known that a $0.618$-EFX allocation exists for any number of agents with additive valuation functions. In this paper, we show that $2/3$-EFX allocations exist when (a) there are at most \emph{seven agents}, (b) the agents' valuation functions can take at most \emph{three values}, or (c) the agents' valuation functions can be represented via a \emph{multigraph}. Our results can be interpreted in two ways. First, by relaxing the notion of EFX to $2/3$-EFX, we obtain existence results for strict generalizations of the settings for which exact EFX allocations are known to exist. Secondly, by imposing restrictions on the setting, we manage to beat the barrier of $0.618$ and achieve an approximation guarantee of $2/3$. Therefore, our results push the \emph{frontier} of existence and computation of approximate EFX allocations, and provide insights into the challenges of settling the existence of exact EFX allocations.

Related papers

• $\textit{X}^2$-DFD: A framework for e${X}$plainable and e${X}$tendable Deepfake Detection [52.14468236527728]
  We propose a novel framework called $X2$-DFD, consisting of three core modules. The first module, Model Feature Assessment (MFA), measures the detection capabilities of forgery features intrinsic to MLLMs, and gives a descending ranking of these features. The second module, Strong Feature Strengthening (SFS), enhances the detection and explanation capabilities by fine-tuning the MLLM on a dataset constructed based on the top-ranked features. The third module, Weak Feature Supplementing (WFS), improves the fine-tuned MLLM's capabilities on lower-ranked features by integrating external dedicated
  arXiv  Detail & Related papers  (2024-10-08T15:28:33Z)
• Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
  Markov Games (MG) is an important model for Multi-Agent Reinforcement Learning (MARL) This paper first refines the AVLPR framework by Wang et al. (2023), with an insight of designing pessimistic estimation of the sub-optimality gap. We give the first algorithm that tackles the curse of multi-agents, attains the optimal $O(T-1/2) convergence rate, and avoids $textpoly(A_max)$ dependency simultaneously.
  arXiv  Detail & Related papers  (2024-02-11T01:51:15Z)
• EFX Allocations Exist for Binary Valuations [0.0]
  We study the fair division problem and the existence of allocations satisfying the fairness criterion envy-freeness up to any item (EFX) By using completely different techniques, we extend this existence to general binary valuations that are not necessarily submodular. We present a time algorithm for computing an EFX allocation.
  arXiv  Detail & Related papers  (2023-08-10T11:28:31Z)
• 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)
• On the Identifiability and Estimation of Causal Location-Scale Noise Models [122.65417012597754]
  We study the class of location-scale or heteroscedastic noise models (LSNMs) We show the causal direction is identifiable up to some pathological cases. We propose two estimators for LSNMs: an estimator based on (non-linear) feature maps, and one based on neural networks.
  arXiv  Detail & Related papers  (2022-10-13T17:18:59Z)
• (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)
• Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness [16.187873844872637]
  We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance. We show that the corresponding allocations not only are EFX but also satisfy maximin share fairness, something that is not true for this algorithm in the non-strategic setting!
  arXiv  Detail & Related papers  (2021-09-17T16:57:20Z)
• Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning [66.94149388181343]
  We present a new version of a popular $Q$-learning algorithm for MARL. We show that it can recover the optimal policy even with access to $Q*$. We also demonstrate improved performance on predator-prey and challenging multi-agent StarCraft benchmark tasks.
  arXiv  Detail & Related papers  (2020-06-18T18:34:50Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)
• Finding Fair and Efficient Allocations When Valuations Don't Add Up [25.962505544590947]
  We show that when agent valuations are matroid rank functions, a socially optimal (i.e. utilitarian social welfare-maximizing) achieves allocation that envy-freeness up to one item (EF1) exists and is computationally tractable. This is the first valuation function class not subsumed by additive valuations for which it has been established that an allocation maximizing Nash welfare is EF1.
  arXiv  Detail & Related papers  (2020-03-16T07:42:27Z)
• 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.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.