Strategyproof Facility Location with Prediction: Minimizing the Maximum Cost

Chenhao Wang; Hau Chan; Jianan Lin

arxiv: 2509.00439 · v2 · submitted 2025-08-30 · 💻 cs.GT

Strategyproof Facility Location with Prediction: Minimizing the Maximum Cost

Hau Chan , Jianan Lin , Chenhao Wang This is my paper

Pith reviewed 2026-05-18 20:37 UTC · model grok-4.3

classification 💻 cs.GT

keywords strategyproof mechanismsfacility locationpredictionconsistencyrobustnessmaximum costapproximation ratioreal line

0 comments

The pith

The MinMaxP mechanism is the only deterministic strategyproof rule that improves consistency beyond 2 for maximum-cost facility location on the line using predictions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper investigates strategyproof mechanisms for facility location that use predictions of the optimal location to reduce the maximum cost to agents. It focuses on mechanisms that are truthful in reporting locations and achieve better performance when predictions are accurate while maintaining robustness otherwise. On the real line, the authors fully characterize the deterministic strategyproof mechanisms that have consistency strictly better than 2 and bounded robustness, showing they must all be the MinMaxP mechanism. This mechanism places the facility at the prediction if it is between the extreme agent positions or at the closest extreme agent otherwise. They prove that this yields an approximation ratio of 1 plus the minimum of 1 and the normalized prediction error η, which is tight for deterministic strategyproof mechanisms.

Core claim

On the real line, we characterize all deterministic strategyproof mechanisms with consistency strictly better than 2 and bounded robustness for the maximum cost. Any such mechanism must coincide with the MinMaxP mechanism, which returns the prediction if it lies between the two extreme agent locations and otherwise returns the agent location closest to the prediction. For any prediction error η ≥ 0, MinMaxP achieves a (1 + min(1, η))-approximation and no deterministic strategyproof mechanism can obtain a better approximation ratio.

What carries the argument

The MinMaxP mechanism, which returns the prediction if it lies between the two extreme agent locations and otherwise returns the agent location closest to the prediction.

If this is right

For any prediction error η ≥ 0, MinMaxP achieves a (1 + min(1, η))-approximation.
No deterministic strategyproof mechanism obtains a strictly better approximation ratio.
Applying MinMaxP independently on each coordinate yields guarantees for two-dimensional ℓ_p spaces.
The same approach extends to the L_p-norm social cost objective on the line and the maximum cost objective on trees.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the prediction model produces something other than a single point or the error is measured in a different way, the uniqueness of MinMaxP may not hold.
Similar uniqueness results could appear in other prediction-augmented truthful mechanism design problems on lines or trees.

Load-bearing premise

The underlying space is a metric and the prediction is a single point whose error is measured in the same metric.

What would settle it

Constructing a deterministic strategyproof mechanism on the line that achieves consistency strictly better than 2 with bounded robustness but differs from MinMaxP at some agent configuration would falsify the characterization.

read the original abstract

We study the mechanism design problem of facility location on a metric space in the learning-augmented framework, where mechanisms have access to imperfect predictions of the optimal facility locations. Our objective is to design strategyproof (SP) mechanisms that truthfully elicit agents' preferences over facility locations and, using the given prediction, select a facility location that approximately minimizes the maximum cost among all agents. In particular, we seek SP mechanisms whose approximation guarantees depend on the prediction error: they should achieve improved performance when the prediction is accurate (the property of \emph{consistency}) while still ensuring strong worst-case guarantees when the prediction is arbitrarily inaccurate (the property of \emph{robustness}). On the real line, we characterize all deterministic SP mechanisms with consistency strictly better than 2 and bounded robustness for the maximum cost. We show that any such mechanism must coincide with the MinMaxP mechanism, which returns the prediction if it lies between the two extreme agent locations and otherwise returns the agent location closest to the prediction. For any prediction error $\eta\ge 0$, we prove that MinMaxP achieves a $(1+\min(1, \eta))$-approximation and that no deterministic SP mechanism can obtain a better approximation ratio. In addition, for two-dimensional spaces with the $\ell_p$ distance, we analyze the approximation guarantees of a deterministic mechanism that applies MinMaxP independently on each coordinate, as well as a randomized mechanism that selects between two deterministic mechanisms with carefully chosen probabilities. We further extend these results to the $L_p$-norm social cost objective on the line metric and the maximum cost objective on the tree metric. Finally, we examine the group strategyproofness of the mechanisms.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Paper cleanly characterizes the unique deterministic SP mechanism for prediction-augmented max-cost facility location on the line and gives tight bounds once the error parameter is normalized as relative.

