Constant-Approximate and Constant-Strategyproof Two-Facility Location

C. Gregory Plaxton; Elijah Journey Fullerton; Zeyuan Hu

REVIEW 2 major objections 5 minor 50 references

Constant-Approximate and Constant-Strategyproof Two-Facility Location

T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Allowing facilities to leave the line yields deterministic two-facility mechanisms that are constant-approximate, constant-strategyproof, and (for one of them) constant-Lipschitz.

desk verdict A genuinely new lifting trick proves constant-strategyproof and constant-Lipschitz two-facility location, but the Lipschitz guarantee rests on a dense appendix that deserves careful independent checking. read the letter →

arxiv 2507.04485 v3 pith:OJ2V45OR submitted 2025-07-06 cs.GT

Elijah Journey Fullerton , Zeyuan Hu , C. Gregory Plaxton This is my paper · ORCID

classification cs.GT

keywords two-facilitylocationmechanismdesignwithoutmoneyconstant-strategyproofnessLipschitzmechanismsapproximationratiofacilityrelaxation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper asks whether a deterministic mechanism can place two public facilities at near-optimal social cost while remaining hard to manipulate. On the line alone, a known lower bound says every strategyproof mechanism can be forced to pay $\Omega(n)$ times the optimal cost, and the same bound survives if strategyproofness is weakened to "no agent can gain more than a constant factor by lying." The paper's first move is to relax the geometry: agents stay on the line, but facilities may be built anywhere in the plane. In this relaxed setting the paper constructs a simple mechanism, M3, that is constant-approximate and constant-strategyproof, and a second mechanism, M4, that also guarantees Lipschitz continuity. If these results are correct, the impossibility for line-restricted mechanisms is an artifact of forcing facilities onto the line, not an inherent conflict between approximate efficiency and approximate truthfulness.

What carries the argument

The carrying object is a vertical offset, a money-burning device. Instead of placing facility $\ell$ directly on the line, the mechanisms place it at distance $\tau_{\ell,2}$ above the line at the same x-coordinate. Because an agent's cost is the $\ell^1$ distance $|x - p_1| + |p_2|$, the vertical component is unavoidable and does not depend on which x-coordinate the agent reports, which is what makes large lies unprofitable. For M4 the offset is capped and smoothed using weights that count how many agents lie between the two line facilities, and the Lipschitz proof works by decomposing the interval over which one reported coordinate moves into cells on which all relevant functions $f_\ell$, $\Delta$, $\psi_\ell$, and $\varphi_\ell$ are differentiable with controlled slopes.

What would settle it

A single concrete counterexample would settle it: find a profile and a one-coordinate perturbation where M4's output changes by more than a constant factor times the input change, or where an agent's distance to M3's output drops by more than $1/\varepsilon$ after misreporting.

Watch

Extended reading notes

Core claim

The paper proves two main theorems. Theorem 1 states that mechanism M3 is constant-approximate and constant-strategyproof: M3 starts from the optimal 1-D solution for a profile and lifts each facility to height $C(\pi)/|S_\ell(\pi)|$, the optimal social cost divided by the number of agents served on that side. The vertical offset adds a cost component that a lying agent cannot erase, capping the gain from misreporting by a constant factor while inflating social cost by at most a factor of 3. Theorem 2 states that mechanism M4 is constant-approximate, constant-strategyproof, and constant-Lipschitz: M4 lifts each facility by $\varphi_\ell(\pi) = \max(8C(\pi)/n, \xi_\ell(\pi))$, where $\xi_\ell$ is built from the gap between the two line facilities and weighted per-side costs, achieving a 15-approximation. The paper's main technical burden is showing that M4 is Lipschitz; it partitions the domain of any single-coordinate perturbation into cells using knot sets K1 through K6, proves per-cell derivative bounds, and assembles them into a global constant.

Load-bearing premise

The constant-Lipschitz guarantee for M4 rests on the appendix's cell decomposition: if even one non-differentiability point is missing from the knot sets K1 through K6, or if one per-cell slope bound in Lemma B.14 is incorrect, the Lipschitz constant can fail.

