Pith. sign in

REVIEW 4 major objections 6 minor 51 references

Approximation guarantees of Median Mechanism in $\mathbb{R}^d$

T0 review · 4 major / 6 minor · reviewed 2026-08-08 · deepseek-v4-flash

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

Pith's one-line read The paper proves that the coordinate-wise median mechanism achieves a dimension-independent constant approximation ratio in every L_q(R^d) space, at most 3, with Euclidean bound sqrt(6 sqrt(3)-8) < 1.55, and that this constant is tight as…

desk verdict Gravin and Jia show the coordinate-wise median has a dimension-independent constant approximation ratio in every L_q(R^d), with matching lower bounds; the result is very likely right and important, but the preprint has real presentation gaps that need fixing before it is fully rigorous. read the letter →

arxiv 2502.08578 v2 pith:4LIWGZVA submitted 2025-02-12 cs.GT

Nick Gravin , Jianhao Jia This is my paper · ORCID
classification cs.GT MSC 68W2591B14
keywords coordinate-wisemedianstrategy-proofmechanismfacilitylocationL_qspacesapproximationratiodesignwithpredictionsdimension-independentboundsgeneralized
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

Settling a long-open question about the most classic truthful facility-location mechanism, the paper proves that the coordinate-wise median has a dimension-independent approximation ratio in every $L_q(\mathbb{R}^d)$ space. The ratio is at most $UB(q)$, a constant that increases from $1$ for $q=1$ to $3$ for $q=\infty$; for Euclidean distance, $UB(2)=\sqrt{6\sqrt{3}-8}\approx 1.55$. This replaces the previous best known $\sqrt{d}$ upper bound and shows that the working assumption of $\Theta(\sqrt{d})$ growth is wrong. The paper also constructs instances whose ratio is $UB(q)(1-O(1/d))$, proving the bound is essentially tight as the dimension grows, and extends the argument to the generalized median mechanism used when a prediction is available.

What carries the argument

The argument is carried by a relaxed optimization program. Normalizing the optimal facility to $\mathbf{f}$ with $\lVert\mathbf{f}\rVert_q=1$ and the median to the origin, the paper minimizes $\sum_i g(p_i)$ with $g(p)=\lVert p-\mathbf{f}\rVert_q-\lambda\lVert p\rVert_q$ over reports $p_i$ whose coordinate-wise median is $0$. The median constraint is encoded by the signature $\sigma(p)\in\{-1,1\}^d$ and the balance condition $\sum_i\sigma(p_i)=0$. Lemma 1 shows that at the optimum every report is determined by one constant $c$, and Lemma 2 rewrites each report's contribution as a function of $x_i=\Delta_{S(p_i)}$, the fraction of the optimal facility's $\ell_q^q$-mass lying in the positive coordinates of $p_i$. Relaxing the signature constraint to $\sum_i x_i=n/2$ yields program (6) with objective $h(x)=\lambda(\delta(1-x)^{1/q}-x^{1/q})$, which is convex near $0$ and concave near $1$; Lemma 3 reduces the optimum to two levels $a$ and $1$, and taking $n\to\infty$ leaves a one-variable function $u(a)$. The conditions $u(a^*)=u'(a^*)=0$ produce equation (10), whose solution $a^*(q)$ determines $\lambda^*(q)=1/UB(q)$.

What would settle it

A concrete falsifier would be a finite configuration in $L_2(\mathbb{R}^d)$ whose median's social cost exceeds $\sqrt{6\sqrt{3}-8}$ times the optimum, or, for the sup norm, a configuration with ratio greater than $3$. Short of that, evaluating the relaxed program (6) at $\lambda=1/UB(q)$ for large finite $n$ and finding a negative minimum would show the claimed upper bound cannot be derived from the stated relaxation.

Watch

Extended reading notes

Core claim

