Polynomial-Time Algorithms for Fair Orientations of Chores

Basic Information

• Paper ID: 2501.13481
• Title: Polynomial-Time Algorithms for Fair Orientations of Chores
• Authors: Kevin Hsu, Valerie King (University of Victoria)
• Categories: cs.GT (Game Theory), cs.AI (Artificial Intelligence), cs.DM (Discrete Mathematics)
• Publication Date: arXiv preprint, January 2025
• Paper Link: https://arxiv.org/abs/2501.13481

Abstract

This paper investigates the fair allocation of chores (tasks with negative utility) on graphs, where each vertex represents an agent and each edge represents a chore. When an edge is not adjacent to a vertex, the marginal utility of that chore for the corresponding agent is zero. Zhou et al. (IJCAI 2024) conjectured that the EFX orientation decision problem for pure chore graphs is NP-complete. This paper resolves this conjecture by providing a polynomial-time algorithm that finds EF1 and EFX orientations for pure chore graphs (if they exist). Notably, this contrasts sharply with the NP-completeness of the EFX orientation decision problem for pure goods graphs, revealing a surprising separation between goods and chores. The paper also proves that the EF1 and EFX orientation problems on multigraphs are NP-complete.

Research Background and Motivation

Problem Definition

The core problem studied in this paper is fair allocation of chores on graphs:

1. Graph Model: Each vertex in graph G corresponds to an agent, and each edge corresponds to a chore
2. Utility Constraints: When edge e is not adjacent to vertex i, the marginal utility of e for i is 0
3. Allocation Objective: Find an orientation satisfying fairness conditions (EF1 or EFX)

Research Significance

1. Practical Applications: Models various real-world scenarios such as office allocation for employees, classroom scheduling, and divorce asset division
2. Theoretical Value: Fair allocation is referred to as "the most mysterious problem in fair division"
3. Complexity Theory: Reveals fundamental differences in computational complexity between goods and chores

Limitations of Existing Methods

1. EFX Existence: The existence of EFX allocations in general cases remains an open problem
2. Graph Restrictions: Existing results primarily focus on goods; research on chores is relatively limited
3. Complexity Differences: Zhou et al. conjectured that the complexity for chores is the same as for goods

Research Motivation

1. Resolving Important Conjecture: Directly addresses Zhou et al.'s NP-completeness conjecture
2. Revealing Essential Differences: Explores the computational complexity separation between goods and chores
3. Algorithm Design: Provides practical polynomial-time algorithms

Core Contributions

1. Resolving Important Conjecture: Proves that Zhou et al.'s NP-completeness conjecture regarding EFX0 orientation for chore graphs is incorrect, providing a polynomial algorithm with O(|V(G)|⁴) time complexity
2. EF1 Algorithm: Provides an EF1 orientation decision and construction algorithm with O(|V(G)|²) time complexity
3. Complexity Separation: First proves computational complexity separation between goods and chores for the EFX orientation problem
4. Multigraph Hardness: Proves NP-completeness of EF1 and EFX orientation problems on multigraphs
5. Theoretical Framework: Establishes a complete reduction chain from EFX0-ORIENTATION to 2SAT

Methodology Details

Task Definition

Input: Graph G=(V(G), E(G)) and utility function set u Output: An orientation satisfying EF1 or EFX0 conditions, or determine that none exists Constraints:

• Utility functions are monotone decreasing: ui(S) ≤ ui(T) when T ⊆ S
• Marginal utility constraint: utility of non-adjacent edges is 0

Core Definitions

EF1 Definition: An allocation π is EF1 if and only if for every pair of agents i≠j, there exists an edge e∈πi such that ui(πi{e}) ≥ ui(πj)

EFX0 Definition: An allocation π is EFX0 if and only if no agent strongly envies another agent

Algorithm Architecture

The paper proposes a three-layer nested algorithm architecture:

EFX0-ORIENTATION → EFX0-ORIENTATION-OBJECTIVE → PD-VERTEX-COVER → 2SAT

1. EF1 Orientation Algorithm