Editorial extensions

If this is right

The known $\Omega(n)$ lower bound for line-restricted strategyproof mechanisms no longer blocks constant-factor approximations once facilities may be built in the plane.
M4's Lipschitz bound means a facility reallocation problem can bound moving costs by the size of preference changes over time without knowing the future.
The mechanisms are deterministic and anonymous, and they require no payments or randomization.
The approximation constants are explicit (3 for M3, 15 for M4), so the guarantees are concrete rather than merely asymptotic.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The vertical-offset construction is a transferable trick: any base mechanism whose per-group cost is bounded can be made harder to manipulate by adding a report-independent distance component, suggesting extensions to other metric spaces and to more than two facilities.
A likely tradeoff curve connects the approximation ratio and the strategyproofness factor through the offset height; the paper notes the tradeoff but leaves its exact shape open.
For dynamic settings, running M4 repeatedly on a changing profile would bound total reallocation distance by the total variation of the profile sequence, with no need to model how the population evolves.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper gets around the known Omega(n) lower bound for strategyproof two-facility location by relaxing strategyproofness to constant-strategyproofness and, more importantly, letting facilities live in the plane while agents stay on the line. The main contribution is M4, which is constant-approximate, constant-strategyproof, and constant-Lipschitz. The lifting idea—raising facilities off the line by an amount tied to optimal cost divided by number of agents served—is genuinely new and looks like a useful tool for the facility-location/mechanism-design toolkit.

What is good: the proofs for M3 are clean, and the approximation and strategyproofness arguments check out. M4 is more intricate but the architecture is sensible: it is a stabilized version of a 1-D mechanism, and the Lipschitz property is proven through a cell decomposition in Appendix B. The paper is honest about the cost of the relaxation; the constants are large (about 11 for strategyproofness, 15 for approximation) and the 1-D lower bound for constant-strategyproof mechanisms is cited rather than proved. The references look right, and I see no circular fitting.

Where I would be careful: the constant-Lipschitz claim for M4 is only as solid as Appendix B. There are several "it is easy to see" steps in constructing the knot sets K1 through K6, in particular that each active interval is a single interval, the slope formulas in P4, and the analogous statements for h2. I did not verify every one by hand. If any is wrong, Theorem 2's Lipschitz bound could fail. This is not a fatal objection—the appendix is detailed and the structure is checkable—but it is exactly the kind of place where a subtle mistake can hide. The paper would be stronger if those steps were expanded or machine-checked. The unproved assertions about M3 (not strategyproof, not Lipschitz) are minor and easily fixed.

Who this is for: people working on facility location mechanisms, approximate strategyproofness, or stability of mechanisms. It deserves a serious referee. My own verdict is conditional: the main ideas are right, but the Lipschitz appendix needs a careful independent check before the result is fully trusted.

Referee Report

2 major / 5 minor

Summary. The paper studies deterministic two-facility location with n agents on the real line, but allows facilities to be placed anywhere in the plane. It first observes that the known Ω(n) lower bound for strategyproof mechanisms extends to constant-strategyproof mechanisms, motivating the plane-facility relaxation. The first main result is mechanism M3, which takes the canonical optimal 1-D solution and lifts each facility vertically by C(π)/|S_l(π)|; the paper proves M3 is 3-approximate and (1/ε)-strategyproof for ε=(2−√3)/3. The second main result is mechanism M4, based on an auxiliary 1-D mechanism M2, with vertical offsets φ_l = max(8C(π)/n, min(Δ(π), 2ψ_l(π))); the paper proves M4 is 15-approximate, constant-strategyproof (by comparison with M3), and constant-Lipschitz. The Lipschitz proof is the technical core: Appendix B partitions each coordinate interval into cells via knot sets K1–K6 and derives per-cell derivative bounds culminating in Lemma B.14 and Lemma B.4.

