Understanding EFX Allocations: Counting and Variants

• URL: http://arxiv.org/abs/2504.03951v1
• Date: Fri, 04 Apr 2025 21:36:09 GMT
• Title: Understanding EFX Allocations: Counting and Variants
• Authors: Tzeh Yuan Neoh, Nicholas Teh,
• Abstract summary: 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.
• Score: 0.8287206589886881
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Envy-freeness up to any good (EFX) is a popular and important fairness property in the fair allocation of indivisible goods, of which its existence in general is still an open question. In this work, we investigate the problem of determining the minimum number of EFX allocations for a given instance, arguing that this approach may yield valuable insights into the existence and computation of EFX allocations. We focus on restricted instances where the number of goods slightly exceeds the number of agents, and extend our analysis to weighted EFX (WEFX) and a novel variant of EFX for general monotone valuations, termed EFX+. In doing so, we identify the transition threshold for the existence of allocations satisfying these fairness notions. Notably, we resolve open problems regarding WEFX by proving polynomial-time computability under binary additive valuations, and establishing the first constant-factor approximation for two agents.

Related papers

• FinTSB: A Comprehensive and Practical Benchmark for Financial Time Series Forecasting [58.70072722290475]
  Financial time series (FinTS) record the behavior of human-brain-augmented decision-making.<n>FinTSB is a comprehensive and practical benchmark for financial time series forecasting.
  arXiv  Detail & Related papers  (2025-02-26T05:19:16Z)
• On the existence of EFX allocations in multigraphs [0.8057006406834466]
  We study the problem of dividing indivisible goods to several agents that have valuation set functions over the sets of goods.<n>As fair we consider the allocations that are envy-free up to any good (EFX), i.e., no agent envies any proper subset of the goods given to any other agent.
  arXiv  Detail & Related papers  (2025-02-13T21:16:27Z)
• STORM: A Spatio-Temporal Factor Model Based on Dual Vector Quantized Variational Autoencoders for Financial Trading [55.02735046724146]
  In financial trading, factor models are widely used to price assets and capture excess returns from mispricing.<n>We propose a Spatio-Temporal factOR Model based on dual vector quantized variational autoencoders, named STORM.<n>Storm extracts features of stocks from temporal and spatial perspectives, then fuses and aligns these features at the fine-grained and semantic level, and represents the factors as multi-dimensional embeddings.
  arXiv  Detail & Related papers  (2024-12-12T17:15:49Z)
• Temporal Fair Division of Indivisible Items [61.235172150247614]
  We study a fair division model where indivisible items arrive sequentially, and must be allocated immediately and irrevocably. Previous work on online fair division has shown impossibility results in achieving approximate envy-freeness under these constraints. We aim to ensure that the cumulative allocation at each round satisfies approximate temporal envy-freeness up to one item (TEF1)
  arXiv  Detail & Related papers  (2024-10-18T16:43:36Z)
• 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. 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.
  arXiv  Detail & Related papers  (2024-06-18T09:01:37Z)
• 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)
• Action Quality Assessment with Temporal Parsing Transformer [84.1272079121699]
  Action Quality Assessment (AQA) is important for action understanding and resolving the task poses unique challenges due to subtle visual differences. We propose a temporal parsing transformer to decompose the holistic feature into temporal part-level representations. Our proposed method outperforms prior work on three public AQA benchmarks by a considerable margin.
  arXiv  Detail & Related papers  (2022-07-19T13:29:05Z)
• Robust Allocations with Diversity Constraints [65.3799850959513]
  We show that the Nash Welfare rule that maximizes product of agent values is uniquely positioned to be robust when diversity constraints are introduced. We also show that the guarantees achieved by Nash Welfare are nearly optimal within a widely studied class of allocation rules.
  arXiv  Detail & Related papers  (2021-09-30T11:09:31Z)
• 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)
• Universal Off-Policy Evaluation [64.02853483874334]
  We take the first steps towards a universal off-policy estimator (UnO) We use UnO for estimating and simultaneously bounding the mean, variance, quantiles/median, inter-quantile range, CVaR, and the entire cumulative distribution of returns.
  arXiv  Detail & Related papers  (2021-04-26T18:54:31Z)
• 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)

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.