read the letter

The main thing to know is that this paper characterizes all deterministic strategyproof mechanisms for the maximum-cost facility location problem on the line that can use a prediction to get consistency better than the usual factor of 2 while keeping robustness bounded. Only the MinMaxP mechanism satisfies those conditions, and it achieves a tight (1 + min(1, η)) approximation ratio. What the paper does well is deliver a clean uniqueness result together with matching bounds. MinMaxP simply checks whether the prediction lies between the leftmost and rightmost agent positions; if yes it uses the prediction, otherwise it uses the nearer endpoint. The authors prove no other deterministic SP mechanism can improve on the consistency-robustness tradeoff they identify. They also give approximation results for the mechanism applied coordinate-wise in the plane under ℓ_p distances, a randomized variant, extensions to trees and to L_p social cost, and a check on group strategyproofness. These pieces are technically solid and build directly on the line case. The soft spots are minor. The abstract is a bit light on the exact definitions of consistency, robustness, and the error parameter η, which makes the claims hard to assess from the summary alone. The stress-test note points out a potential issue with scale invariance if η were an absolute distance. Reading the full paper shows that η is defined as a relative quantity (prediction error normalized by the optimal maximum cost), so the bound remains invariant under scaling and the uniqueness proof holds. No load-bearing gaps appear in the derivations or citations. This work is aimed at people in algorithmic mechanism design who study facility location or learning-augmented mechanisms. Readers who want tight characterizations and explicit mechanisms for truthful location with side predictions will find it useful. It deserves a serious referee because the core result on the line is self-contained and the extensions demonstrate broader applicability. I recommend sending it to peer review.

Referee Report

1 major / 1 minor

Summary. The paper studies strategyproof facility location mechanisms on metric spaces that use imperfect predictions of optimal facility locations to approximately minimize the maximum cost. On the real line, it characterizes all deterministic SP mechanisms with consistency strictly better than 2 and bounded robustness, proving they must coincide with the MinMaxP mechanism (which returns the prediction if between the extreme agent locations, else the closest extreme). It shows MinMaxP achieves a (1 + min(1, η))-approximation for prediction error η ≥ 0 with a matching lower bound. Extensions cover ℓ_p spaces in 2D (deterministic and randomized), L_p-norm costs on the line, tree metrics, and group strategyproofness.

Significance. If the results hold, this provides a strong contribution to learning-augmented mechanism design by delivering a complete characterization of deterministic SP mechanisms with improved consistency for max-cost facility location, along with tight error-dependent approximation bounds. The uniqueness result for MinMaxP is a notable strength, as are the extensions across multiple metrics and objectives. The work bridges strategyproofness with prediction-based performance in a clean way.

major comments (1)

[Abstract] Abstract (and the statement of the main approximation result): The claimed (1 + min(1, η))-approximation for MinMaxP (and the matching lower bound) is stated for arbitrary η ≥ 0. Facility-location approximation ratios are invariant under uniform scaling of all positions and the prediction, yet min(1, η) is not scale-invariant if η denotes absolute distance. The bound therefore holds for all instances only if η is the relative error (absolute prediction error normalized by the optimal maximum cost on that instance). This normalization is not visible in the abstract and is load-bearing for both the performance guarantee and the uniqueness characterization that relies on the same consistency-robustness tradeoff.

minor comments (1)

The abstract could more explicitly preview the approximation ratios obtained in the 2D ℓ_p and tree-metric extensions to improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback. We address the single major comment below and will incorporate the suggested clarification into the revised manuscript.

read point-by-point responses

Referee: [Abstract] Abstract (and the statement of the main approximation result): The claimed (1 + min(1, η))-approximation for MinMaxP (and the matching lower bound) is stated for arbitrary η ≥ 0. Facility-location approximation ratios are invariant under uniform scaling of all positions and the prediction, yet min(1, η) is not scale-invariant if η denotes absolute distance. The bound therefore holds for all instances only if η is the relative error (absolute prediction error normalized by the optimal maximum cost on that instance). This normalization is not visible in the abstract and is load-bearing for both the performance guarantee and the uniqueness characterization that relies on the same consistency-robustness tradeoff.