Significance. If the Appendix B arguments are completed as intended, the paper delivers a genuinely new positive result: constant approximation, constant strategyproofness, and Lipschitz continuity are simultaneously achievable in a two-facility setting, under the explicit relaxation that facilities (but not agents) may leave the line. The mechanisms are simple and directly defined, with no fitted parameters, and the main-text proofs for M3 and for the approximation ratio of M4 are elementary and checkable. The Lipschitz analysis is a substantial and original piece of piecewise-differentiability argument; it is also the part of the paper that most needs additional rigor before the result can be considered fully established.

major comments (2)

[Appendix B.1] The proof of Lemma B.4, and therefore the constant-Lipschitz assertion of Theorem 2, rests on the predicates P1(K1), P2(K2), P3(K3), P4(K4) and their analogues for h2, all of which are introduced with the phrase 'it is easy to see' and no proof. These are load-bearing structural claims: P1 asserts that active(π) is constant on each cell and that each candidate cost is affine with slope in {−1,1} or {−1,0}; P2 asserts that index(π) changes at most twice per cell; P3/P4 assert the transition behavior of h1 and give the slope formulas 2/i, 1/i, and −1/i, which are then used in Lemma B.14 to obtain the O(1/sℓ) Lipschitz bound. If, for instance, the set of πk values for which a fixed i belongs to active(π) were not a single interval, or if a slope formula failed at a boundary case, the cell decomposition would miss a nondifferentiability point and the Lipschitz guarantee could fail. The authors should supply complete derivations of these predicates, including the analogous ones for h2, or at least a detailed proof that each cell excludes all relevant kinks.
[Appendix B.1, K6] The zero-gap/positive-gap partition is not fully justified. The text adds knots only at values where h1(π)=μ(π) and concludes that every resulting cell is either zero-gap or positive-gap. But Δ(π)=0 is equivalent to f1(π)=f2(π)=μ(π), i.e., h1(π)≥μ(π)≥h2(π), not merely to h1(π)=μ(π). The equivalence h1=μ iff h2=μ is true, but the proof that the sign of h1−μ determines the sign of Δ throughout each cell should be written out; as it stands, this is a non-obvious step in the argument that Lemma B.4 inherits.

minor comments (5)

[Lemma 3.1] The displayed inequality should use d(π1, σ∗), not d(π∗1, σ∗); as written, d(π∗1, σ∗)=0, which makes the manipulation-gain comparison vacuous.
[Appendix B.2, Lemma B.11] In the proof of Lemma B.11, the final displayed expression 'O(1 +ψℓ(π)/∆(π)/sℓ' is missing a closing parenthesis and should be O((1 + ψℓ(π)/∆(π))/sℓ).
[Section 1 and Section 3.2] The claim that the Ω(n) lower bound of [35] generalizes to constant-strategyproof mechanisms is stated without proof or reference; since the paper uses this claim to motivate the plane-facility relaxation, a proof sketch or precise citation should be included.
[Appendix B.1, K6] The assertion 'h1(π)=μ(π) (and hence also h2(π)=μ(π))' is true but is stated without proof; making the short argument explicit would help the reader verify the subsequent zero-gap/positive-gap conclusion.
[References] Reference [8] lists the Chan et al. survey as appearing at the 13th IJCAI; IJCAI 2021 is the 30th, so the conference number appears to be a typo.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the mechanisms are defined directly and analyzed against the canonical optimum, with no fitted parameters, no renamed predictions, and no load-bearing self-citations.

full rationale