On its own terms, the paper claims that for every $q\in[1,\infty]$ and every dimension $d$, the coordinate-wise median's approximation ratio $\alpha(q,d)$ is at most $UB(q)$ with $UB(1)=1$, $UB(2)=\sqrt{6\sqrt{3}-8}<1.55$, and $\lim_{q\to\infty}UB(q)=3$. Theorem 2 shows this is tight: there are configurations in $\mathbb{R}^d$ whose ratio is at least $UB(q)(1-O(1/d))$, so in the high-dimensional limit the worst case is exactly $UB(q)$. A consequence is that the previously known $\sqrt{d}$-approximation for Euclidean space, which follows from embedding $L_1$ into $L_2$, is far from tight. The same relaxed-program analysis yields explicit consistency and robustness guarantees for the prediction-augmented median mechanism in arbitrary dimension.

Load-bearing premise

The upper-bound proof assumes that, once the number of agents is large, the single agent whose coordinate-sum value falls in the middle range can be dropped from the extremal configuration; if that limit step fails, the one-variable equation that determines $UB(q)$ does not follow.

Editorial extensions

If this is right

  • Facility-location mechanisms in $L_2(\mathbb{R}^d)$ no longer need a $\sqrt{d}$ factor: the median mechanism is a $<1.55$-approximation in every dimension, so restricting to $\mathbb{R}^2$ is unnecessary for worst-case efficiency.
  • For the supremum norm $L_\infty$, the median mechanism is a $3$-approximation for any $d$, with lower-bound instances reaching $3-1/d$.
  • The lower-bound constructions show the dimension-independent constants are optimal in the limit $d\to\infty$, so no future upper bound smaller than $UB(q)$ can be correct for all dimensions.
  • The generalized median mechanism with predictions keeps its $\mathbb{R}^2$ guarantees in arbitrary dimension up to an $11\%$ loss, and its consistency guarantee approaches $1$ at different rates as the prediction confidence $c\to 1$.
  • Papers on mechanism design with predictions that invoked the $\sqrt{d}$ bound can now replace it by a universal constant, improving their stated guarantees.

