---
title: "Guaranteeing Maximin Shares: Some Agents Left Behind"
authors:
  - "Hadi Hosseini"
  - "Andrew Searns"
doi: "10.24963/ijcai.2021/34"
url: "https://ijcai.org/proceedings/2021/34"
pdf: "https://ijcai.org/proceedings/2021/0034.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "238-244"
track: "Main Track"
keywords:
  - "Agent-based and Multi-agent Systems: Computational Social Choice"
  - "Agent-based and Multi-agent Systems: Resource Allocation"
  - "Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems"
---

# Guaranteeing Maximin Shares: Some Agents Left Behind

Hadi Hosseini, Andrew Searns

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 238-244. DOI: [10.24963/ijcai.2021/34](https://doi.org/10.24963/ijcai.2021/34)

## Abstract

The maximin share (MMS) guarantee is a desirable fairness notion for allocating indivisible goods. While MMS allocations do not always exist, several approximation techniques have been developed to ensure that all agents receive a fraction of their maximin share. We focus on an alternative approximation notion, based on the population of agents, that seeks to guarantee MMS for a fraction of agents. We show that no optimal approximation algorithm can satisfy more than a constant number of agents, and discuss the existence and computation of MMS for all but one agent and its relation to approximate MMS guarantees. We then prove the existence of allocations that guarantee MMS for 2/3 of agents, and devise a polynomial time algorithm that achieves this bound for up to nine agents.  A key implication of our result is the existence of allocations that guarantee the value that an agent receives by partitioning the goods into 3n/2 bundles, improving the best known guarantee when goods are partitioned into 2n-2 bundles. Finally, we provide empirical experiments using synthetic data.