Improved MMS Approximations for Few Agent Types

Parnian Shahkar, Jugal GargIJCAI 2025 · DOI

TL;DR

This paper tackles the challenge of fairly dividing indivisible goods among agents with different preferences, specifically when agents can be grouped into a small number of types (2 or 3). The authors introduce novel algorithms that achieve better approximation guarantees for "maximin share" (MMS) fairness in these scenarios, improving upon existing methods that offer a weaker guarantee for general cases.

What Problem Does This Paper Address?

Fair division of resources is a classic problem. A key fairness criterion is the "maximin share" (MMS), which ensures each agent receives a bundle of goods at least as valuable as the worst bundle they could guarantee for themselves. While MMS allocations are always guaranteed to exist when all agents have identical preferences (a single "type"), this guarantee breaks down when there are three or more agents with distinct preferences. This has led researchers to focus on approximate MMS allocations, where agents receive at least a fraction ($\alpha$) of their MMS value. The current best general guarantee for approximate MMS allocations is $\frac{3}{4}$-MMS. This paper investigates whether we can achieve better approximation guarantees when the number of agent types is small (specifically, two or three), a common scenario in real-world applications.

Methods

The core innovation of this paper lies in leveraging the structure of instances with a small number of agent types. The authors build upon existing techniques like "ordering" (sorting items by value for each agent) and "normalization" (rescaling valuations so each agent's MMS value is 1). Their key strategy involves:

  • Focusing on the Majority Type: They first construct an allocation based on the preferences of the "majority type" (the type with the most agents). This involves creating "bags" of items, aiming for each bag to contain exactly one "high-valued" item for that majority type.
  • Adapting for Other Types: The allocation derived from the majority type is then adapted to accommodate the preferences of the minority types. This involves carefully analyzing how the minority types value the bags created for the majority type.
  • Case Analysis and Bag Manipulation: For two types, they devise an algorithm that assigns bags to the majority type and then attempts to assign the remaining bags to the minority type. If the minority type cannot claim all remaining bags, items are pooled and reallocated. For three types, a more intricate case analysis is performed based on how the two minority types value the bags. This involves categorizing bags into four classes and using specialized algorithms (including a novel Algorithm 5) to handle complex scenarios, particularly when many bags are undesirable to the minority types.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Exploiting Type Structure is Key: The paper demonstrates that by specifically considering the limited number of agent types, significant improvements in fairness guarantees are possible beyond the general $\frac{3}{4}$-MMS bound.
  • Majority Type as a Foundation: Using the majority type's preferences as a starting point for allocation simplifies the problem and provides a robust base for subsequent adjustments.
  • The Power of Case Analysis: For three types, the problem becomes significantly more complex, requiring a detailed breakdown into different scenarios based on how minority types value the allocated bags. This highlights the combinatorial nature of fair division problems.
  • Novel Bag-Filling for Complex Scenarios: Algorithm 5, designed for a specific challenging case in the 3-type scenario, introduces a new approach to bundle items when multiple types have low valuations for them, ensuring a fair outcome.

Key Results

The paper presents the following main results:

  • 2-Type Agents: An algorithm is presented that guarantees a $\frac{2}{3}$-MMS allocation for instances with two agent types. This is an improvement over the general $\frac{3}{4}$-MMS bound.
  • 3-Type Agents: An algorithm is presented that guarantees a $\frac{16}{21}$-MMS allocation for instances with three agent types. This is also an improvement over the general bound.

Limitations and Future Work

  • Scalability: The authors acknowledge that their approach faces scalability challenges as the number of agent types increases, with the case analysis becoming significantly more intricate.
  • Generalization to More Types: A key open question is whether uniform improvements can be achieved for any $k < n$ types, with guarantees that decrease as $k$ increases, surpassing the current $\frac{3}{4}$-MMS bound. The paper's focus on 2 and 3 types is a step towards this broader goal.
  • Uniform Improvements: The paper poses the question of whether uniform improvements can be achieved for any $k < n$ types, with guarantees that decrease as $k$ increases, surpassing the current $\frac{3}{4}$-MMS bound.

Summary updated

BibTeX
@inproceedings{shahkar2025improved,
  author = {Parnian Shahkar and Jugal Garg},
  title = {{Improved MMS Approximations for Few Agent Types}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/452},
}
Figure