Reading between the lines

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

  • Not in the paper: keeping the single middle-level point $x_i=b$ in the finite-$n$ program would yield explicit finite-dimension bounds and quantify the $O(1/d)$ slack between the lower and upper bounds.
  • The worst-case instances use only two types of reports (points near the optimum and sparse points near the median's zero vector), suggesting that simple clustered instances capture the extremal behaviour; this could make it easier to design and certify other anonymous strategy-proof mechanisms.
  • If the same reduction works for weighted $\ell_q$ norms, it would give dimension-free guarantees for separable quadratic preference domains, where agents' preferences are coordinate-wise weighted; the paper does not claim this extension.
  • A natural open question the paper leaves implicit is whether any deterministic, anonymous, strategy-proof mechanism can beat $1.55$ in high-dimensional Euclidean space; the lower-bound examples here only match the median's own upper bound.
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.

Referee Report

4 major / 6 minor

Summary. This paper studies the worst-case approximation ratio of the coordinate-wise median mechanism in L_q(R^d) for q ∈ [1, ∞] and arbitrary dimension d. The authors formulate the ratio as a minimization program over agent reports with the median normalized to the origin, relax the median constraint to a scalar constraint, and reduce the relaxed program to a one-dimensional optimization. This yields dimension-independent upper bounds UB(q), with UB(2) = √(6√3 − 8) ≈ 1.55 and UB(q) → 3 as q → ∞. The paper also constructs instances giving lower bounds LB(q,d) = UB(q)(1 − O(1/d)), and extends the framework to the generalized median mechanism CMP(c) for facility location with predictions, giving consistency and robustness guarantees in L_2(R^d).

Significance. If completed, the result would be a significant advance: it would settle the approximation ratio of the coordinate-wise median in all L_q spaces, disproving the common √d belief, and would immediately improve guarantees in several learning-augmented mechanism-design settings. The optimization-based framework is elegant, and the paper ships explicit algebraic expressions for the Euclidean case, concrete lower-bound constructions, and a clear tightness statement as d → ∞. However, several load-bearing steps are not rigorously justified in the present version: the finite-n to limiting reduction in the upper bound and the inequality direction in the lower-bound construction both require repair before the central theorems are established.

major comments (4)
  1. [Section 3.2, after Lemma 3 and footnote 7] The reduction of the finite-n relaxed program (6) to a two-level solution supported on {a,1} is not proved. Lemma 3 permits an optimal solution to contain one point with x_i = b ∈ (z,1), and the text asserts that by duplicating points and taking n → ∞ the effect of this single b can be ignored, with footnote 7 claiming without proof that a finite-n violation at n0 can be converted into a two-level violation at n = 100·n0. Since equation (10) and hence the exact constant UB(q) are derived exclusively from this two-level reduction, Theorem 1 does not currently follow for arbitrary finite n. The gap is likely repairable: one can try to replace the single b by a convex combination of values in {a,1} with the same mean, using the convexity/concavity structure of h from Claim 3 to show the objective does not increase, but the full argument must be written out and the limit exchange made rigorous.
  2. [Section 3.3, displayed inequality chain] The lower-bound proof prints a chain of inequalities, each with ≤, and concludes with '≤ 1/λ* · (1 − O(1/d))'. Since the displayed quantity is the approximation ratio of the constructed instance, a lower bound requires the final inequality to be ≥, or the intermediate inequalities to be reversed. As printed, the chain would bound the ratio from above and contradicts the stated conclusion LB(q,d) = UB(q)(1 − O(1/d)). In addition, Theorem 2's sentence 'the approximation ratio of the median mechanism is at most LB(q,d)' should read 'at least'.
  3. [Lemma 2 and equation (6)] Lemma 2(i) as printed gives g(p) = (1 − λ^{q/(q−1)})^{(q−1)/q} · Δ_S^{1/q} − λ · Δ_S^{1/q}, which is the opposite ordering of the two Δ terms from the expression h(x) = λ(δ(1−x)^{1/q} − x^{1/q}) used in (6), where x = Δ_S. If read literally, this swaps the roles of the positive and negative coordinate sets and changes the sign of the first term in the relaxed objective. The intended formula should be stated unambiguously — e.g., g(p) = λδ·(1−x)^{1/q} − λ·x^{1/q} — and the overline notation for the negative-coordinate set should be clearly typeset in Lemma 2, its proof sketch, and Appendix A.1.
  4. [Section 3.3, social cost computation] In the displayed computation of Σ_{p∈P} ∥f − p∥_q, the factor multiplying the Type-I distance is printed as n/(1 − 2a*). The number of Type I points is n/(2 − 2a*), and the factor n/(1 − 2a*) is inconsistent with the subsequent limit ratio, which cancels n/(2 − 2a*). Please correct the count or explain the different normalization.
minor comments (6)
  1. [Theorem 1] Theorem 1 asserts that UB(q) is increasing in q, but the proof only gives numerical evidence and closed forms for q = 1, 2, ∞; please either prove monotonicity or explicitly label it as a numerical observation.
  2. [Theorem 2] The statement 'the approximation ratio of the median mechanism is at most LB(q,d)' should be 'at least', and the O(1/d) term should be quantified with a constant independent of d.
  3. [Theorems 3 and 4] The formulas in Theorems 3 and 4, such as '4√2c + 3 · c + 6√2c + 3 − 10c − 8', lack parentheses and are ambiguous; they should be typeset with explicit brackets so the intended grouping is clear.
  4. [Section 3.2] The phrase 'we can assume that the minimum in (1) and (6) is attained when the number of points n goes to infinity' conflates the finite-n problems with their limit; it should be replaced by a precise limiting argument or an ε-approximation statement.
  5. [Footnote 9] Footnote 9 inherits the unproved reduction from footnote 7; the claim should either be proved once in Section 3.2 and referenced, or removed and replaced by a complete proof for the generalized median case.
  6. [Theorem 1 proof] The proof of Theorem 1 should state explicitly that the case q = 1 is trivial, since the median mechanism is optimal in L_1 and the parameter λ^{1/(q−1)} is undefined at q = 1.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the upper-bound optimization and lower-bound construction are self-contained; the sole self-citation is not load-bearing.

full rationale

The derivation of UB(q) is self-contained. The paper encodes the worst-case ratio as optimization problem (1), relaxes it to (6) via equation (5), solves the relaxed problem using convexity (Claim 3) and the structural Lemma 3, and derives the one-variable equation (10) for a*(q) and lambda*(q). The resulting UB(q)=1/lambda* is an upper bound because (6) is a relaxation of (1). The lower-bound section constructs explicit instances with parameters a*, lambda* and c*, then computes the social-cost ratio directly; using the upper-bound parameters in the matching construction is standard tightness analysis, not circular reasoning. The only self-citation ([13], co-authored by Gravin) appears in a related-work remark about non-truthful rules for price-of-anarchy guarantees and supports no load-bearing step. The paper does rely on an asymptotic justification after Lemma 3 (footnote 7) to discard the single xi=b point as n tends to infinity; this is a proof gap rather than a circular reduction, since equation (10) follows from a genuine relaxation of the original problem rather than from an assumed conclusion. A finite-n violation of that limit exchange would invalidate the exact constant UB(q), but that concern is about correctness, not circularity.

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

The central claim rests on standard analysis of L_q norms and on the strategic facility location model; no new entities or empirically fitted parameters are introduced. The main technical assumptions are the relaxation step and the n to infinity reduction, which are proven or argued in the paper.

assumptions (3)
  • domain assumption The social cost is the sum of L_q distances and agents report truthfully under the strategy-proof median mechanism.
    Defines the approximation ratio in Section 2; standard in the facility location literature.
  • standard math Convexity and differentiability properties of L_q norms, and first-order optimality conditions for the local minimizers used in Lemma 1.
    Used to characterize optimal points with fixed signatures; requires q>=1 and points away from 0 and f.
  • domain assumption Tie-breaking for even n in the coordinate-wise median can be chosen consistently and gives the declared median m=0 in lower-bound instances.
    The lower-bound construction balances positive and zero entries exactly in each coordinate; the paper relies on this without explicit proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximation guarantees of Median Mechanism in $\mathbb{R}^d$." pith.science (2026). https://pith.science/paper/4LIWGZVA

@misc{pith2026250208578,
  author       = {Pith},
  title        = {Pith review of: Approximation guarantees of Median Mechanism in $\mathbbR^d$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4LIWGZVA}},
  note         = {Machine review of arXiv:2502.08578}
}
abstract

