Parsimonious Predictions for Strategyproof Scheduling

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:

1. 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.

2. 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.

In 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.

Scheduling 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.

There 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.

We will add some applications in the next version.

3. Comment on line 180: We will fix this, thanks.

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.

$\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.

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.

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.

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:

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.

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.

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.

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.

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.

We 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:

Prediction error: We 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.

As 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.

The 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.

Lastly, 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.

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.

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.

Thank you also for pointing out the minor issues. We will make sure to fix them in the next version.