Authors: We agree that the abstract (and the statements of the main results) should explicitly indicate that η denotes relative prediction error. In the body of the paper, η is defined as the ratio of the absolute distance between the prediction and the optimal facility location to the optimal maximum cost (i.e., η = d(p, f*)/OPT). This normalization ensures the approximation ratio is scale-invariant, as both the error and OPT scale identically under uniform scaling of the instance. The (1 + min(1, η)) bound and the matching lower bound therefore hold for every instance. The uniqueness characterization likewise relies on this normalized notion of consistency and robustness. We will revise the abstract to read “for any relative prediction error η ≥ 0” and add a brief parenthetical reminder in the theorem statements. No changes to the proofs or technical content are required. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation follows from SP, consistency, and robustness definitions

full rationale

The paper's core results—the characterization that all qualifying deterministic SP mechanisms coincide with the explicitly defined MinMaxP, the (1 + min(1, η)) upper bound, and the matching lower bound—are obtained by direct analysis of strategyproofness constraints, consistency requirements, and robustness on the metric space. These steps start from the standard definitions of the properties and the mechanism's rule (return prediction if inside extremes, else closest agent location) without any reduction to fitted parameters, self-definitional loops, or load-bearing self-citations. The approximation claims are proven for the stated prediction error η and hold independently of the input data used to define the mechanism itself.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard domain assumptions of metric spaces and strategyproofness; no free parameters or invented entities are introduced in the abstract.

axioms (2)

domain assumption The underlying space is a metric space (real line, ℓ_p plane, or tree).
Invoked throughout the problem statement and extensions.
domain assumption A mechanism is strategyproof if truthful reporting of locations is a dominant strategy for every agent.
Core definition used to constrain the class of mechanisms considered.

pith-pipeline@v0.9.0 · 5838 in / 1473 out tokens · 54781 ms · 2026-05-18T20:37:50.013441+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We characterize all deterministic SP mechanisms with consistency strictly better than 2 and bounded robustness for the maximum cost. ... MinMaxP ... (1 + min(1, η))-approximation
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean embed_strictMono_of_one_lt unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

η(π, x) = d(o(x), π) / MC(x, o(x))

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

[1]

Learning- augmented mechanism design: Leveraging predictions for facility location

Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. Learning- augmented mechanism design: Leveraging predictions for facility location. In Proceedings of the 23rd ACM Conference on Economics and Computation , pages 497–528, 2022

work page 2022
[2]

Strategyproof ap- proximation of the minimax on networks

Noga Alon, Michal Feldman, Ariel D Procaccia, and Moshe Tennenholtz. Strategyproof ap- proximation of the minimax on networks. Mathematics of Operations Research, 35(3):513– 526, 2010

work page 2010
[3]

Randomized strategic facility location with predictions

Eric Balkanski, Vasilis Gkatzelis, and Golnoosh Shahkarami. Randomized strategic facility location with predictions. Advances in Neural Information Processing Systems , 37:35639– 35664, 2024. 17

work page 2024
[4]

MAC advice for facility location mechanism design

Zohar Barak, Anupam Gupta, and Inbal Talgam-Cohen. MAC advice for facility location mechanism design. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems (NeurIPS) , 2024

work page 2024
[5]

Border and J

Kim C. Border and J. S. Jordan. Straightforward elections, unanimity and phantom voters. The Review of Economic Studies , 50(1):153–170, 1983

work page 1983
[6]

Mechanism design for facility location problems: A survey

Hau Chan, Aris Filos-Ratsikas, Bo Li, Minming Li, and Chenhao Wang. Mechanism design for facility location problems: A survey. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI) , pages 4356–4365, 2021

work page 2021
[7]

Strategic facility location via predictions

Qingyun Chen, Nick Gravin, and Sungjin Im. Strategic facility location via predictions. In Proceedings of the 20th International Conference of Web and Internet Economics (WINE) , 2024

work page 2024
[8]

Mechanism design for two-opposite-facility location games with penalties on dis- tance

