Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Problem considered is the following: Given a m intelligent agents or machines and a set of Jobs (with release times and deadlines, processing time requirement and a utility) the goal is to allocate a maximum utility subset of jobs feasibly under some fairness criteria. They consider two fairness criteria namely: Minimax fairness and envy freeness. 

The paper obtains novel approximation algorithms for various problems arising in this setting, improving upon the existing best results for some of them. 
main_review: 
I like this paper -- well motivated and well written problem. The algorithm for minimax fairness (1/3-approximation guarantee) which improves upon existing state of the art (1/5-approximation) is in particular quite interesting. The algorithm is surprisingly simple (yet, in my opinion non-trivial to prove) : keep filling a subset ("bag") of tasks until some agent finds it attractive enough. There are other complementary results -- for example making the above algorithm PTIME runnable and those considering the envy free fairness setting. 
limitations_and_societal_impact: Quite theoretical - so this question seems N/A
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper addresses the following job scheduling problem. There are n jobs and m processors. Job i “arrives” at time r_i, has a processing time p_i, and needs to be executed non-preemptively by time d_i (deadline). It is scheduled on a processor for execution, which can be working on one job at a time and derives utility u_i from execution of a job i. Each processor accumulates the sum of the utilities of the individual jobs it processes.

Two core solution concepts are used for allocating/scheduling the jobs onto processors. 1) maximizing the minimum utility accumulated by any processor, and 2) having the accumulated utility of each processor be no less than that of any other. The latter is matched with a Pareto optimality concept. Variants of those core concepts are investigated.

main_review: The paper is interesting and provides “relaxation bounds” for construction of schedules in general instances. I can see how the proofs go and actually some of the arguments are reminiscent of those used in classical job-shop scheduling theory. It would be useful to discuss a bit or provide pointers to connections to job-shop scheduling.

Also, it appears from the proofs that if we restrict the classes of “arrival” times r_i, the processing times p_i and deadlines d_i -- so that we reduced the “busrtiness” of the job “flow” – then we can obtain (potentially) much tighter “relaxation bounds” for the performance. That is, it appears that if we control/suppress the “burstiness” of the jobs, we’ll be able to schedule them more efficiently on the same set of processors. I believe the reader would benefit from at least a discussion of that aspect, even if the existing proofs cannot be “massaged” to demonstrate this effect. 

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper presents algorithms for fair division of items to agents. Each item is a job that needs to be processed within a given interval for its utility to be extracted by the agent processing it. This adds a layer of complexity since given any set of items, it is NP-hard to find the subset of feasible items that maximizes utility for the agent (utilities are additive but heterogeneous across agents). Two notions of fairness are considered. The first part of the paper focuses on max-min fairness. The main results are to improve the bounds for (a) the best existential max-min fair allocation, and (b) the best approximation to max-min fairness that can be obtained algorithmically in polynomial time. The difference between the two is primarily because of the NP-hardness stated above of finding the optimal subset of feasible jobs in a given set of jobs. The second paper of the paper focuses on variants of envy freeness. Here, the goal is to obtain envy-free solutions that are also Pareto optimal. But, this is impossible, and so are various extensions such as relaxing to EF1. Nevertheless, some positive results are obtained by relaxing EF1 an approximate notion, or relax Pareto optimality to individual optimality and focus on rigid jobs, etc.
main_review: The paper has some interesting and non-trivial results, and as such, and I appreciate the technical work in the paper. But, my main concern is fit. I do not see a clear connection of this paper to ML. It is basically a set of results in designing fair scheduling algorithms. The authors try to explain the relevance by saying that fairness is important in AI and ML. Of course that is true, but this paper does not give any results for fairness in ML. I think the paper is more suitable for a conference like EC, and possibly AAAI, or even some theoretical computer science conferences, but I don't think it is suitable for NeurIPS.

I have read the authors' response. The main concern remains the suitability of the paper for this particular venue, since the connections to learning are still rather vague. On technical merit alone, the score of the paper would be 6 instead of 4, which I have communicated to the AC.
limitations_and_societal_impact: Limitations are not discussed explicitly, although the section on future work does point out some ways that the results in this paper can be made more general. I think the paper would benefit from a discussion on the limitations of the fairness measures used here to model fairness as an abstract concept, i.e., what are situations where these are the right measures and when are there other measures that fit fairness goals better?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the scheduling problem of assigning jobs, each with a release time a deadline and a duration, to heterogeneous machines with the objective of *fairness*. More specifically, each machine has a utility for each job and its total utility is defined as the sum of utilities of jobs that were assigned to it and can be feasibly scheduled. With respect to fairness two concepts are considered:

- Maximin Share (MMS): the MMS of a machine can be thought of as the value it would obtain in the worst case by partitioning the jobs into bundles and was the last machine to select a bundle. If every machine obtains a utility that is no less than an $\alpha$-fraction of its MMS.

With respect to MMS the paper proves the existence of an $1/3$-approximate MMS schedule and shows that a $(0.24-\epsilon)$ one can be constructed in polynomial time. These improve upon the best known $1/5$-approximate MMS schedule due Ghodsi et al.

-  Envy freeness up to one item (EF1) + Pareto optimal (PO): EF1 means that although envy between different machines may exist, it disappears after removal of one item, and an allocation is PO if there does not exist another allocation that makes nobody worse off but somebody strictly better off.

The authors show that no algorithm can return a schedule satisfying EF1 and PO simultaneously for all input instances. When all durations are unit and the valuations are identical then such a schedule can be computed in polynomial time. It is also shown, that the schedule maximising Nash social welfare is PO and simultaneously 1/4-approximate EF1 (and 1/2-approximate EF1 if all jobs have unit processing times.)
main_review: Regarding MMS, the algorithm itself is quite involved and consists 1) so-called large jobs are sequentially assigned to the machines so that when a machine receives a job the MMS values of the other machines do not decrease, and 2) the remaining jobs are put into a bundle until some machine chooses to "get" a subset of that bundle. This approach more or less directly gives the existential result but needs to be massaged in order to give the constructive one. I did not check the proofs line by line but they seem to check out.

With respect to EF1 and PO, it is shown that they are not compatible even in special cases. For the special case of unit processing time and identical valuations a polynomial time algorithm is given based on a maximum weighted $m$-matching on a specific graph. Naturally the algorithm crucially builds upon the fact that the jobs have unit sizes. Although the algorithm is only pseudo-polynomial (all possible time-slots are considered individually) it can be transformed into a polynomial one via standard tricks.

In the experimental results the algorithm is compared to -- and outperforms -- Round-Robin.

The paper considers an interesting problem, and at least the result with respect to MMS is interesting since it improves the state of the art, and the algorithm and its analysis are definitely non-trivial (although I cannot say to what extend they build upon previous works and which ideas are new). The results regarding EF1 + PO seem quite specific and not so interesting to me. Overall this is a nice and well written paper and I think it should be accepted, although I am a bit uncertain on whether this is the correct venue for such a result.




limitations_and_societal_impact: no limitations and no potential negative societal impact that I can think of.
review_title: null

Meta-review: This paper was well-liked by the reviewers.  The only concern was fit for NeurIPS.  I believe there will be interest in this work and I prefer to error on the side of being inclusive. 
Decision: Accept (Poster)