acceptodds
Under review as a conference paper at ICLR 2027

Learning-Augmented Strategyproof Mechanisms for Two-Facility Location

Abstract

In learning-augmented mechanism design for two-facility location, we examine strategyproof mechanisms that, given access to predictions, elicit facility location preferences of the agents truthfully and determine two facility locations on the line that approximately minimize the utilitarian social cost, defined as the sum of agents' distances to their closest facilities. Because the predictions may be inaccurate, we evaluate the mechanisms' performance in terms of their consistency and robustness, which are the approximation guarantees on the utilitarian social cost when the prediction is correct and when the prediction is arbitrary, respectively. We consider two types of predictions, namely the locations of an optimal pair of facilities and the preferred location of each agent, and investigate the consistency and robustness of strategyproof mechanisms with access to each of the two prediction types. For deterministic strategyproof mechanisms, we characterize the optimal consistency-robustness trade-off for each prediction type and provide mechanisms that attain the trade-off exactly. Predictions of optimal facility locations cannot improve upon the optimal prediction-free approximation ratio, whereas predictions of agent preferences yields a nontrivial trade-off. For randomized mechanisms, we provide mechanisms that establish upper bounds on the consistency-robustness trade-off for each prediction type, and complement them with a uniform lower bound.

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

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_EmG9OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the mechanism design problem to locate two facilities on a line while having available a prediction via an ad hoc oracle.

The paper considers the case in which the oracle provides a prediction of the agents' preferences or a prediction of the optimal facility placements. The authors then study the problem of outlining the optimal tradeoff between consistency, intended as the worst case guarantee when the prediction is accurate, and robustness, intended as the worst case approximation ratio when the prediction is arbitrary. The authors consider both deterministic and random mechanisms and propose different mechanisms to cover the different frameworks considered.

Critical strengths

The paper considers a problem that is relevant to the AI community. Being able to include predictions in an algorithmic mechanism design problem is a timely problem. The trade.off presented are novel.

Critical weaknesses

The paper presents several issues, mostly due to how the results are presented. I had to read multiple times the statements and the proofs in order to ensure I understood correctly the meaning of the sentences and the argument used in the proof-steps. .

Some more specific points, section by section.

In the our contribution section:

  • "A common lower bound rules out perfect consistency with uniformly finite robustness " does this mean that there is a lower bound that acts as a bound for both frameworks you considered or a different thing? In the section containing theorem 5 I read "We adapt the two-profile comparison of Ma & Peng (2026), fixing an accurate prediction on one of the profiles", how is this related to what you are proposing in the introduction? Are these two things the same?

In section 3:

  • The proof of Theorem 1 is in Appendix A as Lemma 4 and Proposition 1. It should be labelled more clearly. Moreover, if I understood the proof correctly, Theorem 1 is based on the mechanisms presented in the following parts of section 3. I would move the two theorems after the main pieces of the proofs have been established, rather than leaving the two statements before them. At the very least, it should be made clear that the order in which the results are presented is not the same as the logical structure of the proof.

  • In 3.1 the authors comment on the parameter δ\delta before it is introduced. At this point it is not clear what it is meant by left and right biased version.

  • In the definition of the Biased Dictatorial Mechanism (BDM) I read "Define D- by reflecting all reports, applying D+, and reflecting its output back." It is not clear with respect to what the reports should be reflected. Also, I would specify that the reports are the ones coming from the agents.

  • While I am convinced that the proof of lemma 1 is correct, the argument is not sound and not clearly explained. It is not clear to me what "a positive facility exposed by another positive report" is. Also, there is a certain degree of conflation between the notion of facility and facility position, leading to weird sentences such as "The same argument uses threshold B0B_0, since every attainable positive facility is at least B0B_0."

  • In the section "selection from the prediction" I read "Sort the prediction while retaining identities, ...". I am confused. In the extreme point mechanism the dictator is selected based on the relative position. Is your case different? Does this mean that your mechanisms are not anonymous?

  • technically, the second statement of theorem 2 is already known, as it is the standard analysis of the extreme point mechanism.

  • in the section on the upper bounds the authors consider only random mechanisms. It should be clarified that this choice can be done without loss of generality as the bounds for the randomised mechanisms are true also for deterministic ones.

  • Definition 4 is not complete as it does not provide the instruction to build the probability distribution to determine the position of the second facility.


Lastly, the writing is sloppy and unclear in certain parts. I highlight the main issues in the crucial parts of the presentation. For example the authors use "random mechanisms" interchangeably with "sampling mechanisms". The same goes with "facilities" and "anchors". The paper should adopt one convention and stick with it.

  • "Full-profile predictions allow consistency arbitrarily close to 1 with finite robustness, and the bounds extend to the prediction-free endpoint", the results on the endpoint mechanism are already known. At most you are showing that your analysis is consistent with the previous work.

  • the paper introduces the notation P+Q=Opt, but never use it again (at least in the main body of the paper).

  • it should be made explicit that ranks means ordering.

  • "it favors reports to the right of xix_i" is a descriptive sentence, not one that should belong to a definition.

