Fair Allocation of Indivisible Chores: Beyond Additive Valuations

Dr. Bo Li

Department of Computing at The Hong Kong Polytechnic University.

Abstract. Discrete fair division has recently attracted significant attention, driven by its real-world applications and theoretical complexities. A key difficulty is that the traditional fairness concepts cannot be satisfied. Among the various concepts proposed to address this issue, maximin share (MMS) fairness is one of the most popular and widely accepted. While MMS fairness has been extensively studied and well understood in the context of allocating goods, its application to chores—especially under non-additive valuations—remains less explored.

In this work, we first provide a fundamental hardness result: no algorithm can guarantee better than a \( \min\!\left\{ n, \frac{\log m}{\log \log m} \right\} \)-approximation when agents have binary submodular cost functions, where \( m \) is the number of chores and \( n \) is the number of agents. This result shows a sharp contrast with the allocation of goods, where constant approximations exist even for general submodular valuations. We then prove that for arbitrary subadditive cost functions, there always exists an allocation that is \( \min\!\{ n, \lceil \log m \rceil \} \)-approximation, and thus the approximation ratio is asymptotically tight.

We then shift our focus to concrete combinatorial settings where the valuations are subadditive. In particular, we consider three well-motivated models: vertex cover, job scheduling, and bin packing. For the vertex cover model, each agent incurs a cost for selecting vertices that cover the edges (viewed as items) assigned to them. For the job scheduling model, each agent manages a set of (unrelated) machines to process the jobs (viewed as items) allocated to them. For the bin packing model, each agent must pack their allocated items into bins, incurring a cost based on the number of bins used. For each model, we design algorithms and prove that constant approximate MMS can be guaranteed, and we also provide matched lower bounds on the best-possible approximations.

Biography. Bo Li is an assistant professor in the Department of Computing at The Hong Kong Polytechnic University. Formerly, he was a Postdoctoral Fellow at the University of Oxford and the University of Texas at Austin. He received his Ph.D. in Computer Science from Stony Brook University and B.S. in Applied Maths from Ocean University of China. He is broadly interested in algorithms and game theory, including problems related to algorithmic game theory, computational social choice, fair division, and approximation and online algorithms.