
We study the problem of fairly allocating a set of $m$ indivisible chores (i.e. 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 selecting the least valued bundle---and focus on ordinal approximation of MMS that aims at finding the largest $d$ for which $1$-out-of-$d$ MMS exists. Our main theoretical contribution is showing the existence of $1$-out-of-$\lfloor\frac{3n}{4}\rfloor$ MMS allocations and proving that $1$-out-of-$\lfloor\frac{2n}{3}\rfloor$ MMS allocations of chores can be computed in polynomial time. Furthermore, we show that practical polynomial-time algorithms exist for approximating $1$-out-of-$\lfloor\frac{3n}{4}\rfloor$ MMS bound for chores. This is in contrast to computing allocations that guarantee a fraction of MMS to each agent, where only a polynomial-time approximation scheme (PTAS) with run-time exponential in the approximation accuracy $1/\epsilon$ is known.

Ordinal Maximin Share Approximation for Chores

Oral Session 2B1-1

technical paper

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

The AAMAS conference series was initiated in 2002 in Bologna, Italy as a joint event comprising the 6th International Conference on Autonomous Agents (AA), the 5th International Conference on Multiagent Systems (ICMAS), and the 9th International Workshop on Agent Theories, Architectures, and Languages (ATAL).

Subsequent AAMAS conferences have been held in Melbourne, Australia (July 2003), New York City, NY, USA (July 2004), Utrecht, The Netherlands (July 2005), Hakodate, Japan (May 2006), Honolulu, Hawaii, USA (May 2007), Estoril, Portugal (May 2008), Budapest, Hungary (May 2009), Toronto, Canada (May 2010), Taipei, Taiwan (May 2011), Valencia, Spain (June 2012), Minnesota, USA (May 2013), Paris, France (May 2014), Istanbul, Turkey (May 2015), Singapore (May 2016), São Paulo (2017) and Stockholm, Sweden (2018), Montreal (May 2019), Auckland (May 2020, Virtual), London (May 2021, Virtual).
<br>
<br>



A ticket is required to attend this event, please register using the link below:

https://aamas2022-conference.auckland.ac.nz/attending/registration/

Registration Is Required

AAMAS 2022

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

Andrew Searns

1

6

SHORT BIO

Presentations

Ordinal Maximin Share Approximation for Chores

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES