Parsimonious Predictions for Strategyproof Scheduling
Authors: Richard Cole
Anupam Gupta
Pranav Jangir
Venue: NeurIPS 2025 poster ()
Keywords: algorithmic game theory
mechanism design
scheduling
learning with predictions
Primary area: theory
TL;DR: This paper proposes a novel learning-augmented deterministic and truthful mechanism for the strategic unrelated machine scheduling problem using fewer predictions to achieve the best possible consistency and robustness.

Abstract: We consider the problem of scheduling $m$ jobs on $n$ unrelated
  strategic machines to minimize the maximum load of any machine, but
  the machines are strategic and may misreport processing times to
  minimize their own load. The pioneering work of Nisan and Ronen gave
  an $n$-approximate deterministic strategyproof mechanism for this
  setting, and this was recently shown to be best possible by the
  breakthrough results of Christodoulou et al. This large approxation
  guarantee begs the question: how can we avoid these large worst-case
  results. In this work, we use the powerful framework of algorithms
  with (machine-learned) predictions to bypass these strong
  impossibility results. We show how we can predict $O(m+n)$ values to
  obtain a deterministic strategyproof algorithm whose makespan is
  within a constant factor of the optimal makespan when the
  predictions are correct, and $O(n)$ times the optimum no matter how
  poor the predictions are.

Parsimonious Predictions for Strategyproof Scheduling
Richard Cole
Anupam Gupta
Pranav Jangir
Department of Computer Science
New York University New York, NY 10012.
Abstract
We consider the problem scheduling m jobs on n unrelated strategic machines to minimize the maximum load of any machine. As the machines are strategic they may misreport processing times to minimize their own load. The pioneering work of Nisan and Ronen gave an n-approximate deterministic strategyproof mechanism for this setting, and this was recently shown to best possible by the breakthrough results of Christodoulou et al. This large approxation guarantee begs the question: how can we avoid these large worst-case results. In this work, we use the powerful framework of algorithms with (machine-learned) predictions to bypass these strong impossibility results. We show how we can predict O + n) values to obtain a deterministic strategyproof algorithm whose makespan is within constant factor the optimal makespan when the predictions are correct, and (nn) times the optimum no matter how poor the predictions are.
Introduction
We consider the NP-hard problem of scheduling jobs unrelated machines minimize the makespan, ie., the load of the most loaded machine, in the setting where the machines are agents which can behave strategically. In this game-theoretic setting, introduced by Nisan and Ronen (200T), only the machines know the processing times for the jobs. Since they suffer a cost for processing jobs (i.e., the processing time/size of the job), they have incentive misreport sizes (i.e., to overstate or understate them) to the mechanism in order to get a more desirable bundle of jobs. Our goal to design mechanism that achieves (a) good approximation ratio, that always find schedule with makespan comparable to that of the optimal solution on the true processing sizes, and (b) strategyproofness, that machine has any incentive misstate their processing times.
In the non-strategic setting classical approximation algorithms,, the unrelated machines scheduling problem can be approximated
factor of 2 (due works Lenstra et al. (1990) and Shmoys and Tardos 1993)), ), and it is NP-hard to approximate better than a factor of 3/2, leaving a small gap between the constants in the upper and lower bounds. But when the machines is now known that the optimal approximation factor any strategyproof mechanism not a constant, but exactly The paper of Nisan and Ronen (2001) gave a mechanism achieving the n-approximation, and now a matching lower bound n for any strategyproof mechanism is known due to Christodoulou al. 2002 2023). This leaves with large gap between the results that achievable in the non-strategic and strategic settings in the worst-case.
behave strategically,
Since worst-case instances may be pathological and the analysis pessimistic, can ask: how can we give mechanisms that perform better in non-worst-case settings? An important approach of algorithms with predictions Cearning-augmente framework, has gained momentum, giving balance between the robustness guarantees of the worst-case model, and better results when given
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

