acceptodds
Under review as a conference paper at ICLR 2027

Consistency-Robustness Tradeoffs for Strategyproof Scheduling with Predictions

Abstract

We study strategyproof scheduling on \(n\) unrelated machines with predictions. Each machine is controlled by an agent with privately known processing times, while the mechanism receives a public prediction of the processing-time matrix before the agents report. The objective is to minimize the makespan subject to strategyproofness. We measure performance by consistency, the approximation guarantee for correct predictions, and robustness, the worst-case guarantee for arbitrary predictions. We introduce EdgeSkip, a deterministic strategyproof member of the class of job-wise weighted mechanisms. Such mechanisms allocate each job independently using prediction-dependent weights. Using a polynomial-time \(2\)-approximate reference schedule computed from the prediction and a standard tradeoff parameter, EdgeSkip is \(4\)-consistent and \((2n-2)\)-robust, improving on the \((6,2n)\) guarantee of Balkanski, Gkatzelis, and Tan. Without computational restrictions, EdgeSkip with an optimal reference schedule is \(C\)-consistent and \(\max{n,(n-1)C/(C-1)}\)-robust for every \(C>1\). We prove a matching information-theoretic lower bound for all job-wise weighted mechanisms, thereby determining the exact consistency-robustness tradeoff for this class. For arbitrary deterministic strategyproof mechanisms, we establish the robustness lower bound \(\max{n,C/(C-1)}\) for every \(C>1\). We also study an error-tolerant variant and improve upon prior guarantees. Experiments demonstrate that our mechanisms achieve good empirical performance.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Mechanism Design, Scheduling Game, Learning-Augmented Mechanism

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_4qxhOpenReview ↗
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 nn machines and mm jobs. Jobs need to be assigned to machines. Job jj assigned to machine ii has a processing time pijp_{ij}, 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 (pij)j(p_{ij})_j 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 nn, 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 O(1)O(1) and robustness O(n)O(n), 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 γ\gamma. It starts with a κ\kappa-approximate "reference" assignment σ^\hat{\sigma}. (Could this be anything else than the 2-approximation from 1990?) Let TT be this makespan. A new assignment is computed. Job jj is currently assigned to machine i′:=σ^(j)i' := \hat{\sigma}(j) in the reference assignment. If it is assigned to machine ii, 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 ii caused by these new assignments does not exceed γT\gamma T. A job is allowed to move only once; this guarantees a polynomial-time running time. After this process a weight matrix r0r^0 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 κ=2\kappa=2, the (consistency, robustness) ratios are (4,2n−1)(4, 2n - 1), which improves both over the ratios (6,2n)(6, 2n) achieved by ScaledGreedy and over the ratios (4,2.5n)(4, 2.5n) achieved by an algorithm from 2025, called CGJ in this paper.

