Fair and Efficient Allocation of Indivisible Mixed Manna

Basic Information

• Paper ID: 2507.03946
• Title: Fair and Efficient Allocation of Indivisible Mixed Manna
• Authors: Siddharth Barman (Indian Institute of Science), Vishwa Prakash HV (Chennai Mathematical Institute), Aditi Sethia (Indian Institute of Science), Mashbat Suzuki (UNSW Sydney)
• Classification: cs.GT (Computer Science - Game Theory)
• Publication Date: October 15, 2025 (arXiv preprint version 2)
• Paper Link: https://arxiv.org/abs/2507.03946v2

Abstract

This paper investigates the problem of fair allocation of indivisible mixed manna among agents with additive valuations. Mixed manna refers to items whose values can be positive, negative, or zero. The paper establishes theoretical guarantees that fairness (based on relaxations of envy-freeness) and Pareto efficiency can be simultaneously achieved. Specifically, the fairness guarantee is based on the concept of "envy-freeness up to k reallocations" (EFR-k): an allocation A is EFR-k if there exists a subset R of at most k items such that for each agent i, a reallocation of items in R yields an allocation A^i that is envy-free with respect to i.

Research Background and Motivation

Problem Definition

Fair allocation is a frequently encountered problem in real-world scenarios such as estate division, task assignment, boundary disputes, and debt allocation. When participating agents have personal preferences, the question of "who gets what" possesses both practical urgency and theoretical richness.

Research Challenges

1. Complexity of Mixed Manna: Unlike pure goods or chores, items in mixed manna may have different value signs for different agents, making allocation significantly more complex.
2. Trade-off Between Fairness and Efficiency: In the setting of indivisible items, traditional envy-freeness cannot be guaranteed to exist, necessitating the search for appropriate relaxation conditions.
3. Limitations of Existing Approaches:
   • For chore allocation, the existence of EF1 and Pareto optimal allocations remains unresolved even for four agents
   • For mixed manna, this problem remains open even for three agents
   • Existing market-based methods do not directly generalize when valuations are negative

Research Motivation

The paper aims to provide theoretical guarantees for fair and efficient allocation of mixed manna by introducing the EFR-k concept and developing effective computational algorithms.

Core Contributions

1. Theoretical Existence Guarantee: Proves that for mixed manna allocation among n agents with additive valuations, there always exists an allocation that is both EFR-(n-1) and Pareto optimal.
2. Algorithmic Computability: When the number of agents n is fixed, an EFR-(n-1) and Pareto optimal allocation can be computed in polynomial time.
3. Independent EFR Results:
   • EFR-(n-1) mixed manna allocations can be computed in polynomial time
   • When all items are goods, EFR-⌊n/2⌋ allocations exist and can be efficiently computed
4. Tightness Results:
   • For chores, the (n-1) bound is tight
   • For goods, the ⌊n/2⌋ bound is tight
5. Technical Innovation: First application of the Knaster-Kuratowski-Mazurkiewicz (KKM) theorem in discrete fair allocation.

Methodology Details

Task Definition

Input:

• n agents, denoted n = {1,...,n}
• m indivisible items, denoted m = {1,...,m}
• Additive valuation functions {vi}i∈n, where vi(t) ∈ ℝ represents agent i's valuation of item t

Output: Allocation A = (A1,...,An), where Ai ⊆ m is the set of items allocated to agent i

Objective: Find an allocation simultaneously satisfying EFR-k and Pareto optimality

Core Concepts

EFR-k Definition

An allocation A is EFR-k if and only if there exists a subset R ⊆ m of size at most k such that for each agent i, a reallocation of items in R yields an allocation A^i that is envy-free with respect to i.

Key Technical Components

1. Valuation Perturbation: To obtain non-degenerate conditions, additive perturbations are applied to given valuations:

   v̄i(t) = vi(t) - εi,t
   

   
   where εi,t is uniformly drawn from (0,ε).
2. Weight Offset: For each weight vector w ∈ Δn-1, each component is offset by parameter η > 0:

   SWη(A,w) := Σi∈[n] (wi + η)v̄i(Ai)
   

3. KKM Cover: For each agent i, define the set

   Ci := {w ∈ Δn-1 : there exists allocation Xi ∈ Oη(w) such that i is envy-free under Xi}
   

Main Algorithm Framework

Proof Strategy for Theorem 3.1

1. Construct Perturbed Valuations: Ensure non-degeneracy properties
2. Define KKM Cover: Construct a closed set family {Ci} satisfying KKM conditions
3. Apply KKM Theorem: Obtain intersection w* ∈ ∩i Ci
4. Counting Argument: Prove that the size of reallocation set R is at most n-1

Algorithm 1: Conflict-Aware Sequential Selection for Goods

For pure goods, a round-robin based algorithm is designed:

• Conflict Resolution Phase: Identify items most preferred by multiple agents and add them to reallocation set R
• Selection Phase: Active agents select their most preferred items in lexicographic order

Technical Innovations

1. Novel Application of KKM Theorem: First application of the classical KKM theorem to discrete fair allocation problems, providing a completely different technical approach from existing market-based methods.
2. Perturbation Technique: Carefully designed valuation perturbations ensure non-degeneracy, making weighted social welfare maximization problems well-behaved.
3. Counting Argument: Utilizes acyclicity properties of bipartite graphs to prove size bounds on reallocation sets.

Experimental Setup

