EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture

Basic Information

• Paper ID: 2410.17002
• Title: EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture
• Authors: Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, Nidhi Rathi
• Classification: cs.GT (Game Theory), cs.DS (Data Structures and Algorithms)
• Publication Date: October 2024 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2410.17002

Abstract

This paper investigates the fair allocation of indivisible items under valuation functions represented by multi-graphs. In this model, agents correspond to graph vertices and items correspond to edges, with each agent having positive valuations only for edges incident to them. The objective is to find a fair allocation satisfying the EFX (envy-free up to any item) condition. Building upon the work of Christodoulou et al. (2023), who proved the existence of EFX allocations for monotone valuations on simple graphs, this paper extends the investigation to various classes of multi-graphs. The main contributions include: (1) proving the existence of EFX allocations for monotone valuations on bipartite multi-graphs and MMS-feasible valuations on multi-cycles; (2) providing corresponding pseudo-polynomial time algorithms; (3) offering a complete characterization of the EFX orientation problem; (4) establishing NP-completeness for determining EFX orientation existence.

Research Background and Motivation

Problem Background

Fair division theory is an important research direction at the intersection of economics, social sciences, mathematics, and computer science, aiming to allocate a set of resources fairly among multiple participants. In the case of indivisible items, classical envy-free allocations may not exist; consequently, researchers have proposed various relaxations, with EFX considered the fairness concept closest to envy-freeness in discrete settings.

Research Motivation

1. Theoretical Challenge: For four or more agents, the existence of EFX allocations remains a major open problem
2. Model Extension: Following Christodoulou et al.'s proof of EFX allocation existence on simple graphs, the natural question arises: what about multi-graphs?
3. Practical Applications: The model applies to scenarios where agents in geographic settings care only about nearby resources, such as trade corridors and natural gas pipelines

Limitations of Existing Approaches

• Existing results are primarily limited to simple graphs (any two agents share at most one item)
• Systematic research on multi-graphs (where two agents can share multiple items) is lacking
• The existence and computational complexity of EFX orientations remain incompletely characterized

Core Contributions

1. Existence Theorems: Proves that EFX allocations always exist for monotone valuations on bipartite multi-graphs and for MMS-feasible valuations on multi-cycles
2. Algorithm Design: Provides pseudo-polynomial time algorithms for computing EFX allocations, with polynomial time computation for reducible valuations
3. Complete Characterization: Offers a complete characterization of EFX orientation existence on bipartite multi-graphs based on two key parameters (q and d(G))
4. Complexity Analysis: Establishes NP-completeness for determining EFX orientation existence, even for constant numbers of agents
5. Approximation Results: Proves the existence of orientations where at least ⌈n/2⌉ agents satisfy EFX and remaining agents satisfy 1/2-EFX when exact EFX orientations do not exist

Methodology Details

Task Definition

Input:

• Multi-graph G = (V,E) where V = n represents n agents and E represents m items
• Valuation functions {vi}i∈n satisfying vi(S) = vi(S ∩ E(i)), where E(i) is the set of edges incident to agent i

Output:

• Complete allocation X = (X1,...,Xn) satisfying the EFX condition
• Or EFX orientation (each item allocated to one of its endpoint agents)

Constraints:

• EFX: For any agents i,j and item g ∈ Xj, vi(Xi) ≥ vi(Xj \ {g})
• Valuation function types: monotone, reducible, MMS-feasible, etc.

Model Architecture

Core Concepts

1. T-cut Configuration: For adjacent agents i ∈ S and j ∈ T, agent j partitions E(i,j) into two packages C1 and C2, both EFX-feasible for j
2. Available Set: Define Ai,j(X) as the set of available edges for agent i from E(i,j) under current allocation X
3. Safe Set: For envied agent i, define Si(X) as its safe set

Key Properties

The algorithm maintains six key properties:

1. X is an EFX orientation
2. Items in E(i,j) are allocated according to j-cut configuration
3. Each agent receives its most preferred available package
4. Non-envied agents have empty available sets
5. Non-envied agents' valuations of unallocated incident edges do not exceed current package value
6. Envied agents' enviers are in their safe sets

Technical Innovations

1. Configuration Mechanism Design

Innovatively introduces the T-cut configuration concept, combining ideas from two-agent cut-and-choose protocols, providing a systematic approach for handling multiple edges in multi-graphs.

2. Staged Algorithm Framework

Designs five algorithms sequentially satisfying the six key properties:

• Algorithm 1: Greedy orientation satisfying properties (1)-(3)
• Algorithm 2: Handling non-envied agents satisfying property (4)
• Algorithm 3: Increasing non-envied agents' valuations satisfying property (5)
• Algorithm 4: Constructing safe sets satisfying property (6)
• Algorithm 5: Final allocation of remaining items

3. Bipartite Structure Exploitation

Fully leverages the structural properties of bipartite graphs, particularly that envied vertices appear in only one partition, significantly simplifying analysis and algorithm design.

Experimental Setup

Theoretical Analysis Framework

This is primarily a theoretical work, with results verified through mathematical proofs rather than experiments. The analysis framework includes:

1. Existence Proofs: Constructive proofs demonstrating how to find allocations satisfying the conditions
2. Algorithm Complexity Analysis: Analyzing time complexity of each algorithm step
3. Counterexample Construction: Using concrete instances to prove non-existence of EFX orientations in certain cases

