- 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 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 , since every attainable positive facility is at least ."
-
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 " 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
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.
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.
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.
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 t and uses a bias parameter δ 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), where x^i is the predicted location of agent i. After sorting, we obtain the sequence of (location, agent identity) pairs (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 j with probability Pr(j∣i)=∑k∈Nωik∣xi−xk∣ωij∣xi−xj∣, where ωij=1 if j lies on the favored side of i, and ωij=τ otherwise. The second facility is then placed at xj. 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, 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 δ in Section 3.1, δ 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 xi with −xi, applying Dδ,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−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.