Mechanism Design with Predictions

1 Introduction

A recently popular trend in algorithmic design is augmenting (online) algorithms with imperfect predictions. This line of work suggests that there exists an opportunity to bypass the worst-case lower bounds of online problems, which are caused by the uncertainty of the future. In this setting, the algorithm is given access to error-prone predictions, and its performance is bounded in terms of the quality of the predictions. The algorithm should perform better than the worst-case bound with accurate predictions, and never perform much worse than the best pure online algorithm even if the prediction error is large. Many classic online problems have been considered in the context, such as ski rental [Purohit et al., 2018; Gollapudi and Panigrahi, 2019; Anand et al., 2020], caching [Lykouris and Vassilvitskii, 2018; Rohatgi, 2020], and scheduling [Purohit et al., 2018; Lattanzi et al., 2020; Im et al., 2021; Li and Xian, 2021].

Mechanism design and online algorithm design share some similarities. Both of them need to deal with missing information. Due to the uncertainty about the future or the agents' private information, algorithms (mechanisms) have to be overly cautious and thereby worst-case bounds arise. Thus, it is interesting to investigate if predictions can help with mechanism design. This paper proposes a study of mechanism design with predictions. For generality and simplicity, we directly use agents' private information as predictions. This is justifiable in many applications. For example, in repeated auctions, we may use historical bidding records as the predictions. We note that there are several related works [Medina and Vassilvitskii, 2017; Antoniadis et al., 2020]. In [Medina and Vassilvitskii, 2017], repeated posted price auctions were considered. In [Antoniadis et al., 2020], the authors mainly focused on developing an online bipartite matching algorithm with predictions and noticed that the algorithm can be converted to a truthful mechanism. In this paper, we consider mechanism design with predictions more systematically and investigate a number of different mechanism design settings.

∗This work was supported by Science and Technology Innovation 2030 - "The Next Generation of Artificial Intelligence" Major Project No.2018AAA0100900.

†The corresponding author.

1.1 Challenge

We follow the terminology in [Purohit et al., 2018] which is now standard: say a mechanism's consistency and robustness are its approximation ratios for accurate predictions and for arbitrarily inaccurate predictions respectively. Due to the truthfulness requirement in mechanism design, it is subtle to use predictions to get a good consistency and robustness.

A mechanism consists of two algorithms: the allocation algorithm and the payment algorithm. Due to truthfulness, the allocation algorithm needs to satisfy a certain monotone property, which is a global property of the algorithm. It is usually infeasible to change the allocation for certain inputs based on the predictions without changing the allocation for other inputs. For example, a widely-used approach to ensure robustness in online algorithm design is switching to pure online algorithms when the predictions are found to be unreliable. However, in mechanism design, switching to traditional mechanisms when the prediction error is large may hurt truthfulness. The agent who benefits more from the traditional mechanism may misreport the private information such that the prediction error looks large.

Thus, we need to design the allocation algorithm with predictions as a whole mapping to satisfy the monotone property. This gives a big challenge to maintain a good consistency and robustness. In other words, it is much less flexible to design a truthful mechanism than an (online) algorithm.

1.2 Our Contributions

We study four very different and well-studied mechanism design problems and observe that predictions are indeed helpful.

Revenue-Maximizing Single-Item Auction

Maximizing the revenue is one of the most fundamental problem in auction design. There is a rich literature (e.g. [Myerson, 1981; Goldberg et al., 2001; Azar et al., 2013]). We consider the revenue-maximizing single-item auction and compare the revenue to the highest bid, the most ambitious benchmark. It is well-known that there is no good mechanism in worst-case mechanism design with respect to this goal. If we assume that all bids belong to [1, h], no deterministic truthful mechanism has an approximation ratio better than h ( [Goldberg et al., 2001]).

With perfect predictions, it is trivial to achieve 1approximation since we can simply run anonymous pricing scheme and set the price as the highest predicted value. However, this mechanism is very fragile. The approximation ratio drops to infinity even if there is only a tiny error in the predictions. This is of course highly undesirable. To address the issue, we propose a notion of error tolerance to measure how much prediction error the mechanism can tolerate to get a reasonable good approximation. Let η ≥ 1 be the relative prediction error, where η = 1 means that there is no error. We give a deterministic truthful mechanism with γ-consistent and h-robust, where the robustness ratio matches the worst-case bound of h in the traditional setting and the consistency ratio γ ≥ 1 is a parameter we can choose. The approximation ratio smoothly increases as a function of γη when η ≤ γ, and then has a big drop after η > γ. Therefore, there is a tradeoff between the consistency and the error tolerance. Moreover, we prove that such a tradeoff is necessary and in some sense optimal for all deterministic truthful mechanisms. Our mechanism is simple and practical. It is the second price auction with individual reserve prices, where these reserves are set based on the predictions.