Evaluation Metrics

• EFX Satisfaction: Whether all agents satisfy the EFX condition
• Time Complexity: Algorithm runtime (polynomial vs. pseudo-polynomial)
• Approximation Ratio: Quality of approximate solutions when exact solutions do not exist

Experimental Results

Main Results

1. Existence Theorems

Theorem 4.11: For monotone valuations on bipartite multi-graphs, EFX allocations always exist and can be computed in pseudo-polynomial time; for reducible valuations, computation is possible in polynomial time.

Theorem 5.1: For MMS-feasible valuations on multi-cycles, EFX allocations always exist and can be computed in pseudo-polynomial time.

2. Complete Characterization of EFX Orientations

Complete characterization based on parameters q (maximum edges between any two agents) and d(G) (graph diameter):

3. Complexity Results

Theorem 3.6: Determining whether an EFX orientation exists on a bipartite multi-graph is NP-complete, even for constant numbers of agents.

4. Approximation Results

Theorem 4.12: For additive valuations on bipartite multi-graphs, there always exists an orientation where at least ⌈n/2⌉ agents satisfy EFX and remaining agents satisfy 1/2-EFX.

Case Studies

The paper demonstrates algorithm execution through multiple concrete examples:

• Figures 7-10 show step-by-step algorithm execution on specific bipartite multi-graphs
• Counterexample constructions (Figures 1-5) prove non-existence of EFX orientations in certain cases

Theoretical Findings

1. Critical Role of Bipartite Structure: The bipartite structure ensures envied vertices appear in only one partition, which is key to algorithm success
2. Effectiveness of Configuration Mechanism: T-cut configuration provides a unified framework for handling multi-edges
3. Parametric Complexity: The two parameters q and d(G) completely characterize EFX orientation existence

Related Work

Current State of EFX Research

• Two Agents: Plaut and Roughgarden proved existence for monotone valuations
• Three Agents: Series of works proved existence for various valuation types
• Special Valuations: Existence results for special cases like identical valuations and binary valuations

Fair Division on Graphs

• Christodoulou et al. first proposed the EFX allocation model on simple graphs
• Subsequent work studied EF1 orientations, mixed items, and other extensions
• This paper is the first systematic study of multi-graphs

Concurrent Work

Two independent concurrent works also study EFX on multi-graphs:

• Sgouritsa and Sotiriou (2025): Prove EFX existence for monotone valuations on bipartite multi-graphs
• Bhaskar and Pandit (2024): Study EFX existence on specific multi-graph classes

Conclusions and Discussion

Main Conclusions

1. Theoretical Contribution: Provides the first complete characterization of EFX allocation existence on bipartite multi-graphs, extending the existing theoretical framework
2. Algorithmic Contribution: Provides practical pseudo-polynomial time algorithms, achieving polynomial time for specific valuation types
3. Complexity Characterization: Completely analyzes the computational complexity of the EFX orientation problem

Limitations

1. Graph Class Restrictions: Results focus primarily on bipartite multi-graphs; general multi-graphs remain open
2. Valuation Function Restrictions: While covering multiple valuation types, the most general case remains unresolved
3. Algorithm Efficiency: For general monotone valuations, only pseudo-polynomial time complexity is achievable

Future Directions

1. General Multi-graphs: Authors conjecture EFX allocations exist on arbitrary multi-graphs, but proof requires new techniques
2. Algorithm Optimization: Seek more efficient algorithms, particularly polynomial time algorithms
3. Social Welfare: Study the trade-off between EFX allocations and efficiency

In-Depth Evaluation

Strengths

1. Theoretical Depth: Provides complete existence proofs and complexity analysis with significant theoretical contributions
2. Technical Innovation: The T-cut configuration mechanism and staged algorithm framework are innovative
3. Result Completeness: Offers complete parametric characterization of EFX orientation existence
4. Clear Presentation: Paper structure is clear, proofs are detailed, and content is accessible

Weaknesses

1. Lack of Experimental Validation: As a purely theoretical work, lacks algorithm performance evaluation on real data
2. Limited Application Scenarios: Practical applications of multi-graph models are relatively limited
3. Technical Limitations: Extension to general multi-graphs still faces technical challenges

Impact

1. Academic Value: Provides important theoretical progress for fair division theory, advancing EFX research
2. Methodological Contribution: Proposed technical framework may inspire solutions to other graph-based fair division problems
3. Open Problems: Provides important technical foundation for EFX existence on general multi-graphs

Applicable Scenarios

1. Theoretical Research: Provides important reference for fair division theory researchers
2. Algorithm Design: Configuration mechanism can be applied to design other fair division algorithms
3. Complexity Theory: NP-completeness results have value for computational complexity research

References

The paper cites important literature in fair division, including:

• Christodoulou et al. 2023: Pioneering work on EFX allocations on simple graphs
• Plaut and Roughgarden 2020: Proof of EFX existence for two agents
• Chaudhury et al. 2020: Important progress for three agents
• Caragiannis et al. 2016: First introduction of the EFX concept

Summary: This is a high-quality theoretical computer science paper making important contributions to fair division theory. The paper is technically sound with complete results, providing deep insights into understanding EFX allocation problems on multi-graphs, representing significant progress in the field.