Core Insight (Proposition 1): An orientation π of graph G is EF1 if and only if each vertex i receives at most one edge with negative utility.

Algorithm Flow:

1. Use Proposition 2 to convert all zero-utility edges to negative-utility edges
2. Check whether each connected component K satisfies |E(K)| ≤ |V(K)|
3. If satisfied, use Observation 3 to construct an orientation with in-degree at most 1
4. Time Complexity: O(|V(G)|²)

2. EFX0 Orientation Algorithm

FINDEFXORIENTATION (Algorithm 3):

• Input: EFX0-ORIENTATION instance (G,u)
• Output: EFX0 orientation or false

Key Steps:

1. Edge Subdivision: Replace non-objective edge eij with new vertex k and two new edges eik, ejk
2. Objective Instance Construction: Transform into EFX0-ORIENTATION-OBJECTIVE instance
3. Call Subalgorithm: Use FINDEFXORIENTOBJ to solve

FINDEFXORIENTOBJ (Algorithm 2):

• Core Insight (Proposition 5): An orientation of an objective instance is EFX0 if and only if each vertex either receives exactly one edge or receives only dummy edges

Algorithm Flow:

1. Find all negative connected components K
2. Check whether each K contains ≤|V(K)| negative edges
3. Construct PD-VERTEX-COVER instance (H,P,D)
4. Call FINDPDVERTEXCOVER to solve

FINDPDVERTEXCOVER (Algorithm 1):

• Reduction Target: Reduce PD-VERTEX-COVER to 2SAT
• Construction Method:
  • Variables: Each vertex i corresponds to a boolean variable xi
  • Constraints: Three types of clauses ensure vertex cover and constraint conditions

Technical Innovations

1. Complexity Separation Discovery: First proves the essential difference between goods and chores
2. Multi-layer Reduction Design: Clever three-layer nested reduction structure
3. Graph-Theoretic Insights: Transforms fairness conditions into pure graph-theoretic properties
4. Edge Subdivision Technique: Uniformly handles objective and non-objective edges through edge subdivision

Experimental Setup

Theoretical Analysis Framework

This paper is primarily theoretical work, verifying algorithm correctness and complexity through mathematical proofs:

1. Correctness Proofs: Each algorithm has complete correctness proofs
2. Complexity Analysis: Detailed time complexity analysis
3. Reduction Verification: Proves equivalence of each layer of reduction

Complexity Comparison

• EF1 Orientation: O(|V(G)|²) vs. no previously known algorithm
• EFX0 Orientation: O(|V(G)|⁴) vs. Zhou et al.'s conjecture of NP-completeness
• Multigraphs: Proves NP-completeness, contrasting with simple graphs

Experimental Results

Main Theoretical Results

1. Theorem 9: There exists an O(|V(G)|⁴) time algorithm to determine whether a chore graph has an EFX0 orientation and construct one
2. Proposition 1: Graph-theoretic characterization of EF1 orientation
3. Proposition 5: Graph-theoretic characterization of EFX0 orientation for objective instances
4. Theorem 10: NP-completeness of EF1/EFX0 orientation for multigraphs
5. Theorem 12: NP-completeness of EF1 orientation for multigraphs without self-loops

Complexity Separation Proof

Goods vs. Chores Comparison:

• Goods: EFX orientation decision is NP-complete (Christodoulou et al., EC 2023)
• Chores: EFX0 orientation decision is polynomial-time solvable (this paper)

Simple Graphs vs. Multigraphs Comparison:

• Simple Graphs: Both EF1 and EFX0 are polynomial-time solvable
• Multigraphs: Both EF1 and EFX0 are NP-complete

Algorithm Efficiency Analysis

1. EF1 Algorithm: O(|V(G)|²), with main overhead in BFS and orientation construction
2. EFX0 Algorithm: O(|V(G)|⁴), with bottleneck in graph size after edge subdivision
3. 2SAT Solving: Utilizes the linear-time algorithm of Aspvall et al.

Related Work

Fair Division Theory

