Fair division with prioritized agents

Xiaolin Bu, Zihao Li, Shengxin Liu, Jiaxin Song, Biaoshuai Tao, Ziqi YuInformation 2026 · DOI

TL;DR

This paper introduces a new fairness notion, EFPRIOR, for dividing indivisible items, which extends envy-freeness up to one item (EF1) by prioritizing certain agents. They develop polynomial-time algorithms to compute EFPRIOR allocations, particularly for general valuations where only a partial allocation is guaranteed.

What Problem Does This Paper Address?

The fair division of indivisible items is a classic problem. While envy-freeness (where no agent prefers another's bundle) is a desirable property, it's often impossible to achieve with indivisible items. A common relaxation is envy-freeness up to one item (EF1), where an agent might envy another, but only by at most one item. However, EF1 doesn't account for situations where some agents might inherently deserve priority (e.g., underrepresented groups, or those who were disadvantaged in a previous allocation). This paper addresses the challenge of incorporating such priorities into fair division, proposing a new fairness criterion, EFPRIOR, that ensures EF1 for everyone while also guaranteeing strict envy-freeness from a set of prioritized agents to non-prioritized agents.

Methods

The paper introduces the EFPRIOR (Envy-Freeness with Prioritized Agents) notion. An EFPRIOR allocation is an EF1 allocation where, in addition, every prioritized agent P does not envy any non-prioritized agent Q.

For additive valuations, a simple round-robin algorithm suffices to achieve EFPRIOR.

For general valuations, the core contribution is a polynomial-time algorithm that computes a partial EFPRIOR allocation. This algorithm builds upon techniques for computing EFX (envy-freeness up to any item) allocations, specifically adapting an algorithm by Chaudhury et al. [2021b]. The key innovation lies in a novel approach to exchange agent bundles with the pool of unallocated items, enabling polynomial-time computation. The algorithm iteratively updates allocations and uses a cycle-elimination procedure on an "envy-graph" to maintain fairness properties.

The paper also presents polynomial-time algorithms for two special cases of general valuations:

  1. When all prioritized agents have identical valuations.
  2. When all non-prioritized agents have identical valuations.

These special cases provide insights and building blocks for the general algorithm.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Prioritization as a Secondary Fairness Goal: The paper frames prioritization not as a violation of fairness, but as a mechanism to break ties or provide a justifiable advantage when perfect fairness is unattainable. This is crucial for real-world applications where certain groups might need preferential treatment.
  • EFPRIOR as a Stronger, Yet Achievable, Notion: EFPRIOR is a strict improvement over EF1 when priorities matter. The paper demonstrates its existence and computability, at least partially, even in complex general valuation settings.
  • The Power of Partial Allocations: For general valuations, achieving a complete EFPRIOR allocation is hard. The paper's success in finding a partial EFPRIOR allocation with a small, bounded pool of unallocated items is a significant step, suggesting that most items can still be distributed fairly while respecting priorities.
  • Envy-Graph as a Central Tool: The envy-graph, a standard tool in fair division literature, is adapted and extended to handle the complexities of prioritized agents and partial allocations. The cycle-elimination procedure on this graph is key to maintaining fairness.
  • Bridging Theory and Practice: The paper connects theoretical fairness notions to practical scenarios like university admissions or resource allocation in companies, where prioritization is a common practice.

Key Results

  • Existence and Polynomial-Time Computation:
    • EFPRIOR allocations are guaranteed to exist for additive valuations and can be computed in polynomial time via a round-robin algorithm.
  • For general valuations, a partial EFPRIOR allocation always exists, where the number of unallocated items is less than the size of both the prioritized and non-prioritized sets, and these items have minimal value to all agents. A polynomial-time algorithm is provided for this.
  • Polynomial-time algorithms are presented for EFPRIOR in two special cases: identical valuations within the prioritized set, or identical valuations within the non-prioritized set.
  • Tractability for Small Numbers of Agents: Corollary 3.1 states that EFPRIOR allocations can be found in polynomial time when |P|=1, |Q|=1, or |N|≤3.

Limitations and Future Work

  • Complete EFPRIOR Allocation for General Valuations: The paper explicitly states that the existence and computational tractability of a complete EFPRIOR allocation in the general setting remain open problems. This is identified as a major future research direction.
  • Mixed Divisible and Indivisible Items: The authors suggest extending the EFPRIOR notion to settings involving both divisible and indivisible resources, which is an active area of research.
  • Algorithm Complexity: While the algorithm for partial EFPRIOR allocations is polynomial, its complexity is O(n²m · max(n², m)), which could be further optimized.

Summary updated

BibTeX
@inproceedings{bu2026fair,
  author = {Xiaolin Bu and Zihao Li and Shengxin Liu and Jiaxin Song and Biaoshuai Tao and Ziqi Yu},
  title = {{Fair division with prioritized agents}},
  booktitle = {Information},
  year = {2026},
  doi = {10.1016/j.ic.2026.105407},
}
Figure