The coordinate-wise median is a classic and most well-studied strategy-proof mechanism in social choice and facility location scenarios. Surprisingly, there is no systematic study of its approximation ratio in $d$-dimensional spaces. The best known approximation guarantee in $d$-dimensional Euclidean space $\mathbb{L}_2(\mathbb{R}^d)$ is $\sqrt{d}$ via embedding $\mathbb{L}_1(\mathbb{R}^d)$ into $\mathbb{L}_2(\mathbb{R}^d)$ metric space, that only appeared in appendix of [Meir 2019].This upper bound is known to be tight in dimension $d=2$, but there are no known super constant lower bounds. Still, it seems that the community's belief about coordinate-wise median is on the side of $\Theta(\sqrt{d})$. E.g., a few recent papers on mechanism design with predictions [Agrawal, Balkanski, Gkatzelis, Ou, Tan 2022], [Christodoulou, Sgouritsa, Vlachos 2024], and [Barak, Gupta, Talgam-Cohen 2024] directly rely on the $\sqrt{d}$-approximation result. In this paper, we systematically study approximate efficiency of the coordinate-median in $\mathbb{L}_{q}(\mathbb{R}^d)$ spaces for any $\mathbb{L}_q$ norm with $q\in[1,\infty]$ and any dimension $d$. We derive a series of constant upper bounds $UB(q)$ independent of the dimension $d$. This series $UB(q)$ is growing with parameter $q$, but never exceeds the constant $UB(\infty)= 3$. Our bound $UB(2)=\sqrt{6\sqrt{3}-8}<1.55$ for $\mathbb{L}_2$ norm is only slightly worse than the tight approximation guarantee of $\sqrt{2}>1.41$ in dimension $d=2$. Furthermore, we show that our upper bounds are essentially tight by giving almost matching lower bounds $LB(q,d)=UB(q)\cdot(1-O(1/d))$ for any dimension $d$ with $LB(q,d)=UB(q)$ when $d\to\infty$. We also extend our analysis to the generalized median mechanism in [Agrawal, Balkanski, Gkatzelis, Ou, Tan 2022] for $\mathbb{L}_2(\mathbb{R}^2)$ space to arbitrary dimensions $d$ with similar results.

Figures

Figures reproduced from arXiv: 2502.08578 by the authors.