The paper exhibits no circularity. Mechanism M3 is defined directly as the canonical 1-D optimum lifted vertically by C(pi)/|S_l(pi)|, and its constant-strategyproofness is derived rather than assumed: Lemma 4.2 lower-bounds C(pi*) using only the optimality of canonical(pi*), and Lemma 4.3 proves that the height tau*_{l,2} = C(pi*)/|S_l(pi*, sigma*)| (which equals average cost per served agent by the definition of M3) must be at least epsilon*d(pi_i, tau) whenever agent i lies toward facility l. No parameter is fitted to make the ratio 1/epsilon come out; the identity (1/3 - epsilon)(1 - 3epsilon) = 2epsilon merely selects a proof constant. Mechanism M4 inherits strategyproofness from M3 through the generic transfer Lemma 4.6 after proving pointwise per-facility cost ratios (Lemma 4.7); the approximation bound (Lemma 4.5) and the Lipschitz chain (Lemmas 4.8-4.10 with the Appendix B cell-decomposition argument) analyze the defined mechanism rather than assuming its conclusion. The load-bearing external inputs are genuinely external: the Omega(n) impossibility is cited from Lu et al. [35], the median fact from Procaccia and Tennenholtz [42], and the constant-strategyproofness definition from Oomine et al. [40]; the reference list contains no self-citations. The asserted 'it is easy to see' predicates P1(K1) through P4(K6) and the slope bounds underlying Lemma B.14 constitute a real verification gap - if any non-differentiability point is missing from the knot sets, or any per-cell slope bound is wrong, Theorem 2's Lipschitz guarantee could fail - but an unexpanded proof is not a reduction of the conclusion to its inputs. Likewise, the 'straightforward generalization' of the [35] lower bound to constant-strategyproof mechanisms is asserted without proof, yet it only motivates the second relaxation and is not used in the proofs of Theorems 1-2. No equation in the paper is equivalent to its own premise by construction.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The ledger is clean: no data-fitted parameters appear, and the paper introduces no new entities. The only notable debt is the unproved extension of the known lower bound to constant-strategyproof mechanisms, which is motivation rather than a premise of the main theorems.

assumptions (3)

standard math Left-median minimizes single-facility cost (Fact 1, attributed to Procaccia and Tennenholtz).
Used to characterize canonical two-facility solutions in Lemma 2.2.
domain assumption The Omega(n) lower bound of Lu et al. [35] extends to constant-strategyproof mechanisms.
Stated in Section 1 as 'straightforward to generalize' but no proof or citation is given; used to motivate the second relaxation (facilities in the plane).
standard math Standard calculus facts: a differentiable function with derivative bounded by kappa on an interval is kappa-Lipschitz, and max/min of Lipschitz functions are Lipschitz (Facts 4 and 5).
Used throughout Appendix A and B to combine derivative bounds into Lipschitz bounds.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Constant-Approximate and Constant-Strategyproof Two-Facility Location." pith.science (2026). https://pith.science/paper/OJ2V45OR

@misc{pith2026250704485,
  author       = {Pith},
  title        = {Pith review of: Constant-Approximate and Constant-Strategyproof Two-Facility Location},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OJ2V45OR}},
  note         = {Machine review of arXiv:2507.04485}
}

abstract

We study deterministic mechanisms for the two-facility location problem. Given the reported locations of n agents on the real line, such a mechanism specifies where to build the two facilities. The single-facility variant of this problem admits a simple strategyproof mechanism that minimizes social cost. For two facilities, however, it is known that any strategyproof mechanism is $\Omega(n)$-approximate. We seek to circumvent this strong lower bound by relaxing the problem requirements. Following other work in the facility location literature, we consider a relaxed form of strategyproofness in which no agent can lie and improve their outcome by more than a constant factor. Because the aforementioned $\Omega(n)$ lower bound generalizes easily to constant-strategyproof mechanisms, we introduce a second relaxation: Allowing the facilities (but not the agents) to be located in the plane. Our first main result is a natural mechanism for this relaxation that is constant-approximate and constant-strategyproof. A characteristic of this mechanism is that a small change in the input profile can produce a large change in the solution. Motivated by this observation, and also by results in the facility reallocation literature, our second main result is a constant-approximate, constant-strategyproof, and Lipschitz continuous mechanism.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

50 extracted references · 45 canonical work pages

[1]

Mathematics of Operations Research35(3), 513–526 (2010)