machine-learned information. Concretely, the model asks: can we perform better if we have some (machine-learned) untrusted predictions about the instance? We seek the following two outcomes:
1. Robustness: this requires that the mechanism's 's performance is not much worse than the perfor- mance without predictions, regardless of whether the predictions correct not.
2. Consistency: this asks that if the predictions are indeed correct (i.e., the predictions indeed conform the parameters/features of the true instance they are supposed be predicting), then the mechanism's 's performance is close to that achievable if it truly believed the predictions. We may also ask for an error-tolerant version of consistency, where the algorithm's 's performance relates to the "error" in the predictions.
This line of work was initiated in the setting of online algorithms by Mahdiaa et al. (2012). Purohit et al. (2018) and Lykouris and Vassilvitskii (2021) (see also the survey article by Mitzenmacher and Vassilvitski 2022)): ); it was used in strategic settings by Agrawal et al. (2024) Xu and Lu (2022) and Gkatzelis et al. (2022). (See the annotated bibliography compiled by Balkanski et al. (2024)).
The unrelated machine scheduling problem was studied in this Sarning-augmenten setting by Xu and Lu (2022) and Agrawal et al. (2024), who observed that following the predictions blindly gives an excellent consistency of I, but has arbitrarily poor robustness if the predictions are faulty; to remedy this, they gave algorithms with bounded robustness and consistency. The current best result is due to Balkanski et al. (2023), who gave the SCALED GREEDY algorithm that is (1 + c)n-robust and (4 + 2/c)-conssittenn for any с O. Their algorithm uses the entire matrix p E R4xm of processing times, where Pig is the prediction for the true processing time Pij of the job j on machine i.
Christodoulou et al. (2024) explore whether we can use a smaller set of predictions, namely output predictions, where the mechanism is merely given the predicted machine for each job. They give an algorithm that uses just these m many predictions, and that is ((1)-robust and (n²) Inn)sconsistent. Their algorithm and indeed, all the above algorithms in this domain compute machine "biases". They use greedy-like algorithm using the reported processing times weighted by these biases to assign the jobs. They also show that, given just assignment predictions, no such weighted VGC mechanism can obtain much better trade-offs.
In light of these results, we ask: can we get a different set of linearly many predictions, i.e., O + m) quantities, and achieve the same guarantees?
1.1 Our Results
Our main result answers this question in the affirmative, and gives nearly optimal robust- ness/consistency tradeoffs with only a linear number of predictions.
Theorem 1.1 (Informal Main Theorem). There exists a strategyproof mechanism that takes predic- tions for the value of the optimal makespan, "bias" for each machine, and "good" machine for each job, and produces an assignment which is (1 + c)m--ooustt and (2 + c-1 <-on-soossstentt for any
choice of c >> 1.
This achieves essentially the same guarantees as the result of Balkanski al. (2023) (our results replace a 1/c term in the consistency guarantee by 1/(c-1)), while using far fewer predictions- -nly linearly many instead of quadratically many. And using these few extra predictions (corresponding to
the "biases" for each machines) to avoid the lower bounds of Christooooooo et al. (2024).
Our approach is based on an essentially simple idea: instead of trying to predict the optimal machines for each job, we predict the machines which would be output by an approximation algorithm. This algorithm follows the "relax-and-roume and-round" approach: it solves linear programming (LP) relaxation for the unrelated machine scheduling problem, and then converts the fractional solution into an integral one. Crucially, the assignments given by this rounding algorithm are supported by linear programming duality. We use this in two ways: firstly, we use the machine variables of the dual program as the machine biases. Secondly, along with the output of the rounding process to prove robustness guaranteees.
the structure of the dual solutions (e.g., complementary slackness)
While this approach leads to an - algorithm, the dual structure of the classical LP relaxation is not rigid enough. The next idea is to write a new IP relaxation for unrelated machine scheduling problem, which allows to ensure that the duals are bounded, which gives us more

---

control over the robustness. The final ingredient is showing a good approximation guarantee for this new relaxation.
Finally, like Balkaaski et al. (2023) D. we can extend our work to an error-tolerant version. In this setting, are given parameter r > 1, and predictions are considered "n-good" if they correspond to some processing times that are within a factor of of the true processing times. The goal now is to be consistent when the predictions are "r--good", otherwise the algorithm is required to be robust. The formal definitions and details of the following result appear in Appendix B
Theorem 1.2 (Informal Error- Tolerant Theorem). There exists a strategyproof mechanism that takes the above predictions for the value of the optimal makespan, the optimal dual solution and the predicted rounded solution, and produces assignment which is (1 + e) n-robust (when the predictions are not n-good), and (2 = (when they are Tj fi-good for some î S n) for any choice of c >> 1.
Comparing the Prediction Models. An advantage of parsimonious predictions is that they require only linear space to manipulate and store, compared to the quadratic storage used in the works of and Lu (2022), Agrawal et al. (024)) [Balkankii et al. (2023). It is an open problem to prove that learning these smaller number predictions from data has smaller sample complexity. (We briefly discuss the learnability of the processing times in a PAC-like model in [Appendix A)) That said, we can use the predictions given Balkanski et al. (2023) (i.e., predictions for all the processing times) to obtain our results by first computing the predictions that our mechanism expects (which are all functions of the processing times), and using these 1 + n + m values for our mechanism.
1.2 Other Related Work
Strategyproof mechanisms are increasingly important in open and decentralized systems, since the resources belong to different agents who may act in their own interest and may not cooperate unless they are given the right incentives. In such settings, it is often important to ensure notions of non- manipulability and fairness, either for reasons of social welfare, or because of legal requirements. Strategyproof mechanisms can help ensure that no single agent can manipulate the outcome to their advantage. Specifically for settings of scheduling jobs to machines, note that machines may misreport processing times to reduce their workload, which could lead to poor scheduling decisions and delays for jobs. The first work for the unrelated machine scheduling problem in the strategyproof setting was due to Nisan and Ronen (200I). The lower bounds were given by Nisan and Ronen (2001). ). Christodoulou al. (2009), Koutsoupias and Vidali (2013), Giannakopoulos al. (2021). Dobzinski and Shaulker (2020). AAhhagi et al. (2012), Christodoulou et al. (2007) ), culminating in a matching lower bound of in the recent works of Christodoulou et al. (2022 2023).
The work of Christodoulo et al. (2024) considers the output predictions model, where the mechanism is merely given predicted output for each request: this corresponds to predicted machine for each job our setting. They give an algorithm that is (/3 + 1)-robust and (n²/B3)-coniistee
for any fixed 3 [1, nl; it assigns a bias of rij = 1 for the predicted machine i, and rær n//3 for every other machine i', and chooses the weighted minimizer r rayPoj. They also show that, given just assignment predictions, no weighted VGC mechanism can give a significantly better trade-off than / vs. n²/ /B. In contrast, our work shows that if we are also given a prediction for OPT and the dual variables (one for each machine), we can achieve much stronger results.
The use of linear programs and duality as predictions is widespread: they have been used, e.g., the works of Lavastida et al. (202T), Lattanzi et al. (2020), [Li and Xian (2021) uses linear/convex programs and their duals to perform load balancing in the online setting. Moreover, linear programming duals are used in the work of Dinitz et al. (202T); uses learned duals as a "warm start" speed up algorithms for finding maximum weight bipartite matchings; these ideas are further explored by Davies et al. (2023). Polak and Zub 2024)) [Sakaue and Oki (2022). However, our use in mechanism design, and in particular, our approach of controlling the variation in the duals to make the mechanism more "robust", seems to not have been used before.
2 Definitions
An instance I of the unrelated machine scheduling problem consists of (i) a set J of m jobs, (ii) a collection M of n machines, and (iii) processing time Ptò for each job j J and machine i E M.
3

---

Let p denote the vector of all processing times. Given an instance I, an assignment of jobs to machines is vector {0. m where Fij if and only if job is assigned to machine i. Such an assignment i satisfies E, = 1, and induces a load of Ej PiyTij machine i E M.
The makespan of assignment æ is MS(p, x) == maxieM E, PijJay.
Define the optimal (integer) makespan to be OPT(p) == assiaggggmensss xr MS(p. v), where the minimum is taken over all possible assignments æ of jobs machines, and the optimal (integer) assignment be denoted by x² x (p).
M with it, where (Pj) = + Taj = 1. We frequently move between allocation functions and assignments as needed. (In some cases, we consider
Given an assignment æ, we can also associate an allocation function &
{0. 1 vectors where Σ, Zij 2 1, but we can always reduce some of the æaj values to zero and get Σ; Pij = 1, without increasing the machine loads and makespans.)
2.1 Strategyproofness
Consider an instance the unrelated machine scheduling problem, where the machines report their processing times for all the jobs. Let p E IR be the true processing times for all machine-job pairs. (As is standard, we use p; to denote the 7th row of matrix p. and p-t denote the rest of the rows.) Now suppose some machine i E M reports p RT as its vector of processing times (where pl, may or may equal p;). and the other machines truthfully report p-; E IRT:
let p-:) E {0, 134 x be the assignment of jobs machines, and let (p'. E RT be the payments made by the mechanism to machines.
Define the utility of machine to be
U. = (T. E Pisass p-i).
(I)
Observe that while both the map and the payments are functions of the reports (p', p-i), the second term in the definition utility uses the true processing times.
Definition 2.1 proofess...f An allocation function yo is strategyproof if there exists payments и such that for any machine i and for any misreport of the processing times vector p/. we have U.(p(,p-.).
(p.,, :): )) 2 Definition 2.2 (Monotonicity). Let æ = (((P.P-.) and x' = (p'.p-.) denote the allocations of the mechanism when machine reports p, and p/ respectively. An allocation mechanism is monotone for every machine and for every two reports of the machine and p/., the associated allocations satisfy Σyer(1e a (P ply) S 0. Moreover, call the mechanism item-wise monotone the allocations satisfy (I.z - x (Poj P(y S
Vj E J.
Theorem 2.3 (Nisan and Ronen 2001). Saks and Yu (2005)). For allocation algorithm, there exists a payment function π such that (sp, R.) is strategyproof if and only if the allocation algorithm
satisfies the monotonicity property.
Since any item-wise monotone mechanism also monotone, the following corollary holds:
Corollary 2.4. An allocation algorithm is strategyproof if it satisfies the item-wise monotonicity property. In other words, if for every machine i, suppose I = xxp.. p-s) and x== (p's suppose these allocations satisfy (I:z (Pt) - -P(y)) S 0 for every job j. Then the allocation algorithm is monotone, and hence there exists a payment function that gives strategyproofness.
D'sp-i)), i), and
3 A New Linear Program Relaxation
We now give linear programming relaxation for the scheduling problem, such that the dual variables corresponding to the machines lie in some bounded range. is this control on the dual variables allows to show strong robustness guarantees without losing much the consistency.
The standard linear programming relaxation for the unrelated machine scheduling problem takes an instance I and target makespan T, and defines the set of permissible edges E(T,p) [(i.])

---

Paj S T) by removing all the edges in M x J which correspond to processing times larger than the target value T. The feasibility linear program P(T. p) is then defined as follows:
EMGI)ER(T Fij 2
EP(DEEET Pij Bij S T
machines i E M
220 0.
Again, the first constraints allow the fractional assignment to allocate more than 1 unit of job j. but any such solution can be transformed into one that satisfies these constraints with equality. Using inequalities simplifies the linear programming dual pT);
max Σ,a; ag TT, B
(T p))
0 Pij S 0 0, 2 0.
v(i.5) E E(T,p)
Our new linear programming relaxation for the unrelated machine scheduling problem takes an instance I and target makespan T, and defines the set of permissible edges p) {(i. Piy S T} by removing all the edges in M x J/ which correspond to processing times larger than the target value T. Then for any scalar e 2 1, the linear program relaxation Po p) is the following:
min Z - 1/en E, Yi
(P.(T.))
EMG.EETT Ziz 2 1 ESGDEEETT Psy Zij - Z + Y; T
V jobs j E
A machines i E M
x. Y. Z 0.
In other words, the primal constraint for machine i M says:
E Pij Vij Y; < T
The first constraints assigns each job to some machine, and is a natural one, But the second constraint mysterious due the variables Y; and Z: to demystify this, let us write its dual program D&(T, p):
max Ejera; -aa--Ty -''EEEM
(D(T.p))
jj Bg Púj 00
v(i,) E E(T.p)
Σ HEM 8 1
(4)
B, 2 1/en
vi M
(5)
a, B
Note that the dual program has variables a, for each each E J, and variables for each machine i M; the latter should be thought of as machine "weights". Observe that this LP is very similar the dual for the natural relaxation, where constraints 4 and (5) are the new constraints added to control the range of the 33 values. Moreover, complementary slackness says that 2.j(aj - 3 Pij) 0.
Proposition 3.1. If T 2 OPT(p), then both the primal and dual linear programs above are feasible.
Proof. Indeed, consider the assignment x= (p)) that achieves the optimal makespan for input p; is a feasible solution to the primal program. Moreover, the all-zero solution is feasible for the dual program.
3.1 Properties of the New Programs
The optimal solution for the new dual program DT p) has value no larger than that of the standard dual, since a maximization problem with more constraints. course, added constraints could conceivably make the dual infeasible, but we now show that this is not possible.
Lemma 3.2 (LPs are Bounded). For any 1 and any T > OPT(p), the primal PT is feasible, and any (fractional) solution (xr, Y. 7.) to has value at least 7(1 1/0) - T/c 2 -T/c. Moreover, its dual (T, p) is feasible and bounded as well.
5

---

Proof of Lemma 3.2 The original primal P(T. p) is feasible because of Proposition 3.1 moreover, any solution for the original primal LP is also feasible for the new primal P.(" p) by just setting Z Y; = O. To show the bound on the primal objective value, consider the constraint (3). The non-neg non-tiiativ of the sum PojTi implies that Y; T + Z. Consequently, the primal objective value is
Z + Σ, Y 2 -1T+2 = Z -1
where we used the non-negativity of the variable in the final step. Since the primal Po p) is feasible and bounded from below, we can use strong duality to infer that the dual Dz(T, p) is also feasible and bounded, which completes the proof.
While the objective function for the primal Pc(T, p) is not meaningful per se, we can also show that the optimal fractional solution has small makespan.
Lemma 3.3 (Fractional Makespan), For >> and larget T 2 (p)(p), an optimal fractional
solution (xr Y, T, for the linear program Po(T,)) has (fractional) makespan
max EX(TDEET( PiyTij
T.
Proof. Since any solution to the classical primal is also a solution to the new primal (by setting 2 = Y; 0), the optimal solution to the primal PT p) has objective value most zero. Moreover,
Lemma 3.2 implies that the optimal solution to Po(T, p) has objective value at least 2(1 2(1-1/c) T/c. Combining these facts,
)) = 2
Using constraint (3) again, but this time ignoring the non-negative Y; terms, we get that
EMOJEEET PoJ P TT =
for each machine i M, as claimed.
In other words, any optimal fractional solution for Po(T, is also a solution the following relaxed version of the original linear program P(T,p):
EMG.EEETT Fij 2 1
V jobs j E
(Qx(Tp))
EsO.DEET Pig Fij S XT
V machines i E M
(6)
2 0,
long as we - (Note that when the relaxation parameter À then QI P(T, p). i.e., we get back the original primal linear program.)
3.2 Rounding Algorithm
Assume that T > OPT(p) In this case, the rounding algorithms of Lenstra et al. (1990) and Shmoys and Tardos 1993) take a fractional solution ã 2 O satisfying the relaxed LP QT. p) and output an
integer assignment at E {0, 1 with the following properties:
Σ, oly = so that each job is assigned to exactly one machine,
2. each jach j assigned to some machine i to which it was originally fractionally assigned in 0 (i.c., 2 = = Éेÿ 0), and moreover
3. æt also a solution to Qx.(T,)) but now with X' -
In other words, this map satisfies
MS(p. x²)= S max
Σ E((T
Pijaly < -
T (2+ 1/(c-1) T
This analysis can be tightened a bit to make the additive loss depend on the largest processing time of any job in the optimal solution, but we stick to the analytical form (7) for simplicity.

---

The Mechanism and the Predictions
Our mechanism takes the following predictions: (i) predicted threshold T, (ii) predicted dual variables 3 E [I/,n, 1] for each machine E M, and (iii) a predicted assignment : - M. the ideal solution, the threshold 7 should equal (PT(p), the variables 3 should be an optimal solution to the modified dual program DT(T, p), and the predicted assignment æ should be the assignment x² arising from optimally solving the modified primal Pc p) and then rounding it as in Section 3.2 The predicted assignment corresponds to vector æ E {0, } and henceforth we will use the two objects interchangeably. Finally, observe that if we are instead given prediction p of the processing times, we can compute the values above as described in Section 3 -nnd use them instead.
4.1 The Mechanism
To begin, the DUAI.-PREDICTON mechanism checks whether the predicted dual variables satisfy Σ, 3, and min; 3, 1/cn. If not, rejects the predictions and just runs the greedy algorithm, which is n-robust and truthful Nisan and Ronen (2001). If the 3 values are in the correct range, the mechanism considers the reported processing times p R along with the predictions and does the following:
Mechanism 1: DUAL-PREDICTON
Input: Reported values Piy for (i,j) E M x J, predictions 3 E RT, map 5 : J + M, and T R4.
Output: Assignment æ E {0, 1)mxm.
for each job do
Let s = {il Pt TT. if' sm)ll()) Ø then
(()) - arg min, Pij.
else
L ((j) + arg min, (3, Piy | e small(j)).
I/ breaking ties in favor of G()).
return the vector corresponding to this allocation sp
In words, the QUAL--PREDICTE mechanism builds a set machines small(j) = (j Ptj S π on which the job is "small" compared to our prediction for the optimal makespan, based on the reported sizes p and the prediction T' for the optimal makespan. If this set is empty (a sure indicator of the predictions being incorrect), it assigns the job to the machine which it has the smallest reported size. Else it assigns it machine in small(j) that minimizes B.p.y. breaking ties in favor of the predicted machine {(j).
A technical observation: mechanism uses the reported Pij values to define the set small(j) (which can be thought of as modifying the biases 3,). This is a departure from previous algorithms, which define the biases Tıj based on the predictions and the reported processing times.
The Analysis
We now analyze the quality of the assignment yo returned by the DUAL-PREDICTOR mechanism: proof proceeds in three natural steps.
We first show (1 + c)nr-robustness of the mechanism by proving that no matter what the predictions are, the makespan of the assignment produced by the mechanism is at most (1 + c)n OPT(p).
Next, we show (2 + 1/(c-1)) -io.-iittcnnsscnccc.... We say that when the predictions are correct (i.c., when T = OPT(p), and the 3; values correspond to optimal solution to the dual D. (). and also the predicted assignment @ corresponds to the integer allocation ot obtained taking an optimal solution to the primal PT(T, .nd and rounding in /Seciion 3.2). then our algorithm achieves a makespan of at most (2 + 1/e-1) T: i... nearly optimal solution.
7

---

Finally we show that the mechanism is strategyproof, by showing that the mechanism is monotone.
5.1 Robustness
For robustness, show that matter what the predictions are, the mechanism's 's assignment has makespan MS x) that is at most (n) times the optimal makespan. Let x" be the optimal assignment, so that (pT(p) (S(p, xx))
Theorem 5.1. Given any predictions, MS(p, æ) S (1 c)n MS(p, x*).
Proof. Let yp and yp* be maps from M that correspond to the assignments and at in the natural way. Define rj = max(1, en ()) To begin, we claim that for any job j.
Petns $ STy (P)
(8)
Indeed, consider the various cases:
(j) 2, then PeO)s S Pi, for machines i, and hence also for machine yp (f).
2. Else if (small(i)] 2 1, we consider two subcases.
(a) If (i) & small(j), then i PP)())) Moreover, we assign job j to some job in small(j), and therefore Po())s S T. Chaining the two implies Pet))s < ())
(b) Else both (() and (p) belong to small(i). The mechanism's selection criterion ensures that Bao) Pe(j).j BppG) (s) Since the B values range between 1/en and 1, the claim immediately follows.
This proves the claim 88 Now consider any machine i, and let J ti (p() = ii be the jobs assigned machine i by the mechanism. The load of machine is
Σ Pa.j jET;
(1 + en Bpr()) Pp)))s
Σ (1+ en 3v). iEM
Σ
Pr.
jEJ:
jEJe (f)=v
s
Σ
(1 + en Bv)) MS(p, = (n + en) MS(p, x'),
NEM
where we use E; 3g < in the final step.
5.2 Consistency
We now show the consistency guarantees: when the predictions correct, the makespan of the mechanism's 's assignment at most (2+ 2 times the optimal makespan. We consider the following slightly relaxed definition:
Definition 5.2 (y-Correct Predictions). For 2 1, the predictions G,,3 () are y-correct for processing times p the following conditions hold:
f E (OPT(p), OPT(p).
O 3 for optimal solution (ã, 3) to the dual program DT p). and
the assignment & corresponding to the prediction @ is the assignment æt obtained by rounding an optimal solution 전 the primal P.(T. p), as in Section 3.2
When predictions are 1-correct, we refer to them as correct predictions. We show that y-correct predictions imply good makespan.
Lemma 5.3 (Consistency). If the predictions (f, () are y-correct processing times p, then MS(p. x) s (2 1/(c-1)) f s (2 + 1/(c-1) : OPTTpp)
Proof. Observe that the set (j) is exactly the set of permissible edges from E(T. p)) = ((i.)
Pij S T) which are incident job j. Since T > OPT(p), the set small(j) is non-empty since contains the machine that is assigned to in the optimal integer solution x". The mechanism now

---

assigns job j to the machine p(j) E small(j) minimizing P. Pty.
Piy. We claim that this machine in fact f()). The claim implies that æ (the output of the mechanism) equals @ (the assignment corresponding the predicted allocation), which in turn equals æ (the rounded solution). Hence 7
gives us MS (p, æ) = MS(p, ④) I (2 + 1/e--)) T, which completes the proof.
We now prove the claim that p(j) ((). By the property of the rounding algorithm, we know that Ti, = 1 only if ã. > O. Moreover, we have Fig > only for (i. E E(T, p) and hence ((j)
belongs small(j). We now claim that
BoUNa POUNS S Bag
(9)
for all small(j). Indeed, observe that āj S B. Piz for all (i,j) E small(j) because of dual feasibility. Moreover, complementary slackness implies that Tiy( Px) for all E small()). Since T 0 we have that that a5 BaC Pac)) Moreover, using that 3 B, get that (()) is one of the minimizers of 3 Pij. proving ( Finally, our tie-breaking strategy ensures that the mechanism assigns the job j to P(j).
As aside, note that while we used the fact that ; is obtained from the rounding algorithm of Section 3.2 any & satisfying the properties above (in particular, that TG().s > 0), and having low load, could be used instead.
5.3 Strategyyroofness
To show that the the mechanism above is strategyproof, recall the results from Section 2.1 and specifically Corollary 2.4 which shows that an item-size monotone mechanism strategyproof.
Theorem 5.4 (Strategyproofness). The Dual-Predicae mechanism is item-size monotone and hence strategyproof
Proof. Let the true processing times be given by p. and consider any other report p; made by machine i. If æ æ(p. p-i) and x' = =='',, p-s) are the allocations under the correct reports and the misreport respectively, we want to show that
(zi) - 2 (py P(y < 0.
(10)
Let small(j) and small' (j) denote the sets corresponding to the runs of the mechanism when given reports :-:) and (p/, p-)) respectively.
1. Case I: Suppose Tij = 1, i.e., the job j is assigned to machine under the correct reports. Since
2/y E {0, 1). (10 follows immediately in case Pij S ply. so it suffices to show that ply < Ptj o/y = 1. We consider two cases based on the size of small(j).
Suppose small(j) Ø, then for machine to be assigned job must be that i arg ming Pr. Since pl, < T. must be the case that |small (f) < If small' (f) - 2, then p'y < Pij means still have i = arg min pl.... Else small (j) = {i), and then the mechanism always allocates job j to the unique machine i in small' (j). This means zr = 1, proving the claim for the case when (j) Ø
Else (small(i) 1. Since j is assigned to machine i, we infer that i E small(j) and 3: pıj S Br pes for all /' E small()). (This vacuously true when |small())] = 1.) Since pl. < Pty and the other sizes pe. remain unchanged for i' A i, we get small' (j) small(j). Moreover, since B, 2 0, the job j will continue to be assigned to machine i, and hence æle- = 1.
2. Case II: Suppose æij O. Since z/ E [0, (10) follows immediately in case pl, S Pij. so suffices to show that ptg > Pij
2 0.
Let i be the machine that is assigned the job in the assignment z: i.e., Riy. = 1. If small()) Ø, then Pij >> Piys since it is not assigned the job j. Now, ply is even higher, and hence æ'y 0.

---

Else, small()) * Ø. which means that iz E small(j) with Be, Piçs S Pyp for all machines i' E small()). In case ply > T. we have that ply & small' (j) and therefore dig = 0. Else if Pij < K/g S T, then we have that
Be Pos s 3.ps 3.pp
and therefore, olyy O.
This case analysis implies that any machine misreporting its processing time for job j leads to an allocation satisfying the item-wise wise monotonicity property (TO). Now Corollary 2.4 implies that the mechanism is strategyproof.
D
6
Closing Remarks
This work extends the investigation of learning-augmented algorithms for optimization problems for which the pessimistic lower bounds be circumvented using machine-learned predictions. We considered the unrelated machine scheduling problem the strategic settings, where the agents (machines) can lie about the sizes of jobs get an allocation with lower load. We show how to use only a linear number of predictions (essentially one value for each job and for each machine) to get constant consistency and optimal (n) robustness, improving on previous work that either achieved suboptimal robustness with linearly many predictions, or used quadratically many predictions for the optimal results. Our approach used a new LP relaxation with small integrality gap that also controlled the range of the dual values.
Several tantalizing directions remain open: can improve the bounds even further? Since typical case is when the number of machines much smaller than the number of jobs, can we use only ((n) predictions and get similar algorithmic guarantees? Can we predict these predictions much faster than predicting job sizes? Finally, what other algorithmic problems can use this "range-controlled dual" idea get improvements?
References
Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. 2024. augmented mechanism design: leveraging predictions for facility location. Math. Oper. Res. 49, 4 (2024), 3626-2651.
Ashlagi, Shahar Dobzinski, and Ron Lavi. 2012. mechanisms. Math. Oper. Res. 37, 2 (2012), 244-258.
Optimal lower bounds for anonymous scheduling doi:10. 1287/moor 1130.0534
Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. 2023. Strategyproof scheduling with predictions. In 14th
Innovations in Theoretical Computer Science Conference. LIPlcs. Leibniz Int. Proc. Inform.. Vol, 251. Schloss
Dagstuhl. Leibniz-Zena Zent. Inform., Wadern, Art. No. 11, 22. doi:10. 0oo:10.4230/1pppoe 4230/1ipics....... itcs 2023 11
Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. 2024. Mechanism Design with Predictions: An Annotated Reading List. SIGecom Exch. 21, 1 (Oct. 2024), 54-57. doi:10. 1145/ 3699814 36999821
Shai Ben-David, Nicolà Cesa-Bianchi, David Haussler, and Philip M. Long. 1995. Characterizations of Learnability for Classes of n......n-VVauuee Functions. J. Comput. Syst. Sci. 50, (1995), 74 86. doi:10
1006/ JCSS. 1995 1008
George Christodoulou, Elias Koutsoupias, and Annamária Kovács. 2007. Mechanism design for fractional scheduling on unrelated machines. In Automato, languages and programming. Lecture Notes in Comput. Sci., Vol. 4596. Springer, Berlin, 40-52. (
540 73420-8_6 8_6
George Christodoulou, Elias Koutsoupias, and Annamária Kovács. [2022] @2022. On the Visan-Ronew conjecture. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science FOCS 2021, IEEE Computer Soc., Los Alamitos, CA, 839-850.
George Christodoulou, Elias Koutsoupias, and Annamária Kovács. [2023] @2023 A proof of the Nisan-Roma Ronen conjecture. In - of the 55th Annual ACM Symposium on Theory of Computing ACM, New York, 672-685 doi:10. 1145/ 3564246 3585176
George Christodoulou, Elias Koutsoupias, and Angelina Vidali. 2009. A lower bound for scheduling mechanisms. Algorithmica 55, (2009), 729-740. 100:10..007//00453 008 9165
10

---

George Christodoulou, Alkmini Sgouritsa, and loannis Vlachos. 2024. Mechanism design augmented with oulput advice. arXiv:2406. 141666 [es.GT]
http////www...g/a////../..0 14165
Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang. 2023. Predictive flows for faster ford-fulkerson. In International Conference on Machine Learning. PMLR, 7231-7248.
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. 2021. Faster matchings via learned duals (NIPS 21). Curran Associates Inc., Red Hook. NY. USA, Article 795, pages.
Shahar Dobzinski and Ariel Shaulker. 2020.
Improved Lower Bounds for Truthful Scheduling. arXiv:2007. 00362 [Ts httts://aaxix http:////aaaa...o//aa/////////// wwtp:////////////////////// .03662
Yiannis Giannakopoulos, Alexander Hammerl, and Diogo Poças. 2021. A new lower bound for deterministic truthful scheduling. Algorithmica 83, 9 (2021), 2895-2913. doi:10. 1007/ 10011000000/000550022220 -00453-021-008477
Vasilis Gkatzelis, Kostas Kollias, Alkmini Sgouritsa, and Xizhi Tan. 2022. Improved Price of Anarchy via Predictions (EC 22)) Association for Computing Machinery, New York, NY, USA, 129-557. doi:10. 1145/
3490486 3538296
Elias Koutsoupias and Angelina Vidali. 2013. A lower bound of 1 é for truthful scheduling mechanisms. Algorithmica 66, (2013). 211-223.
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. 2020. Online Scheduling via Learned Weights. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, Jamuary 5-8, 2020, Shuchi Chawla (Ed.). SIAM, 1859-1877, 0oi:10.113771
9781611975994 114
Thomas Lavastida, Benjamin Moseley, R. Ravi. and Chenyang Xu. 2021. Learnable and Distance-Robust Predictions for Online Matching, Flows and Load Balancing, In 29th Annual European Symposiun on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference) (LIPles, Vol. 204). Petra Mutzel. Rasmus Pagh, and Grzegorz Herman (Eds.). Schloss Dagstuhl Leibniz-Zentrum für Informatik. 199:177. doi:10. 4230/LIPICS E 2021.59
Jan Karel Lenstra, David B Shmoys, and Evva Tardos. 1990. Approximation algorithms for scheduling unrelated parallel machines. Mathematical programming 46 (1990), 259-271.
Shi Li and Jiayi Xian. 2021. Online Unrelated Machine Load Balancing with Predictions Revisited. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event (Proceedings of Machine Learning Research, Vol. 133), Marina Mcila and Tong Zhang (Eds.). PMLR, 6523-6532. http://proceeddnngs www.mml.....eeee. wwwppe/eeeeeeeeeeeeeee /11ll/ .html
Thodoris Lykouris and Sergei Vassilvitskii. 2021. Competitive caching with machine learned advice. J. ACM 68, 4 (2021), Art. 24, 25. doi:10. 1111111444444/ /347579
Mohammad Mahdian. Hamid Nazerzadeh, and Amin Saberi. 2012. Online optimization with uncertain informa- tion. ACM TALG 8, 1 (2012), 2:1-2:29.
Michael Mitzenmacher and Sergei Vassilvitskii. 2022. Algorithms with predictions. Commun. ACM 65, 7 (2022), 33-35. doi:10 11 1145/3528088
Noam Nisan and Amir Ronen. 2001. Algorithmic mechanism design. Vol. 35. 166-196. 10i11..1005 game 1999.0788 Economics and artificial intelligence.
Adam Polak and Maksym Zub. 2024. 106487.
maximum flow. Inform. Process. Letz. 186 (2024),
Manish Purohit, Zoya Svitkina, and Ravi Kumar. 2018. Improving online algorithms via ML predictions.
Advances Neural Information Processing Systems 31 (2018).
Shinsaku Sakaue and Taihei Oki. 2022. -nncrttecooveex-alllls-------i with predictions. Advances in Neural Information Processing Systems 35 (2022), 20988-21000.
framework for warm-starting algorithms
Michael Saks and Lan Yu. 2005. Weak monotonicity suffices for truthfulness convex domains. In Proceedings of the 6th ACM conference on Electronic commerce. 286 293..99.
David B Shmoys and Éva Tardos. 1993. An approximation algorithm for the generalized assignment problem. Mathematical programming 62, 1 (1993), 461 474.
Chenyang Xu and Pinyan Lu. 2022. Mechanism Design with Predictions. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, Lue De Raedt (Ed.). ijcai.org, 571-577. doi:10. 24963/ IJCAI 2022/81

---

A Learnability of Predictions
Let us show how we can learn predictions of the processing time, say in a PAC setting, where each instance is obtained by first drawing a context/feature a from distribution D over some set A, and getting the matrix nu X m of processing times using an unknown map f(a) P : 17 Our goal is to learn some map f : A P such that
Pr
Vi,j; log (a) - log [a)(a) Se) 2 1
Then, at the time the mechanism is run on the true input, we suppose that the predictor sees the actual contexts/features a, and gives the prediction f(a) to the algorithm. The guarantee above ensures that Pr ((((() 2 et S 8, where the error parameter ef 2 (1 +) for small
Let sketch one way solve this learning problem. First, separately and learn with confidence
focus each coordinate fij == - 5-55/mm) (/mm)) a trivial union bound then gives the claim. The goal now becomes that of learning a real-valued univariate function g A + I2,, where g(a) In fiy (a), to an additive accuracy of e with high confidence 1 8'. At this point, we can use standard tools from machine learning theory to give bounds on the number of samples that suffice to learn to an additive error of e. Of course, one needs to make some assumptions on the complexity of the map 9. which would depend the applications at hand.
As a concrete example these results, let us assume that the processing times lie in the range [1..... and define ī(a) == [o(a)] then the function ğ becomes {0, 1,...y K) K--valued. Fur- thermore, the gap due to this approximation I gl S 1; translating back via the definitions, the true processing time fiy (a) and its estimate füy (a) exp(ÿ(a)), would differ by at most a constant factor. Finally, given this {0, I,..., K) --alued function ÿ. we can use the results of Ben-David et al. (1995) on learning such functions exactly with high confidence; this work reduces the learning of this function to showing the finiteness of VC-dimension of some related binary classification problems. In all these cases, the sample complexity behaves like ((dd log 1/5), where the parameter de is some notion the dimension of associated concept classes.
,
B Error tolerant Dual-Predictor Mechanism
It can be shown that the PRAL--PEDICTOR mechanism is somewhat brittle even in the presence of minor errors, the mechanism achieves the robustness guarantee. In this section, we design an error tolerant mechanism that builds on the previous mechanism and achieves constant approximation factor not only when the predictions are accurate, but also when the predictions are approximately accurate.
Specifically, our strategyproof mechanism ERROR- TOLERANN DUAL- PREDICRR will take as input an error threshold 2 in addition to the predictions used in Mechanism 1 it will output an allocation with consistency guarantees ensures the robustness guarantees. (Both the guarantees now depend on 17.)
error of the prediction is at most r), and it will always
B.1 Approximately Correct Predictions
To begin, define the following "distortion" between two vectors p, q of processing times:
Pij
D(p. q) = max max
(11)
4i
Pij
Observe that distortion is symmetric, so that D(p, q) = D(g.p).
Definition B.1 ((7, n) Approximate Conrectness). We now say that predictions (f, are (x.))- approximately correct with respect to the (true) processing times p if there exist
(a) processing times q such that the distortion D(g, P) S 17. and
(b) predictions (1)T, 3, :) 7-correct for processing times q, where y-correetness is defined as in Definition 5.2
We say that the processing times q and estimate f certify (7, () approximmeee conrectness.
12

---

B.2 Error-Toleram Mechanism
The error-tolerant mechanism ERROR-TOLERANT TOLERANT DUAL-PREDICTON given a parameter r) 2 along with predictions that are claimed to be (17, approximateyy correct, and it proceeds very similarly to the original DUAL-PREDICTON mechanism: building set of "small" machines for each job and then using a weighted greedy mechanism to assign to one of them (or to the machine with smallest reported processing time) the set empty.
Mechanism Errer-Tolerant Dual-Predictor
Input: Reported values Pij for all (i,j) M x J. predictions 3 E R map F : M, and E R2
Output: Assignment
{0, 10,xm.
for each job j do
Let small() := {il Pij S T.
if PG(J). < T then
L sjall( 6 small()) (p()))
if sm)ll(j)) then ((i) < arg min, Psj.
else
let BBu + B00) and - 3 for all i + +() (()) t arg (3;
(3,Pi Pij i small(j))
// breaking ties in favor of {
return the vector æ corresponding to this allocation yp
There differences between the
mechanism and this error-tolerant version: first, we now add in the predicted machine F(j) to the set small(j) even if the reported size Pęú).j is larger than the threshold 7, as long as not too large. Secondly, we modify the multipliers ,3 to give the predicted machine an advantage, before choosing the machine for job j. Observe that for the setting 1) = 1, the two mechanisms coincide.
B.3 Robustness
The proof of robustness is quite similar to that of the original mechanism.
Theorem B.2. Given any predictions, MS(p, x) < (1 + c)n n7² MS(p, x*).
Proof. Let to and y" be maps from J to M that correspond to the assignments and xx in the natural way. Define
ry = max(1, 3pp .n/
(12)
To begin, we claim that for any job j.
Pe()i Srz (1)'
(13)
Indeed, consider the various cases:
1. If sj) 2, then Pet)s I Pt. for all machines i, and hence also for machine yp" (j).
Else if (small(f)) 1, we consider two subcases.
(a) If (J) small(j), then f < <Pp(()) Moreover, we assign job j some job in small(j), and therefore Po()) S 17 ?.. Chaining the two implies Pe()); 17² (Pr()).
(b) Else both p(j) and (j) belong to small(j). The mechanism' 's selection criterion ensures that
9 PoG)s $ B (pr())s BP0) Pot)s 17 (p
Since the 3 values range between 1/on and the claim immediately follows.
This proves the claim (3).. Finally calculation similar to the proof from Theorem 5.1 shows that the load of machine is most n² (n + en). MS(p, x*), completing the proof.
D
13

---

B.4 Consistency
Now suppose that the predictions ( are (n, -aaaporxximat correct, and let & be the pro- cessing times that certify this (7-7))-aproximmae correctness. (Note that q is not known to the mechanism.) Unwrapping the definition, get that
1. D(p q) S 17. so that p/n S s
2. (pT(g) Sn S (PT(g).
3. 9 B corresponds to optimal dual solution (ā. (3) to the dual (17 q). and 4. (()) corresponds to the solution æ! obtained by rounding an optimal fractional solution T to the primal Po(nT,q) q).
Lemma B.3 (Consistency). the predictions are - approxxiitt correct, then MS s 7p. (2 1/c--1) T S 7 (2 1/(o-1))
where D(p. q) - S
Proof. We first argue that the set small(j) is non-empty. Indeed, the machine @(i) lies in the support of some primal solution to the linear program Po(n T, q) and hence {p()). S 77 T. Since Pi,j S 9b for all (f,j), we have Paú)) S 172 T. By the definition the mechanism, the machine F() is added to the set small(j) it satisfies this last inequality, thereby ensuring that small(j) is non-empty. Hence, the mechanism assigns to the machine small(j) minimizing B, Ptj.
Now consider the machines in small(j) = {i Pij S F U (G(i)). Since p 2 -/n1, the former set is contained in {il qkj S n T'. Morever, as argued the previous paragraph, ((i) also belongs to this set. In other words, the pairs {(i,j) small(j)) are contained in the permissible edges E(nT, q).
Next, the feasibility for the dual program DT 9) means that äj S 3 4ú for all (i,5) E F(nT .): moreover, complementary slackness implies that ā, = 3, qsj for machines E small()) with Tzy > i... in the support of the optimal fractional solution. Hence, the machine {()) is minimizer of 3ig., 3, over machines i small(j). However, we do not have access the processing times 4. but only to Pij. To fix this issue, we use (i) the fact that q6/ S Pij S Pij and (ii) the definition of 3 (as in in the mechanism) to infer that @(j) is the minimizer of 3,Pk over machines i e small(j). This means x T = x!.
Now suppose that D(p, ②) 1j S 17. Then the resulting makespan is
max Σ Pt S max
Σ
4i = MS(E, q)
S (2 + (2- T/f
S (2 1/-1) OPT(q)
< 2/ 12+
which completes the proof.
B.5 Strategyproofness
Theorem B.4 (Strategyproffness) The error-tolerant Dual- mnll-Predictor mechanism is strategyproof.
The proof is essentially identical to the proof of Theorem 5.4 so we only sketch it here.
Proof. (Sketch) For job j, machine i was not in small(j), the only way for machine i to become part of small' (j) is to reduce its processing time for the job j. Likewise, the only way to be removed from small(j) is to increase its processing time. Therefore, if machine already had the job j (zij = 1), reducing its processing time ensures that it still receives the job, irrespective of whether small( (j) is empty or not.
On the other hand, if machine i did not receive the job, the case when small(j) Ø is trivial. If small(j)) A Ø, increasing its processing time can only increase its scaled processing time until eventually does not belong to small' (j); this shows Fzy = Z'y3 0 as required.
14

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: As the abstract and introduction claims, we designed job scheduling mechanism for unrelated machines that requires only O(n + m) predictions and achieves nearly optimal consistency and robustness. Both consistency and robustness are proved thoroughly.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: is clearly stated in "Our Results" section that we achieve marginally worse consistency than Balkanski al. (2023) while using far fewer predictions- instead of quadratic.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
15

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The paper ensures that each theoretical result has clearly stated assumptions and provides a formal proof. The proofs are well organized and broken up into supporting lemmas wherever required to make them more readable. Due to space limitations, we provide an intuitive proof sketch in the main body and detail the complete proof in the supplemental material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
16

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (bttps://nips.co/
public/guides wublic//guuddeee/Codttiiiiiissso
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (httpa:
Coo///ubeeeeeeeeeeeeee / httipsscccpuullc//ggeee huno:i/icgudddss/odduuuuuiiii ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
17

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The paper respects NeurTPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents theoretical results for foundational theoretical problem in algorithmic game theory and has no foresecable societal impact.
18

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not contain any result data that poses such risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use any existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
19

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, Vatasets.papersstt paperswi thcode. comdetts has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
20

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
No LLMs were used for any of the results in this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
21


Reviews:
[{"review_id": "jvbTLK0pr4", "reviewer": "Reviewer_GfdH", "summary": "This paper studies an important problem from the algorithmic game theory literature, strategy-proof scheduling. The authors show how it is possible to use a linear number of predictions (O(n+m) where m if the number of jobs and n is the number of machines) to improve on the approximations known when taking a worst-case analysis approach. They do so by using a novel framing of the problem, and match or improve on known results in the space, using less predictions/predicted information.", "questions": "1. I understood mathematically the role of the  predicted \\beta’s in the dual formulation. Furthermore, the paper does state that they can be viewed as “machine weights” (line 183) or machine biases (line 245).  However, if I was to actually deploy the mechanism in practice, is there an intuitive way to obtain these weights/biases? \n\n2. Theorem 5.1 provides a guarantee on the robustness of the mechanism, no matter what the prediction quality is. Theorem 5.2 looks at consistency and provides a more nuanced insight since the result depends on the quality of the prediction. Is it possible to revisit Theorem 5.1 and consider prediction quality? If so, would this require a different analytical approach?\n\n3. Can you provide examples of other, specific domains where the proposed approach might be useful?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Overall this is a strong, technically interesting paper, that advances the state-of-the art in strategy-proof scheduling, a classic problem from algorithmic game theory. \n\nStrengths:\n- Studying a well-motivated problem (strategic scheduling) from the algorithmic game theory literature.\n- Novel framing of the problem (i.e. a new framing of the underlying linear programming relaxation) which allows them to provide a nearly optimal tradeoffs with respect to consistency and robustness using a linear number of predictions.\n- Appears to be technically sound and full proofs are provided in the appendix (with good proof sketches in the main paper).\n\nWeaknesses:\n- The paper is dense which limits its accessibility. While reading the work, I was trying to figure out how I might use the results in practice. While I understood the role of the beta's in the dual formulation, I was less confident when it come to understanding how I would \"predict\" them if I was considering them as features of the machine. More clarity here would have been useful.", "was_revised": true, "final_justification": "Thanks for the response. I continue to like the paper and my review doesn't change.", "rebuttal": "Thanks for your encouragement and comments. It's great to hear that you found the work strong and technically interesting. We address your comments below:\n\n**Paper is dense**: Please see below for a detailed discussion; we will elaborate more in the paper as well, and try to make the paper more accessible. \n\n**Way to obtain these weights/biases**: Note that in the setting of unrelated machines where jobs have very different processing times on different machines, the machine weights depend on features of the (job, machine) pairs, and not just the machines themselves. To get an intuitive understanding, it may be useful to consider the setting where the processing times of a job on some machine are of the form, say, $p_j * s_i$, where $p_j$ is a job-dependent term, and $s_i$ a machine-dependent term. In this case, one can hope for the machine weights to depend only on the machine features. One intuitive way to get these weights here would be to use a “multiplicative-weights” iterative approach, where we assign uniform weights, and then increase or reduce the weights based on whether the machine loads are too high or too low. Such a process would converge to near-optimal weights after a small number of rounds.\n\n**Theorem 5.1 and 5.2**: We would be hesitant to change Theorem 5.1, since the robustness property wants us to be good, regardless of the quality of the predictions. However, we do agree that one wants a smoother trade-off between the robustness and the consistency: we hope that the results of the Appendix (particularly Lemma C.3) give a partial answer to this, since they give guarantees even if the predictions are not correct, but not too incorrect.\n\n**Examples of other domains where these techniques can be useful**: This is something we are thinking about, where we are looking at other “load-balancing” problems in routing and scheduling, where we may be able to use a similar linear-programming approach. In general, packing and resource allocation are big areas where similar issues come up; there are more challenges there, but we hope to things interesting things to say."}, {"review_id": "tPiwe0CiLi", "reviewer": "Reviewer_x1Zx", "summary": "The paper considers the unrelated machine scheduling to minimize the makespan. The processing time matrix is not known a priori. The machines are strategic agents, meaning that they may misreport processing times to benefit themselves, i.e., lower their processing load. The problem is to design a strategyproof mechanism where misreporting can only lower each agent’s utility and minimize the makespan. The problem is considered under the algorithms with predictions setting, where the mechanism is given predictions about makespan, machine loads, and the job-to-machine mapping. The problem of strategyproof scheduling has been studied where the predicted processing times are accessible and a constant consistent and O(n) robust algorithm exists. The author proposes a strategyproof mechanism based on linear program relaxation and rounding, with the number of predictions required being linear in the number of machines and jobs. The consistency is constant and robustness is in O(n), i.e., the machine is approximately optimal if the predictions are correct and O(n) times the optimum under arbitrarily bad predictions.", "questions": "1. It seems that the predicted job-to-machine map phi is not as important, which is used just for tie-breaking. Is it possible to drop this via still achieving the same robustness and consistency? \n\n2. Can the authors justify strong sensibility and rationale for the prediction error metric — gamma-correct predictions? If the authors can show that a gamma-correct prediction for some gamma is always (or nearly always) achievable via some learning techniques, the reviewer may consider a re-evaluation.", "limitations": "N/A", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n1. The problem is well-presented. \n2. The contribution of reducing the number of predictions is critical. \n3. The key metrics of algorithms with predictions are analyzed, e.g., consistency and robustness. \n\nWeaknesses: \nAlthough the attempt to reduce the number of predictions is meaningful, the total contribution does not seem to pass the bar of NeurIPS. It did not at least convince the reviewer that it was the case. I will elaborate below. \n\nThe definition of prediction error is too tailored to the analysis and the algorithm and it is very strict. There are two weaknesses: 1) the prediction for the makespan is at least the optimum and 2) the predictions for machine load and assignment need to be exact so that the mechanism can output a solution (after rounding) that matches the optimal solution to the modified primal. First of all, it seems unclear how the bound of the makespan predictions can be achieved. Second, it is hard to examine the hardness of the second condition; it is unclear if the machine load and assignment can easily end up getting the exact outcome in practice. These two weaknesses make the error metric unintuitive and hard to examine its effectiveness in measuring the prediction quality. It seems possible that some set of predictions does not have correctness. It seems hard for any learning model to produce predictions that are gamma-correct for any gamma. \n\nThe weakness in the prediction error makes the consistency hard to interpret. It is still the case that the algorithm is constant consistent when all predictions are perfect, but it does not make meaningful sense when the predictions are not perfect and some predictions do not correspond to any gamma-correctness. Therefore, the reviewer has to assess the consistency not as a function of the prediction error, but as a constant for the case of perfect predictions. This drawback significantly lowers the technical contribution of the paper. \n\nIn my opinion, the assessment of prediction error definition is inherently discretionary. I assess it as indecent due to 1) being too strict and tailored to the algorithm and 2) non-coverage for all predictions. This makes the analysis for an error-dependent consistency less contributive — I have to interpret the consistency as being meaningful for the case of the perfect prediction but not the general case. This lowers the contribution of the paper to below the bar of acceptance. \n\nMinor issues: \n1. It is unclear when reading section 3 “a new linear program relaxation”, what the old is and what the contributions of the new one are. The authors include the old linear program in the appendix, but a clear discussion is needed for the readers to appreciate the contributions. \n2. Incomplete sentence in Line 300, “complementary slackness implies that …”.", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and questions: we are happy to see you agree with the importance of parsimony in predictions, and  that you found the paper interesting and well-written.\n\nWe respectfully disagree with some of the concerns you voice, and would like to suggest that the prediction error definition is quite natural under the circumstances. Let us elaborate:\n\n**Prediction error**:\nWe feel that the predicted optimal makespan is a reasonable thing to predict for a collection of jobs. Most models output estimates with confidence intervals. If such a model predicts the makespan lies in some interval $[\\mu_1, \\mu_2]$ with high probability, we can output $\\mu_2$ our estimate for the makespan. In this case the prediction would indeed be an overestimate for the makespan with high probability.\n\nAs for the prediction of the optimal machine for jobs, we agree that there is no natural way to talk about “nearly-correct” assignments, since it is a mapping. As written, we want these predictions to conform to the rounding of the LP solution. But we can weaken the requirement considerably from what is given in the submission. It would be fine to have any predictions which ensure two properties: (a) ensure the assignment has low load, and (b) that the job is sent to some machine to which it has been sent fractionally. Indeed, previous work on the problem (at Neurips 2024) considered the optimal assignment as a prediction, but achieved a worse robustness/consistency tradeoff. We will add a discussion about this in the next version.\n\nThe prediction error considered in our work is the same as that used in all earlier works, and it ties together all our different types of predictions under a single parameter, $\\eta$. We could incorporate multiple error parameters, one per type of prediction, for example: predictions where the makespan is multiplicatively $\\gamma$-correct, the assignment $\\phi$ is $\\eta$-correct (i.e., results in a makespan less than $\\eta \\cdot OPT$), and the $\\beta$ values are multiplicatively $\\varepsilon$-correct (baseline for correctness would be the beta values corresponding to the mapping $\\phi$). An error-tolerant mechanism, similar to the one we describe in the appendix can be designed that still provides the same consistency and robustness, albeit with different constants. However, we chose to use a unifying error metric, as also used in earlier works.  This has the additional benefit of allowing us to compare our error-tolerant mechanism against the work of Balkanski et al., and we show that our constants match theirs. Highlighting that using fewer predictions does not lead to any deterioration, even in the constants.\n\nLastly, in the learning-augmented algorithms model, it is generally assumed that the mechanism is equipped with predictions about the agents. We make no assumptions about how the predictions are produced and simply treat the predictions as additional information available to a plug-and-play algorithm that offers optionality.\n\n**Question on $\\varphi$'s importance**: This is an interesting question. Indeed, we want to emphasize the importance of tie-breaking in our algorithm, and in the previous algorithms for this problem which give constant consistency. If we consider the non-strategyproof algorithms that give good “offline” approximations to makespan minimization, they round the LPs and make very coordinated decisions. If we want to do coordination in a strategyproof setting, this strong signal across machines has to come from the predictions. (Else we face the Omega(n) lower bound.) So we can use predictions of all the job sizes, but lacking that, we think these job-to-machine maps — or some surrogate for them — are probably necessary to get constant consistency. \n\n**On learnability of $\\gamma$ correct predictions**: Apart from the discussion about the gamma-correct predictions above, we give a discussion of PAC-style learning techniques in Appendix A of the paper.\n\nThank you also for pointing out the minor issues. We will make sure to fix them in the next version."}, {"review_id": "xERx7pmvfV", "reviewer": "Reviewer_gcXb", "summary": "The paper considers learning-augmented truthful mechanisms for makespan scheduling on unrelated machines. In makespan scheduling on unrelated machines, we are given $m$ jobs to be scheduled on $n$ machines, and the goal is to assign the jobs to the machines with the objective to minimize the maximum processing load assigned to a single machine. The processing time $p_{ij}$ of a job $j$ depends on the machine $i$ to which it is assigned. In this paper, the authors consider a strategic variant of this problems, where the machines are selfish agents that might misreport their processing times for the jobs in order to receive a smaller processing load. The goal is to design a strategyproof scheduling mechanism in which no agent has an incentive to misreport their processing times, while still minimizing the objective of the underlying scheduling problem. In this setting, the best-possible approximation ratio of any strategyproof mechanism is $n$. In the learning-augmented setting, the mechanism has access to untrusted predictions on the problem instance. If the meachnism has access to predicted processing times for all job-machine-pairs, then there is a $\\mathcal{O}(1)$-consistent and $\\mathcal{O}(n)$ -robust algorithm (Balkanski et al. (2023)), where the consistency is the approximation ratio for perfect predictions and the robustness is the approximation ratio for arbitrary predictions. If the number of predicted values is linear, then the previously best-known learning-augmented algorithm is $\\mathcal{O}(1)$-consistent and $\\mathcal{O}(n^2)$-robust (Christodoulou et al. 2024). The main contribution of this paper is a $\\mathcal{O}(1)$-consistent and $\\mathcal{O}(n)$-robust algorithm using a linear number of predicted values. \n\nTo achieve this result, the authors assume access to a predicted optimal job assignment, a predicted optimal makespan, and predicted optimal variables for the dual of a certain LP-relaxation. At its core, the presented mechanism greedily matches a job $j$ to the machine $i$ of minimum $p_{ij}\\beta_i$, where $p_{ij}$ is the reported processing time of job $j$ on machine $i$ and $\\beta_i$ is the predicted dual variable, provided that the reported time is smaller then the prediceted optimal makespan. The predicted assignment is only used for tiebreaking. The key idea of the analysis is the usage of a new LP-relaxation that guarantees the dual variables to be within a certain range. Assuming access to predictions on these dual variables, the authors can now use that the predicted values are within this range, which is crucial for proving the improved guarantees. In the appendix, the authors give an error-tolerant version of this mechanism.", "questions": "* How does the error-tolerant algorithm behave if the predicted $\\beta$-values are slightly infeasible, i.e., outside the range $[1/cn,1]$? Does it immediately fall back into the robustness case, or does it still achieve improved guarantees?\n* Apart from the new LP-relaxation, what would you consider the main technical contribution of your paper?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n* The presented algorithm essentially matches the previously best-known consistency and robustness trade-off, while using significantly smaller predictions ($\\mathcal{O}(n+m)$ instead of $\\mathcal{O}(n \\cdot m)$ ), and significantly improves upon the previously best-known guarantees for predictions of a linear size. This seems to be significant progress towards the best-possible trade-off for small predictions.\n* The main technical contribution to achieve this result is a new LP-relaxation. This new LP-relaxation allows to bound the dual variables within a certain range, which is crucial for the proof of the consistency and robustness guarantees. In my opinion, this is a new and very elegant idea to achieve improved results. \n* Since many learning-augmented algorithms in the literature are based on predicted dual variables, the used techniques could potentially also be applicable in different contexts, which raises intriguing follow-up questions.\n\nWeaknesses:\n* In the appendix, the authors show how to design an error-tolerant version of their mechanism, which is also less brittle (more robust against small perturbations in the predicted values). I agree that this approach gives an error-dependency and addresses the brittleness with respect to the predicted makespan and the predicted assignment. However, I am not sure about error-tolerance with respect to the predicted $\\beta$-values. The original algorithm is defined to immediately discard infeasible predicted $\\beta$-values, even if they are only outside the feasibility range by an $\\epsilon$. The error-tolerant version seems to do the same (at least the proof of Theorem C.2 still assumes that the predicted values are feasible), which would mean that error-tolerant mechanism remains very brittle against slightly infeasible $\\beta$-values.\n* While the presented approach uses smaller predictions than the algorithm by Balkanski et al. (2023), it is completely unclear to me what the benefit of these smaller predictions is. As stated by the authors, it remains unclear whether it is easier to learn these smaller predictions than the $m \\cdot n$ processing times. Since the presented learnability result is with respect to the processing times, it remains unknown whether it is possible to learn the smaller predictions without also learning the processing times. Even the error-threshold $\\eta$ is with respect to the distortion of processing times and not a function of the actual predictions.\n* Apart from the new LP-relaxation, most of the used techniques seem to be already established in the area of learning-augmented algorithm design, which somewhat limits the technical contribution beyond the new relaxation. Admittedly, you could also see this as a strength of the new relaxation rather than a weakness.", "was_revised": true, "final_justification": "In my opinion, the paper is a very strong contribution. As outlined in my original review, the results of the paper essentially match the previous best-known tradeoff while using smaller predictions and simplifying the algorithm and analysis. The new LP-relaxation is a strong and elegant technical contribution. My only real concern regarding the brittleness w.r.t the $\\beta$-values was adequately addressed  in the author's rebuttal. Overall, I maintain my initial positive estimation of the paper and recommend to accept it.", "rebuttal": "Thanks for your encouragement and comments: we appreciate that you found the work interesting and elegant, and we agree that the ideas here may be useful broadly. Below, please find responses to your specific comments.\n\n**$\\beta$ values slightly infeasible**: This is a nice question! Indeed, the algorithm should be robust to infeasibilities in the beta-values: if the beta-values are slightly infeasible, we can first scale them down to make them sum to 1. And then this would make them lie in $[1/(c’n), 1]$ for some slightly smaller c’. So the quality would suffer smoothly in how infeasible these beta values are. We will add a discussion about this in the next version.\n\n**fewer predictions are good**: For the second comment, we view having fewer predictions as giving us the power of compression: indeed, we can compute these predictions from predictions of the processing times, so they are at least as powerful. Moreover, these are fewer objects to store and process during the algorithm’s execution. (Indeed, we feel that our algorithm is conceptually cleaner as a result of these predictions.) Moreover, it is also a proof of concept, that a small number of natural quantities suffice (machine weights, and job-to-machine assignments). We hope that future work will be able to show how to learn these faster. \n\n**Additional technical contributions**: The other technical part would be the simple algorithm, which goes hand-in-hand with the LP. The previous algorithm of Balkanski et al. was not very intuitive, and more difficult to interpret, whereas we feel our algorithm follows naturally from the LP, and leads into the analysis quite naturally as well. We do view the simplification of the algorithm (and, as you say, the use of classical techniques, as a technical benefit, since we feel it exposes more of the essential ideas of the problem and its solution. Besides these technical benefits, our contributions are more conceptual: how we can make the predictions more parsimonious using LPs in non-trivial ways, and how new LPs may need to be devised to work well for problems related to learning augmented algorithms."}, {"review_id": "28SDi38plh", "reviewer": "Reviewer_4V1n", "summary": "This paper addresses the problem of scheduling m jobs on n strategic, unrelated machines to minimize makespan, a setting where worst-case analysis shows that any strategyproof mechanism has a pessimistic guarantee. To bypass this limitation, the authors use the learning-augmented framework, designing a mechanism that uses parsimonious (i.e., simple) predictions. The core of their method is an LP relaxation designed to control the range of its dual variables, which are then used as predicted machine \"biases”.  The proposed mechanism takes as input a predicted optimal makespan, a predicted bias for each machine, and a predicted \"good\" machine for each job. It achieves a makespan that is (1+c)n times the optimum regardless of prediction quality (robustness) and (2+1/(c−1)) times the optimum when predictions are correct (consistency), essentially matching the performance of previous work that required complex predictions.", "questions": "For NeurIPS, I think it would be valuable to give a little bit of practical context about the unrelated machine scheduling problem in strategic settings — i.e., what are some applications that this problem models (or approximately models)?\n\nMinor comment: on line 180, I believe “assims” should be “assigns”.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**  \nA very well-written paper on a nice problem.  Analysis appears to all be sound, and the results are surprising in that parsimonious (i.e., succinct/simple) predictions can achieve the same (nearly optimal) consistency/robustness trade off for this problem.  The authors achieve this result via a new linear programming relaxation and dualization for the problem that may be of independent interest.\n\n**Weaknesses**  \nMy sense is that learning-augmented papers at NeurIPS typically include some small numerical studies to show how the newly proposed algorithms compare against baselines — such a study would be a valuable addition to this paper.  I would guess that those results would strictly increase the paper’s strength, since algorithms that use parsimonious predictions often compare quite favorably against those that use more complicated predictions models.", "was_revised": true, "final_justification": "I find the work interesting and believe it is a strong contribution to the field of learning-augmented algorithms and NeurIPS as a whole.  I appreciate the authors' efforts to contextualize some of the practical applications of the problem and hope to see some brief discussion of this in the final version.  I maintain my initial positive score.", "rebuttal": "Thanks for your encouragement and comments: we are happy that you found our results interesting and surprising (we did too!) and liked the presentation. We address your comments below:\n\n1. **Numerical Studies**: This is a great suggestion, thanks: while our focus was on the theoretical aspects, looking at the empirical performance on natural classes of instances would be a nice direction for future work.\n\n2. **Practical context**: Resource assignment problems are already hard to optimize, even in centralized systems. A common example is allocating jobs across cloud compute providers, where tasks need to be assigned to machines with different computational resources. When we move to more open and decentralized systems like those on the Internet, the problem becomes harder. Here, the resources belong to different agents who may act in their own interest and may not cooperate unless they are given the right incentives.\n\nIn such settings, it is often important to ensure notions of non-manipulability and fairness. This could be for reasons related to social welfare or because of legislative requirements. Strategyproof mechanisms are useful in these situations because they make sure that no single powerful agent can manipulate the outcome to their advantage.\n\nScheduling problems in practice can take many forms where fairness matters more than revenue. For example, in healthcare, different departments often manage their own resources. They might misreport their capacity to reduce their workload or to increase their revenue. Without a strategyproof mechanism, this can lead to poor scheduling, delays, and less access for patients.\n\nThere are also other examples like peer reviews or job assignments through bidding, especially when play money is involved. These systems can also be manipulated and they do not have the dimension of revenue maximization. While they may not exactly match the unrelated machine scheduling model, they still show the same basic need: to design mechanisms that work well even when agents behave strategically.\n\nWe will add some applications in the next version.\n\n3. **Comment on line 180**: We will fix this, thanks."}]

Author rebuttal:

Meta-review: This paper studies strategyproof scheduling in the algorithms with predictions framework. The main result is a strategyproof mechanism for the classical problem of makespan minimization on unrelated machines that achieves O(1)-consistency (approximation when predictions are correct) and O(n)-robustness (approximation when predictions are incorrect) with O(m + n) predicted values. This result matches the consistency and robustness from previous work, but with significantly less predicted values (O(m+n) instead of mn).
The reviewers agreed that this is a strong result and that using a small number of predictions is crucial in algorithms with predictions. The technical contribution with the LP relaxation framework for this problem was also highly appreciated.
Decision: Accept (poster)