Maximin-Aware Allocations of Indivisible Chores with Symmetric and Asymmetric Agents

Maximin-Aware Allocations of Indivisible Chores with Symmetric and Asymmetric Agents

Tianze Wei, Bo Li, Minming Li

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 2897-2905. https://doi.org/10.24963/ijcai.2023/323

The real-world deployment of fair allocation algorithms usually involves a heterogeneous population of users, which makes it challenging for the users to get complete knowledge of the allocation except for their own bundles. Recently, a new fairness notion, maximin-awareness (MMA) was proposed and it guarantees that every agent is not the worst-off one, no matter how the items that are not allocated to this agent are distributed. We adapt and generalize this notion to the case of indivisible chores and when the agents may have arbitrary weights. Due to the inherent difficulty of MMA, we also consider its up to one and up to any relaxations. A string of results on the existence and computation of MMA related fair allocations, and their connections to existing fairness concepts is given.
Keywords:
Game Theory and Economic Paradigms: GTEP: Fair division
Game Theory and Economic Paradigms: GTEP: Computational social choice