On the existence of EFX allocations in multigraphs

• URL: http://arxiv.org/abs/2502.09777v1
• Date: Thu, 13 Feb 2025 21:16:27 GMT
• Title: On the existence of EFX allocations in multigraphs
• Authors: Alkmini Sgouritsa, Minas Marios Sotiriou,
• Abstract summary: We study the problem of dividing indivisible goods to several agents that have valuation set functions over the sets of goods. 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.
• Score: 0.8057006406834466
• License:
• Abstract: We study the problem of "fairly" dividing indivisible goods to several agents that have valuation set functions over the sets of goods. 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. The existence or not of EFX allocations is a major open problem in Fair Division, and there are only positive results for special cases. [George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023] introduced a restriction on the agents' valuations according to a graph structure: the vertices correspond to agents and the edges to goods, and each vertex/agent has zero marginal value (or in other words, they are indifferent) for the edges/goods that are not adjacent to them. The existence of EFX allocations has been shown for simple graphs with general monotone valuations [George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023], and for multigraphs for restricted additive valuations [Alireza Kaviani, Masoud Seddighin, Amir Mohammad Shahrezaei 2024]. In this work, we push the state-of-the-art further, and show that the EFX allocations always exists in multigraphs and general monotone valuations if any of the following three conditions hold: either (a) the multigraph is bipartite, or (b) each agent has at most $\lceil \frac{n}{4} \rceil -1$ neighbors, where $n$ is the total number of agents, or (c) the shortest cycle with non-parallel edges has length at least 6.

Related papers

• Continuous K-Max Bandits [54.21533414838677]
  We study the $K$-Max multi-armed bandits problem with continuous outcome distributions and weak value-index feedback. This setting captures critical applications in recommendation systems, distributed computing, server scheduling, etc. Our key contribution is the computationally efficient algorithm DCK-UCB, which combines adaptive discretization with bias-corrected confidence bounds.
  arXiv  Detail & Related papers  (2025-02-19T06:37:37Z)
• A Polynomial-Time Algorithm for EFX Orientations of Chores [0.0]
  We show a surprising separation between the case of goods and the case of chores. We also show the analogous decision problem for multigraphs to be NP-complete.
  arXiv  Detail & Related papers  (2025-01-23T08:53:18Z)
• Resource Allocation under the Latin Square Constraint [3.8028747063484585]
  We introduce a problem of allocating $n$ indivisible items among $n$ agents over $n$ rounds. This constraint ensures that each agent receives no more than one item per round and receives each item at most once. 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)
• Partial Identifiability in Inverse Reinforcement Learning For Agents With Non-Exponential Discounting [64.13583792391783]
  inverse reinforcement learning aims to infer an agent's preferences from observing their behaviour. One of the central difficulties in IRL is that multiple preferences may lead to the same observed behaviour. We show that generally IRL is unable to infer enough information about $R$ to identify the correct optimal policy.
  arXiv  Detail & Related papers  (2024-12-15T11:08:58Z)
• Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
  We study EgalMAB, an egalitarian assignment problem in the context of multi-armed bandits. We design and analyze a UCB-based policy EgalUCB and establish upper bounds on the cumulative regret.
  arXiv  Detail & Related papers  (2024-10-08T09:49:47Z)
• 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)
• 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)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  Online gradient descent (OGD) is well known to be doubly optimal under strong convexity or monotonicity assumptions. In this paper, we design a fully adaptive OGD algorithm, textsfAdaOGD, that does not require a priori knowledge of these parameters.
  arXiv  Detail & Related papers  (2023-10-21T18:38:13Z)
• (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)
• 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)

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.