In comparison, ScaledGreedy closes a machine once a new assignment exceeds the threshold γT\gamma T, 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 p^ij\hat{p}_{ij}? This error is defined as the maximum of the over- and underestimation factors over all (i,j)(i,j) pairs. A tweak in EdgeSkip changes the final weight matrix r0r^0, defining an algorithm called TolerantEdgeSkip. However, this algorithm needs an upper bound ηˉ\bar{\eta} 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 η\eta; if not, there is some other depending on the upper bound ηˉ\bar{\eta}.

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

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\mathbf x represents an assignment as a binary matrix, σ^\hat{\sigma} specifies the reference machine for each job, and MrM_{\mathbf r} is the mechanism that consists of an assignment rule x\mathbf 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^\hat{p_{ij}} and the reports pijp_{ij} 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 IiI_i the incoming predicted load, and explain that r0\mathbf r^0 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~\widetilde{\mathbf 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\mathbf r^0 to r\mathbf 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}\eta\in\{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\eta=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.

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.

Reviewer_AuESOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies strategyproof scheduling with predictions. A scheduler must schedule a set of jobs on unrelated, heterogeneous machines to minimize the makespan. Each machine ii has a processing time pijp_{ij} for each job jj, which is hidden from the scheduler. However, each machine reports a processing time rijr_{ij} for each job jj to the scheduler. The reported time may differ from the true processing time because the machine wants to maximize its payoff. The scheduler needs to take two actions for each job: (i) decide which machine it is scheduled on and (ii) determine how much to pay that machine. In doing so, it aims to achieve a strategyproof solution in which machines have no incentive to misreport their processing times. For example, a mechanism can assign each job jj to the machine that reports the smallest processing time for jj and pay that machine the second-smallest reported processing time. This mechanism achieves a makespan within a factor of nn of optimal, and this is the best one can do with deterministic strategyproof mechanisms without predictions.

In this paper, the authors study a prediction model in which each machine–job pair also has a predicted processing time. The predictions may be wrong. The objective is to design solutions that have good consistency and robustness, where consistency (resp., robustness) is the approximation ratio between the cost of the algorithm and OPT when predictions are correct (resp., arbitrarily incorrect). There is generally a tension between these two parameters; e.g., the mechanism mentioned above gives an (n,n)(n,n) consistency–robustness tradeoff, while a mechanism that ignores reported times and fully trusts predictions, using a 2-approximation for makespan scheduling on the predicted times, is polynomial-time and strategyproof (because it ignores reported times) but has unbounded robustness and gives (2,∞)(2,\infty) consistency/robustness.

The existing consistency–robustness guarantees include (6,2n)(6,2n) for ScaledGreedy of Balkanski et al. [ITCS 2023] and (4,2.5n)(4,2.5n) for the mechanism of Cole et al. [NeurIPS 2025]. In particular, ScaledGreedy belongs to a "job-wise weighted" family of mechanisms, which is revisited in this paper. The main contribution is a (4,2n−2)(4,2n-2) algorithm, called EdgeSkip, that belongs to the same family and has certain refinements over ScaledGreedy (less on the algorithmic side and more on the analysis side). The authors also extend this tradeoff to achieve improved consistency guarantees (but not necessarily in polynomial time; note that the problem is NP-hard, and we cannot achieve consistency 1 in polynomial time unless P = NP). They also show that the tradeoff is tight for mechanisms in the job-wise weighted family. There is also an error analysis, using the same error model as Balkanski et al. [ITCS 2023]. Finally, they implement and compare ScaledGreedy and EdgeSkip on the HCSP benchmark.

Critical strengths
  • The authors study a classic scheduling problem and improve the best-known consistency–robustness bounds, which have been studied in several previous works.
  • The algorithms are simple (and likely practical), and the analysis techniques are deep.
  • Particular attention has been paid to topics such as the error model.
  • The paper is generally well-written and easy to follow.
Critical weaknesses
  • The consistency–robustness tradeoff is not fully characterized; in particular, there may be mechanisms (outside the job-wise weighted family) that achieve a better consistency–robustness tradeoff (perhaps a (4,n)(4,n) mechanism?).
  • The experiments are somewhat limited; given the similarity between EdgeSkip and ScaledGreedy, I was hoping to see a comparison with the mechanism of Cole et al. [NeurIPS 2025].
  • The algorithmic novelty (in terms of design rather than analysis) may be minor. The job-wise weighted family is a natural family studied in previous work.
Questions for authors
  1. Can randomization help achieve improved consistency–robustness trade-offs? Have you considered it?
  2. Can the ideas behind the algorithm extend to a setting where only partial information about processing times is predicted? E.g., predictions are provided for only a subset of jobs or machines.
  3. Is there a particular reason why the mechanism of Cole et al. [NeurIPS 2025] was not included in the experiments?
3 comments

Thank you for your feedback.

RE: Randomization. Following your question, we considered a simple randomized extension for two machines. With an optimal reference schedule, our deterministic mechanism achieves consistency 3/2 and robustness 3. The classical randomized strategyproof mechanism of [Nisan and Ronen, STOC 1999] ignores predictions and guarantees an expected makespan of at most 74OPT\frac{7}{4}OPT, so both its consistency and robustness are at most 7/4. Choosing between these two mechanisms with equal probability, independently of the reports, gives a universally strategyproof mechanism. Its consistency is at most 12⋅23+12⋅74=138\frac12\cdot\frac23+\frac12\cdot\frac74=\frac{13}{8}, and its robustness is at most 12⋅3+12⋅74=198\frac12\cdot 3+\frac12\cdot\frac74=\frac{19}{8}, both measured by expected makespan. At consistency 138\frac{13}{8}, our lower bound requires every deterministic strategyproof mechanism to have robustness at least 135>198\frac{13}{5}>\frac{19}{8}. Thus, randomization strictly improves the tradeoff for two machines. We believe that randomization can also improve the consistency–robustness tradeoff for general n. Determining the optimal randomized tradeoff remains a direction for future work.

RE: Partial predictions. If predictions are available for only some processing times, we can fill in the missing values with fixed positive numbers, such as 1, and then run EdgeSkip. These numbers must be chosen independently of the machines' reports. The mechanism remains strategyproof, and its robustness guarantee still holds because that guarantee allows arbitrary prediction errors. However, even if all available predictions are correct, the numbers used for the missing values may be far from the true processing times. We therefore cannot claim the same consistency guarantee as when all processing times are predicted correctly. The main open question is how to use the available predictions to obtain a better guarantee than robustness alone. We will discuss this question in the revised paper.

RE: Comparison with Cole et al. We agree that this comparison would strengthen the experiments. Our current experiments do not include the mechanism of [Cole, Gupta, and Jangir, NeurIPS 2025] because the prediction-based methods in our comparison use the full predicted processing-time matrix, whereas Cole et al. use a predicted optimal makespan, a dual-derived value for each machine, and a recommended machine for each job. We will add an experimental comparison with their mechanism and explain how we generate its predictions. We will use the same underlying instances and clearly describe the information given to each method.

Thank you to the authors for their responses and for answering my questions.

I maintain my positive evaluation of the paper and believe it has merit. Although the algorithmic contributions are modest, I believe the improved consistency–robustness guarantees and the analysis techniques (particularly the tight characterization for job-wise weighted mechanisms) provide meaningful and non-trivial contributions.

The authors' responses have also clarified certain points. The proposed experimental comparison with Cole et al. would further improve the paper. Overall, I believe the paper deserves acceptance.

Thank you! We will try to further improve the paper.

Reviewer_U87bOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers learning-augmented algorithms for strategic makespan minimization. In the non-strategic base problem, we are given nn machines and mm jobs, each with machine dependent processing times pijp_{ij}, and our goal is to assign each job to a machine while minimizing the maximum total processing load over all machines. In the strategic version, the machines are strategic agents and their processing time vectors are private information. Goal now is to design a strategyproof mechanism (job allocation + payments). The best-possible approximation guarantee for stategyproof mechanisms is Θ(n)\Theta(n).

In the learning-augmented setting, the mechanism has access to predicted processing times which are considered public information. Task is to design a mechanism that achieves an improved approximation factor when the reported processing times match the predictions (consistency) while guaranteeing a robustness if the reported times are arbitrarily off, with a smooth transition between the two extremes depending on some error measure. The previously best-known result for the considered type of prediction is a (2+γ)κ(2+\gamma)\kappa-consistent and n(1+1/γ)n(1+1/\gamma)-robust mechanism by Balkanski et al, where κ\kappa is the approximation factor for the underlying scheduling problem and γ\gamma is a trade-off parameter.

In this paper, the authors improve this guarantee. For κ=2\kappa=2, which is the best-known approximation factor for the underlying scheduling problem, they achieve 44-consistency and (2n−2)(2n-2)-robustness. For κ=1\kappa=1, they achieve CC-consistency and max⁡(n,(n−1)CC−1)\max(n,\frac{(n-1)C}{C-1})-robustness for every C>1C > 1. Both improve the constants in the guarantee by Balkanski et al. To complement these upper bound, the authors prove a lower bound of max⁡(n,CC−1)\max(n,\frac{C}{C-1}) on the robustness for all CC-approximative deterministic mechanisms and a lower bound of max⁡(n,(n−1)CC−1)\max(n,\frac{(n-1)C}{C-1}) for a specific class of mechanisms that contains both, the algorithm presented in this paper and the algorithm by Balkanski et al.

Critical strengths
  • For κ=1\kappa = 1, the authors give tight bounds for the class of job-wise weighted mechanisms that includes both their algorithm and the one by Balkanski et al. This is a very useful insight as it proves that different techniques are required in order to improve the trade-off even further. Both, the upper and lower bound, are non-trivial proofs. In particular the lower bound is a nice and insightful construction.
  • The analysis of the robustness bounds is quite elegant, and seems to contain novel ideas compared to the existing literature.
Critical weaknesses
  • The presented algorithm seems very similar to the one by Balkanski et al. The biggest difference is the following: Instead of allowing the first job that exceeds a certain thresholds to still be assigned to the corresponding machine, this algorithm does not include that exceeding job. No major new algorithmic ideas are required. These similarities also lead to a very similar strategyproofness and consistency analysis.
  • The presented results "just" improve constants in the consistency and robustness trade-off without closing the gap, making them somewhat incremental. (Although the gap is closed for a certain class of mechanisms, see strength).
Questions for authors
  • Could you elaborate how your result compares to the one by Cole et al.? Their mechanism is 44-consistent and 2.52.5-robust, while receiving fewer predicted values (O(n+m)O(n+m)). Your polytime (κ=2\kappa=2) result only slightly improves upon this while requiring more predicted value (O(n⋅m)O(n\cdot m)).
3 comments

Thank you for your feedback.

RE: Comparison with Cole et al. We agree that their mechanism requires fewer predictions. [Cole, Gupta, and Jangir, NeurIPS 2025] use 1+n+m predictions: the optimal makespan, a dual-derived value for each machine, and a recommended machine for each job. Our EdgeSkip mechanism uses the full matrix of nm predicted processing times and computes a 2-approximate reference schedule from it. Thus, our result uses more prediction information to obtain a stronger worst-case guarantee.

At consistency 4, their robustness guarantee is 2.5n, while ours is 2n-2. This reduces the robustness upper bound by more than 20%. Our prediction model is the same as that of [Balkanski, Gkatzelis, and Tan, ITCS 2023], whose (6,2n) guarantee we improve to (4,2n-2). We will make the different prediction requirements more explicit when comparing with Cole et al.

RE: Algorithmic contribution. We agree that EdgeSkip keeps the main design ideas of ScaledGreedy by Balkanski et al., and that its strategyproofness and consistency arguments are similar. In addition to skipping a reassignment that would exceed capacity, EdgeSkip changes the weights for jobs moved from their reference machines. These weights use the predicted processing time on the target machine, whereas ScaledGreedy keeps reference-based weights on machines faster than the target. The main technical contributions are the robustness analysis and the lower bound for the entire job-wise weighted class, which you highlighted. We will explain these algorithmic changes and the main proof ideas more clearly in the revised paper.

We notice that job-wise weighted mechanisms are a general and natural class of mechanisms, for which we have tight tradeoff bounds.

Thank you to the authors for their response. I appreciate the clarification on Cole at al. My overall impression of the paper has not changed, I will stick with my score of 3.

Thank you!

Reviewer_NnxAOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers the strategyproof makespan minimization problem on unrelated machines, in the learning-augmented setting. This is a version of the classical problem of assigning jobs to machines that have possibly different processing times for the same job. In this version, each machine reports the job lengths and there is also a public prediction of the job lengths. The mechanism has to be strategyproof in that no machine can profit by misreporting job lengths and must satisfy the usual desiderata of consistency and robustness for learning-augmented algorithms under this condition. The main result is an improvement of the previously known consistency-robustness tradeoff for the problem. There are also some auxiliary results showing lower bounds under restricted settings on the consistency-robustness tradeoff.

Critical strengths

The paper improves the consistency-robustness tradeoff for a previously studied problem and also establishes optimality in at least one setting.

Critical weaknesses

The improvements in bounds are modest, and the main result does not have a matching lower bound. In other words, this is neither the first nor the last paper on this problem, which is of mild interest to the broader community.

The technical contribution of the paper is limited. The algorithm seems to essentially reuse ideas from the previous paper on the problem, with some optimizations to get a better bound. I found it hard to identify interesting and conceptually novel contributions in the paper.

Questions for authors

No questions. The paper is clearly written (with some occasional sentences that are not clear, but this is common nowadays with the iuse of AI) but the results weren't super interesting in my opinion.

4 comments
AuthorsOpenReview ↗

We have tight tradeoff bounds for weighted mechanisms

Thank you for your feedback.

RE: Optimality of bounds. We determine the optimal consistency–robustness tradeoff for all job-wise weighted mechanisms, which are a very general and natural class containing ScaledGreedy and EdgeSkip. For every C>1, both the upper and lower bounds match at {n,(n-1)CC-1} (see Corollary 1 and Theorem 4), when imposing no computational restriction. Thus, no choice of weights within this class can improve this tradeoff. Moreover, the same bound is optimal among all deterministic strategyproof mechanisms for two machines, as shown in Appendix B.

With computational restriction, we agree that the optimal polynomial-time tradeoff remains open, although we have improved consistency from 6 to 4 and robustness from 2n to 2n-2. We will distinguish this open gap more clearly from the tight tradeoff established for the job-wise weighted class.

RE: Technical contributions. Our EdgeSkip mechanism builds on the predicted-speedup ordering and weighted allocation approach of [Balkanski, Gkatzelis, and Tan, ITCS 2023]. Our changes are simple. This is because the previous approach is already good and natural enough, and there is no need for a large change.

However, the analysis becomes much more different and challenging. Rejecting a job before it exceeds the capacity removes a property used in the previous robustness proof: a machine that rejects a job need not have accumulated load up to the threshold. Our dependency forest instead bounds their combined contribution without counting the same load repeatedly, giving the improved robustness guarantee.

The matching lower bound in Theorem 4 also requires a separate argument. We construct a prediction for which consistency forces many jobs to have large weight ratios between the same pair of machines, and we then use these ratios to construct actual processing times that force a large makespan. This may provide insights to lower-bound constructions for all types of mechanisms.

Dear Reviewer NnxA,

As we are less than 30 hours from the end of the discussion period, we want to check in with you to see if our response has addressed your concerns. If so, we would appreciate it if you could adjust your score accordingly. We are happy to address any additional concerns you might have.

Thanks for the rebuttal response. Unfortunately, my original concerns remain. There is no unconditional lower bound that this paper matches, and the technical novelty is limited. For a foundational problem, this would not be limiting, but for a problem of modest importance, the paper's contribution is below the bar for a selective conference in my opinion. I'll keep my original scoe.

AuthorsOpenReview ↗

Clarification on the matching lower bound

Thank you for the follow-up. We agree that for three or more machines, the optimal tradeoff among all deterministic strategyproof mechanisms remains open when 1<C<n1<C<n. We would like to clarify one point about the scope of our lower bound. Section 4.1 proves that every CC-consistent deterministic strategyproof mechanism on n≥2n\ge 2 machines has robustness at least max⁡{n,CC−1}\max\{n,\frac{C}{C-1}\} for C>1C>1, with no restriction on how it assigns jobs which is unconditional (general). This general lower bound matches our upper bound for every C>1C>1 when there are two machines. For three or more machines, we prove the full tradeoff for the class of job-wise weighted mechanisms, which includes both ScaledGreedy and EdgeSkip.

Comments on the paper

1 comment

Dear reviewers, dear authors,

thank you for engaging in the discussion for this submission.

@Reviewers: The authors commented on your questions and stated weaknesses. Please acknowledge their rebuttal and decide whether it affects your assessment and score. Thank you!

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.