Fair Division with Allocator's Preference

Xiaolin Bu, Zihao Li, Shengxin Liu, Jiaxin Song, Biaoshuai Tao

TL;DR

This paper introduces a new model for fair division of indivisible resources that accounts for the preferences of an "allocator" (e.g., a government or parent) in addition to the agents receiving the resources. The authors investigate how to achieve allocations that are fair to both agents and the allocator, and explore the complexity of maximizing the allocator's efficiency while ensuring agent fairness, providing both existence results and inapproximability bounds.

What Problem Does This Paper Address?

The classic fair division problem focuses on allocating resources (like goods, tasks, or even course enrollments) among agents, ensuring that the allocation is "fair" according to criteria like envy-freeness (no agent prefers another's bundle) or proportionality (each agent gets at least 1/n of their value). However, many real-world scenarios involve a central entity – an allocator – who also has preferences about how resources are distributed. Think of a government allocating educational resources, a parent dividing an inheritance, or a company assigning projects. This allocator might care not only about the total value generated but also about who gets what. This paper bridges this gap by introducing an "allocator's preference" into the fair division framework, leading to the concept of "doubly fair" allocations that satisfy fairness criteria from both the agents' and the allocator's perspectives.

Methods

The paper tackles two main problems:

  1. Existence of Doubly Fair Allocations: The authors introduce "doubly EF-c" and "doubly PROP-c" notions, extending standard fairness criteria to include the allocator. They prove existence results for these doubly fair allocations under various conditions (e.g., monotone, additive, or binary valuations) using sophisticated mathematical tools. A key technique involves constructing and analyzing generalized Kneser graphs and their chromatic numbers, as well as topological arguments related to simplicial complexes. For specific cases like two agents with additive utilities, they develop constructive polynomial-time algorithms.
  2. Maximizing Allocator's Efficiency: This problem focuses on finding an allocation that maximizes the allocator's total utility, subject to the constraint that the allocation is fair to the agents (and the allocator). The authors provide a landscape of results, including NP-hardness proofs and inapproximability bounds, showing how difficult it is to achieve optimal efficiency. They also present polynomial-time approximation algorithms and exact algorithms for specific settings (e.g., binary valuations, constant number of agents). Techniques here include reductions from known hard problems (like partition and maximum independent set) and linear programming formulations.

Datasets

Not discussed in the paper. The paper deals with theoretical models and algorithmic analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Allocator Matters: The core insight is that ignoring the allocator's preferences can lead to allocations that are neither efficient nor perceived as fair by the resource owner, even if agents are satisfied.
  • Doubly Fair is Harder: Achieving fairness for both agents and an allocator is more challenging than standard fair division. The paper introduces new formalisms (doubly EF-c, doubly PROP-c) to capture this.
  • Graph Theory to the Rescue: The existence proofs for doubly fair allocations heavily rely on advanced graph theory, specifically the chromatic numbers of generalized Kneser graphs. This is a novel application of these tools to fair division.
  • Efficiency vs. Fairness Trade-off: When maximizing the allocator's efficiency, there's a significant trade-off with fairness. The paper shows that achieving high efficiency while maintaining fairness is often computationally intractable, leading to strong inapproximability results.
  • Constructive vs. Non-Constructive: While some existence proofs are non-constructive (proving something exists without showing how to find it), the paper also provides polynomial-time algorithms for specific cases, demonstrating practical approaches.

Key Results

  • Existence Guarantees:
    • A doubly EF-1 allocation always exists for two agents with general monotone utilities.
  • For additive utilities, doubly EF-1 allocations are guaranteed for two agents and can be found in polynomial time.
  • A doubly PROP-O(log n) allocation always exists for n agents with additive utilities.
  • A doubly PROP-2 allocation always exists for personalized bi-valued valuations.
  • Complexity and Approximability:
    • Maximizing allocator's efficiency subject to EF-c for two agents is NP-hard to approximate within a factor of 2.
  • For a general number of agents, maximizing efficiency subject to EF-c is NP-hard to approximate within factors like $m^{1-\epsilon}$ or $n^{1/2-\epsilon}$.
  • For binary valuations, the problem becomes tractable for certain fairness constraints (e.g., EF-c with constant agents, PROP-c with general agents).
  • Polynomial-time algorithms are provided for finding doubly EF-1 allocations (identical allocator utilities) and doubly PROP-2 allocations (personalized bi-valued utilities).

Limitations and Future Work

  • Non-Constructive Proofs: Some existence proofs (especially for general monotone utilities) are non-constructive, meaning they prove an allocation exists but don't provide an algorithm to find it.
  • Lower Bounds on c: The paper doesn't determine the minimum c for which a doubly EF-c/PROP-c allocation is always guaranteed to exist, especially for binary valuations. Finding a non-existence counterexample for doubly EF-1 or PROP-1 is an open challenge.
  • General Valuations: Extending results to more complex valuation functions (e.g., submodular) is an open area.
  • Multi-Dimensional Preferences: The paper focuses on two sets of preferences (agents and allocator). Generalizing to t valuation profiles (multiple allocators or multi-dimensional agent preferences) is a promising future direction.
  • Algorithmic Techniques: The authors note that their current techniques (Kneser graphs, linear programming) have limitations, particularly in analyzing bi-partitions and providing constructive proofs for all cases. Developing new techniques to overcome these limitations and close the gap between upper and lower bounds on c is an important future task.

Summary updated

Abstract

We consider the problem of fairly allocating indivisible resources to agents, which has been studied for years. Most previous work focuses on fairness and/or efficiency among agents given agents’ preferences. However, besides the agents, the allocator as the resource owner may also be involved in many real-world scenarios (e.g., government resource allocation, heritage division, company personnel assignment, etc.). The allocator has the inclination to obtain a fair or efficient allocation based on her own preference over the items and to whom each item is allocated. In this paper, we propose a new model and focus on the following two problems concerning the allocator’s fairness and efficiency: We consider the two fundamental fairness criteria: envy-freeness and proportionality. For the first problem, we study the existence of an allocation that is envy-free up to c goods (EF-c) or proportional up to c goods (PROP-c) from both the agents’ and the allocator’s perspectives, in which such an allocation is called doubly EF-c or doubly PROP-c respectively. When the allocator’s utility depends exclusively on the items (but not to whom an item is allocated), we prove that a doubly EF-1 allocation always exists. For the general setting where the allocator has a preference over the items and to whom each item is allocated, we prove that a doubly EF-1 allocation always exists for two agents, a doubly PROP-2 allocation always exists for binary valuations, and a doubly PROP- $$O(\log n)$$ allocation always exists in general. For the second problem, we provide various (in)approximability results in which the gaps between approximation and inapproximation ratios are asymptotically closed under most settings. Most of our results are based on some novel technical tools including the chromatic numbers of the Kneser graphs and linear programming-based analysis.
BibTeX
@inproceedings{bu2023fair,
  author = {Xiaolin Bu and Zihao Li and Shengxin Liu and Jiaxin Song and Biaoshuai Tao},
  title = {{Fair Division with Allocator's Preference}},
  booktitle = {WINE},
  year = {2023},
  url = {https://openreview.net/forum?id=LyBDR1tRLL7},
}
Figure