Alon, N., Feldman, M., Procaccia, A., Tennenholtz, M.: Strategyproof approxi- mation of the minimax on networks. Mathematics of Operations Research35(3), 513–526 (2010)

work page 2010
[2]

Journal of Economic Theory177, 405–425 (2018)

Ashlagi, I., Gonczarowski, Y.A.: Stable matching mechanisms are not obviously strategy-proof. Journal of Economic Theory177, 405–425 (2018)

work page 2018
[3]

In: Proceedings of the 17th Interna- tional Symposium on Algorithmic Game Theory

Auricchio, G., Zhang, J.: Thek-facility location problem via optimal transport: A Bayesian study of the percentile mechanisms. In: Proceedings of the 17th Interna- tional Symposium on Algorithmic Game Theory. pp. 147–164 (Sep 2024)

work page 2024
[4]

Journal of Economic Theory61(2), 262–289 (1993)

Barberà, S., Gul, F., Stacchetti, E.: Generalized median voter schemes and com- mittees. Journal of Economic Theory61(2), 262–289 (1993)

work page 1993
[5]

In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence

Birrell, E., Pass, R.: Approximately strategy-proof voting. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence. pp. 67–72 (Jul 2011)

work page 2011
[6]

Journal of Political Economy 56(1), 23–34 (1948)

Black, D.: On the rationale of group decision-making. Journal of Political Economy 56(1), 23–34 (1948)

1948
[7]

In: Proceedings of the 25th ACM Conference on Economics and Computation

Candogan, O., Feng, Y.: Mobility data in operations: Multi-location facility lo- cation problem. In: Proceedings of the 25th ACM Conference on Economics and Computation. p. 201 (Jul 2024)

work page 2024
[8]

In: Proceedings of the 13th International Joint Conference on Artificial Intelligence

Chan, H., Filos-Ratsikas, A., Li, B., Li, M., Wang, C.: Mechanism design for fa- cility location problems: A survey. In: Proceedings of the 13th International Joint Conference on Artificial Intelligence. pp. 4356–4365 (Aug 2021)

work page 2021

Show all 50 references

[9]

Chen, N., Deng, X., Zhang, J.: How profitable are strategic behaviors in a market? In: Proceedings of the European Symposium on Algorithms. pp. 106–118 (Sep 2011)

2011
[10]

American Economic Journal: Microeconomics8(2), 202–14 (2016)

Chen, P., Egesdal, M., Pycia, M., Yenmez, M.B.: Manipulability of stable mecha- nisms. American Economic Journal: Microeconomics8(2), 202–14 (2016)

2016
[11]

In:Proceedingsofthe5thInternationalConferenceonCombinatorialOptimization and Applications

Cheng, Y., Yu, W., Zhang, G.: Mechanisms for obnoxious facility game on a path. In:Proceedingsofthe5thInternationalConferenceonCombinatorialOptimization and Applications. pp. 262–271 (Aug 2011)

2011
[12]

Theoretical Computer Science497, 154–163 (2013)

Cheng, Y., Yu, W., Zhang, G.: Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theoretical Computer Science497, 154–163 (2013)

2013
[13]

Trans- portation Science 12(2), 107–118 (1978)

Church, R.L., Garfinkel, R.S.: Locating an obnoxious facility on a network. Trans- portation Science 12(2), 107–118 (1978)

1978
[14]

In: Proceed- ings of the 23rd ACM Conference on Economics and Computation

Dale, E., Fielding, J., Ramakrishnan, H., Sathyanarayanan, S., Weinberg, S.M.: Approximately strategyproof tournament rules with multiple prizes. In: Proceed- ings of the 23rd ACM Conference on Economics and Computation. pp. 1082–1100 (Jul 2022)

2022
[15]

In: Proceedings of the 17th International Symposium on Algorithmic Game Theory

Deligkas, A., Lotfi, M., Voudouris, A.A.: Agent-constrained truthful facility loca- tion games. In: Proceedings of the 17th International Symposium on Algorithmic Game Theory. pp. 129–146 (Sep 2024)

