- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
As the authors indicate, AI has been extensively used to create the scientific content and the writeup. I cannot follow well some parts of the paper and I am wondering if this is the reason. Nevertheless the results are interesting and strictly improve the state of the art of an important problem. But I did not enjoy reading the paper. Here is its content:
You have machines and jobs. Jobs need to be assigned to machines. Job assigned to machine has a processing time , which contributes to the load of that machine. The maximum load over all machines, called makespan, is the objective value we want to minimize. This is an NP-hard problem, but a 2-approximation is known since 1990.
Now there is a game, where machines are the players reporting processing times (\hat{p}_{i j}) _ j . The central algorithm assigns jobs to machines according to these reports, and asks the players for some payments. The creativity lies in the assignment, as a standard payment rule is used. We would like to design the game in such a way that reporting the true processing times is a dominant strategy for each player. This property is called strategyproofness and I think is desired, because it makes reporting simple for the players and allows the algorithm to optimize on real values. However, if we impose strategyproofness, then the approximation ratio increases to , the number of machines. This is a major result in this area, shown in two STOC papers from 1990 and 2023. The approximation ratio is measured with respect to an optimal assignment.
This is where in 2023 a paper by Balkanski, Gkatzelis and Tan, published in ITCS, introduced an algorithm ScaledGreedy. It achieves consistency and robustness , which are the approximation ratio when the reports are the truth processing times (consistency) or adversarial (robustness).
The main contribution is an algorithm called EdgeSkip, which has a parameter . It starts with a -approximate "reference" assignment . (Could this be anything else than the 2-approximation from 1990?) Let be this makespan. A new assignment is computed. Job is currently assigned to machine in the reference assignment. If it is assigned to machine , its processing time decreases by the factor \hat{p}{i'j} / {\hat{p}{ij}}. The algorithm makes these changes, in decreasing order of these factors (the greedy aspect of the algorithm), in case the load on caused by these new assignments does not exceed . A job is allowed to move only once; this guarantees a polynomial-time running time. After this process a weight matrix is computed. This matrix is used to compute the final assignment. Theorem 1 bounds the robustness of the algorithm as a function of its consistency. For , the (consistency, robustness) ratios are , which improves both over the ratios achieved by ScaledGreedy and over the ratios achieved by an algorithm from 2025, called CGJ in this paper.
In comparison, ScaledGreedy closes a machine once a new assignment exceeds the threshold , while EdgeSkip avoids this last assignment and keeps the machine still open for smaller jobs.
The next question is smoothness. How does the approximation ratio depend on the prediction error of ? This error is defined as the maximum of the over- and underestimation factors over all pairs. A tweak in EdgeSkip changes the final weight matrix , defining an algorithm called TolerantEdgeSkip. However, this algorithm needs an upper bound on the error. Performance is similar to a consistency–robustness pair. If the given bound is satisfied, there is some approximation ratio depending on the real error ; if not, there is some other depending on the upper bound .
Some lower bound is given on the consistency–robustness ratio pairs that a strategyproof deterministic algorithm can achieve. It consists of a small 3-jobs 2-machine example.
Experiments conclude this paper, comparing 5 different algorithms (including the 2 from this paper). There are cases when the ErrorTolerantEdgeSkip algorithm wins the comparison, when the prediction error is large, but most of the time it is PredictionOnly which is the winner.
Critical strengths
I like the question. The results improve previous work, by small changes in the algorithm, which however need a different technique to analyse them.
Critical weaknesses
But I had difficulties to read the paper. In my opinion it needs an important re-organisation to be publishable.
Questions for authors
I realized very late when reading the paper that there are 3 processing times. The predicted one. The reported one. And the real one. For strategyproofness algorithms, the last two are identical.
Line 52: the reader does not know at this point what a type is.
Line 68. Here you say that you want to improve on the polynomial time guarantee. But running time is not really the issue for this problem, and not mentioned later. Also you mention payments. It was not clear before that you consider games with payments. In this case I would like to learn more on the restriction on the payments. Because couldn't we enforce any arbitrary assignment with payments in the domain {0, infinity} ?
Line 85. The notion of dependency forest is not clear to me, even after reading the paragraph from line 290. I don't really understand that paragraph.
Section 1.2. There is a huge literature on games where the players are the jobs instead of the machines as in this paper. Could you drop a sentence here to mention this difference?
The usual notation I saw in the scheduling literature uses n for jobs and m for machines.
In the preliminaries a job -> machine assignment is first specified by a binary matrix x. Then it is specified instead by a function hat sigma. And later again by a function M_r. I found this very confusing.
Line 188. The setting is not clear to. Initially the algorithms gets all these reported hat p_{ij} times. At what moment does the algorithm learn the real p_{ij}?
Line 208: Since I_i represents a load, I wouldn't call it a counter, which suggest integer values.
Line 213. The reader does not know what a base weight matrix is. Also why does bold r need a subscript 0? There are no subscripts 1, 2, ... later used in the paper.
Line 243: charged by itself -> to (not sure)
Line 359. I don't understand what repeated ratios are.
Line 384: What do the letters HCSP stand for?
Line 427. Can you briefly say what these settings are? The 3 noises in Figure 1 are among those 21? Are noise settings 16, 17 depicted in Figure 1?
3 comments
I see that the authors will take into account my small comments, which will improve the readability of the paper. Good catch that the other reviewers asked for a comparison with Cole et at. After these improvements, the paper still deserves a weak accept. I hope it will make it, but cannot push further.
Thank you! We will try to further improve.
Thank you for your feedback. We agree that the paper needs clearer explanations of the model and proofs. We will revise these parts as follows.
RE: Predictions, reports, and payments. There are three quantities: the true processing times, the machines' reports, and the external predictions. The predictions are public information supplied independently of the machines' reports. Strategyproofness makes truthful reporting a dominant strategy. Consistency concerns correct predictions, while robustness allows arbitrary prediction errors; both guarantees are evaluated under truthful reports. The mechanism does not need to learn the true times separately. We will explain this distinction before introducing the algorithms and state explicitly when we use the same notation for true times and truthful reports.
Payments go from the mechanism to the machines. Each machine's utility is its payment minus the total true processing time of its assigned jobs. For our weighted mechanisms, each job has a threshold: with the other machines' reports fixed, a machine wins the job if its reported time is below that threshold. It is known that paying the winner this threshold guarantees truthful reporting. Therefore, we only need to analyze the allocation rule of the mechanism, while the payments are determined automatically by the thresholds of the rule.
-Line 68: By “polynomial time guarantee” we mean that we study the approximation guarantees of polynomial-time mechanisms, in addition to those mechanisms without computational restrictions.
-Line 85: The dependency forest in the proof of Lemma 3 addresses a specific difficulty. A proposed move is rejected when the jobs already moved to a machine, together with the proposed job, would exceed its capacity. That rejected job may later move to another machine and contribute to another rejection. Adding the bounds from these rejections separately could therefore count the same job more than once. The forest records these relationships so that the proof can account for the overlaps. We will explain this process with a small example before introducing the formal construction.
-Section 1.2: We will add a brief discussion on games where the players are the jobs. They are quite different from our setting.
-Job -> machine assignment: x represents an assignment as a binary matrix, σ^ specifies the reference machine for each job, and Mr is the mechanism that consists of an assignment rule x and a payment rule. These three notations are necessary. We will explain it in a clearer way.
-Line 188: Indeed the mechanism gets the predictions pij^ and the reports pij at the same time. It will never get the true times, but a truthful mechanism can guarantee that the reported times are equal to the true times.
-Line 208: We will call Ii the incoming predicted load, and explain that r0 denotes the original weights before their modification in TolerantEdgeSkip.
-Line 213: “base weight matrix” simply refers to the weights constructed by EdgeSkip, which is not an additional technical concept. The superscript 0 distinguishes these original weights from the modified weights r used later in TolerantEdgeSkip. It does not index a sequence of matrices. We agree that this terminology and notation are unnecessary at first introduction. We will replace “base weight matrix” with “weight matrix” and simplify r0 to r.
-Line 243: the original sentence is not clear enough. We will change it to “Thus, the charging argument cannot rely only on the accepted incoming load on i. “
-Line 359: We will also replace "repeated ratios" with its explicit meaning: several distinct jobs have weight ratios at least K between the same two machines.
-Line 384: HCSP stands for Heterogeneous Computing Scheduling Problem. It appears in Line 106. We will repeat the full name in the experimental section.
-Line 427: The 21 noisy settings are the combinations of the three error structures shown in Figure 1 (i.i.d., machine–job, and sparse) and the seven noise levels η∈{1.1,1.25,1.5,2,3,5,10}. Thus, all 21 settings are depicted in Figure 1, with seven noisy points in each column; the perfect-prediction case η=1 is excluded from this count. The numbers 17 and 16 denote the numbers of settings in which EdgeSkip and TolerantEdgeSkip outperform their respective baselines, rather than setting indices. We will clarify this wording in the text.