Mechanism design augmented with output advice
Authors: George Christodoulou
Alkmini Sgouritsa
Ioannis Vlachos
Venue: NeurIPS 2024 spotlight (2024)
Keywords: mechanism design
output advice
quality of recommendation
facility location
scheduling
house allocation
auctions
Primary area: algorithmic_game_theory
TL;DR: Our paper proposes a mechanism design model augmented with an output prediction and applies it to various problems using a universal error measure in the algorithmic design with predictions setting.

Abstract: Our work revisits the design of mechanisms via the learning-augmented framework. In this model, the algorithm is enhanced with imperfect (machine-learned) information concerning the input, usually referred to as prediction. The goal is to design algorithms whose performance degrades gently as a function of the prediction error and, in particular, perform well if the prediction is accurate, but also provide a worst-case guarantee under any possible error. This framework has been successfully applied recently to various mechanism design settings, where in most cases the mechanism is provided with a prediction about the types of the players.

We adopt a perspective in which the mechanism is provided with an output recommendation. We make no assumptions about the quality of the suggested outcome, and the goal is to use the recommendation to design mechanisms with low approximation guarantees whenever the recommended outcome is reasonable, but at the same time to provide worst-case guarantees whenever the recommendation significantly deviates from the optimal one. We propose a generic, universal measure, which we call quality of recommendation, to evaluate mechanisms across various information settings. We demonstrate how this new metric can provide refined analysis in existing results.

This model introduces new challenges, as the mechanism receives limited information comparing to settings that use predictions about the types of the agents. We study, through this lens, several well-studied mechanism design paradigms, devising new mechanisms, but also providing refined analysis for existing ones, using as a metric the quality of recommendation. We complement our positive results, by exploring the limitations of known classes of strategyproof mechanisms that can be devised using output recommendation.

