Tractable Graph Structures in EFX Orientation

doi:10.1007/978-3-032-03639-1_10

Tractable Graph Structures in EFX Orientation

2026-01-01

0

PRE

AI

DOI：10.1007/978-3-032-03639-1_10

Original

Original request for help

Save

Abstract

En 中文

Since its introduction, envy-freeness up to any good (EFX) has become a fundamental solution concept in fair division of indivisible goods. Its existence, however, remains elusive-even for four agents with additive utility functions, it is unknown whether an EFX allocation always exists. Unsurprisingly, researchers have explored restricted settings to delineate tractable and intractable cases. Christadolou, Fiat et al. [EC'23] introduced the notion of EFX-orientation, where the agents form the vertices of a graph and the items correspond to edges, and an agent values only the items that are incident to it. The goal is to allocate items to one of the adjacent agents while satisfying the EFX condition. This graph based setting has received considerable attention and has led to a growing body of work. Building on the work of Zeng and Mehta'24, which established a sharp complexity threshold based on the structure of the underlying graph-polynomial-time solvability for bipartite graphs and NP-hardness for graphs with chromatic number at least three-we further explore the algorithmic landscape of EFX-orientation by exploiting the graph structure using parameterized graph algorithms. Specifically, we show that bipartiteness is a surprisingly stringent condition for tractability: EFX orientation is NP-complete even when the valuations are symmetric, binary and the graph is at most two edge-removals away from being bipartite. Moreover, introducing a single non-binary value makes the problem NP-hard even when the graph is only one edge removal away from being bipartite. We further perform a parameterized analysis to examine structures of the underlying graph that enable tractability. In particular, we show that the problem is solvable in linear time on graphs whose treewidth is bounded by a constant. Furthermore, we also show that the complexity of an instance is closely tied to the sizes of acyclic connected components on its one-valued edges.

Keywords:

ASSIGNMENT

Tractable Graph Structures in EFX Orientation

Abstract

Journal

Organization

Cited Papers