Figure 1
Figure 1. UB(q) The optimal facility location is at f = (1, 1, · · · , 1) ∈ R d and the median m = (0, 0, · · · , 0) ∈ R d . We shall use parameters a ∗ , λ∗ given by (10). We also define parameter c ∗ (analog of c from Section 3.1) as c ∗ def ==  1−a ∗ a ∗ · (λ ∗) q/(q−1) 1−(λ∗) q/(q−1) 1/q 1 +  1−a ∗ a ∗ · (λ∗) q/(q−1) 1−(λ∗) q/(q−1) 1/q . The number of points n is a very large integer. There are only two types of point… view at source ↗
Figure 2
Figure 2. plot of ra and rb Hence, our work implies that there is no reason from the perspective of approximation guarantees to restrict attention to L2(R 2 ) case in strategic facility location setting. On the other hand, there is still a lack of satisfying characterization of strategy-proof mechanism in higher-dimensions d ≥ 3. Namely, the existing characterizations that work for general d-dimensional spaces [11, 36] allow … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 50 canonical work pages

  1. [1]

    Agrawal, E

    P. Agrawal, E. Balkanski, V. Gkatzelis, T. Ou, and X. Tan. Learning-augmented mechanism design: Leveraging predictions for facility location. In Proceedings of the 23rd ACM Conference on Economics and Computation, EC ’22, page 497–528. Association for Computing Machinery, 2022

    work page 2022

  2. [2]

    N. Alon, M. Feldman, A. D. Procaccia, and M. Tennenholtz. Strategyproof approximation 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

    E. Balkanski, V. Gkatzelis, and G. Shahkarami. Randomized strategic facility location with predictions. arXiv preprint arXiv:2409.07142 , 2024

    work page Pith review arXiv 2024

  4. [4]

    Balkanski, V

    E. Balkanski, V. Gkatzelis, and X. Tan. Strategyproof scheduling with predictions. In 14th Innovations in Theoretical Computer Science Conference, ITCS 2023 , volume 251 of LIPIcs, pages 11:1–11:22. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2023

    work page 2023

  5. [5]

    Banerjee, V

    S. Banerjee, V. Gkatzelis, S. Hossain, B. Jin, E. Micha, and N. Shah. Proportionally fair online allocation of public goods with predictions. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023 , pages 20–28. ijcai.org, 2023. 16

    work page 2023

  6. [6]

    MAC Advice for Facility Location Mechanism Design

    Z. Barak, A. Gupta, and I. Talgam-Cohen. MAC advice for facility location mechanism design. CoRR, abs/2403.12181, 2024

    work page Pith review arXiv 2024

  7. [7]

    Barber` a

    S. Barber` a. Strategyproof social choice. Handbook of social choice and welfare , 2:731–831, 2011

    work page 2011

  8. [8]

    Barber` a, F

    S. Barber` a, F. Gul, and E. Stacchetti. Generalized median voter schemes and committees. Journal of Economic Theory , 61(2):262–289, 1993

    work page 1993