1. EFX Existence: Procaccia termed it "the most mysterious problem"
2. Restrictive Results: Special cases including identical utility functions, lexicographic preferences, and three agents
3. Graph Instances: Graph model introduced by Christodoulou et al.

Complexity Theory

1. Goods Case: NP-completeness of EFX orientation
2. Mixed Case: Zhou et al.'s results on mixed goods/chores
3. Multigraphs: Various positive and negative results

Algorithm Design

1. Reduction Techniques: Reductions from graph problems to SAT
2. Graph-Theoretic Tools: Vertex cover, connectivity analysis
3. Orientation Algorithms: BFS-based construction methods

Conclusions and Discussion

Main Conclusions

1. Conjecture Refutation: Zhou et al.'s NP-completeness conjecture is incorrect
2. Algorithm Contributions: Provides practical polynomial-time algorithms
3. Theoretical Insights: Reveals the essential difference between goods and chores
4. Complete Picture: Provides a complete complexity characterization of chore allocation problems on simple graphs

Limitations

1. Multigraph Hardness: The multigraph case remains NP-complete
2. Constant Factors: O(|V(G)|⁴) complexity may be high in practice
3. Utility Function Restrictions: Requires satisfaction of monotonicity assumptions
4. Self-Loop Handling: Although self-loops are supported, they increase algorithm complexity

Future Directions

1. Algorithm Optimization: Reduce the time complexity of the EFX0 algorithm
2. Multigraph Algorithms: Find special tractable cases for multigraphs
3. Approximation Algorithms: Approximation schemes when exact algorithms are infeasible
4. Practical Applications: Apply theoretical results to real allocation scenarios

In-Depth Evaluation

Strengths

1. Theoretical Breakthrough:
   • Resolves important open problems and conjectures
   • Discovers fundamental differences between goods and chores
   • Provides complete complexity characterization
2. Technical Innovation:
   • Clever multi-layer reduction design
   • Transforms fairness conditions into pure graph-theoretic properties
   • Innovative application of edge subdivision technique
3. Algorithm Quality:
   • Provides practically usable polynomial-time algorithms
   • Algorithms have strong theoretical guarantees
   • Complexity analysis is detailed and accurate
4. Writing Quality:
   • Clear paper structure with rigorous logic
   • Complete and detailed proofs
   • Comprehensive related work review

Weaknesses

1. Practical Efficiency:
   • O(|V(G)|⁴) complexity may be slow on large-scale graphs
   • Lacks experimental verification of actual running times
2. Applicable Scope:
   • Multigraph case remains difficult
   • Utility functions must satisfy specific assumptions
   • Does not consider online or dynamic scenarios
3. Algorithm Constants:
   • Theoretical complexity analysis does not account for constant factors
   • Actual implementation may have significant overhead

Impact

1. Theoretical Contribution:
   • Provides important insights for fair division theory
   • Advances computational complexity theory
   • Establishes foundation for subsequent research
2. Practical Value:
   • Algorithms applicable to real task allocation problems
   • Provides theoretical guidance for system design
   • Assists in designing fairness mechanisms
3. Reproducibility:
   • Algorithm descriptions are detailed and clear
   • Theoretical proofs are complete
   • Easy to implement and verify

Applicable Scenarios

1. Task Allocation: Distribution of negative-utility work such as food delivery and cleaning tasks
2. Resource Scheduling: Fair scheduling problems under constraints
3. Mechanism Design: Automated systems requiring fairness considerations
4. Theoretical Research: Serves as foundational tool for other fair allocation problems

References

The paper cites important literature in the field, including:

• Zhou et al. (IJCAI 2024): EFX allocation for mixed goods/chores
• Christodoulou et al. (EC 2023): Complexity of EFX orientation for goods graphs
• Procaccia (2020): Assessment of EFX problem importance
• Classical results in computational complexity theory

Overall Assessment: This is a high-quality theoretical computer science paper that resolves important open problems and provides valuable algorithms and theoretical insights. The paper's main contribution lies in revealing the fundamental computational complexity difference between goods and chores, and providing practical polynomial-time algorithms. While there is room for improvement in practical efficiency and applicable scope, its theoretical value and academic impact are significant.