Fair Allocation of Indivisible Chores: Beyond Additive Costs

Summary

This paper studies the allocation of m indivisible chores among n agents with non-additive preferences. The authors show that, for the case of approximate MMS, the best approximation factor is super constant, and specifically they give a lower bound of min{n, log m/ log log m } for submodular costs, and an upper bound of min{n, log m} for subadditive costs. The lower bound also implies a negative result for 1-out-of-d MMS allocations in this setting. The authors proceed to study special cases of subadditive costs, and specifically costs encoded by combinatorial problems, and namely bin-packing and job scheduling. So, for example, in the case of bin-packing, the cost for a subset of items is the minimum number of bins to pack them. For both cases, the authors give an algorithm for finding a 1-out-of-(n/2) MMS allocation.

Strengths

- The paper studies an interesting, natural problem: chore allocation beyond additive costs. - The results are relatively complete, and the authors settle, up-to-constants, all their questions.

Weaknesses

- The main algorithmic results (for bin-packing and scheduling) seem like twists to the standard approximation algorithms (e.g., Next Fit or Best Fit for bin-packing). Of course, this is expected, but these connections/insights are not explicit in the text, so it’s harder to see what’s new about this work. (Some typos: Line 134: “which is somehow the most unfair algorithm” -> drop “somehow”. Line 342: “or the job scheduling setting, we restrict us on the case”)

Questions

Have combinatorial values of this nature (and as a tool for bypassing negative results) been considered in the goods case?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

This paper studies the MMS fair allocation of combinatorial tasks (indivisible chores) problem where the cost function is submodular or subadditive. For submodular functions, they prove that no algorithm can ensure better than min{n, log m/log log m}-approximation. For more general subadditive cost functions, they prove that there always exists an allocation that is min{n , log m}-approximation MMS, which is (almost) asymptotically tight. What’s more, for ordinal relaxation, 1-out-of-d MMS, they prove that for any d≥2, there is an instance for which no allocation is 1-out-of-d MMS. Finally, the authors give two specific settings which are bin packing setting and job scheduling setting and prove that 1-out-of-[n/2] MMS allocations always exist for these two settings.

Strengths

This paper provides solid and clean theoretical results on MMS chores allocations. It also contains some interesting techniques. For example, the author gives a quite interesting example for Theorem 1, and I also find the proof of Theorem 2 mathematically natural and complete.

Weaknesses

I do not find any obvious weaknesses. Perhaps the relevance of this paper to machine learning is not very strong.

Questions

No question.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Not applicable.

Summary

The paper deals with problem of allocating indivisible chores to agents whose valuation functions for bundles of chores are subadditive or submodular, where an allocation that guarantees every agent their maximin share (MMS) may not exist. Here, an agent's maximin share is the agent's worst-case disutility from a partitioning of the items that minimizes the disutility of the worst (maximum disutility) partition. The paper provides new upper and lower bounds on the approximability of MMS allocations. I have reviewed a previous version of this paper submitted to IJCAI 23 where I was positive about the technical contributions of the paper. This revision addresses the concerns with writing and a minor technical issue raised there. The revisions have certainly helped with the readability.

Strengths

The problem setting of subadditive and submodular (dis)utility functions is novel. The new results for these classes of valuation functions provided is this paper are likely to be of interest to the comsoc / fair division research community. The technical results are interesting, non-trivial and use interesting techniques that are new to me. I was able to verify the technical results. Relevant related work is well cited and discussed.

Weaknesses

The relevance to NeurIPS for what seems a very AI/computational social choice focused paper is not clear although this is attempted in the introduction.

Questions

None

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

None

Summary

The paper studies the classical fair allocation of indivisible items setting with two twists: (1) Items correspond to *tasks* instead of *goods*, i.e., any agent would prefer receiving no item at all. (2) Valuations are not additive but may be subadditive. The paper also considers some special cases of subadditive valuations, namely, submodular, "bin packing", and "scheduling" costs. As an objective, the paper focusses on the classic notion of the maximin share (MMS). Since MMS allocations do not always exist, the paper considers both a multiplicative as well as an "ordinal" relaxation of the MMS notion. The contribution of the paper is threefold (I am omitting the ordinal approximation results for simplicity): (1) For the subadditive case, the paper presents a lower bound of $\min\{n,log(m)/loglog(m)\}$ as well as a mechanism providing an approximation of $\min\{n,\log(m)\}$. (2) For bin packing, the paper presents a multiplicative $2$-approximation and a tight lower bound of $2$ for any mechanism. (3) For job scheduling, the paper presents a mechanism providing a multiplicative $2$-approximation, however, without a matching lower bound.

Strengths

- The paper makes significant progress within the classic setting of fair allocation of indivisible items. While this literature has been long focussed on the case of additive valuations/costs, in recent years there has been a growing body of literature studying more general valuations/costs, with the paper under review being one of these. Hence, I am optimistic that the paper will lead to follow-up work. - The paper develops new mechanisms that are tailored to the studied cost functions. These mechanisms and their analysis is certainly non-trivial and lead to a significant technical contribution.

Weaknesses

- Since the result for the general, subadditive case is rather negative (i.e., there is no constant approximation for MMS), the main contribution of the paper is for the special cases of bin packing and scheduling. Having said this, this can hardly be seen as a critique for the paper, but rather as a sign of the challenging endeavor to study beyond additive costs. - I think that the writing of the paper could be improved, as I had to reread several parts of the paper. I added a list of suggestions within the minor comments. - Unfortunately, the newly developed mechanism is not very elegant, and one can't help but wonder whether there exists a simpler mechanism to achieve the same approximation guarantee. Also, the mechanisms do not come with a polynomial-time implementation, hence, leaving the question open whether the same guarantees can be achieved efficiently. **Minor Comments** - The paper uses the term "tasks", while a large fraction of the literature uses the term "chores". I would suggest to add a comment on that. - line 21: You mention "functions" without clarifying their role in the problem. (Of course this is clear for any person knowing fair allocation, but for others it may not.) - line 60: "As far as we know, all the above works also assume additive costs" - Sounds a bit weird in this context, since checking these papers should be doable. - line 71: "the asymptotically tight multiplicative" - I think it is weird to use this phrase in a theorem environment, especially since you are ignoring log-factors. I would suggest to just mention the upper and lower bounds. - line 99: "Note that no bounded approximation" - At this point, it is not clear what should be approximated. - Proof of theorem 1: I was very confused of the usage of the term "covering planes" since, as far as I understand, these objects are actually (partial) grids, i.e. finite set of points. - line 214: I think it would be helpful for the reader to learn about the meaning of the abbreviation "IDO". - line 228-236: I did not find the intuition for the algorithm very helpful before reading the algorithm (and even after that). I would suggest to refine this, having in mind that the reader has not read the algorithm at this point. - line 316: I think that $j \in P_i$ is a bad choice for an index since here $j$ is a machine but before $j$ used to correspond to jobs/items. - Section 5: It would have been nice to hear some (very brief) summary of how Theorem 4 is achieved, i.e., how does the mechanism look like?

Questions

- Intuitively, subadditive costs make the problem "easier" in the sense that allocation all tasks to one agent at least has the same approximation guarantee as in the additive case. This is certainly not the case for superadditive cost functions. Do you have any results in this direction? - I was missing a concrete (real-world) motivation for subadditive cost functions in the context of allocation tasks. Could you elaborate on that?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The limitations of the paper are well addressed, in particular, within Section 6. Here, the paper transparently communicates all resulting open questions.

Response

I thank the authors for their detailed response. I do not have any further questions at this point.