EFX Allocation In (Multi)Hypergraphs

• URL: http://arxiv.org/abs/2608.03171v1
• Date: Tue, 04 Aug 2026 06:02:06 GMT
• Title: EFX Allocation In (Multi)Hypergraphs
• Abstract summary: We consider the allocations that are envy-free-up-to-any-good (EFX)<n>Finding if EFX alloca- tions always exist, even for agents with additive valuations, is a major open problem in Fair Division.
• Score: 3.702284004959709
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study fair allocations of indivisible goods among agents with heterogeneous monotone valuations. As fair we consider the allocations that are envy-free-up-to-any-good (EFX). Finding if EFX alloca- tions always exist, even for agents with additive valuations, is a major open problem in Fair Division. Christodoulou et al. (2023) introduced the (multi-hyper)graph setting, where agents and goods are represented by vertices and edges of a graph, respectively, and only the endpoints of an edge may have non-zero marginal value for it. We show that for hypergraphs with girth at least 4 and agents with general monotone valuations there always exists an EFX allocation and can be constructed in polynomial time. We generalize our approach to also show that multi-hypergraphs with girth (on the simple hypergraph) at least 4 always admit an EFX allocation, as long as there exists a single vertex whose incident edges have multiplicity at most the size of that edge minus 2; our construction in this case needs pseudo-polynomial time.

Related papers

• Estimating Fair Graphs from Graph-Stationary Data [58.94389691379349]
  We consider group and individual fairness for graphs corresponding to group- and node-level definitions.<n>To evaluate the fairness of a given graph, we provide multiple bias metrics, including novel measurements in the spectral domain.<n>One variant of FairSpecTemp exploits commutativity properties of graph stationarity while directly constraining bias.<n>The other implicitly encourages fair estimates by restricting bias in the graph spectrum and is thus more flexible.
  arXiv  Detail & Related papers  (2025-10-08T20:51:57Z)
• On Approximate MMS Allocations on Restricted Graph Classes [0.31457219084519]
  We study the problem of fair division of a set of indivisible goods with connectivity constraints.<n>It is known that for some classes of graphs, such as complete graphs, cycles, and $d$-claw-free graphs for any fixed $d$, such approximate allocations indeed exist.<n>We show that such allocations exist for several well-studied classes, including block graphs, cacti, complete multipartite graphs, and split graphs.
  arXiv  Detail & Related papers  (2025-08-08T14:17:44Z)
• Pruning Spurious Subgraphs for Graph Out-of-Distribution Generalization [90.74916553208153]
  We propose PrunE, the first pruning-based graph OOD method that eliminates spurious edges to improve OOD generalizability.<n>PrunE employs two regularization terms to prune spurious edges: 1) graph size constraint to exclude uninformative spurious edges, and 2) $epsilon$-probability alignment to further suppress the occurrence of spurious edges.
  arXiv  Detail & Related papers  (2025-06-06T10:34:48Z)
• 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)
• 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)
• Polynomial-Time Algorithms for Fair Orientations of Chores [1.0312968200748118]
  This paper addresses the problem of finding fair orientations of graphs of chores.<n>We find EF1 and EFX orientations of graphs containing only chores if they exist, even if there are self-loops.<n>We also show the EF1 and EFX orientation problems for multigraphs to be NP-complete.
  arXiv  Detail & Related papers  (2025-01-23T08:53:18Z)
• 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)
• Graph Sparsification via Mixture of Graphs [67.40204130771967]
  We introduce Mixture-of-Graphs (MoG) to dynamically select tailored pruning solutions for each node. MoG incorporates multiple sparsifier experts, each characterized by unique sparsity levels and pruning criteria, and selects the appropriate experts for each node. Experiments on four large-scale OGB datasets and two superpixel datasets, equipped with five GNNs, demonstrate that MoG identifies subgraphs at higher sparsity levels.
  arXiv  Detail & Related papers  (2024-05-23T07:40:21Z)
• GraphMETRO: Mitigating Complex Graph Distribution Shifts via Mixture of Aligned Experts [75.51612253852002]
  GraphMETRO is a Graph Neural Network architecture that models natural diversity and captures complex distributional shifts. GraphMETRO achieves state-of-the-art results on four datasets from the GOOD benchmark.
  arXiv  Detail & Related papers  (2023-12-07T20:56:07Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• All the World's a (Hyper)Graph: A Data Drama [55.144729234861316]
  Hyperbard is a dataset of diverse data representations from Shakespeare's plays. Our representations range from simple graphs capturing character co-occurrence in single scenes to hypergraphs encoding complex communication settings. As an homage to our data source, and asserting that science can also be art, we present all our points in the form of a play.
  arXiv  Detail & Related papers  (2022-06-16T14:51:28Z)
• Geometric Graph Representation Learning via Maximizing Rate Reduction [73.6044873825311]
  Learning node representations benefits various downstream tasks in graph analysis such as community detection and node classification. We propose Geometric Graph Representation Learning (G2R) to learn node representations in an unsupervised manner. G2R maps nodes in distinct groups into different subspaces, while each subspace is compact and different subspaces are dispersed.
  arXiv  Detail & Related papers  (2022-02-13T07:46:24Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  This paper presents a convex-analytic framework to learn from data. We show that a triangular convexity decomposition is guaranteed by a transform of the corresponding to its upper part.
  arXiv  Detail & Related papers  (2021-09-17T17:46:12Z)

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.