Xujin Chen, Xiaodong Hu, Xiaohua Jia, Minming Li, Zhongzheng Tang, and Chenhao Wang. Mechanism design for two-opposite-facility location games with penalties on dis- tance. In Proceedings of the 11th International Symposium on Algorithmic Game Theory (SAGT), pages 256–260, 2018

work page 2018
[9]

Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game

Xujin Chen, Xiaodong Hu, Zhongzheng Tang, and Chenhao Wang. Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game. Information Processing Letters, 168:106098, 2021

work page 2021
[10]

Mechanism design aug- mented with output advice

George Christodoulou, Alkmini Sgouritsa, and Ioannis Vlachos. Mechanism design aug- mented with output advice. In Advances in Neural Information Processing Systems: Annual Conference on Neural Information Processing Systems (NeurIPS) , 2024

work page 2024
[11]

Mechanism design with predic- tions for facility location games with candidate locations

Jiazhu Fang, Qizhi Fang, Wenjing Liu, and Qingqin Nong. Mechanism design with predic- tions for facility location games with candidate locations. In Theory and Applications of Models of Computation - 18th Annual Conference, (TAMC) , volume 14637, pages 38–49, 2024

work page 2024
[12]

Approximately optimal mechanisms for strategyproof facility location: Minimizing lp norm of costs

Itai Feigenbaum, Jay Sethuraman, and Chun Ye. Approximately optimal mechanisms for strategyproof facility location: Minimizing lp norm of costs. Mathematics of Operations Research, 42(2):434–447, 2017

work page 2017
[13]

Strategyproof facility location and the least squares ob- jective

Michal Feldman and Yoav Wilf. Strategyproof facility location and the least squares ob- jective. In Proceedings of the 14th ACM Conference on Electronic Commerce (EC) , pages 873–890, 2013

work page 2013
[14]

Facility location games with fractional preferences

Chi Kit Ken Fong, Minming Li, Pinyan Lu, Taiki Todo, and Makoto Yokoo. Facility location games with fractional preferences. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI) , pages 1039–1046, 2018

work page 2018
[15]

Strategyproof facility location for concave cost functions

Dimitris Fotakis and Christos Tzamos. Strategyproof facility location for concave cost functions. In Proceedings of the 14th ACM Conference on Electronic Commerce (EC) , pages 435–452, 2013. 18

work page 2013
[16]

Facility location

Christian Frank. Facility location. In Algorithms for Sensor and Ad Hoc Networks: Ad- vanced Lectures, 2007

work page 2007
[17]

Optimality of the coordinate-wise median mech- anism for strategyproof facility location in two dimensions

Sumit Goel and Wade Hann-Caruthers. Optimality of the coordinate-wise median mech- anism for strategyproof facility location in two dimensions. Social Choice and Welfare , 61(1):11–34, 2023

work page 2023
[18]

Heuristics for the fixed cost median problem

Dorit S Hochbaum. Heuristics for the fixed cost median problem. Mathematical program- ming, 22(1):148–162, 1982

work page 1982
[19]

Mechanism design with predictions for obnoxious facility location

Gabriel Istrate and Cosmin Bonchis. Mechanism design with predictions for obnoxious facility location. CoRR, abs/2212.09521, 2022

work page arXiv 2022
[20]

Nearly complete characterization of 2-agent deterministic strategyproof mecha- nisms for single facility location in l p space

Jianan Lin. Nearly complete characterization of 2-agent deterministic strategyproof mecha- nisms for single facility location in l p space. In International Conference on Combinatorial Optimization and Applications , pages 411–425. Springer, 2020

work page 2020
[21]

Strategyproof facility location for three agents on a circle

Reshef Meir. Strategyproof facility location for three agents on a circle. In Algorithmic Game Theory - 12th International Symposium (SAGT) , 2019

work page 2019
[22]

Algorithms with predictions

Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communica- tions of the ACM , 65(7):33–35, 2022

work page 2022
[23]

Locating libraries on a street

Eiichi Miyagawa. Locating libraries on a street. Social Choice and Welfare, 18(3):527–541, 2001

work page 2001
[24]

On strategy-proofness and single peakedness

Herv´ e Moulin. On strategy-proofness and single peakedness. Public Choice, 35(4):437–455, 1980

