Graph structures that always allow fair division orientations found
A Polynomial Time Characterization For Strongly EFX Orientable Graphs
Computer Science and Game Theory
Summary
Dividing things fairly among people when each values different items can be complicated. This paper focuses on a type of problem where goods and people are represented as a graph, and fairness means no one envies another based on edges they value. The authors provide a clear and efficient way to tell which graphs always allow a fair division orientation, completing previous work that left this question open. Their method identifies such graphs by looking at how the graph can be broken down and certain special properties of its parts.
What this means in practice
- •For software engineers: Determine if a network structure guarantees fair division of tasks or resources without envy regardless of valuation.
- •For game designers: Design game mechanics that involve fair resource sharing on graphs that are guaranteed to have fair orientations.
A theory result. No direct application yet.
Authors
Jinghan A Zeng
Abstract
Discrete fair division is the problem of dividing a discrete set of goods among agents in a fair manner. In this setting, one of the most sought-after notions of fairness is envy-freeness up to any good (EFX). In 2023, Christodoulou, Fiat, Koutsoupias, and Sgouritsa introduced the idea of a graphical valuation, where the fair division problem is represented by a simple graph where vertices are the agents and the edges are the goods, and each vertex only values incident edges. They showed that an EFX allocation always exists, while determining the existence of an EFX orientation is NP-hard. They posed an open question of determining which graphs always admitted an EFX orientation regardless of valuation. These graphs, called strongly EFX orientable graphs, were first studied by Zeng and Mehta in 2025, who demonstrated that all such graphs have chromatic number at most 3, and bipartite graphs always admit an EFX orientation regardless of valuation. In this manuscript, we finish resolving this question by giving a polynomial time characterization of strongly EFX orientable graphs. In particular, we show that a connected graph $G$ is strongly EFX orientable if and only if either of the following is true: (1) $G$ is bipartite, or (2) the block decomposition of $G$ contains exactly one nonbipartite block $B$, and there exists a vertex $v \in B$ such that the degree of $v$ within $B$ is 2 and $G-v$ is bipartite. This proof was discovered by AI, with human intervention to break the problem into the appropriate subproblems.