On Fair Division under Heterogeneous Matroid Constraints

Amitay Dror, Michal Feldman, Erel Segal-HaleviAAAI 2021 · DOI

Introduction

Fair division of indivisible items is a fundamental problem in multi-agent systems. While the standard "Envy-Free up to One Item" (EF1) guarantee is well-understood for unconstrained settings, real-world applications—such as assigning medical shifts or peer-review tasks—often involve strict feasibility constraints. This paper investigates the challenge of achieving fair allocations when agents have both heterogeneous preferences and heterogeneous constraints, specifically modeled as matroids.

The Challenge of Heterogeneity

In many practical scenarios, agents cannot accept arbitrary bundles. For instance, a doctor might be limited by a maximum number of night shifts, or a reviewer might have a cap on papers per sub-field. Previous research often assumed homogeneous constraints (all agents have the same limits) or allowed for "free disposal." However, in "complete allocation" settings where every item must be assigned, these assumptions fail.

The core difficulty lies in the breakdown of the classic envy-cycle elimination algorithm. In the presence of heterogeneous constraints, rotating bundles between agents in an envy cycle (e.g., A envies B, B envies C, C envies A) may result in an agent receiving a bundle they are legally prohibited from holding.

Defining Fairness: F-EF1

To address these constraints, the authors utilize the notion of Feasible Envy-Freeness up to One Item (F-EF1). Under F-EF1, Agent A is said to envy Agent B only if A prefers B's bundle even after B's bundle is reduced to the most valuable subset that Agent A could feasibly hold, minus at most one item. This definition accounts for the physical or legal impossibility of an agent holding certain combinations of items.

Algorithmic Frameworks

The paper introduces three primary algorithmic approaches to navigate these constraints:

  1. Iterated Priority Matching: Designed for $n$ agents with binary valuations (0/1 preferences) and partition matroids. This method uses bipartite matching in successive rounds. By maintaining a topological sort of the envy graph to determine matching priority, the algorithm ensures the graph remains a Directed Acyclic Graph (DAG), preventing envy cycles from forming.
  2. Round Robin Squared ($RR^2$): A specialized approach for 2 agents with general additive preferences. It employs a nested round-robin structure: the first layer determines the category of items, and the second layer selects the specific item within that category, ensuring feasibility for both agents.
  3. Iterated Swaps: Targeted at 3 agents with binary valuations and base-orderable matroids. This framework starts with a socially optimal (maximum weight) allocation and iteratively performs "smart" transfers or swaps to mitigate envy without compromising overall welfare.

Key Results

The authors map the frontier of feasibility for F-EF1 allocations. Their findings include several polynomial-time algorithms for partition matroids and broader classes like base-orderable matroids.

Summary of results for fair division under matroid constraints.

As shown in the table above, the paper provides positive results for $n$ agents with binary valuations and 2 agents with general valuations under partition matroids. It also extends results to "Beyond Partition" settings, such as base-orderable matroids for a small number of agents. Conversely, the paper identifies impossibility results, showing that F-EF1 allocations may not exist if agents have different item categories or if constraints exceed the complexity of matroids.

Conclusion and Future Directions

This work significantly advances the understanding of fair division under complex constraints. While it provides robust solutions for binary valuations and the two-agent general case, the existence of complete F-EF1 allocations for $n \geq 3$ agents with general additive valuations remains a major open question. Future research may also look to extend the base-orderable matroid results to a larger number of agents.

Summary updated

BibTeX
@inproceedings{dror2021fair,
  author = {Amitay Dror and Michal Feldman and Erel Segal-Halevi},
  title = {{On Fair Division under Heterogeneous Matroid Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16670},
}
Figure