2024
[16]

In: Proceedings of the 12th Innovations in Theoretical Com- puter Science Conference

Ding, K., Weinberg, S.M.: Approximately strategyproof tournament rules in the probabilistic setting. In: Proceedings of the 12th Innovations in Theoretical Com- puter Science Conference. pp. 14:1–14:20 (Jan 2021) Constant-Approximate and Constant-Strategyproof Two-Facility Location 17

2021
[17]

In: Proceedings of the 2nd International Conference on Algorithmic Decision Theory

Escoffier, B., Gourvès, L., Nguyen, K.T., Pascual, F., Spanjaard, O.: Strategy- proof mechanisms for facility location games with many facilities. In: Proceedings of the 2nd International Conference on Algorithmic Decision Theory. pp. 67–81 (Oct 2011)

2011
[18]

Mathematical Programming 153(2), 655–685 (2015)

Fernandes,C.G.,Meira,L.A.A.,Miyazawa,F.K.,Pedrosa,L.L.C.:Asystematicap- proach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems. Mathematical Programming 153(2), 655–685 (2015)

2015
[19]

Autonomous Agents and Multi-Agent Systems37(10) (2022)

Filimonov, A., Meir, R.: Strategyproof facility location mechanisms on discrete trees. Autonomous Agents and Multi-Agent Systems37(10) (2022)

2022
[20]

Theoretical Computer Science858, 13–34 (2021)

Fotakis, D., Kavouras, L., Kostopanagiotis, P., Lazos, P., Skoulakis, S., Zarifis, N.: Reallocating multiple facilities on the line. Theoretical Computer Science858, 13–34 (2021)

2021
[21]

ACM Transactions on Economics and Computation2(4) (2014)

Fotakis, D., Tzamos, C.: On the power of deterministic mechanisms for facility location games. ACM Transactions on Economics and Computation2(4) (2014)

2014
[22]

IEICE Transactions on Fundamentals E102-A(9), 1179–1186 (2019)

Fukui, Y., Shurbevski, A., Nagamochi, H.:λ-group strategy-proof mechanisms for the obnoxious facility game in star networks. IEICE Transactions on Fundamentals E102-A(9), 1179–1186 (2019)

2019
[23]

Social Choice Welfare 61(1), 11–34 (2023)

Goel, S., Hann-Caruthers, W.: Optimality of the coordinate-wise median mecha- nism for strategyproof facility location in two dimensions. Social Choice Welfare 61(1), 11–34 (2023)

2023
[24]

In: Proceedings of the 24th ACM Conference on Economics and Computation

Gonczarowski, Y.A., Heffetz, O., Thomas, C.: Strategyproofness-exposing mecha- nism descriptions. In: Proceedings of the 24th ACM Conference on Economics and Computation. p. 782 (Jul 2023)

2023
[25]

In: Proceedings of the 24th ACM Conference on Economics and Computation

Gupta, S., Moondra, J., Singh, M.: WhichLp norm is the fairest? Approximations for fair facility location across all “p”. In: Proceedings of the 24th ACM Conference on Economics and Computation. p. 817 (Jul 2023)

2023
[26]

In: Proceedings of the 34th AAAI Conference on Artificial Intel- ligence

Hossain, S., Micha, E., Shah, N.: The surprising power of hiding information in facility location. In: Proceedings of the 34th AAAI Conference on Artificial Intel- ligence. pp. 2168–2175 (Feb 2020)

2020
[27]

In: Proceedings of the 21st AAAI Conference on Artificial Intelligence

Hyafil, N., Boutilier, C.: Regret-based incremental partial revelation mechanisms. In: Proceedings of the 21st AAAI Conference on Artificial Intelligence. pp. 672–678 (Jul 2006)

2006
[28]

Istrate, G., Bonchis, C.: Mechanism design with predictions for obnoxious facility location (2022), https://arxiv.org/abs/2212.09521

2022 arXiv
[29]