work page 1980
[25]

Heterogeneous facility location without money

Serafino Paolo and Ventre Carmine. Heterogeneous facility location without money. Theo- retial Compututer Science, 636:27–46, 2016

work page 2016
[26]

Approximate mechanism design without money

Ariel D Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. ACM Transactions on Economics and Computation (TEAC) , 1(4):1–26, 2013

work page 2013
[27]

Beyond the worst-case analysis of algorithms

Tim Roughgarden. Beyond the worst-case analysis of algorithms . Cambridge University Press, 2021

work page 2021
[28]

Characterization of group-strategyproof mechanisms for facility location in strictly convex space

Pingzhong Tang, Dingli Yu, and Shengyu Zhao. Characterization of group-strategyproof mechanisms for facility location in strictly convex space. In Proceedings of the 21st ACM Conference on Economics and Computation , pages 133–157, 2020

work page 2020
[29]

Mechanism design with predictions

Chenyang Xu and Pinyan Lu. Mechanism design with predictions. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pages 571–577, 2022. 19

work page 2022

[1] [1]

Learning- augmented mechanism design: Leveraging predictions for facility location

Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. Learning- augmented mechanism design: Leveraging predictions for facility location. In Proceedings of the 23rd ACM Conference on Economics and Computation , pages 497–528, 2022

work page 2022

[2] [2]

Strategyproof ap- proximation of the minimax on networks

Noga Alon, Michal Feldman, Ariel D Procaccia, and Moshe Tennenholtz. Strategyproof ap- proximation of the minimax on networks. Mathematics of Operations Research, 35(3):513– 526, 2010

work page 2010

[3] [3]

Randomized strategic facility location with predictions

Eric Balkanski, Vasilis Gkatzelis, and Golnoosh Shahkarami. Randomized strategic facility location with predictions. Advances in Neural Information Processing Systems , 37:35639– 35664, 2024. 17

work page 2024

[4] [4]

MAC advice for facility location mechanism design

Zohar Barak, Anupam Gupta, and Inbal Talgam-Cohen. MAC advice for facility location mechanism design. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems (NeurIPS) , 2024

work page 2024

[5] [5]

Border and J

Kim C. Border and J. S. Jordan. Straightforward elections, unanimity and phantom voters. The Review of Economic Studies , 50(1):153–170, 1983

work page 1983

[6] [6]

Mechanism design for facility location problems: A survey

Hau Chan, Aris Filos-Ratsikas, Bo Li, Minming Li, and Chenhao Wang. Mechanism design for facility location problems: A survey. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI) , pages 4356–4365, 2021

work page 2021

[7] [7]

Strategic facility location via predictions

Qingyun Chen, Nick Gravin, and Sungjin Im. Strategic facility location via predictions. In Proceedings of the 20th International Conference of Web and Internet Economics (WINE) , 2024

work page 2024

[8] [8]

Mechanism design for two-opposite-facility location games with penalties on dis- tance

Xujin Chen, Xiaodong Hu, Xiaohua Jia, Minming Li, Zhongzheng Tang, and Chenhao Wang. Mechanism design for two-opposite-facility location games with penalties on dis- tance. In Proceedings of the 11th International Symposium on Algorithmic Game Theory (SAGT), pages 256–260, 2018

work page 2018

[9] [9]

Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game

Xujin Chen, Xiaodong Hu, Zhongzheng Tang, and Chenhao Wang. Tight efficiency lower bounds for strategy-proof mechanisms in two-opposite-facility location game. Information Processing Letters, 168:106098, 2021

work page 2021

[10] [10]

Mechanism design aug- mented with output advice

George Christodoulou, Alkmini Sgouritsa, and Ioannis Vlachos. Mechanism design aug- mented with output advice. In Advances in Neural Information Processing Systems: Annual Conference on Neural Information Processing Systems (NeurIPS) , 2024

work page 2024

[11] [11]

Mechanism design with predic- tions for facility location games with candidate locations

Jiazhu Fang, Qizhi Fang, Wenjing Liu, and Qingqin Nong. Mechanism design with predic- tions for facility location games with candidate locations. In Theory and Applications of Models of Computation - 18th Annual Conference, (TAMC) , volume 14637, pages 38–49, 2024

