Ordinal Maximin Share Approximation for Goods (Extended Abstract)

Hadi Hosseini, Andrew Searns, Erel Segal-Halevi

IJCAI 2023 pp. 6894-6899

doi:10.24963/IJCAI.2023/778 /ijcai/2023/hosseini2023ijcai-ordinal/

Abstract

In fair division of indivisible goods, l-out-of-d maximin share (MMS) is the value that an agent can guarantee by partitioning the goods into d bundles and choosing the l least preferred bundles. Most existing works aim to guarantee to all agents a constant fraction of their 1-out-of-n MMS. But this guarantee is sensitive to small perturbation in agents' cardinal valuations. We consider a more robust approximation notion, which depends only on the agents' ordinal rankings of bundles. We prove the existence of l-out-of-floor((l+1/2)n) MMS allocations of goods for any integer l greater than or equal to 1, and present a polynomial-time algorithm that finds a 1-out-of-ceiling(3n/2) MMS allocation when l = 1. We further develop an algorithm that provides a weaker ordinal approximation to MMS for any l > 1.

PDF IJCAI Semantic Scholar

Cite

Text

Hosseini et al. "Ordinal Maximin Share Approximation for Goods (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2023. doi:10.24963/IJCAI.2023/778

Markdown

[Hosseini et al. "Ordinal Maximin Share Approximation for Goods (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2023.](https://mlanthology.org/ijcai/2023/hosseini2023ijcai-ordinal/) doi:10.24963/IJCAI.2023/778

BibTeX

@inproceedings{hosseini2023ijcai-ordinal,
  title     = {{Ordinal Maximin Share Approximation for Goods (Extended Abstract)}},
  author    = {Hosseini, Hadi and Searns, Andrew and Segal-Halevi, Erel},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2023},
  pages     = {6894-6899},
  doi       = {10.24963/IJCAI.2023/778},
  url       = {https://mlanthology.org/ijcai/2023/hosseini2023ijcai-ordinal/}
}