Theoretical Computer Science1024, 114913 (2025)

Kanellopoulos, P., Voudouris, A.A., Zhang, R.: Truthful two-facility location with candidate locations. Theoretical Computer Science1024, 114913 (2025)

2025
[30]

Algorithmica84(10), 2898–2925 (2022)

de Keijzer, B., Wojtczak, D.: Facility reallocation on the line. Algorithmica84(10), 2898–2925 (2022)

2022
[31]

Mathematical So- cial Sciences 8(1), 29–43 (1984)

Kim, K.H., Roush, F.W.: Nonmanipulability in two dimensions. Mathematical So- cial Sciences 8(1), 29–43 (1984)

1984
[32]

In: Proceedings of the 15th Conference on Computability in Europe

Klootwijk, S., Manthey, B.: Probabilistic analysis of facility location on random shortest path metrics. In: Proceedings of the 15th Conference on Computability in Europe. pp. 37–49 (Jul 2019)

2019
[33]

In: Proceedings of the 24th International Joint Conference on Artificial In- telligence

Lee, D.T.: Efficient, private, andϵ-strategyproof elicitation of tournament voting rules. In: Proceedings of the 24th International Joint Conference on Artificial In- telligence. pp. 2026–2032 (Jul 2015)

2026
[34]

American Economic Review107(11), 3257–3287 (2017) 18 Fullerton, Hu, and Plaxton

Li, S.: Obviously strategy-proof mechanisms. American Economic Review107(11), 3257–3287 (2017) 18 Fullerton, Hu, and Plaxton

2017
[35]

In: Proceedings of the 11th ACM Conference on Electronic Commerce

Lu, P., Sun, X., Wang, Y., Zhu, Z.A.: Asymptotically optimal strategy-proof mech- anisms for two-facility games. In: Proceedings of the 11th ACM Conference on Electronic Commerce. pp. 315–324 (Jun 2010)

2010
[36]

Current Science103(9), 1021–1032 (2012)

Lubin, B., Parkes, D.C.: Approximate strategyproofness. Current Science103(9), 1021–1032 (2012)

2012
[37]

SIAM Journal on Computing36(2), 411–432 (2006)

Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility lo- cation problems. SIAM Journal on Computing36(2), 411–432 (2006)

2006
[38]

In: Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (Jul 2020)

Micha, E., Shah, N.: Proportionally fair clustering revisited. In: Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (Jul 2020)

2020
[39]

Public Choice 35(4), 437–455 (1980)

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

1980
[40]

Journal of Graph Algorithms and Ap- plications 21(3), 247–263 (2017)

Oomine, M., Shurbevski, A., Nagamochi, H.: Parameterization of strategy-proof mechanisms in the obnoxious facility game. Journal of Graph Algorithms and Ap- plications 21(3), 247–263 (2017)

2017
[41]

International Journal of Game Theory 21, 221–235 (1992)

Peters, H., van der Stel, H., Storcken, T.: Pareto optimality, anonymity, and strategy-proofness in location problems. International Journal of Game Theory 21, 221–235 (1992)

1992
[42]

ACM Transactions on Economics and Computation1(4) (2013)

Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. ACM Transactions on Economics and Computation1(4) (2013)

2013
[43]

In: Proceedings of the 8th Innovations in Theoretical Computer Science Conference

Schneider, J., Schvartzman, A., Weinberg, S.M.: Condorcet-consistent and approx- imately strategyproof tournament rules. In: Proceedings of the 8th Innovations in Theoretical Computer Science Conference. pp. 35:1–35:20 (Jan 2017)

2017
[44]

Journal of Eco- nomic Theory 104(2), 405–428 (2002)

Schummer, J., Vohra, R.V.: Strategy-proof location on a network. Journal of Eco- nomic Theory 104(2), 405–428 (2002)

2002
[45]

In: Proceed- ings of the 11th Innovations in Theoretical Computer Science Conference