Frugal Path Auction

Path auction is a reverse auction, where the auctioneer needs to buy a path and pays the edges in the path. The goal here is to minimize the total payment and the benchmark is the second cheapest path. This is a classic problem in frugal mechanism design. The problem was coined by [Archer and Tardos, 2002]. They showed that the VCG mechanism obtains an approximation ratio of Θ(n), where n is the number of agents, and the ratio is the best possible [Elkind et al., 2004]. We obtain a deterministic truthful mechanism with 2γ-consistent and (n2 /γ)-robust. In terms of error tolerance, the approximation ratio smoothly increases as a function of γ(1 + η) as long as η ≤ γ. Here we observe a three way tradeoff among consistency, robustness and error tolerance. The mechanism is the generalized VCG mechanism (a.k.a affine maximizer), where the weights for different agents are set based on the predictions.

Besides the VCG mechanism, [Karlin et al., 2005] proposed √ -mechanism for frugal path auction. The approximation ratio of √ -mechanism is still Θ(n), but it can outperform the VCG mechanism in some graphs. Later, this technique was generalized to more problems in frugal mechanism design [Chen et al., 2010]. We can also apply our technique to √ -mechanism to get a similar improvement when predictions are given.

Truthful Job Scheduling

Truthful mechanism for scheduling unrelated machines is the center problem of the very first algorithmic game theory paper [Nisan and Ronen, 2001], whose goal is to minimize the makespan. This problem is very different from the previous two settings in two aspects: it is a multidimensional mechanism design problem and the objective is not related to the payment. In [Nisan and Ronen, 2001], the authors showed that the VCG mechanism gives an approximation ratio of m, where m is the number of machines, and proved a lower bound of 2 for any deterministic truthful mechanism. They conjectured that no deterministic truthful mechanism has an approximation ratio better than m. Many papers worked on closing the gap [Christodoulou et al., 2007; Koutsoupias and Vidali, 2007; Ashlagi et al., 2009; Giannakopoulos et al., 2020; Dobzinski and Shaulker, 2020; Christodoulou et al., 2020]. The closest result so far proves a lower bound of Ω(√m) [Christodoulou et al., 2020].

For this problem, we give a deterministic truthful mechanism with approximation ratio of O(min{γη2 , m3 γ 2 }), where again γ is the consistency parameter we can choose and η is the prediction error. Here, we compute an (approximate) optimal allocation based on the predicted information and use that allocation as a guide for the mechanism.

Two-Facility Game on a Line

Finally, we consider a mechanism without money: twofacility game on a line. This setting was coined by [Procaccia and Tennenholtz, 2009], where the authors gave an upper bound of n - 2 and a lower bound of 1.5 for deterministic truthful mechanisms. The lower bound was later improved to 2 [Lu et al., 2009] and (n - 1)/2 [Lu et al., 2010]. Finally, [Fotakis and Tzamos, 2014] showed a tight lower bound of n - 2.

Since the space of truthful mechanism without money is more restricted, it is even more difficult to make use of predictions here. We get a deterministic truthful mechanism with (1 + n/2)-consistent and (2n - 1)-robust, whose consistency ratio is slightly better than the best known mechanism. Whether there is a mechanism with o(n)-consistent and a bounded robustness is a very interesting open question.

2 Preliminaries

This section introduces the terminology necessary to understand the paper. An expert can skip it directly. We take the single-item sealed-bid auction for an example. In the auction, there is a seller that has a single good and several bidders who are interested in buying the good. Each bidder i has a private value vi representing the maximum willingness-to-pay for the item. Each bidder i privately tells the auctioneer a bid bi, while the auctioneer decides who is the winner (i.e. the allocation rule) and how much he needs to pay (i.e. the payment rule). Say the bidder who sets bi = vi is a truthtelling bidder. If a bidder is the winner, his utility is vi - pi, where pi is the price he needs to pay. Otherwise, the utility is 0.