work page 2024

[12] [12]

Approximately optimal mechanisms for strategyproof facility location: Minimizing lp norm of costs

Itai Feigenbaum, Jay Sethuraman, and Chun Ye. Approximately optimal mechanisms for strategyproof facility location: Minimizing lp norm of costs. Mathematics of Operations Research, 42(2):434–447, 2017

work page 2017

[13] [13]

Strategyproof facility location and the least squares ob- jective

Michal Feldman and Yoav Wilf. Strategyproof facility location and the least squares ob- jective. In Proceedings of the 14th ACM Conference on Electronic Commerce (EC) , pages 873–890, 2013

work page 2013

[14] [14]

Facility location games with fractional preferences

Chi Kit Ken Fong, Minming Li, Pinyan Lu, Taiki Todo, and Makoto Yokoo. Facility location games with fractional preferences. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI) , pages 1039–1046, 2018

work page 2018

[15] [15]

Strategyproof facility location for concave cost functions

Dimitris Fotakis and Christos Tzamos. Strategyproof facility location for concave cost functions. In Proceedings of the 14th ACM Conference on Electronic Commerce (EC) , pages 435–452, 2013. 18

work page 2013

[16] [16]

Facility location

Christian Frank. Facility location. In Algorithms for Sensor and Ad Hoc Networks: Ad- vanced Lectures, 2007

work page 2007

[17] [17]

Optimality of the coordinate-wise median mech- anism for strategyproof facility location in two dimensions

Sumit Goel and Wade Hann-Caruthers. Optimality of the coordinate-wise median mech- anism for strategyproof facility location in two dimensions. Social Choice and Welfare , 61(1):11–34, 2023

work page 2023

[18] [18]

Heuristics for the fixed cost median problem

Dorit S Hochbaum. Heuristics for the fixed cost median problem. Mathematical program- ming, 22(1):148–162, 1982

work page 1982

[19] [19]

Mechanism design with predictions for obnoxious facility location

Gabriel Istrate and Cosmin Bonchis. Mechanism design with predictions for obnoxious facility location. CoRR, abs/2212.09521, 2022

work page arXiv 2022

[20] [20]

Nearly complete characterization of 2-agent deterministic strategyproof mecha- nisms for single facility location in l p space

Jianan Lin. Nearly complete characterization of 2-agent deterministic strategyproof mecha- nisms for single facility location in l p space. In International Conference on Combinatorial Optimization and Applications , pages 411–425. Springer, 2020

work page 2020

[21] [21]

Strategyproof facility location for three agents on a circle

Reshef Meir. Strategyproof facility location for three agents on a circle. In Algorithmic Game Theory - 12th International Symposium (SAGT) , 2019

work page 2019

[22] [22]

Algorithms with predictions

Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communica- tions of the ACM , 65(7):33–35, 2022

work page 2022

[23] [23]

Locating libraries on a street

Eiichi Miyagawa. Locating libraries on a street. Social Choice and Welfare, 18(3):527–541, 2001

work page 2001

[24] [24]

On strategy-proofness and single peakedness

Herv´ e Moulin. On strategy-proofness and single peakedness. Public Choice, 35(4):437–455, 1980

work page 1980

[25] [25]

Heterogeneous facility location without money

Serafino Paolo and Ventre Carmine. Heterogeneous facility location without money. Theo- retial Compututer Science, 636:27–46, 2016

work page 2016

[26] [26]

Approximate mechanism design without money

Ariel D Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. ACM Transactions on Economics and Computation (TEAC) , 1(4):1–26, 2013

work page 2013

[27] [27]

Beyond the worst-case analysis of algorithms

Tim Roughgarden. Beyond the worst-case analysis of algorithms . Cambridge University Press, 2021

work page 2021

[28] [28]

Characterization of group-strategyproof mechanisms for facility location in strictly convex space

Pingzhong Tang, Dingli Yu, and Shengyu Zhao. Characterization of group-strategyproof mechanisms for facility location in strictly convex space. In Proceedings of the 21st ACM Conference on Economics and Computation , pages 133–157, 2020

work page 2020

[29] [29]

Mechanism design with predictions

Chenyang Xu and Pinyan Lu. Mechanism design with predictions. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pages 571–577, 2022. 19

work page 2022