Theoretical Analysis Framework

As a theoretical paper, results are verified primarily through mathematical proofs rather than empirical experiments. The paper employs the following analytical framework:

1. Existence Proofs: Use KKM theorem to prove existence of EFR-(n-1) and PO allocations
2. Tightness Analysis: Construct counterexamples to prove tightness of bounds
3. Algorithm Complexity: Analyze time complexity of algorithms

Complexity Analysis

• Fixed Number of Agents: EFR-(n-1) and PO allocations can be computed in m^poly(n) time
• General Case: EFR-(n-1) allocations can be computed in polynomial time
• Goods Case: EFR-⌊n/2⌋ allocations can be computed in polynomial time

Experimental Results

Main Theoretical Results

Theorem 3.1 (Main Existence Result)

Every fair allocation instance with indivisible mixed manna and additive valuations admits an allocation that is both EFR-(n-1) and Pareto optimal.

Theorem 4.1 (Computability Result)

For mixed manna allocation instances with a fixed number of agents, an EFR-(n-1) and Pareto optimal allocation can be computed in polynomial time.

Theorem 5.1 (Independent EFR Result)

For fair allocation instances with mixed manna and additive valuations, there always exists an allocation that is both EFR-(n-1) and EF1, computable in polynomial time.

Theorem 5.4 (Improved Bound for Goods)

For fair allocation instances with pure goods, Algorithm 1 computes an EFR-⌊n/2⌋ allocation in polynomial time.

Tightness Results

Theorem 5.2 (Tightness for Chores)

There exist chore allocation instances that do not admit an EFR-(n-2) allocation, proving the (n-1) bound is tight.

Theorem 5.5 (Tightness for Goods)

There exist goods allocation instances that do not admit an EFR-(⌊n/2⌋-1) allocation, proving the ⌊n/2⌋ bound is tight.

Computational Complexity Results

Theorem A.1 (Complexity of Decision Problem)

Given an allocation A and positive integer k < n-2, determining whether A is EFR-k is NP-complete.

Related Work

Classical Fair Allocation Theory

• Divisible Case: Classical results by Varian and Weller show that envy-freeness and PO can be simultaneously achieved
• Indivisible Goods: Mature theory exists for simultaneous achievement of EF1 and PO (Nash social welfare maximization)

Challenges in Chores and Mixed Manna

• Chore Allocation: Existence of EF1 + PO remains unresolved even for four agents
• Mixed Manna: Existence of EF1 + PO for three agents remains an open problem
• Methodological Differences: No function analogous to Nash social welfare exists to guarantee EF1 for chores

Related Relaxation Concepts

• EF1: Eliminate envy by removing one item
• EFX: Eliminate envy by removing any item
• Fractional Allocation: Envy-freeness with fractional allocation of at most (n-1) items

Conclusions and Discussion

Main Conclusions

1. Theoretical Breakthrough: First to provide simultaneous guarantees of fairness and efficiency for general mixed manna settings
2. Technical Innovation: Novel application of KKM theorem in discrete fair allocation opens new research directions
3. Practical Value: Algorithmic results provide computational foundations for practical applications

Limitations

1. Bound Size: The EFR-(n-1) bound is relatively large, requiring reallocation of approximately 2 items per agent on average
2. Fixed Agent Assumption: Polynomial-time algorithms require fixed number of agents
3. Additive Valuation Restriction: Results apply only to additive valuation functions

Future Directions

1. Improved Bounds: Seek smaller reallocation sets R
2. Extended Valuation Types: Consider non-additive valuation functions
3. Practical Applications: Apply theoretical results to concrete allocation scenarios

In-Depth Evaluation

Strengths

1. Significant Theoretical Contribution: Resolves fundamental questions about fair and efficient allocation of mixed manna
2. Novel Technical Approach: Application of KKM theorem demonstrates deep mathematical insight
3. Comprehensive Results: Includes both existence and algorithmic results, upper and lower bounds
4. Rigorous Proofs: Complete mathematical derivations with careful technical details

Weaknesses

1. Limited Practical Applicability: The EFR-(n-1) bound may be too large for practical applications
2. Lack of Empirical Evaluation: As a theoretical paper, lacks performance evaluation on real data
3. Algorithm Efficiency: The m^poly(n) complexity for fixed agents may be high in practice

Impact

1. Academic Impact: Makes important contributions to fair allocation theory, expected to be widely cited
2. Methodological Value: KKM theorem application may inspire further related research
3. Practical Prospects: Provides theoretical foundation for designing practical allocation systems

Applicable Scenarios

1. Estate Division: Complex division scenarios involving both assets and liabilities
2. Task Allocation: Allocation of tasks with both attractive and unattractive components
3. Resource Management: Resource allocation problems requiring simultaneous consideration of benefits and costs

References

The paper cites important literature in fair allocation, including:

• Budish (2011): Introduction of EF1 concept
• Caragiannis et al. (2019): Relationship between Nash social welfare and EF1+PO
• Aziz et al. (2022): EF1 existence for mixed manna
• Sandomirskiy & Segal-Halevi (2022): Related results on fractional allocation

Overall Assessment: This is a high-quality theoretical paper that provides important theoretical guarantees for fair and efficient allocation of mixed manna by introducing the EFR concept and applying the KKM theorem. Despite certain limitations in practical applicability, its theoretical contributions and technical innovations represent significant progress in the field of fair allocation.