Some further minor issues:

  • the first sentence of the abstract is extremely dense and also oddly written "In learning-augmented mechanism design for two-facility location, we examine [...]", maybe the author meant "in the context of learning-augmented mechanism[...]" or "In this paper, we examine ..."

  • the authors often say that something "appears in the appendix", please consider adopting the more standard version "are deferred to the appendix" or something along these lines.


Overall the paper proposes some meaningful contribution, however the presentation of the paper hinders its impact. I am willing to upgrade my score if the authors provide a compelling argument and answer all the raised concerns/questions.

Questions for authors
  • the BDM mechanism resembles me of the mechanisms used in Auricchio et al. "Facility location problems with capacity constraints: two facilities and beyond" (IJCAI '24), where the facilities are located starting from a dictator and then selecting the new positions depending on a distance between the dictator and other agents. While I appreciate that the presented mechanism is not precisely a verbatim change of these mechanisms, I think it would be better to at least acknowledge these mechanisms in the introduction. Moreover, the mechanisms presented in the IJCAI paper work when there are more than two facilities to locate, hence a natural question would be whether this help extending your results to m>2.

  • what does "Sort the prediction while retaining identities" mean? Are your mechanisms anonymous?

  • Is the probability used in definition 4 the same as the one used for the other mechanism?

  • Does "anchor" mean "facility/dictator" and "sampling mechanism" mean "random mechanism"?

4 comments

Thank you for your detailed feedback. We will carefully revise the language throughout the paper, especially the definitions and proofs, to make the arguments easier to follow.

RE: BDM mechanism and [IJCAI 24]. Thank you for pointing us to [Auricchio et al. IJCAI 2024]. Their Propagating Median Mechanism also places further facilities using distances from an initial facility, and we will acknowledge this connection. Their mechanism uses groups determined by capacities and reported ranks, whereas BDM fixes a dictator tt and uses a bias parameter δ\delta to determine the second facility. Their approximation guarantee depends on the capacity constraints. For example, with three facilities and reports (0,1,1,1,1,2), their rule with capacity two places all facilities at 1. Its social cost is 2, while the uncapacitated optimum places facilities at 0,1,2 and has zero cost. Thus, using their rule without capacities can give an unbounded approximation ratio. We will discuss this obstacle to extending our results to more facilities.

RE: Meaning of “Sort the prediction while retaining identities”. We mean that we sort the agents according to their predicted locations while keeping track of which agent corresponds to each location. For example, suppose the predicted profile is x^=(5,1,8,3)\hat{x}=(5,1,8,3), where x^i\hat{x}_i is the predicted location of agent ii. After sorting, we obtain the sequence of (location, agent identity) pairs (1,2),(3,4),(5,1),(8,3)(1,2),(3,4),(5,1),(8,3). Thus, if the mechanism selects the second agent in the sorted sequence as the dictator, it selects agent 4. Importantly, the dictator's identity is determined solely by the prediction and remains fixed even if agents change their reported locations. Since there is a dictator, the mechanism is not anonymous.

RE: Probabilities in Definition 4. In Definition 4, after selecting an anchor agent i uniformly at random to place the first facility, the mechanism determines the second facility by sampling a partner agent jj with probability Pr⁡(j∣i)=ωij∣xi−xj∣∑k∈Nωik∣xi−xk∣,\Pr(j\mid i)=\frac{\omega_{ij}|x_i-x_j|}{\sum_{k\in N}\omega_{ik}|x_i-x_k|}, where ωij=1\omega_{ij}=1 if jj lies on the favored side of ii, and ωij=τ\omega_{ij}=\tau otherwise. The second facility is then placed at xjx_j. If all reported locations coincide, both facilities are placed at that common location.

This follows the same general principle as the standard Proportional mechanism, but uses direction-dependent weights. In particular, when τ=1\tau=1, it reduces to the standard Proportional mechanism. It also differs from the Prediction-Guided Sampling mechanism in Section 4.1, which uses prediction-dependent distributions to select the anchor and nominee, followed by a different weighted sampling rule for the second facility.

RE: Anchor and Sampling mechanism. An "anchor" refers to an agent whose reported location is selected as the first facility. It is similar to a dictator in that one facility is placed at this agent's report, but the anchor is selected randomly, whereas the dictator in our deterministic mechanisms has a fixed identity. A "sampling mechanism" is indeed a randomized mechanism. We use this term to emphasize that the facility locations are determined by sampling agents according to specified probability distributions.

Below are our point-to-point responses to Critical Weaknesses.

-For the common lower bound in our contribution section, it refers to a single lower bound (Theorem 5) that applies to both prediction models considered in our paper. The two-profile comparison adapted from Ma and Peng (2026) is the proof technique used to establish this common lower bound.

-For the proof of Theorem 1, the upper bound is established by Lemma 4 and Proposition 1, while the matching lower bound is in Proposition 2, all in Appendix A. We will clarify this proof structure.

-For the parameter δ\delta in Section 3.1, δ\delta controls the bias in selecting the second facility, with larger values favoring the right side in the right-biased version. The left-biased version is defined symmetrically by reflection, and we will explain these concepts more clearly before Definition 3.

-For the definition of BDM, we mean reflecting all agents' reported locations about the origin, i.e., replacing each xix_i with −xi-x_i, applying Dδ,t+D_{\delta,t}^{+}, and then negating both resulting facility locations.

-For the proof of Lemma 1, the phrase "a positive facility exposed by another positive report" refers to a second facility located to the right of the dictator, whose position is determined by another agent's positive report.

-For the second statement of Theorem 2, we agree that the approximation n−2n-2 for the Two-Extremes mechanism is already known. Our contribution is the matching lower bound showing that predictions cannot improve.

-For the randomized upper bounds, we will clarify that Section 4 specifically focuses on randomized mechanisms, which include deterministic mechanisms as special cases.

AuthorsOpenReview ↗

Clarification on the Follow-up

Dear Reviewer,

Thank you for your detailed review again. We would greatly appreciate it if you could take a moment to review our response. Since there are about 30 hours remaining before the discussion deadline, we hope there is still an opportunity to clarify any concerns you may have.

Thank you very much for your time and consideration.

Reviewer_EmG9OpenReview ↗

reply

Dear authors,

Thank you for your detailed reply.

While after the point-by-point reply to the critical weaknesses I am more well inclined to upgrade the score, I would like to point out that the amount of "additional explaination" needed to better position the paper and explain the results is non-trivial.

Also I was expecting to see an updated version of the paper on this platform to better assess the quality of the changes to apply.

AuthorsOpenReview ↗

An updated version

Dear Reviewer,

We have updated a new version in the platform. While issues have been addressed according to our first reply, we have also polished the writing and presentation throughout the paper. All changes are marked in blue color.

In the following, we highlight some important changes.

First, regarding your concern about the expose of Theorem 1, we divide it into two separate theorems: Theorem 1 for the upper bound, and Theorem 2 for the lower bound. And they are no longer in the beginning o Section 3, as suggested. The original Theorem 2 (now Theorem 3) is put at the end of this section.

Second, we added comparison with the work of Auricchio et al. IJCAI 2024, in both the related work and the remark in Section 3.1.

Third, the statement of Definition 4 is now clearer, with the probabilities explicitly expressed.

Finally, as suggested by Reviewer oXwv, we added discussion on approximately accurate predictions, in Appendix C.

Thank you again for the suggestions on improving the paper.

Reviewer_aqp2OpenReview ↗
Rating
4(+3)
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

Two facilities go on a line and the mechanism must minimise the total distance while remaining strategyproof, with the planner also given a prediction: the full list of locations, or just a good pair of facility locations. Performance is measured by consistency (quality when the prediction is right) and robustness (quality when it is arbitrary).

For deterministic mechanisms and any number of agents of at least five, the paper pins down the exact trade-off for both prediction types, including the threshold below which no finite robustness is possible; perfect consistency is possible only with five agents, at a robustness of seven. Facility-pair predictions help nothing. For randomized mechanisms it gives a sampling family in which the prediction sets the sampling weights, an explicit curve for full profiles, and a general lower bound ruling out perfect consistency with finite robustness.

Critical strengths
  1. The deterministic question is settled exactly, for every size and both formats. Each point on the curve comes with a matching lower bound, so the frontier is exact, endpoints included. Earlier work had partial answers, so an exact characterisation ends the question rather than extending it.
  2. With only a facility pair, no deterministic strategyproof mechanism beats ignoring the prediction, while the full profile buys real improvements. That is the lesson one can take away — the format, not only the accuracy, decides whether augmentation can help — and the negative side is an optimality result, so no better mechanism can overturn it.
Critical weaknesses

None

Questions for authors

Is there any lower bound for randomized facility-pair mechanisms, given that the general one is vacuous above robustness of about four?

3 comments

Thank you for your feedback.

The lower bound in Theorem 5 applies to facility-pair predictions. It gives consistence guarantees C≥1+(R−R−1)22C\ge 1+\frac{\big(\sqrt R-\sqrt{R-1}\big)^2}{2}, for every finite robustness R. For example, when R=4R=4, it gives C≥1.0359C\ge 1.0359. We have not established a stronger lower bound specifically for facility-pair predictions.

The consistency 3+τ3+\tau and robustness 3+1τ3+\frac{1}{\tau} are tight for our Directional Proportional Sampling family. They do not establish the optimal tradeoff among all randomized strategyproof mechanisms, and we do not know whether consistency below 3 is possible with finite robustness in this prediction model. We will make this distinction clearer and identify a stronger lower bound for facility-pair predictions as an open question.

We also noticed that the overall rating is "1: Clear rejection", while the review lists no weaknesses and gives positive assessments of the results. Could you please confirm this rating? Thank you again.

AuthorsOpenReview ↗

Clarification on the Rating and Follow-up

Dear Reviewer,

Thank you for your review and for highlighting the strengths of our work.

We would like to kindly ask whether you could double-check your overall rating. Your review acknowledges several strengths of our paper and does not identify any specific weaknesses, yet the assigned rating is 1. We are therefore wondering whether this rating accurately reflects your assessment or might have been selected inadvertently.

We have also submitted our rebuttal and would greatly appreciate it if you could take a moment to review our response. With approximately 30 hours remaining before the discussion deadline, we hope there is still an opportunity to clarify any concerns you may have.

Thank you very much for your time and consideration.

I am sorry for wrong rating. I have changed it to a clear acceptance. Thanks again for your response.

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

The paper studies the problem of strategyproof facility location aiming to minimize social cost on the case with 2 facilities. For this problem it is known that deterministic mechanisms can achieve an approximation ratio of Theta(n) while randomized mechanisms Theta(1). The paper studies a setting where predictions are available and aims to characterize the trade-off between consistency (predictions are accurate) and robustness (predictions are wrong).

It gives a complete characterization for deterministic mechanisms which is effectively negative saying that one cannot achieve consistency o(n) without infinite cost in robustness.

For randomized mechanisms, it shows that one can get 1+eps consistency with poly(1/eps) robustness.

The results apply to a prediction setting about the locations of the agents and extends to a weaker setting where one is given predictions only for the optimal facility placements.

Critical strengths

Studying mechanism design with predictions is natural and interesting and can bypass impossibilities. The paper shows how one can get improved results for 2-facility location without significant degradation whenever the predictions are wrong.

Critical weaknesses

The results are solid but somewhat limited in scope:

  • The setting of two-facility location considered is a bit restrictive.
  • The randomized upper and lower bounds do not match, leaving a gap between (O(1/\varepsilon^2)) and (\Omega(1/\varepsilon)) robustness for (1+\varepsilon) consistency.
Questions for authors

What happens when the predictions are only approximately accurate? Is there a natural notion of prediction error under which the mechanisms could achieve a smoother degradation in performance between consistency and robustness?

1 comment
AuthorsOpenReview ↗

We have results for approximately accurate predictions

Thank you for your feedback.

RE: Approximately accurate predictions. We examined how our full-profile sampling mechanism performs when predictions are approximately correct. As in [Agrawal et al., EC 2022], we measure location error relative to the optimal cost by defining η=nmax⁡i∣xi−x^i∣OPT(x)\eta=\frac{n\max_i|x_i-\widehat x_i|}{OPT(x)}. This is the maximum location error divided by the optimal average cost, and it is zero when the prediction is correct. For our Prediction-Guided Sampling mechanism with consistency CC, robustness RR, and Lmax=max⁡(L0,L1)L_{max}=\max(L_0,L_1), where L0L_0, L1L_1 are the sampling parameters in Appendix B.1, we obtain an approximation guarantee of min⁡(R,C+(C+5+2Lmax)η)\min(R,C+(C+5+2L_{max})\eta). This bound equals CC at zero error and grows linearly until it reaches RR. For our Uniform Certral Sampling mechanism with consistency 1+ϵ1+\epsilon, where 0<ϵ≤230<\epsilon\le \frac23, the coefficient of η\eta depends only on ϵ\epsilon. We will add this result and its proof.

RE: The setting restriction. We acknowledge that our model focuses on two facilities on the line. However, this setting is a natural and technically challenging next step beyond single-facility location, while optimal guarantees are already known for single-facility location. Precisely, the median mechanism on the line minimizes social cost even without predictions, and [Agrawal et al., EC 2022] further establish optimal prediction guarantees for maximum cost on the line and optimal tradeoffs for deterministic mechanisms in the Euclidean plane. For two facilities, however, the best deterministic strategyproof approximation ratio without predictions grows linearly with the number of agents, even on the line. We determine exactly how much each type of prediction can improve this guarantee for every fixed n5.

RE: The randomized gap. We agree that the gap between O(1/ε2)O(1/\varepsilon^2) and Ω(1/ε)\Omega(1/\varepsilon) is a limitation of our results. We do not currently know whether the upper bound can be improved or the lower bound strengthened. The optimal randomized approximation ratio remains unknown even without predictions. We will state this limitation clearly.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.