Show all 51 references
  1. [9]

    Barber` a, J

    S. Barber` a, J. Mass´ o, and S. Serizawa. Strategy-proof voting on compact ranges. games and economic behavior, 25(2):272–291, 1998

    1998

  2. [10]

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

    1948

  3. [11]

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

    1983

  4. [12]

    H. Chan, A. Filos-Ratsikas, B. Li, M. Li, and C. Wang. Mechanism design for facility location problems: A survey. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021 , pages 4356–4365. ijcai.org, 2021

    2021

  5. [13]

    Q. Chen, N. Gravin, and S. Im. Strategic facility location via predictions. arXiv preprint arXiv:2410.07497, 2024

    2024 arXiv

  6. [14]

    Cheng, W

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

    2013

  7. [15]

    median voters

    S. Ching. Strategy-proofness and “median voters”. International Journal of Game Theory , 26:473–490, 1997

    1997

  8. [16]

    Christodoulou, A

    G. Christodoulou, A. Sgouritsa, and I. Vlachos. Mechanism design augmented with output advice. arXiv preprint arXiv:2406.14165 , 2024

    2024 arXiv

  9. [17]

    Dokow, M

    E. Dokow, M. Feldman, R. Meir, and I. Nehama. Mechanism design on discrete lines and cycles. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012 , pages 423–440. ACM, 2012

    2012

  10. [18]

    Escoffier, L

    B. Escoffier, L. Gourv` es, K. T. Nguyen, F. Pascual, and O. Spanjaard. Strategy-proof mech- anisms for facility location games with many facilities. In Algorithmic Decision Theory - Sec- ond International Conference, ADT 2011 , volume 6992 of Lecture Notes in Computer Science...

    2011

  11. [19]

    Feigenbaum and J

    I. Feigenbaum and J. Sethuraman. Strategyproof mechanisms for one-dimensional hybrid and obnoxious facility location models. In Incentive and Trust in E-Communities, Papers from the 2015 AAAI Workshop , volume WS-15-08 of AAAI Technical Report. AAAI Press, 2015

    2015

  12. [20]

    Feigenbaum, J

    I. Feigenbaum, J. Sethuraman, and C. Ye. Approximately optimal mechanisms for strate- gyproof facility location: Minimizing Lp norm of costs. Mathematics of Operations Research, 42(2):434–447, 2017

    2017

  13. [21]

    Feldman and Y

    M. Feldman and Y. Wilf. Strategyproof facility location and the least squares objective. In Proceedings of the fourteenth ACM Conference on Electronic Commerce, EC 2013, pages 873–

    2013

  14. [22]

    Filimonov and R

    A. Filimonov and R. Meir. Strategyproof facility location mechanisms on discrete trees. Au- tonomous Agents and Multi-Agent Systems , 37(1), Dec. 2022

    2022

  15. [23]

    Filos-Ratsikas and A

    A. Filos-Ratsikas and A. A. Voudouris. Approximate mechanism design for distributed facility location. In Algorithmic Game Theory: 14th International Symposium, SAGT 2021 , page 49–63. Springer-Verlag, 2021

    2021

  16. [24]

    Fotakis and C

    D. Fotakis and C. Tzamos. Winner-imposing strategyproof mechanisms for multiple facility location games. In Internet and Network Economics - 6th International Workshop, WINE 2010, volume 6484 of Lecture Notes in Computer Science , pages 234–245. Springer, 2010

    2010

  17. [25]

    Fotakis and C

    D. Fotakis and C. Tzamos. On the power of deterministic mechanisms for facility location games. ACM Transactions on Economics and Computation (TEAC) , 2(4):15:1–15:37, 2014

    2014

  18. [26]

    Fotakis and C

    D. Fotakis and C. Tzamos. Strategyproof facility location for concave cost functions. Algo- rithmica, 76(1):143–167, 2016

    2016

  19. [27]

    A. Gibbard. Manipulation of schemes that mix voting with chance. Econometrica, 45(3):665– 681, 1977

    1977

  20. [28]

    Gkatzelis, K

    V. Gkatzelis, K. Kollias, A. Sgouritsa, and X. Tan. Improved price of anarchy via predictions. In The 23rd ACM Conference on Economics and Computation , EC’22, pages 529–557. ACM, 2022

    2022

  21. [29]

    Goel and W

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

    2023

  22. [30]

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

    1984

  23. [31]

    P. Lu, X. Sun, Y. Wang, and Z. A. Zhu. Asymptotically optimal strategy-proof mechanisms for two-facility games. In Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), pages 315–324. ACM, 2010

    2010

  24. [32]

    P. Lu, Y. Wang, and Y. Zhou. Tighter bounds for facility games. In Proceedings of the 5th International Workshop on Internet and Network Economics , WINE ’09, page 137–148. Springer-Verlag, 2009

    2009

  25. [33]

    L. Mei, M. Li, D. Ye, and G. Zhang. Facility location games with distinct desires. Discrete Applied Mathematics, 264:148–160, 2019

    2019

  26. [34]

    R. Meir. Strategyproof facility location for three agents on a circle. In Algorithmic Game The- ory - 12th International Symposium, SAGT 2019 , volume 11801 of Lecture Notes in Computer Science, pages 18–33. Springer, 2019

    2019

  27. [35]

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

    1980

  28. [36]

    Peremans, H

    W. Peremans, H. Peters, H. vd Stel, and T. Storcken. Strategy-proofness on Euclidean spaces. Social Choice and Welfare , 14:379–401, 1997

    1997

  29. [37]

    Peters, H

    H. Peters, H. van der Stel, and T. Storcken. Range convexity, continuity, and strategy-proofness of voting schemes. Zeitschrift f¨ ur Operations Research, 38:213–229, 1993. 18

    1993

  30. [38]

    A. D. Procaccia and M. Tennenholtz. Approximate mechanism design without money. In Proceedings of the 10th ACM Conference on Electronic Commerce , EC ’09, page 177–186. ACM, 2009

    2009

  31. [39]

    M. A. Satterthwaite. Strategy-proofness and arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory , 10:187–217, 1975

    1975

  32. [40]

    Schummer and R

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

    2002

  33. [41]

    Serafino and C

    P. Serafino and C. Ventre. Heterogeneous facility location without money. Theoretical Com- puter Science, 636:27–46, 2016

    2016

  34. [42]

    T. Todo, A. Iwasaki, and M. Yokoo. False-name-proof mechanism design without money. In The 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 2, AAMAS ’11, page 651–658. International Foundation for Autonomous Agents and Multiagent Systems, 2011

    2011

  35. [43]

    T. Walsh. Strategy proof mechanisms for facility location in Euclidean and Manhattan space. arXiv preprint arXiv:2009.07983 , 2020

    2009 arXiv

  36. [44]

    Xu and P

    C. Xu and P. Lu. Mechanism design with predictions. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022 , pages 571–577. ijcai.org, 2022

    2022

  37. [45]

    Zou and M

    S. Zou and M. Li. Facility location games with dual preference. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems , AAMAS ’15, page 615–623. International Foundation for Autonomous Agents and Multiagent Systems, 2015. A Missing pro...

    2015

  38. [46]

    The corresponding a′ 1 is the optimal solution (i.e

    = 0. The corresponding a′ 1 is the optimal solution (i.e. a1 = a′

  39. [47]

    The equations for u′ 1(a′

    if a′ 1 ≤ 1−c 2 , or otherwise, a1 = 1−c 2 . The equations for u′ 1(a′

  40. [48]

    (23) We multiply 2(a′ 1 − 1) on both side of the second equation in (23) and get (1 + c) · δ1 · (1 − a′ 1)1/2 − (a′ 1)1/2 + (a′ 1)−1/2 + 4(a′ 1 − 1) = 0

    = 0 are    (1 + c) · δ1 · (1 − a′ 1)1/2 − (a′ 1)1/2 − 1 + 2 · a′ 1 + c = 0 1 2 · (1 + c) · δ1 · (1 − a′ 1)−1/2 − (a′ 1)−1/2 + 2 = 0. (23) We multiply 2(a′ 1 − 1) on both side of the second equation in (23) and get (1 + c) · δ1 · (1 − a′ 1)1/2 − (a′ 1)1/2 + (a′ 1)−1/2 + 4(...

  41. [49]

    The corresponding a′ 2 is the optimal solution (i.e

    = 0. The corresponding a′ 2 is the optimal solution (i.e. a2 = a′

  42. [50]

    The equations for u′ 2(a′

    if a′ 2 ≤ 1+c 2 , or otherwise, a2 = 1+c 2 . The equations for u′ 2(a′

  43. [51]

    (29) 26 We multiply 2(a′ 2 − 1) on both side of the second equation in (29) and get (1 − c) · δ2 · (1 − a′ 2)1/2 − (a′ 2)1/2 + (a′ 2)−1/2 + 4(a′ 2 − 1) = 0

    = 0 are    (1 − c) · δ2 · (1 − a′ 2)1/2 − (a′ 2)1/2 − 1 + 2 · a′ 2 − c = 0 1 2 · (1 − c) · δ2 · (1 − a′ 2)−1/2 − (a′ 2)−1/2 + 2 = 0. (29) 26 We multiply 2(a′ 2 − 1) on both side of the second equation in (29) and get (1 − c) · δ2 · (1 − a′ 2)1/2 − (a′ 2)1/2 + (a′ 2)−1/2 +...

Pith tools

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