Schvartzman, A., Weinberg, S.M., Zlatin, E., Zuo, A.: Approximately strategyproof tournament rules: On large manipulating sets and cover-consistence. In: Proceed- ings of the 11th Innovations in Theoretical Computer Science Conference. pp. 3:1– 3:25 (Jan 2020)

2020
[46]

In: Proceedings of the 14th International Conference on Au- tonomous Agents and Multiagent Systems

Sui, X., Boutilier, C.: Approximately strategy-proof mechanisms for (constrained) facility location. In: Proceedings of the 14th International Conference on Au- tonomous Agents and Multiagent Systems. pp. 605–613 (May 2015)

2015
[47]

In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence

Sui, X., Boutilier, C., Sandholm, T.: Analysis and optimization of multi- dimensional percentile mechanisms. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence. pp. 367–374 (Aug 2013)

2013
[48]

In: Proceedings of the 21st ACM Conference on Economics and Computation

Tang, P., Yu, D., Zhao, S.: Characterization of group-strategyproof mechanisms for facility location in strictly convex space. In: Proceedings of the 21st ACM Conference on Economics and Computation. pp. 133–157 (Jul 2020)

2020
[49]

Zhou, H., Li, M., Chan, H.: Strategyproof mechanisms for group-fair facility lo- cation problems. In: Proceedings of the 31st International Joint Conference on Artificial Intelligence (Jul 2022) A Some Results for Establishing Lipschitz-Type Bounds In this appendix we state an...

2022
[50]

Lemma B.1

for allπk in I(X). Lemma B.1. Let X be a cell in cells(K2). Then the function πk − h1(π) is nondecreasing overX. Proof. Let x(1) and x(2) be distinct values inX. Assume that x(1) < x(2) and let ε denote x(2) − x(1). For eachi in {1, 2}, let π(i) denote the profile π∗ with Cons...

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Mathematics of Operations Research35(3), 513–526 (2010)

Alon, N., Feldman, M., Procaccia, A., Tennenholtz, M.: Strategyproof approxi- mation of the minimax on networks. Mathematics of Operations Research35(3), 513–526 (2010)

work page 2010

[2] [2]

Journal of Economic Theory177, 405–425 (2018)

Ashlagi, I., Gonczarowski, Y.A.: Stable matching mechanisms are not obviously strategy-proof. Journal of Economic Theory177, 405–425 (2018)

work page 2018

[3] [3]

In: Proceedings of the 17th Interna- tional Symposium on Algorithmic Game Theory

Auricchio, G., Zhang, J.: Thek-facility location problem via optimal transport: A Bayesian study of the percentile mechanisms. In: Proceedings of the 17th Interna- tional Symposium on Algorithmic Game Theory. pp. 147–164 (Sep 2024)

work page 2024

[4] [4]

Journal of Economic Theory61(2), 262–289 (1993)

Barberà, S., Gul, F., Stacchetti, E.: Generalized median voter schemes and com- mittees. Journal of Economic Theory61(2), 262–289 (1993)

work page 1993

[5] [5]

In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence

Birrell, E., Pass, R.: Approximately strategy-proof voting. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence. pp. 67–72 (Jul 2011)

work page 2011

[6] [6]

Journal of Political Economy 56(1), 23–34 (1948)

Black, D.: On the rationale of group decision-making. Journal of Political Economy 56(1), 23–34 (1948)

1948

[7] [7]

In: Proceedings of the 25th ACM Conference on Economics and Computation

Candogan, O., Feng, Y.: Mobility data in operations: Multi-location facility lo- cation problem. In: Proceedings of the 25th ACM Conference on Economics and Computation. p. 201 (Jul 2024)

work page 2024

[8] [8]

In: Proceedings of the 13th International Joint Conference on Artificial Intelligence

Chan, H., Filos-Ratsikas, A., Li, B., Li, M., Wang, C.: Mechanism design for fa- cility location problems: A survey. In: Proceedings of the 13th International Joint Conference on Artificial Intelligence. pp. 4356–4365 (Aug 2021)

work page 2021