Ordinal Maximin Share Approximation for Chores

Hadi Hosseini, Andrew Searns, Erel Segal-Halevi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

We study the problem of fairly allocating a set of m indivisible chores (items with non-positive value) to n agents. We consider the desirable fairness notion of 1-out-of-d maximin share (MMS)-the minimum value that an agent can guarantee by partitioning items into d bundles and receiving the least valued bundle-and focus on ordinal approximation of MMS that aims at finding the largest d ≤ n for which 1-out-of-d MMS allocation exists. Our main contribution is a polynomial-time algorithm for 1-out-of-⌊2n/3⌋ MMS allocation, and a proof of existence of 1-out-of-⌊3n/4⌋ MMS allocation of chores. Furthermore, we show how to use recently-developed algorithms for bin-packing to approximate the latter bound up to a logarithmic factor in polynomial time.

Original languageEnglish (US)
Title of host publicationInternational Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages597-605
Number of pages9
ISBN (Electronic)9781713854333
StatePublished - 2022
Event21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022 - Auckland, Virtual, New Zealand
Duration: May 9 2022May 13 2022

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume1
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022
Country/TerritoryNew Zealand
CityAuckland, Virtual
Period5/9/225/13/22

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering

Fingerprint

Dive into the research topics of 'Ordinal Maximin Share Approximation for Chores'. Together they form a unique fingerprint.

Cite this