Definition 1. ([Roughgarden and Iwama, 2017]) A mechanism is truthful if for any bidder i, setting bi = vi always maximizes his utility regardless of other bidders' bids, and the utility of any truthtelling bidder is non-negative.

Now we state a widely-used theorem proposed by [Myerson, 1981].

Definition 2. (Monotonicity) An allocation rule is monotone if the winner still wins when he increases the bid unilaterally.

Theorem 1. (Myerson's Lemma [Myerson, 1981]) For a single-parameter environment, the mechanism is truthful only if its allocation rule is monotone, while for any monotone allocation rule, there exists an unique payment rule which makes the mechanism truthful. Moreover, such a payment rule can be given by an explicit formula.

For single-item auctions, the unique payment is the winner's threshold bid.

Definition 3. (Threshold Bid) Given a single-item auction mechanism and the bid of each bidder, the threshold bid of a bidder is the minimum bid that he could make and win the auction when all other bidders fix their bids.

3 Revenue-Maximizing Single-ItemAuction

In this section, we consider revenue-maximizing single-item auction. There is one item and n > 1 bidders. Each bidder i has a private value v∗ i ∈ [1, h] and reports a bid bi ∈ [1, h]. Use a n-dimensional vector X to denote the allocation of the item, where each entry xi is either 1 or 0 and it equals 1 only if bidder i wins. Each bidder i has an utility ui = xi · v∗ i - pi, where pi is the payment. The auctioneer aims to design a truthful mechanism that maximizes the selling price, and the benchmark is the highest private value. In mechanism design with predictions, we are given access to the predictions of bidders' private values, denoted by ˆ V = {ˆ vi}i∈[n]. The predictions are erroneous and we define a natural prediction error η :=maxi∈[n]{ v∗ i ˆ vi , ˆ vi v∗ i }.

Theorem 2. There exists a deterministic truthful mechanism parameterized by γ ≥ 1 with approximation ratio at most min{f (η), h} where

From Theorem 2, the claimed mechanism has a robustness ratio h, which is the best possible in the traditional setting. The consistency ratio of the mechanism is determined by a parameter γ. Notice that the function f(η) is piecewise and has a "jump" when η = γ. We refer to the length of the first piece in f(η) as the error tolerance. Later in this section, we will prove that this jump point is unavoidable for any deterministic truthful mechanism. In order to communicate our main ideas more clearly, this section simplifies the algorithm and the analysis by assuming that the number of bidders is at least 3. In this paper's full version, we show that removing this assumption still gets the claimed approximation ratio.

Algorithm 1 Single-ItemAuction with Predictions

Input: The predicted private values ˆ V = {ˆ vi}i∈[n], the bids B = {bi}i∈[n] and a parameter γ ≥ 1.

Output: The winner and the payment.

• 1: Reindex the bidders in the decreasing order of their predicted values.
• 2: Assign a bar br(i) to each bidder i. Initially, br(i) ← 1 ∀i ∈ [n].
• 3: if ∀i ∈ [n], ˆ vi ≥ ˆ v1/γ 2 then
• 4: Update the bar of bidder 1: br(1) ←max{ˆ v1/γ, 1}.
• 5: else
• 6: Update the bar of bidder 1: br(1) ←max{ˆ v1/γ, 1}.
• 7: For each bidder i with ˆ vi ≥ ˆ v1/γ 2 , update the bar: br(i) ← max{ˆ v1/γ 2 , 1}.
• 8: end if
• 9: Define a bidder set S := {i ∈ [n]|bi ≥ br(i)}.
• 10: return the bidder j ∈ S with the highest bid and the threshold bid θ(j).

3.1 Mechanism

We start by giving some intuitions. For simplicity of notation, reindex the bidders in the decreasing order of their predicted values. So now bidder 1 has the largest predicted value ˆ v1. Notice that if the predictions are error-free, letting bidder 1 win and charging him ˆ v1 gives the optimal solution. Inspired by this, a natural idea is the following. If the reported bid b1 is no less than the predicted value ˆ v1, let bidder 1 win. Otherwise, ignore bidder 1 and let the remaining bidder with the highest bid win.

Clearly, this allocation rule is monotone. Then due to Theorem 1, we can ensure the truthfulness by charging the winner the threshold bid. More precisely, if bidder 1 wins, the payment is ˆ v1, while if bidder i (̸= 1) wins, the payment is the second highest remaining bid. The mechanism has a consistency ratio of 1, meaning that it gets the optimal value ˆ v1 when η = 1. However, the approximation ratio will increase to h immediately even if η is only slightly larger than 1. Thus, although the robustness ratio of the mechanism is h which is the best possible in the traditional setting, we cannot refer to it as an ideal mechanism due to the tiny error tolerance.

One way to get a mechanism with a larger error tolerance is setting a lower bar for bidder 1. For example, let bidder 1 win if b1 is at least ˆ v1/γ, where γ is a parameter ≥ 1. The mechanism will have a comparable performance when η ≤ γ, because bidder 1 will always win and the threshold bid is at least ˆ v1/γ. We build on this idea to give our mechanism. Moreover, we refine the way we handle other bidders such that the approximation ratio will not increase to h immediately once the prediction error becomes larger than γ. The mechanism is described in Algorithm 1.

3.2 Analysis

Observing that in Algorithm 1, increasing any bidder's bid will only improve the chance that he wins, the allocation rule is monotone. Hence, we have the following lemma.

Lemma 4. Algorithm 1 is a truthful mechanism.

Now we focus on the approximation ratio analysis. We first give a simple proof of the robustness ratio h, and then show that the approximation ratio is at most f(η).

Lemma 5. Algorithm1 has an approximation ratio at most h.

Proof. The upshot is that for any bidder i, θ(i) ≥ br(i), because if bi < br(i), bidder i will not be included in S and lose the auction. Since br(i) ≥ 1 for any bidder i, the winner's payment is at least 1. Note that h is the upper bound of all bids. We have the optimal selling price OPT ≤ h, implying that the approximation ratio is at most h.

We distinguish two cases to analyze the other bound: (1) η ≤ γ and (2) η > γ. The main difference of the two cases is whether we can ensure that bidder 1 is in S or not.

Lemma 6. The approximation ratio of Algorithm 1 is at most γη if η ≤ γ.

Proof. In this case, we can claim that bidder 1 is always in S, i.e., b1 ≥ br(1). If br(1) = 1, b1 is always at least br(1). Otherwise, br(1) = ˆ v1/γ. Since v∗ 1 ≥ ˆ v1/η and η ≤ γ, we still have b1 ≥ br(1).

Suppose that the winner is bidder j and the optimal payment is the private value v∗ k of bidder k. If j = 1, the payment is θ(1) ≥ br(1). Otherwise, the threshold bid of bidder j is at least b1 ≥ br(1). Observing that regardless of which case, the payment is at least br(1), we can bound the payment PAY as follows:

completing the proof.

Lemma 7. The approximation ratio of Algorithm 1 is at most max{γ 2 η2 , hη γ 2 } if η > γ.

Proof Sketch. In this case, we cannot ensure that b1 ≥ br(1). Notice that if bidder 1 is still included in S, following the same analysis in Lemma 6 gives the ratio γη. So we only need to focus on the case that b1 < br(1). We further distinguish two subcases: (1) ∀i ∈ [n], ˆ vi ≥ ˆ v1/γ 2 , and (2) ∃i ∈ [n], ˆ vi < ˆ v1/γ 2 . Basically, the two terms in the target approximation ratio come from these two subcases respectively. For the first subcase, we observe that the ratio between any two bidders' predicted values is at least 1/γ 2 . This implies that for any two bidders, the ratio between their real values is at least 1/(γ 2 η2 ). Thus, using the second price mechanism should return a payment at least OPT/(γ 2 η2 ). For the second subcase, the payment could drop to 1. But here, we can show that the optimal payment is at most hη/γ 2 , which proves the claimed ratio. Due to space, the detailed proof is omitted.

Combining the above lemmas, we can prove Theorem 2.

3.3 Lower Bounds

This subsection gives two lower bounds of the auction problem. We only state the theorems here and provide the proofs in the full version of this paper.

Theorem 3. For any deterministic truthful mechanism with a consistency ratio γ, the approximation ratio is at least h/η when η > γ.

For any γ ≤ h1/5 , when η is slightly larger than γ, our ratio f(η) is close to h/γ, which matches the lower bound given by Theorem 3. To show the optimality of the mechanism's performance when η ≤ γ, we assume that η is sampled uniformly from [1, γ] and prove a lower bound of the expected approximation ratio.

Theorem 4. For any deterministic truthful mechanism with a consistency ratio γ (< √h), supposing that the prediction error η is a random variable uniformly distributed on [1, γ], the expected approximation ratio is at least (γ+1)γ/2, which is exactly the expected ratio of Algorithm 1.

4 Frugal Path Auction

In frugal path auction, there is a graph G = ({s, t} ∪ V,E) with at least two edge-disjoint s-t paths. Each edge e ∈ E is owned by an agent and the cost c∗e is a secret known only to that agent. Denote the number of agents by n. Each agent e submits a sealed bid be. Then, the auctioneer selects an s-t path L as the winner and gives payment pe to each e ∈ L. If an agent wins, the utility is pe - c∗e . Otherwise, the utility is 0. The goal is to design a truthful mechanism such that the total payment ∑e∈E pe is minimized. In mechanism design with predictions, the auctioneer is given access to the edge cost predictions ˆ C = {ˆ ce}e∈E.

For a frugal mechanism, a standard way to measure its performance is frugal ratio. The formal definition of frugal ratio is a long statement (see [Karlin et al., 2005]). For simplicity, this section states an equivalent but more accessible definition specific to the path auction problem given in [Archer and Tardos, 2002]. Say a frugal path mechanism M. For an instance I, use P(I) to denote the total payment of M and S(I) to denote the cost of the second cheapest s-t path. The frugal ratio of a mechanismM is defined to be FR = supI P (I)/S(I).

For the brevity of the algorithm's statement and analysis, we assume that the graph consists of just some parallel s-t paths and each edge has a positive cost. Notice that the assumptions do not affect the problem's hardness. The worstcase bound is still Ω(n) under the assumptions. The mechanism is described in Algorithm 2.

Theorem 5. Algorithm 2 is truthful and has a frugal ratio at most f(η), where the prediction error η := maxe∈E{ c∗e ˆ ce , ˆ ce c∗e } and

Mechanism Intuition. The basic intuition is the same as the single-item auction problem. That is, we set a bar for the path with the minimum predicted cost and treat it differently when the reported cost is below or above the bar. Recollect that in single-item auction, if b1 is below the bar, the mechanism ignores bidder 1 directly. However, things are different in path auction. Ignoring a path may lead to an unbounded

Algorithm 2 Frugal Path Auction with Predictions

Input: A graph G, the predicted edge costs ˆ C = {ˆ ce}e∈E, the bids B = {be}e∈E and a parameter γ ∈ [1, n1/3 ]. Output: The winner and the payments.

• 1: Say path ˆL is the path with the minimum predicted cost.
• 2: For any s-t path L′ ̸= ˆL, set its weight w(L′ ) ← 1.
• 3: if ∀e ∈ ˆL, be ≤ γˆ ce then
• 4: Set w(ˆL) ← γ/n.
• 5: else
• 6: Set w(ˆL) ←n/γ.
• 7: end if
• 8: return the path L with the minimum weighted bid and the threshold bid θ(e) of each edge e ∈ L.

frugal ratio. For example, consider a graph with three edgedisjoint s-t paths. Their costs are 1,1 and ∞ respectively. Say we ignore the first path. Then any truthful mechanism has to pay ∞, but the second cheapest path cost is only 1. Hence, the frugal path mechanism needs a more careful design after setting up a bar. When the bid of the predicted cheapest path is far larger than the predicted cost, instead of ignoring it directly, we assign a large weight to it so that the path is still a candidate but less competitive. The proof sketch of Theorem 5 is stated in the following while the detailed proof is provided in the full version of this paper.

Proof Sketch of Theorem 5. The truthfulness proof is simple. We can easily show that the weight function guarantees the monotonicity, and thus the truthfulness. For the ratio analysis, we distinguish two cases based on whether η is at most γ. The reason is that when η ≤ γ, we can ensure that the weight of ˆL is always γ/n, and thereby ˆL always wins. Analyzing the threshold bid of each edge in ˆL is a bit subtle, but the intuition is the following. If edge e ∈ ˆL cannot win when its bid is larger than γˆ ce, its threshold bid is at most γˆ ce, implying that the total payment of all such edges is at most γη times the second cheapest path cost. Otherwise, the threshold bid is bounded by γ/n times the second cheapest path cost because the weight of ˆL becomes n/γ when be > γˆ ce. Then, the total payment of these edges should be at most γ times the second cheapest path cost. For the case that η > γ, we show that regardless of which path wins, the threshold bid of each winning edge is at most n/γ times the second cheapest path cost. Thus, the total payment gives a frugal ratio of n2 /γ.

Essentially, Algorithm 2 can be viewed as a variant of the VCG path mechanism which incorporates predictions. Besides the VCG path mechanism, there is another famous mechanism for path auction called √ -mechanism [Karlin et al., 2005]. Leveraging the idea of √ -mechanism can improve the robustness slightly. In some graphs, the robustness ratio decreases by a factor of √n. See more details in the full version of this paper. In the following, we give a lower bound to show the optimality of Algorithm 2 when η is small.

Theorem 6. For any deterministic truthful mechanism, the frugal ratio is Ω(η2 ) given any η = O(√n).

Algorithm 3 Truthful Job Scheduling with Predictions

Input: Machines M, jobs J, the bid matrix {bij}(i,j)∈M×J, the predicted matrix {ˆ tij}(i,j)∈M×J and a parameter γ ∈ [1, m].

Output: The allocation matrix X and the payment matrix P .

• 1: Construct a new processing time matrix ¯ T as follows.
• 2: for each job j ∈ J do
• 3: Define ˆ t(min) j := mini∈M ˆ tij .
• 4: For each machine i ∈M, set ¯ tij ← min{ˆ tij, (m/γ) · ˆ t(min) j }.
• 5: end for
• 6: Compute the optimal allocation ¯X of the scheduling instance ¯ T .
• 7: for each job j ∈ J do
• 8: Use k to denote the machine with ¯xkj = 1.
• 9: if ˆ tkj > ¯ tkj then
• 10: Call job j a greedy job.
• 11: Define l := argmini∈M ˆ tij and set up a weight function: wlj ← γ/m and wij ← 1 ∀i ̸= l.
• 12: else
• 13: Call job j a non-greedy job.
• 14: Set up a weight function: wkj ← γ 2 /m2 and wij ← 1 ∀i ̸= k.
• 15: end if
• 16: Let themachine z with theminimumweighted bidwin and pay the threshold bid θzj for job j. Namely, set xzj ← 1, pzj ← θzj and xij , pij ← 0 ∀i ̸= z.
• 17: end for
• 18: return X = {xij}(i,j)∈M×J and P = {pij}(i,j)∈M×J.

When η = γ - ϵ for a tiny positive ϵ, the frugal ratio of Algorithm 2 approaches the lower bound.

5 Truthful Job Scheduling

In this section, we consider the truthful job scheduling on unrelated machines. In the problem, there are n jobs J and m machines M. Each machine i is owned by a selfish agent, and the processing time t∗ij of each job j on machine i is a private value known only to the agent. Without loss of generality, assume that tij > 0. Each job has to be assigned to exactly one machine. The mechanism will ask each machine i to report a processing time bij for each job j, and then allocate jobs. Once job j is assigned to machine i, the mechanism pays the machine (agent) pij . Use X = {xij}(i,j)∈M×J to denote the job allocation matrix, where xij is 1 if job j is assigned to machine i, otherwise 0. The makespan of an allocation X is the completion time of the last job, i.e., MS := maxi∈M ∑j∈J xijt∗ij . The utility of each machine i is defined to be ∑j∈J (pij - xijt∗ij ). The goal is to design a truthful mechanismwhichminimizes themakespan. Inmechanism design with predictions, we are given the predicted processing times ˆ T = {ˆ tij}(i,j)∈M×J. The prediction is errorprone and the prediction error η := max(i,j){ ˆ tij t∗ij , t∗ij ˆ tij }.

This problem is very different from the previous two problems. First, it is not a single-parameter environment. For each machine i, the private value is a n-dimensional vector < t∗i1 , ..., t∗in >. Second, the objective function is not directly related to the payment. The mechanism gives the winners money but the goal is to minimize the makespan. Thus, the payment rule in truthful scheduling is only for the purpose of ensuring the truthfulness. We describe the mechanism in Algorithm 3 and claim the following theorem.

Theorem 7. Algorithm 3 is truthful and has an approximation ratio O(min{γη2 , m3 γ 2 }).

Mechanism Intuition. We deal with each job independently. Thus, each job can be viewed as a single-item auction, and we can apply our technique without hurting the truthfulness. Similar with the previous two mechanisms, we retain the same job allocation when η is small, in order to build the consistency and the error tolerance. We first compute the optimal assignment for the predicted instance, and set up a weight function of machines such that selecting the machine with the minimum weighted bid for each job gets the optimal assignment. Then we decrease the weights of some machines by a factor. This ensures that when η is small, these machines still obtain the minimum weighted bids, and thereby the job assignment remains unchanged. For the robustness guarantee, we observe that if the ratio between any two machines' weights is at most c, the approximation ratio of the mechanism must be bounded by c · m. Thus, we round the predicted instance such that after rounding, the ratio between any two machines' weights is bounded. Notice that using the rounded weights directly may hurt the consistency because the processing time of a job could be different in the predicted instance and the rounded instance. To maintain a good consistency and robustness, we only use the rounded weights to guide the jobs that share the same processing time in both of the two instances. For all other jobs, we set up their weights such that they can be assigned greedily when η = 1.

Proof Sketch of Theorem 7. The proofs of the truthfulness and the robustness are simple. For each job, the allocation rule is monotone and the ratio between any two machines' weights is bounded. The tricky part is to show the O(γη2 ) bound. We first show that the consistency ratio is O(γ). Suppose that η = 1. Partition all jobs into two sets: greedy jobs and non-greedy jobs. For non-greedy jobs, we claim that their assignment is the same as the optimal assignment of ¯ T, and thus, their contribution to the makespan is at most the optimal makespan of ¯ T . For greedy jobs, we show that although they are assigned differently, shifting each one to the machine with the minimum processing time will not increase the makespan too much. Summing over the contributions of the two job sets gives the O(γ) consistency ratio. For erroneous predictions, we distinguish two cases based on whether η is at most √m/γ. For both of the two cases, we can obtain the O(γη2 ) approximation ratio.

6 Two-Facility Game on a Line

In this section, we consider the problem of locating two facilities on a real line to serve a set of selfish agents. In the problem, there are n agents and each agent i has a private location Algorithm 4 Two-Facility Game with Predictions

Input: The reported location profile X = {x1, ..., xn} and the predicted locations ˆ V = {ˆ v1, ..., ˆ vn}.

Output: The two facility locations.

• 1: Compute the optimal facility locations ˆl1, ˆl2 for ˆ V . We assume w.l.o.g. that ˆl1 is the facility which attracts more agents and there exists an agent ˆi with ˆl1 = ˆ vˆi .
• 2: Set l1 ← xˆi .
• 3: Define dA := max xj≤xˆi (xˆi -xj) and dB := max xj≥xˆi (xj - xˆi ).
• 4: if dA ≤ dB then
• 5: Set l2 ← l1 +max{2dA, dB}.
• 6: else
• 7: Set l2 ← l1 -max{dA, 2dB}.
• 8: end if
• 9: return l1 and l2.
• v∗ i . The mechanism asks each agent i ∈ [n] to report the location xi ∈ R, and then outputs two facility locations l1, l2 ∈ R. Each agent i wants to minimize the connection cost ci, which is the distance between v∗ i and the nearest facility. The goal is to design a truthful mechanism which minimizes the total connection cost. In mechanism design with predictions, we are given the predicted location ˆ vi of each agent i ∈ [n]. We show that in an environment without money, we can still use predictions to improve the approximation ratio slightly. The mechanism is described in Algorithm 4.

Theorem 8. Algorithm 4 is a truthful mechanism with (1 + n/2)-consistent and (2n - 1)-robust.

Mechanism Intuition. The mechanism builds on the line mechanism [Lu et al., 2010]. We notice that in the line mechanism, there exists an arbitrarily selected dictator. Thus, a natural idea is leveraging predictions to select the dictator. An advantage of this idea is that the robustness can always be guaranteed because selecting any agent to be the dictator obtains an O(n) approximation ratio. Then we check the structure of optimal solutions, and find that for any instance, there always exists an agent such that the line mechanism's performance can be improved if letting this agent be the dictator. Thus, setting the dictator to be such an agent in the predicted instance makes the mechanism consistent.

Proof Sketch of Theorem 8. Since Algorithm 4 is essentially the line mechanism, the truthfulness and the robustness are proved directly. The remaining part is the consistency analysis. For the case that η = 1, we partition agents into two sets based on the facilities that serve them in the optimal solution. Say S1 is the agents served by facility ˆl1. For any agent in S1, the current connection cost is at most the connection cost in the optimal solution because facility ˆl1 opens. According to the definition of ˆl1, at least half of agents are in S1. For the remaining agents, we show that each one's connection cost is at most OPT plus the connection cost in the optimal solution. Thus, the total connection cost is at most (1+n/2)OPT.