Mechanism design augmented with output advice
George Christodoulou Aristotle University of Thessaloniki and Archimedes/RC Athena, Greece gichristo@csd auth.gr
Alkmini Sgouritsa
Athens University of Economics and Business and Archimedes/RC Athena, Greece alkmini @aueb.
Toannis Vlachos
Athens University of Economics and Business and Archimedes/RC Athena, Greece
ioa. vlahos@aueb. gr
Abstract
Our work revisits the design of mechanisms via the learning learning-augmeeteed frame- work. In this model, the algorithm enhanced with imperfect (machine-learnd)) information concerning the input, usually referred to as prediction. The goal is design algorithms whose performance degrades gently as function of the pre- diction error and, in particular, perform well if the prediction is accurate, but also provide a worst-case guarantee under any possible error. This framework has been successfully applied recently to various mechanism design settings, where in most cases the mechanism is provided with a prediction about the rypes of the agents. We adopt perspective which the mechanism is provided with an output recom- mendation. We make assumptions about the quality of the suggested outcome, and the goal is to use the recommendation to design mechanisms with low approxi- mation guarantees whenever the recommended outcome is reasonable, but at the same time to provide worst-case guarantees whenever the recommendation signif- icantly deviates from the optimal one. We propose a generic, universal measure, which we call quality of recommendation, to evaluate mechanisms across various information settings. We demonstrate how this new metric can provide refined analysis in existing results.
This model introduces new challenges, the mechanism receives limited infor- mation comparing to settings that use predictions about the types of the agents. We study, through this lens, several well-studied mechanism design paradigms, devising new mechanisms, but also providing refined analysis for existing ones, using metric the quality of recommendation. We complement positive results, by exploring the limitations of known classes strategyproof mechanisms that can be devised using output recommendation.
Introduction
Motivated by the occasionally overly pessimistic perspective of worst-case analysis, a recent trend has emerged focusing on the design and analysis of algorithms within the so-called
framework (refer to [30] for overview). Within this framework, algorithms enhanced with imperfect information about the input, usually referred to as predictions. These predictions can stem from machine learning models, often characterized by high accuracy, leading to exceptional performance. However, their accuracy is not guaranteed, so the predicted input may differ significantly from the actual input. Blindly relying these predictions have significant consequences compared to employing a worst-case analysis approach.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The framework aims to integrate the advantages of both approaches. The goal is to use these predictions to design algorithms whose performance degrades gently as function of the inaccuracy of the prediction, known as the prediction error. In particular, they should perform well whenever the prediction is accurate -a property known as consistency- and also provide a worst-case guarantee under any possible error -a property known as robustness.
Xu and Lu [39] and Agrawal et al. (2) applied the design settings, where there is incomplete information regarding the preferences (or types) of the participants over set of alternatives. Traditional mechanism design addresses this information gap by devising strategyproof mechanisms that offer appropriate incentives for agents to report their true types. In the with predictions about the types of the agents. The aim is to leverage these predicted types to design strategyproof mechanisms that provide consistency and robustness guarantees. Since then, this model
framework in mechanism
model, it is generally assumed that the mechanism is equipped
has found application in diverse mechanism design settings [8] 11 27 25
Mechanisms with output advice In this work, we propose an alternative perspective on mechanism design with predictions. We assume that the mechanism is provided with external advice to output a specific outcome, rather being provided with predictions of the agents' types. For example, in a job scheduling problem, the designer may receive a recommended partition of tasks for the machines, rather than a prediction about the machines' processing times. Similarly, in an auction setting, an allocation of goods is provided, rather than a prediction about the agents' valuations.
Following the tradition of the learning-augmented framework, quality of the recommended outcome, which may or may not be a good fit for the specific (unknown) input. The goal is to the recommendation approximation guarantees whenever the recommended outcome is a good fit, but at the same time provide worst-case guarantees whenever the recommendation deviates from the optimal one.
make no assumptions about the
design strategyproof mechanism with good
We observe that one can reinterpret previous models within the framework of our model, viewing as more constrained version of predictions with limited information Since only require limited information regarding the outcome, our model may be better suited to handle cases where historical input data is absent limited, which may occur for various reasons such privacy concerns, data protection, challenges in anonymizing, or simply because the information is missing. For instance, historical data in an auction may sometimes only contain information about the winners and perhaps the prices, omitting details about their exact valuation or the values of those who lost. Additionally, our model may be applied in cases where the designer does not need know the specifics of the algorithm and treats it as black box, as long as it yields satisfactory allocations, even if the inner workings are not fully understood.
We make no assumption about how the outcome recommendation was produced, which makes quite general and adaptable to different application domains. For instance, the outcome may represent the optimal allocation with respect to predicted data (as seen in (2), or a solution generated by an approximation algorithm a heuristic. Consequently, the quality of the recommended outcome may be affected by various factors, such as the accuracy of the predicted data or limited computational resources which prevent the computation of optimal solutions, even when the data is accurate.
beneficial side effect of our model that an outcome recommendation fits in a plug-and-play fashion with generic machinery for strategyproofness in multi-dimensional mechanism design, particularly maximal range VCG mechanisms (or more generally with affine maximizers) in straightforward manner: simply add the recommended outcome to the range of the affine maximizer (see Scction55).
Quality of recommendation In the learning augmented framework, the performance of an algorithm (or mechanism) is evaluated based on the prediction error, which quantifies the disparity between the predicted and actual data. Unfortunately. there is no universal definition for such an error; it is typically domain-specifie (e.g., the ratio of processing times for scheduling [7 R or (normalized) geometric distance for facility location (2). Therefore, if one modifies the information data model for a specific problem-for instance, by assuming that only a fraction or a signal of the predicted data is provided it becomes necessary to redefine the prediction error.
For example, in [2]. it is assumed that the mechanism is provided with the optimal allocation with respect to the predicted types. Refer to the discussion in Section 3 for comparison and differences with their model.

---

To address this issue, we propose a generic, universal measure that can be applied to analyze algorithms across various information settings and application domains. We define the quality of recommendation as the approximation ratio between the cost (or welfare) of the recommended outcome and the optimal cost (or welfare) both evaluated w.r.t the actual input. It is worth emphasizing that although the above definition aligns naturally with our information model, as we do not assume the designer is provided with predicted data, it can also be applied to richer information models with partial or even full predicted input.
We argue that it provides a unified metric for settings involving predictions, particularly when the objective is to design mechanisms (or more generally algorithms) with low approximation or competitive ratio. The disparity between predicted and actual data, captured by the predicted error, may not always be relevant and can lead to misleading evaluations; there are cases where this error may be significantly large, but the optimal solution remains largely unchanged. For example, consider the problem of makespan minimization in job scheduling (see also Section [ for detailed example in facility location). In 27 &. the prediction error used is the maximum ratio of processing times, and it appears in the approximation guarantees. There are simple instances where this ratio is arbitrarily large, but the optimal allocation remains the same. Consequently, when the prediction error is incorporated into the analysis, it may lead to overly pessimistic guarantees for mechanisms that perform much better (see Section 3). Our metric avoids such pathological situations.
1.1 Contributions
We propose studying mechanisms augmented with output advice, setup that utilizes limited in- formation to provide improved approximation guarantees. Additionally, we introduce unified metric that can provide more accurate evaluations, even for settings with richer information models. We explore the limitations of the class of strategyproof mechanisms that can be devised using this limited information across various mechanism design settings. Detailed results concerning the house allocation problem can be found in the full version of the paper. Table T summarizes our results.
Facility Location In the facility location problem, there are agents each with preferred location and the goal is to design a strategyproof mechanism that determines the optimal facility location based on an objective. In Section 3 we derive new approximation bounds for the facility location problem revisiting the Minimum Bounding Box and the Coordinatewise Median mechanisms defined in 12), as function of the quality of recommendation. We provide tight bounds, and demonstrate that in some cases they outperform previous analysis with the use of a prediction error.
Scheduling In Section 4 we study a scheduling problem with unrelated machines, where each machine has a cost for each job, which corresponds to the processing time of the job on the machine. Each job is assigned to exactly one machine, and the goal is to minimize the makespan having an output allocation as a recommendation. We devise new strategyproof mechanism (Mechanism Db. that takes also as input confidence parameter 3 E n). reflecting the level of trust in the recommendation. We show that this mechanism is (3 + 1)-consistent and -rouust (Theorem 3 B
Altogether, we obtain a min((3 + 1),, n +  = upper bound on the approximation ratio, where أ is the quality of the recommendation, that we show that is asymptotically tight (Theorem 4 We complement this positive result, by showing that, given only the outcome advice, it is impossible to achieve a better consistency-robut -robusttesss trade-off in the class of the weighted VCG mechanisms (Theorem
Combinatorial Auctions Next, we study combinatorial auctions given a recommended allocation (see Section 5). In the combinatorial auctions setting, there is set of m indivisible objects to be sold to n bidders. who have private values for each possible bundle of items. We observe that our advice model fits nicely with the maximal in range VCG mechanisms or more generally with the affine maximizers, by preserving prootegyrroofness. These mechanisms provide the best known bounds for the approximation of the maximum social welfare for several classes of valuations [19 17 24 By including the recommended outcome in the range of the affine maximizer, we immediately obtain 1 L-consistency, while maintaining the robustness guarantees of those mechanisms.
House Allocation Finally, we switch to the house allocation problem. In this problem, we aim to assign houses to set of n agents in way that ensures strategyproofness and maximizes the social welfare. We use the TTC mechanism (55 with the recommendation as an initial endowment, and prove that this is m approximmate for unit-range valuations and min n² " apppoxiitat
3

---

Table 1: Contribution Results. Consistency, robustness and approximation results proved for the mechanism design problems augmented with output advice. In the house allocation problem, bounds are shown for unit-range valuations, while the ones in parentheses are for unit-sum valuations. In combinatorial auctions, Par is the approximation ratio guarantee of a maximal in range mechanism. f(t. p) aapprxximaaioon
Problem
Cons
Rob
Facility Location (egalitarian)
1 12]
1+v2 22
min à. + V2)
Facility Location (utilitarian)
22A+42
22
2/Xx+2
min (2np 0- + v2, 22242
1-A
1-2 min + 1)Ā, + p, B3)
Scheduling
B +
n=
Combinatorial Auctions
1
PM
min (P, PM
House Allocation
1
ni (or n²))
min p. (or n²
for unit-sum valuations, where is the quality of recommendation. Finally, we prove it is optimal among strategyproof, neutral and nonbossy mechanisms using the characterization of (88 and the correspondence between serial dictator mechanisms and TTC mechanisms
1.2 Related Work
Learning-augmennted mechanism design Recently, there has been increased interest in leveraging predictions improve algorithms' worst case guarantees. The influential framework of Lykouris and Vassilvitskii [28] is applied on caching, formally introducing the notions of consistency and robustness, under minimal assumptions on the machine learned oracle. The learning-augmentee framework is naturally brought to the algorithmic mechanism design field by [2] and 33 independently. Agrawal al. design learning-augmented strategyproof mechanisms for the problem of facility location with strategic agents. Xu and Lu [39 apply the algorithmic design with predictions framework on revenue-maximinn single-item auctions, frugal path auctions, scheduling, and two-facility location. Another version of the facility location problem, obnoxious facility location, is studied by Istrate and Bonchis 225. Prasad al. [31] develop a new methodology for multidimensional mechanism design that uses side information with the dual objective of generating high social welfare and high revenue. Strategyproof scheduling of unrelated machines is studied in [8] achieving the best of both worlds using the learning-augen augmented framework. Revenue maximization is also considered in [9] in the online setting, while Lu et al. [27 study competitive auctions with predictions. Caragiannis and Kalantzis [1]] assume that the agent valuations belong to a known interval and study single-item auctions with the objective of extracting a large fraction of the highest agent valuation as revenue. Other settings enhanced with predictions include the work of Gkatzelis et al. [22], where predictions are applied to network games and the design of decentralized mechanisms in strategic settings. In [0), the scenario includes a set of candidates and set of voters, and the objective is to choose candidate with minimum social cost, given some prediction of the optimal candidate.
Facility Location For single facility location on the line, the mechanism that places the facility on the median over all the reported points is strategyproof and optimal for the utilitarian objective, and it achieves a 2-approximation for the egalitarian social cost, which is the best approximation achievable by any deterministic and strategyproof mechanism [32] In the two-dimensional Fuclidean space, the Coordinatewise Median mechanism achieves /2-approximation for the utilitarian objective [29], and a 2-approximation for the egalitarian objective (23]: these approximation bounds are both optimal among deterministic and strategyproof mechanisms, In (2) they consider as a prediction the position of the facility to improve the above results. Concerning the egalitarian social cost and the two-dimensional version of the problem, they achieve perfect consistency, and a robustness of 1 + 22. They also prove that their mechanism provides an optimal trade-off between robustness and consistency. Regarding the utilitarian social cost in two dimensions, they propose a deterministic mechanism achieving v/x2+2 -consistency, 1/2x+2 robustness and optimal trade-off 1+
among deterministic, anonymous, and strategyproof mechanisms.
Scheduling Christodoulou et al. [5] validated the conjecture of Nisan and Ronen, and proved that the best approximation ratio of deterministic strategyproof mechanisms for makespan minimization for n unrelated machines is n. Even if we allow randomization, the best known approximation
guarantee achievable by randomized strategyproof mechanism is O(n) [3]. Following the pre- diction framework, Xu and Lu (39] study the problem with predictions & denoting the predicted

---

processing time of job by machine i. They propose a deterministic strategyproof mechanism with approximation ratio of ( " }), where r E [1, m] is configurable consistency parameter and rj 2 1 is the prediction error. Balkanski al. [8 extend these results by identifying deterministic strategyproof mechanism that guarantees a constant consistency with a robustness of 2n, achieving the best of both worlds.
Combinatorial Auctions An important direction in combinatorial auctions related to our work is the design of strategyproof mechanisms that approximate the optimal social welfare using polynomi- ally many queries, see e.g. [7 [4 19 18]. Auctions incorporating predictions have been explored across various settings such as revenue maximization auctions [[] 39 competitive auctions [27] and the online setting [9] is noteworthy that the design of strategyproof, near-optimal auctions
using neural networks 20 36 has been studied extensively for automated mechanism design.
House Allocation Regarding the house allocation problem, Filos-Ratsikas et al. [21] prove that a randomized mechanism, called the Random Priority Mechanism, has approximation ratio of O ((vn). and that this is optimal among all strategyproof mechanisms. There exist lower bounds for all deterministic strategyproof mechanisms which are (2(n²) for unit-sum and (2()) for unit-range, respectively. To the best of our knowledge there is no single point of reference, for these bounds, but can follow from known results in the literature, after observing that deterministic strategyproof mechanisms are ordinal, see [4] 4 A lower bound of ((n²) on the Price of Anarchy for any deterministic mechanism (not necessarily strategyproof) is proved in [1]. In [4 ( bound is proved for the distortion of all ordinal deterministic mechanisms.
2
Model
We consider various mechanism design scenarios that fall into the following abstract mechanism design setting. There is set of n agents and (possibly infinite) set of alternatives A. Each agent i E [1.....n] n can express their preference over the set of alternatives via a valuation function t, which is private information known only to them (also called the type of agent i). The set Tr of possible types of agent consists of all functions b, A + R. Let also T = XieN T denote the space of type profiles.
mechanism defines for each agent set B, of available strategies the agent can choose from. We consider direct revelation mechanisms, i.e., B; = Ti for all i, meaning that the agents' strategies are to simply report their types to the mechanism. Each agent provides bid by E T, which may not match their true type 4, if this serves their interests. A mechanism (S.p) consists of two parts:
selection algorithm: The selection algorithm selects an alternative based on the agents' inputs (bid vector) b = (bI....,b,, bw). We denote by f(b) the alternative chosen for the bid vector bb).
The payment scheme p= (pi...., Pr.) determines the payments, which also depend the bid vector b. The functions p1..... Pr represent the payments that the mechanism hands to each agent, i.e., pa
payment scheme:
R.
The utility of agent i is the actual value they gain from the chosen alternative minus the payment they have to pay, u. (b(b) = (bb)) Pbb).. We consider strategyproff mechanisms. A mechanism is strategyproof, if for every agent, reporting their true type is a dominant strategy. Formally,
ux(t,, b-:) 2 u (t b-:), Vi E [m], t,,t, E Tr. b E T-i
where T-, denotes all parts of T except its i-th part.
In some of our applications (c.g. facility location and scheduling settings), it is more natural to con- sider that the agents are cost-minimizers rather than mility-maximizers. Therefore, for convenience we will assume that each agent aims to minimize cost function rather than maximizing utility function. We stress that some of our applications (e.g. facility location, one-sided matching) fall into mechanism design without money, In those cases will assume (t( = 0, Vt and [r]].
Social objective We assume that there is an underlying objective function that needs to optimized. We consider both cost minimization social objectives (facility location in Section 3 scheduling in Section 4 and welfare maximization (house allocation Section ??, auctions in Section 5). In the context of cost minimization problem, we assume that we given social cost function
5

---

C: x A-AR,, If all agents' types were known, then the goal would be to select the outcome that minimizes C(t, a).
The quality of a mechanism for a given type vector is measured by the cost (E) achieved by its selection algorithm f, MECH(t) = C(t. s(t)), which is compared to the optimal cost OPT(t) minaeA Ctt, a). We denote an optimal alternative for given bid vector t by a".
In most application domains, it is well known that only subset of algorithms can be selection algorithms of strategyproof mechanisms. In particular, no mechanism's 's selection algorithm is optimal for every t, prompting natural focus the approximation ratio of the mechanism's selection algorithm. A mechanism is p-approximate, for some 2 1, if its selection algorithm is Mucu(t) for all possible inputs t.
p-approximate, that is, if 2 OPT(t)
Mechanisms with advice We assume that in addition to the input bid b, the mechanism is also given as a recommeendation/dtiicc, a predicted alternative à E A. but without any guarantee of its [ A natural requirement, known as consistency, requires that whenever the recommendation accurate, then the mechanism should achieve low approximation. A mechanism is said to be 8-consistent if it is 3-approximate when the prediction is accurate, that is, the predicted outcome à is optimal for the given vector. On the other hand, the prediction is poor, robusiness requires that the mechanism retains some reasonable worst-case guarantee. A mechanism is said to be 7-robust if is 7-approximate for all predictions:
quality]]
max MECH(T, a-)
MECH(t, à)
OpT(t) S 3;
max E,
OpT(t) S.
In order to measure the quality of the prediction, we define the recommendation ernor, denoted by C(t,û) as the approximation ratio of the recommended outcome cost to the optimal one i.e., ف OrT(t))
In some of our applications, the social objective a welfare maximization problem, where there an underlying welfare function W T x AA + E+ that needs to be maximized. We adapt our definitions for approximation and for the prediction error accordingly. In particular, the quality of mechanism for given type vector t is measured by the welfare MECH(t, à) = (t,, (t, â)), which is compared OPT(t)
the optimal welfare OpT(t) A W(t, a). mechanism is p-approximate, if p 2 MECH(E)
for all possible inputs Consistency and robustness are defined similarly to the cost minimization OpT(t)
version, while the recommendation error is defined as the approximation ratio أ (ttaa Note that
for both versions, the quality of recommendation exceeds 1, with 1 indicating perfect quality and higher values indicating poorer quality. Additionally, we require a smooth decay of the approximation ratio as function of the quality of the recommendation as it moves from being perfect to being arbitrarily bad. We say that an algorithm is smooth its approximation ratio degrades at a rate that is
at most linear in e 5 6 33
3 Facility Location
In this section, we study mechanisms for the facility location problem in the two-dimensional Euclidean space. There are agents each with a preferred (private) location 2, (Iz (I4,y;), 1 S S in R?. The goal of the mechanism is to aggregate the preferences the agents and determine the optimal facility location at a point (tt in R Given facility at point a E IR_ the private cost (a) of each agent is measured by the distance of z; from a, i.e., l1(a) = ((zz, a), and the private objective of each agent is minimize their cost. Two different social cost functions have been used to evaluate the quality of a location a 2 the egalitarian cost, which measures the maximum cost incurred by a among all agents C(t, a) = max, (a). and the utilitarian cost, which considers the sum of the individual costs i.c., C't, a) = Σ, (a).
We assume that the mechanism is equipped with a recommended point E IR. This is perceived as a recommendation to place the facility at à. For given we denote by a" (t) the optimal location minimizing the social cost, and by p(t) the quality of the recommended outcome, which is defined as
We adapt the notation accordingly incorporate the recommendation à, e.g. the selected alternative is now denoted by (t, a). and the cost of the mechanism by MECH(t, â) etc.

---

the approximation ratio C(t, @) ())(P(( and measures the approximation that would by achieved by placing the facility à. We use the simpler notation a" and ý when t clear from the context.
We note that for this problem our model coincides with the model studied in (2 for facility location problems, although information is the type of the agents, and they assume that they receive signal of the predicted input a, the optimal location w.r.t. the predicted types. Due this perspective, they defined as prediction error the (normalized) distance of their prediction, comparing to the optimal solution w.r.t the actual types. We perceive à as an output advice. Clearly, one can interpret the output as a signal of some sort of predicted data. However, we treat the advice as a recommendation, with unknown quality, and under this perspective the context of this paper. it makes more sense to measure it by the approximation ratio w.r.t the actual (but unknown) input.
perspective is slightly different. Their paper considers that the missing
We showcase this effect in the following example of the faciliiyy location problem in the line for the utilitarian social cost, and we further discuss it in Section Consider 2m agents, see Figure] [ whose preferred locations are clustered in two different points, the one at position (0, 0) and the other at position (1,0), O), where the first point is preferred by agents and the other is preferred by m - 1 agents. The solution a" that minimizes the social cost places the facility point (0, 0) (preferred by m agents) resulting in a total cost of (t = m 1. Now, take two different recommendations â1 and 02 at points (-1.0) 0) and (1, 0) respectively. The prediction error is the same for both points and it is equal to m-1- However, any recommendation between a* and 02 is almost optimal for large m, in contrast to Øj. The quality of the recommendation captures this difference: the social cost for the two recommendations are C(ā1) 3m and C(āg) m, and therefore the quality of the 3m 3m-22 and İo
recommendation for å1 and à2 are respectively ýr
which converge to 3 and
1 respectively as m grows.
m
7
Figure 1: Quality of recommendation versus prediction error
we study the egalitarian cost and show that the Minimum Bounding Box Mechanism, defined by Agrawal et al. [2]. achieves an approximation ratio of p. which combined with the robustness bound of gives an overall approximation guarantee min(p, v2 + 1]. In Section 3.2 we focus on the utilitarian cost and show that the Coordinatewise Median Mechanism with predictions, defined in 2 achieves an approximation ratio of at most V2p which combined with the robustness bound of gives an overall approximation guarantee of min (V2p, x/22+22, }. where À [0,1] is parameter that models the confidence of the designer on the recommendation; larger values of X, correspond to increased confidence about the advice. Finally, in Section 3.3 we compare the bounds obtained function of ğ previously known results obtained function of the prediction error.
In Section 3.1
3.1 Egalitarian Cost
The main result of this section is an approximation ratio of ف for the egalitarian cost, by analyzing the Minimum Bounding Box mechanism defined in [2]. The robustness result for this mechanism (2). gives total approximation ratio of min v2 1}. which we prove that is tight in the full version.
Intuitively, the Minimum Bounding Box mechanism works as follows?: If the minimum rectangle that contains all the imput points 2,, i E {1...., n.,, contains the recommendation point å, then we output à. Otherwise, we select the boundary point with the minimum distance from à.
Theorem 1. The Minimum Bounding Box mechanism is min v2 + 1) -approximate.
Proof.
MECH(t, max d(z,, f(t, a)) S CC(t a) pOPT(t)
The inequality holds because, whenever the prediction is outside the minimum bounding box, the mechanism projects the prediction on its boundaries, in a way that improves the egalitarian loss compared to the initial prediction. When the prediction is inside the bounding box. then f(, a)
7

---

and the inequality holds with equality. The term (v2+1) 1) follows from the robustness guarantee proved in (2]. By selecting the minimum of the two bounds, we get the approximation above.
Remark We remark that when f(t a) = à the upper bound of p is tight. In practice, this happens whenever the recommendation is inside the minimum bounding box defined by the agents' locations.
3.2 Utilitarian Cost
Next, we show 22 upper bound for the utilitarian cost by using the Coordinatewise Median with predictions mechanism defined (2. This mechanism specifies a parameter E [0, 1) which models how much the recommendation trusted. Intuitively," the mechanism works as follows; it creates [Ar] copies of the recommendation à = (I., Then, by treating each coordinate separately, it selects the median point among n [An] in total points; the actual bids 2; = (2i, and the |n] copies of the recommendation. After calculating the medians Ia and yo for each coordinate, defines the outcome to be f(t, a) (Ias ya). In the full version of the paper, we show that our analysis is tight.
Theorem 2. The Coordinatewise Median with Predictions mechanism is min 20, 22, 221442 approximate.
I-X
3.3 Comparison of Error Functions
In this section, we compare the quality of recommendation the error 1) defined in 2 and find instances for which our bounds are tight while previous known bounds are not. We first establish that P S 7 + holds for both the egalitarian and the utilitarian objective. We then show that for both objectives, there exist instances that our bounds are strictly better than the ones proved in 2
Lemma 1. For the egalitarian social cost, there exists an instance where á <. 77+11
Lemma 2. For the utilitarian social cost, there exists an instance where 22p < I+A
2
+1
We give all the proofs in the full version of the paper. Note that for the egalitarian objective, our bound
a refinement of the (tight) bound 1) + from (2). On the other hand, for the utilitarian objective, there exist instances for which the 22x2+2 + bound of [2] is better than ours. For this reason, in the 1+
full version of the paper we observe the behaviour of ý. in real-world datasets 26
4 Scheduling
In this section, we study strategyproof mechanisms for the makespan minimization scheduling problem. In this problem, we have a set of n unrelated machines (the agents) and a set M of m jobs. Each machine has (private) cost byj for each job j. which corresponds to the processing time of job j in machine i. Since we consider only strategyproof mechanisms, each machine declares their true cost lig for each job j; let = (la1, (l. (.m) The goal of the mechanism is to process the machines' declarations t = (t1...
) and subsequently determine both an allocation a(t) of the jobs to the machines and a payment scheme p(t) (p1 (t) machine i for processing their allocated jobs. An allocation is given by a vector = (a1...., an). where a; = (a.1...... ).m), and a:j is set if job is assigned machine and 0 otherwise. An allocation a is feasible if each job is allocated to exactly one machine, i.e., Σien Gij 1, for all j E M, and EiENjeM aij = m. we denote by A the set of all feasible allocations.
(t)). where pt(t) given each
The cost experienced by each machine under an allocation a the total cost of all jobs assigned to it: (a) = (a:) JE 4ij(aj = 4 ag The private objective of each machine i is to maximize their utility (t) (t) - (t)).. In the strategyproof mechanisms that consider here, this happens when each machine declares its true cost. The social cost function that is usually used in this problem in order to evaluate the quality of an allocation is the maximum cost among all machines, which is known as the makespan: C(t, a) = max; (a).
For completeness we include the definition of the mechanism in the full version. We further refer the reader 2 for the exact definition and for the proof of strategyproofness and robustness.

---

We assume that the mechanism is provided with recommendation à E A. which can be seen as suggestion on how to allocate the jobs to the machines. For a given t we denote by (t) the optimal allocation minimizing the social cost function, i.e., a" (t) E arg minle.A C(t, a),, and by OPT(t) the minimum social cost, i.e., OPT(t) outcome with A(t), which is defined as the approximation ratio C(t, /)/(t) and measures the approximation that we would achieve we selected the recommended allocation â. In the notation of a" and P. we drop the dependency on t when it is clear from the context.
C(t, (t)). We measure the quality of the recommended
In the remainder of this section, we introduce a strategyproof mechanism that we call Allocation- ScaledGreedy (Mechanism D. We prove that, given confidence parameter 1 s 8 I n, it exhibits n² (B+1) conssiseentt and 33 robustnesss (Theorem 3.. Next, we investigate the smoothness of this mech-
anism and demonstrate that its approximation ratio is upper bounded by min + 1)), + A, / }. which asymptotically tight (Theorem 4. Furthermore, we establish that, when provided with the outcome as advice, it is impossible to achieve a better consistency- rrnpiittnccy-obusteeess trade-off than the AllocationSSaleddGredy mechanism within the class of weighted VCG mechanisms (Theorem
4.1 AllocationScaledGrredy Mechanism
In this subsection, we introduce a strategyproof mechanism called AllocctionSCaledGrreed which achieves a (B + -cconssstyyyyy (more precisely, (~=² B + c)-cossistency which converges to / +
for large n) and a - -robusttesss where 3 is a confidence parameter ranging from 1 to n, with 1 corresponding to full trust and n corresponding to mistrust. For 3 = which can be interpreted as ignoring the recommendation, the AllocationScaleeGGreeyy mechanism corresponds to the VCG mechanism; in that case, consistency and robustness bounds coincide, giving an n-approximation (same as VCG). Regarding the smoothness of our mechanism, we prove an asymptotically tight approximation ratio of min + 1)², n + A, n2 J
AllocationScaledGreedyy The mechanism sets a weight riy for every machine i and every job j based on the recommendation à. Tij is set to I wherever d:j 1, and 3 wherever d.j = 0, for some e [L, r1.. It then decides the allocation by running the weighted VCG mechanism for each job separately, and by using Tiy as the (multiplicative) weight of machine i, i.e., each job j is allocated to some machine in arg mine(rayfas) that we denote by iz.
Mechanism 1 The AllocationScaledGGreedy mechanism
Input: instance t R"x"" recommendation à R"xm Output: a
1: rij +- if 0.j =1, 1, 3 otherwise, (8 E n1)
2: i f- arg min, (rentig)
3: if = ij then aij = 1 else dij 0, for each (
Remark 2. We remark that the AllocationScaledGredy mechanism for 3 is a simplification of the SimpleScaledGreedy mechanism of [8). In (8), it is assumed that the mechanism is equipped with predictions of the entire cost matrix E.j, for every machine-job pair. The SimpleScaledGrredyy mechanism utilizes this information to define weights Tij that may take values in the range [1. n]. In contrast, IllocationScaleGGreel uses weights with values only or n, for B 1. Notably, despite the limited information available to SeboaationSaaleGGreed both mechanisms share the same consistency and robustness, but SmmpleScaledGreedy lacks the nice property of being smooth, as for very small prediction error, the upproximation ratio has large discontinuity gap (see full version for an example) as opposed to SecaatiionnalleGreeeey (Theorem F.. SimpleScaledGreeet served as intermediate step in (8) in the design of the more sophisticated mechanism ScaledGreedy. (which again relies heavily on the prediction of the entire cost matrix) which achieves the best of both worlds, constant consistency and O rrobusrbssssssss. However, for similar reasons, ScaledGreedy is not smooth either.
Theorem 3. The AllocationSScaleGGreedy mechanism is (n-13 B + -onnsisten and uf robust..
In the following theorem, we show the smoothness result for the AlloeationScaledCGredy mechanism; we show tight approximation ratio depending p. We prove this theorem in the lemmas. In the
9

---

first one, we show that min + 1) + é. " is an upper bound, and in the second one that 10mnn=13pp =tt= "23 is lower bound the approximation ratio of the AllocationScaled- Greedy mechanism. We defer the reader the full version for the complete proof.
ni=1)
Theorem 4. The AllocatioSScaleGGredd mechanism is most min((3 + 1)₂,n n + P, 2 approximate and this bound asymptotically tight.
4.2 Mechanism Optimality
In this subsection, we provide general impossibility results for the class of weighted VCG mecha- nisme the most general known class of strategyproof mechanisms for multi-dimensional mechanism design settings, such as the scheduling problem. We prove that it is impossible to improve upon the AllocationSScaledGreeedy mechanism, given the recommended outcome. More specifically, there is no weighted VCG mechanism with 3-consistencc that can achieve a robustness better than O ((")) highlighting the optimality of AllocctionSealeeGGredy in this class of mechanisms.
Theorem 5. Given any recommendation å, any weighted VCG mechanism that is B-consistent, must also be D n2 rrobusst. for any S 3 S n.
sketch. sketch. We provide a proof sketch of Theorem 5 and refer the reader to the full version for the complete proof. We will consider instances with machines and n² jobs. Let f3-consistent weighted VCG mechanism and recommendation à that assigns every n jobs to distinct machine. Focusing on each machine i, we specify the cost vector such that the optimal allocation matches à. The costs are such that the mechanism must assign each job j either to machine i or to machine ž that receives job j à. Machine should not receive many jobs, otherwise 8-consistency is violated. Consequently, there are many (approximately " weights rij with value much higher comparing to the weight Tizj. i.e., Fly 2 n
28'
Since this is true for each machine there exists a machine i, such that, focusing only on the n jobs that receives in å, there exist approximately x² jobs with value much higher (comparing to i) among all machines. Then it holds that we can assign approximately u jobs to distinct machines such that those machines have high-valued weight for their assigned job; let J be the set of those jobs. We finally consider the instance where each of those machines has cost of 1 for their assigned job and sufficiently high cost a for any other job in J, machine has a cost slightly less than n for jobs in J. 23
2
and all other machines have infinite cost for jobs in J. The cost for any other job that does not belong to J is for any machine. In this instance t. OpT(t) = 1, but the mechanism allocates all jobs of J to machine i, resulting in MECH(t, â) being approximately a² 43- Hence, any 8-consistent weighted
VCG mechanism is 2 "² -rrouust.
5 Combinatorial Auctions
In this section, we show how output advice can integrate with truthful maximal in range (MIR) mechanisms where the goal is to optimize the social welfare (or more generally an affine function) over restricted outcome space. Let M be MIR mechanism with approximation guarantee PM- We define a mechanism that compares the outcome of M with a suggested solution â and selects the one that achieves the highest social welfare. This mechanism remains MIR, as it simply expands the range of possible outcomes to include à, ensuring it remains strategyproof, and is min pM) J-approximate. obtain strategyproof mechanisms for combinatorial auctions with approximation ratio of min 1n/log m for general valuations, min Pē, / /m/logm) m for subadditive valuations, and min (,, 2} for multi-unit valuations.
Combining with the results of 34 17]
'Technically, weighted VCG mechanisms choose weights r; for each machine i, rather than the more general case of choosing ray for each machine i and job j. that consider here. In scheduling, where the valuation domain is additive, jobs can be grouped into clusters, and a distinct VCG mechanism can be applied to each cluster. The composition these mechanisms remains strategyproof for additive domains. The extreme (and more general) case considered here is to cluster the jobs into m clusters.
*We choose do cost for clarity, in fact it suffices to choose instead t.p mechanism does not allocate job to machine i.
ming ming (rgg)es) such that the
10

---

Acknowledgments and Disclosure of Funding
This work has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGeneration Program.
References
Atila Ahdulkadiroglu and Tayfun Sönmez. Random serial dictatorship and the core from random endow- ments house allocation problems. Econometrica, 66(3) 1998.
[2] Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan.
mechanism design: Leveraging predictions for facility location. In David M. Pennock, Ilya Segal, and Sven Seuken, editors, EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 15, 2022, pages 497-528. ACM, 2022. doi: 10. (o.11445/49488635388880
[3] Mattco Almanza, Flavio Chicrichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. Online facility location with multiple advice. NeurlPS, pages 4661 -4673, 2021.
[4] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsike Ratsikas, and Alexandros A. Voudouris. A few queries go a long way: Information distiortoon tradeoffs in matching. J. Artif. Intell. Res., 74, 2022.
[5] Antonios Antoniadis. Christian Coester, Marek Eliás. Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. ACM Trans. Algorithmms 19(2):1:1119:34 2023, doi: 10.1145/ 3582689.
[6] Antonios Antoniadis, Hajo Broersma, Yang Meng. Online graph coloring with predictions. ISCO, volume 14594 of Lecture Notes in Computer Science, pages 289 302. Springer, 2024.
[7] Autotel. Shared cars locations.
2017.
URL https://www.kaaglee.co httgggee..cm//attattts/gggddd
sttotel-sharesd car- location// /data
[8] Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. Strategyproof scheduling with predictions. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume LIPles, pages 11:1-11:22. Schloss Dagstuhl Leibniz-Zentrum Zentrum für Informatik, 2023. doi: I0:4
[9] Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan, and Cherlin Zhu. Online mechanism design with predictions. CoRR, abs/2310.02877 2023. doi: 10. 0044850/ARXIV.23100033
[10] Ben Berger, Michal Feldman, Vasilis Gkatzelis, and Xizhi Tan. Optimal metric distortion with predictions. CaRR, abs/2307.00 0044000779955 2023. doi: 10.48550/ARXIV.237..0777
[11] Toannis Caragiannis and Georgios Kalantzis. Randomized learning- augmentd auctions with revenue guarantees. In IJCAI, pages 2687-2694. ijeai.org, 2024.
[12] T.-H. Hubert Chan, Arnaud Guerquin, and Mauro Sozio. Fully dynamic k-center clustering. www, pages 579-587, ACM, 2018
[13] George Christodoulou, Elias Koutsoupias, and Annamária Kovács. Mechanism design for fractional scheduling on unrelated machines. ACM Trans. Algoritiums, 6(2):38:1-38:11 2010. doi: 10.1 10.114//771877 1721854.
[14] George Christodoulou, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang, and Jinshan Zhang. Social welfare in one-sided matching mechanisms. In AAMAS Workshops (Selected Papers), volume 10002 of Lecture Notes in Computer Science, pages 30-50, 2016.
[15] George Christodoulou, Elias Koutsoupias, and Annamária Kováes. A proof of the nisan-ronen conjecture. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FI,, USA, June 20-23, 2023, pages 672-685. ACM, 2023. doi: 10.1145/3564246.358511
[16] Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwicgelshohn. Fully dynamic consistent facility location. In NewrIPS, pages 3250-3266 02003260,000 2019.
[17] Shahar Dobzinski and Noam Nisan. Mechanisms for multi-unit auctions. J. Artif. Intell. Res., 37:85 98. 2010.

---

[18] Shahar Dobzinski and Jan Vondrák. Impossibility results for truthful combinatorial auctions with submod- ular valuations. J. ACM, 63(1):5:1-5:19, 2016.
[19] Shahar Dobzinski. Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. Math. Oper. Res, 35(1):1-13, 2010. doi: 10.1287/MOOR. 1090. 0436.
[20] Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David C. Parkes, and Sai Srivatsa Ravindranath. Optimal auctions through deep learning. Commun. ACM, 64(8):109 116, 2021. doi: 10. 10.1145/377044.
[21] Aris Filos-Ratsikas, Spren Kristoffer Stiil Frederiksen, and Jie Zhang. Social welfare one-sided matchings: Random priority and beyond. In Ron Lavi, editor, Algorithmic Game Theory - 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 October 2, 2014. Proceedings. volume 8768 of Lecture Notes in Computer Science, pages 1-12. Springer, 2014. doi:
01199888---66--480----
[22] Vasilis Gkatzelis, Kostas Kollias, Alkmini Sgouritsa, and Xizhi Tan. Improved price of anarchy via predictions. In David Pennock, Ilya Segal, and Sven Seuken, editors, EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, Jul 11 15, 2022, pages 529-557. ACM, 2022. doi: 10.1 145/3490486.3538222
[23] Sumit Goel and Wade Caruthers. Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions. Soc. Choice Welf., 61(1):11-34, 2023. doi: 10. 10.1007/00355-002
[24] Ron Holzman, Noa F. Kfir-Dahav, Dow Monderer, and Moshe Tennenholtz. Bundling equilibrium in combinatorial auctions. Games Econ. Rehav., 47(1):104-123 2004.
[25] Gabriel Istrate and Cosmin Bonchis. Mechanism design with predictions for obnoxious facility location. CoRR, abb/2212.095221 2022. doi: 10445550/ARXXI22222205511
[26] Leskavec Jure. Snap datasets: Stanford large network dataset collection. Retrieved December 2021 from http://snap. stanford. eduldata, 2014.
[27] Pinyan Lu, Zonggi Wan, and Jialin Zhang. Competitive auctions with imperfect predictions. CoRR, abs/2309.1544 15414, 2023. doi: 00445500ARXXI..20011555
[28] Thodoris Lykouris and Sergei Vassilvitskii, Competitive caching with machine learned advice. J. ACM, 68 (4):24:1-24:25, 2021. doi: 10. 10//4449447
[29] Reshef Meir. Strategyproof facility location for three agents on circle. In SAGT, volume 11801 of Lecture Notes in Computer Science, pages 18 33. Springer, 2019.
[30] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Commum. ACM, 65(7): 33-35, 2022. doi: 10. 145/3528087
[31] Siddharth Prasad, Maria-Florina Balcan, and Tuomas Sandholm. Bicriteria multidimensional mechanism design with side information. In NeurIPS, 2023.
[32] Ariel D. Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. ACM Trans. Economics and Compur., 1(4):18:1-18:2,, 2013. doi: 10.1145/2542144.542273
[33] Manish Purohit. Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Samy Bengio. Hanna M. Wallach, Hugo Larochelle, Kristen Grauman. Nicolò Bianch,, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 9684-9693. 2018.
[34] Frederick V. Qiu and S. Matthew Weinberg. Settlig the communication complexity of veg-based mechanisms for all approximation guarantees. In STOC, pages 1192-1203 ACM, 2024.
[35] Alvin E Roth. Incentive compatibility in market with indivisible goods. Economics letters, 922:127-132, 1982.
[36] Weiran Shen, Pingzhong Tang, and Song Zuo. Automated mechanism design via neural networks. In Edith Elkind, Manuela Veloso, Noa Agmon, and Matthew E. Taylor, editors, Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '19, Montreal, QC, Canada, May 13-17, 2019, pages 215 223. International Foundation for Autonomous Agents and Multiagent Systems. 2019. URL http::///e/ :/dll acm. arg/citatioon 333116
12

---

[37] U.S Geological Survey. earthquake-dataan database
Earthquake.
URL
htttp:://wwy wtwp://aggle..co//aaaaaaaeeeeeee /
[38] Lars-Gummn Svensson. Strategy-proof allocation of indivisible goods. Social Choice and Welfare, 16(4):
557-567. 1999.
[39] Chenyang Xu and Pinyan Lu. Mechanism design with predictions. In Luc De Raedt, editor, Proceedings of the Thirty-First International Joint Conference Artificial Intelligence, UJAA 2022, Vienna, Austria, 23-29 July 2022, pages 571-577. ijcai.org, 2022, doi: 10.24966/ICAA.2228881.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The model introduced in the abstract and introduction sections is well defined and applied on several mechanism design problems. Both consistency and robustness guar- antees proved for each problem while the applicability of the quality of recommendation is well established on all problems.
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 the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Despite the fact that the proposed model (output prediction and quality of recommendation) can be applied to a wide range of problems, it is clearly stated that the output prediction limited in the sense that considers less amount of information compared to e.g. input prediction.
Guidelines:
The answer NA means that the paper has no 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 vell-specificattin, 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 few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is 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 handle technical jargon.
The authors should discuss the computational efficiency of 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 faimess.
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 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 to not penalize honesty concerning limitations.
14

---

3. Theory Assumptions and Proofs
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 is accompanied by a comprehen- sive set of assumptions and meticulously crafted proof. The proof' well-organized, typically following a logical progression with lemmas presented in the correct order to support the main theorem.
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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide 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 be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
The paper provides detailed descriptions of all algorithms both theoretically and with accompanying code. Additionally, the supplementary material includes comprehensive guides that allow readers to reproduce and study the experimental results in depth.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not 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 dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution 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 often one good way to accomplish this, but reproducibility can also be provided via detailed 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, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
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) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(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).
15

---

(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, described in supplemental material?
Answer: [Yes]
Justification: Full code and data provided in order make the result reproduction possible. Data is open-source and helpful references and links are provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we 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 new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ wttppsscccppbllic////ccc
wtwponmiisiooooooooo.oocoo 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 as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code 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 to understand the results?
Answer: [Yes]
Justification: The paper justifies the dataset selection as suitable for the facility location problem and exposes the parameters of the mechanism used and the predictions created.
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 a 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, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: In the experimental section, our purpose is to compare the behavior of our error with other defined errors based various predictions. The experiments not contain any randomization uncertainty.
16

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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 or the standard error of the mean.
is OK to report I-sigma error bars, but one 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 not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes].
Justification: While there is need for intense computational power, the details of the computing machine's s CPU are included the experimental section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs 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 NeurlPS Code of Ethics https:
Answer: [Yes]
Justification: NeurIPS Code of ethics is fully respected by our paper.
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 circumstances that require deviation from the Code of Ethics.
The authors should make 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 socictal impacts of the work performed?
17

---

Answer: [NA]
Justification: Our work does not have any societal impact, as it is merely a theoretical work. The proposed new mechanisms be used to promote strategyproofness among agents and efficiency.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact 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 to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not contain any results data that could be misused in any way.
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 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.
recognize that providing effective safeguards 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: [Yes]
Justification: All datasets are cited properly and owners are given credit.
Guidelines:
The answer NA means that the paper does not existing assets.
18

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the datasets..paerssttt paperswi thcode. com/datasets package should be provided. For popular datasets,
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 new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember 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 to participants and screenshots, if applicable, as well as details about compensation (if any)?
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 crowdsourcing 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 the NeurIPS Code of Bthies, 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 or 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.
19

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
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 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 the institution conducting the review.
20


Reviews:
[{"review_id": "UL5aP1NS3I", "reviewer": "Reviewer_i6E2", "summary": "This paper studies the problem of mechanism design with prediction and introduces a new framework based on output predictions. Unlike most previous work, which primarily uses input predictions with varying error metrics, this paper considers output predictions and proposes a new error metric that can be applied in various settings. The authors reexamine four previously studied problems with this new prediction and develop consistency, robustness, and smoothness results for each setting.", "questions": "refer to the weaknesses.", "limitations": "1. Refer to the weaknesses\n2. There are some minors, mainly on the direction of inequalities. While I am not sure if my interpretation is correct, I suggest the authors double-check on these points:\n    1. line 203: $(W(t,a)$ -> $C(t,a)$\n    2. line 211: $\\geq$ -> $\\leq$\n    3. equations between line 219 and line 220: $\\leq$ -> $\\geq$", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The concept of output prediction is novel, and the error metric is general, applicable to a range of problems. \n2. The results for the four settings are comprehensive, with some being tight. The paper also provides comparison to input prediction results in some settings.", "weaknesses": "Except for the facility location section, this paper lacks extensive comparisons to previous results with input predictions. While there are tight results with respect to the output prediction, it is not clear to me what does this mean compared to those with input predictions, and what are the relations between them. More comparison results (both theoretical and empirical) between different forms of predictions and error metrics should be conducted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments. We address concerns about potential weaknesses below.\n\n**Question**: *\"Except for the facility location section, this paper lacks extensive comparisons to previous results with input predictions. While there are tight results with respect to the output prediction, it is not clear to me what does this mean compared to those with input predictions, and what are the relations between them. More comparison results (both theoretical and empirical) between different forms of predictions and error metrics should be conducted.\"*\n\n**Our response**: We would like to argue that we thoroughly compare our results with related literature of this relatively new research area. In particular, we consider four different mechanism design settings. Only two of those were studied before within the learning augmented framework (facility location and scheduling) and we thoroughly compare our results with existing literature in both settings. The other two (welfare maximization in auctions and house allocation) were not previously studied using the learning augmented framework, so we would not be able to compare our work with previous results.\n\nAs a matter of fact, all previous work regarding the facility location problem [2, 42] are based on output (not input) predictions, as our work does, but [42] studies multiple facilities (as we describe in the related work section), so it is not closely related, hence incomparable with our work. [2] studies the same problem and this is why we provide a thorough comparison with this work. In particular, this is the perfect setting to demonstrate why our proposed error (the quality of recommendation) is more natural and results in a better refinement of the approximation bounds (in the case of egalitarian cost).\n\nRegarding scheduling games, again we compare our work with all existing previous results [9, 42]. We make an explicit comparison only with [9] which is the state-of-the art (as [9] improves the bounds of [42] as we discuss in the further related work section that appears in Appendix A). Regarding [9], in Remark 2, we provide a thorough explanation of the connection of our AllocationScaledGreedy mechanism that is enhanced with output advice with the two mechanisms proposed in [9] that use input advice instead. Moreover, our optimality bounds (Theorem 5) provide the first trade-off between the amount of provided information and the best achievable bounds. We will follow the excellent suggestion of the reviewer to highlight this separation in the paper and make it more prominent.\n\nRegarding empirical comparison, we would like to emphasize that our work is mainly theoretical. In the facility location problem with egalitarian cost and in the scheduling problem, our theoretical results are sufficient to provide comprehensive comparison of our results with the work of [2] and [9], respectively. For the facility location problem with egalitarian cost, due to space limitation, those comparisons appear in the appendix (section B.4, see Lemmas 4 and 5, and lines 639-643). For scheduling games, the comparison is given in Theorem 5, and Remark 2. The only case where our theoretical comparison with the results of [2] is inconclusive is the facility location problem with utilitarian cost, and this is the reason why we conduct experiments only for this case (Section B.5).\n\nWe thank the reviewer for catching some typos. The correction on line 203 is indeed correct. The inequalities however should stand as they are, as they refer to the cost minimization objective.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Bk9hJlJ8P4", "reviewer": "Reviewer_i3AA", "summary": "The authors propose a novel paradigm for mechanism design augmented with advice. While classically learning-augmented mechanism design assumes input advice, the authors consider output/outcome advice. They use \"quality of recommendation\" to quantify the quality of the advice and provide approximation, consistency, and robustness guarantees as a function of confidence in the advice and quality of recommendation.", "questions": "1. Why do you only conduct experiments in one of the mechanism design settings?", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The authors propose a novel learning-augmented framework and use it to analyze various well-studied mechanism design settings, contextualizing well in the subfield of learning-augmented mechanism design.", "weaknesses": "I see no significant weaknesses, granted that this is not my area of expertise. Formatting in some parts of the paper can be improved (e.g., spacing and commas in line 110 and consistency of the formatting of the citations). As noted below, I was wondering if there is a reason you only conduct experiments for one of the mechanism design settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review. We address their concern below.\n\n**Question**: *\"Why do you only conduct experiments in one of the mechanism design settings?\"*\n\n**Our response**: Our work is mainly theoretical, and we provide tight results for all four problems and comprehensive comparisons with the literature whenever related literature exists (facility location [2,42] and scheduling [9,42]). For the facility location problem with egalitarian cost, due to space limitation, those comparisons appear in the appendix (section B.4, see Lemmas 4 and 5, and lines 639-643). For scheduling games, the comparison is given in Theorem 5, and Remark 2. There is only one exception to that, where our theoretical comparison with the literature [2], is inconclusive, and this is regarding the facility location problem with utilitarian cost. This is the reason why we conduct experiments only for this case (Section B.5).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VqXeSxZsvw", "reviewer": "Reviewer_PWat", "summary": "This paper explores a novel setting in mechanism design where an output is provided as advice to the mechanism. The authors propose consistency, robustness, and approximation properties for strategy-proof mechanisms. They introduce four types of mechanism design problems and corresponding mechanisms, demonstrating their beneficial properties.", "questions": "1. It is not clear why the output advice might be helpful for mechanism design and why the model requires potentially inaccurate output advice. Why can't the model compute an output from the input (type profile) directly and regard this output as advice?\n2. Following the first question, do you have comparative results showing that without output advice, the consistency of the optimal strategy-proof mechanism is strictly worse than that of the strategy-proof mechanism with accurate output advice?\n3. In my understanding, the VCG mechanism provides an output that maximizes social welfare (minimizes cost), so the approximation ratio of VCG should be 1 if the output is computed precisely. How do you explain your results indicating that the approximation ratio of VCG is $\\Theta(n)$, which seems counterintuitive?", "limitations": "Although the poor presentation does not diminish the positive contributions of this paper, it is a drawback that makes the content difficult to understand.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The setting and algorithms used in mechanism design are intriguing. The approximation analysis is well-conducted and represents a significant technical contribution.", "weaknesses": "1. The paper is difficult to follow due to its presentation. For example, the model of this work differs from other works mentioned in the paper [2, 42]. However, these other works are discussed before the authors’ own work in the introduction, which seems redundant. Additionally, the paper often repeats similar sentences.\n2. Many contributions are relegated to the appendix. This is not ideal as the main body should be self-contained, with the appendix used for further verifications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We are sorry that this reviewer (unlike the other two) was not satisfied with the level of presentation of our results. We argue below why we find the reasons for the low presentation score to be a bit too harsh. \n\n**Reviewer PWat stated as two weaknesses:**\n\n*1. \"The paper is difficult to follow due to its presentation. For example, the model of this work differs from other works mentioned in the paper [2, 42]. However, these other works are discussed before the authors’ own work in the introduction, which seems redundant. Additionally, the paper often repeats similar sentences.\"*\n\n*2. \"Many contributions are relegated to the appendix. This is not ideal as the main body should be self-contained, with the appendix used for further verifications.\"*\n\n\n**Response to weakness 1**: In the introduction, we propose a model as an alternative of those discussed in [2,42] so we feel that is important to discuss their model *before* we introduce ours and argue why our model is motivated given those previous models. \n    \n**Response to weakness 2**: We manage to include all the main contributions in the main body, however space limitations force us to state the detailed proofs in the appendix (we have prepared a full version of the paper). This is typical for a theoretical work as ours.\n    \n\n**Response to questions**\n\n**Question 1**: *\"It is not clear why the output advice might be helpful for mechanism design and why the model requires potentially inaccurate output advice. Why can't the model compute an output from the input (type profile) directly and regard this output as advice?\"*\n    \n**Our response**: We are not sure that we understand this question. In a mechanism design setting, agents' types/preferences are private (see lines 176, 236, 311), and are not offered directly to the algorithm designer. Therefore, the input (type profile) is not known. The whole goal of mechanism design is to design strategyproof mechanisms, i.e., mechanisms that provide incentives to the agents to reveal their true types (see Introduction, lines 39-48, and Model Section, lines 179-192). Therefore, we are not sure what is meant by \"computing the output from the input (type profile)\", as this is not offered to the designer.     \n\n**Question 2**: *\"Following the first question, do you have comparative results showing that without output advice, the consistency of the optimal strategy-proof mechanism is strictly worse than that of the strategy-proof mechanism with accurate output advice?\"*\n    \n**Our response**: Again, we are not sure that we understand this question. The definition of consistency requires some sort of advice/prediction (see lines 37, 214-220). We thoroughly compare the bounds of our mechanisms that are enhanced with output advice with the optimal mechanisms without any advice/prediction. \n    \nThose comparisons for the four problems are more specifically the following: \n\n- Facility location problem: The bounds of the optimal strategyproof mechanisms without any prediction/advice is 2 for the egalitarian cost objective (lines 511-514). The consistency (i.e., its approximation ratio when the output advice is accurate) of the Minimum Bounding Box Mechanism (lines 284-286) is 1 (by setting the quality of recommendation, $\\hat{ρ}$, equal to 1 in Theorem 1). \n\n- Scheduling games: The worst-case guarantee of the VCG mechanism (which is the optimal strategyproof mechanism) is the poor approximation of $n$ (lines 522-524). However, the consistency (accurate output advice) of the AllocationScaledGreedy mechanism for the scheduling problem, is asymptotically constant (Theorem 3 for $\\beta$ being a constant) which is strictly better than $n$. \n\n- House allocation problem: Regarding deterministic stategyproof mechanisms, a $\\Omega(n^2)$ bound is known for the unit-sum case and a $\\Omega(n)$ bound is known for the unit-range case (lines 539-543). The TTC with recommended endowment mechanism (Mechanism 5, lines 832-833) is 1-consistent in both cases by setting $\\hat{ρ}=1$ in Τheorem 7. \n\n- Combinatorial auctions: the worst-case approximation ratios of the best known strategyproof mechanisms for the three applications are strictly more than 1 (lines 1000, 1006, 1011), while the MIR with recommended allocation (Mechanism 6, lines 978-979) is 1-consistent (by setting $\\hat{ρ}=1$ in Lemma 16), which is strictly better. \n    \n    \n**Question 3**: *\"In my understanding, the VCG mechanism provides an output that maximizes social welfare (minimizes cost), so the approximation ratio of VCG should be 1 if the output is computed precisely. How do you explain your results indicating that the approximation ratio of VCG is $\\Theta(n)$, which seems counterintuitive?\"*\n\n**Our response**: It is true that the VCG mechanism by definition finds the optimal solution in the case of the social welfare (or cost) objective. However, in the scheduling game we do not study the welfare objective, but the makespan i.e., the minimization of the maximum completion time (see intro (line 98, 119), and as we define in the description of the problem (line 325)). This is the standard objective (see e.g., [9,14,16,42]) in the scheduling literature (defined in the description of the problem, line 325). Regarding the makespan objective, VCG is known to be [16] the optimal strategyproof mechanism but with a very poor approximation ratio of $n$ (as stated in lines 522-524).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank the reviewers for their thorough reviews and thoughtful comments. We respond to each reviewer's questions with a separate reply to each of their reviews.

Meta-review: This paper proposes a new type of prediction for learning-augmented mechanism design: instead of predictions about the inputs to the mechanism, it considers predictions about the output. This new type of prediction is interesting, well-motivated, and novel. Strong results are achieved and this framework could also initiate some follow-up work.
Decision: Accept (spotlight)