Abstract
Fair division is the problem of allocating a set of items among agents in a fair manner. One of the most sought-after fairness notions is envy-freeness (EF), requiring that no agent envies another's allocation. When items are indivisible, it ceases to exist, and envy-freeness up to any good (EFX) emerged as one of its strongest relaxations. The existence of EFX allocations is arguably the biggest open question within fair division. Recently, Christodoulou, Fiat, Koutsoupias, and Sgouritsa (EC 2023) showed that EFX allocations exist for the case of graphical valuations where an instance is represented by a graph: nodes are agents, edges are goods, and each agent values only her incident edges. On the other hand, they showed NP-hardness for checking the existence of EFX orientation where every edge is allocated to one of its incident vertices, and asked for a characterization of graphs that exhibit EFX orientation regardless of the assigned valuations. In this paper, we make significant progress toward answering their question. We introduce the notion of strongly EFX orientable graphs -- graphs that have EFX orientations regardless of how much agents value the edges. We show a surprising connection between this property and the chromatic number $\chi(G)$ of the graph $G$. In particular, we show that graphs with $\chi(G)\le 2$ are strongly EFX orientable, and those with $\chi(G)>3$ are not strongly EFX orientable. We provide examples of strongly EFX orientable and non-strongly EFX orientable graphs of $\chi(G)=3$ to prove tightness. Finally, we give a complete characterization of strong EFX orientability when restricted to binary valuations.
Introduction
Fair division explores how to allocate resources among agents so that everyone is satisfied. The gold standard, Envy-Freeness (EF), requires that no agent prefers another's bundle over their own. However, with indivisible items, EF is often impossible. This has led to the study of EFX (Envy-Freeness up to any good): an agent might envy another, but that envy must vanish if we remove any single item from the other person's bundle.
This research focuses on graphical valuations, where agents are nodes and goods are edges. Agents only value edges incident to them. The central question is: Which graph structures guarantee an EFX orientation (assigning each edge to an endpoint) regardless of the specific valuations agents place on those edges? These are termed strongly EFX orientable graphs.
Methods
The authors utilize theoretical graph theory and combinatorial proofs to characterize these graphs. Key methodological steps include:
- Defining Strong EFX Orientability: Establishing the property where a graph admits an EFX orientation for any monotone valuation function.
- Binary Valuation Analysis: Analyzing 0-1 valuations to find necessary conditions for the general case.
- Graph Coloring Integration: Linking fairness to the chromatic number ($\chi(G)$) using tools like Menger’s Theorem and subdivisions of $K_4$.
- Counter-example Construction: Designing specific valuations for structures like glued triangles to demonstrate failure of strong EFX orientability.
Key Insights and Results
The most striking discovery is the direct link between a graph's colorability and its fairness potential.
The Chromatic Bound
- Bipartite Graphs ($\chi(G) \leq 2$): Every bipartite graph is strongly EFX orientable. This provides a broad class of networks where fairness is structurally guaranteed.
- Upper Bound ($\chi(G) > 3$): Any graph requiring more than three colors is never strongly EFX orientable. This establishes a hard limit on the complexity of fair networks.
- The 3-Chromatic Gap: For graphs with $\chi(G) = 3$, the result depends on specific topology. For instance, an odd cycle with a chord is strongly EFX orientable, while two triangles glued at a vertex are not.
Binary vs. General Valuations
The paper distinguishes between general and binary (0-1) valuations. A graph $G$ is 0-1 strongly EFX orientable if and only if for every forest subgraph $H$, there exists a set of nodes (one per tree) whose neighbors in $H$ form an independent set in $G$. This provides a complete characterization for the simpler binary case.
Discussion and Future Work
While this work significantly advances the understanding of EFX in graphical settings, several questions remain:
- Complete 3-Chromatic Characterization: A full structural description of which $\chi(G)=3$ graphs are strongly EFX orientable for general monotone valuations is still needed.
- Additive vs. Monotone: It is unknown if graphs that are EFX orientable for all additive valuations are also EFX orientable for all monotone valuations.
- Pareto Optimality: Future research should investigate graphs that admit EFX orientations that are also Pareto Optimal, ensuring efficiency alongside fairness.
- Computational Complexity: Determining if a graph is strongly EFX orientable remains a complex open problem.
Summary updated