pith. sign in

arxiv: 1907.08918 · v1 · pith:UFBBG2Y2new · submitted 2019-07-21 · 💻 cs.DS · cs.GT

Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio

Minming Li , Pinyan Lu , Yuhao Yao , Jialin Zhang This is my paper

Pith reviewed 2026-05-24 18:45 UTC · model grok-4.3

classification 💻 cs.DS cs.GT
keywords facility locationstrategyproof mechanismapproximation ratiotwo facilitiesline metricoptional preferencesheterogeneous agents
0
0 comments X

The pith

A deterministic strategyproof mechanism for two heterogeneous facilities on a line achieves a 2.75 approximation ratio for total agent cost.

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

The paper examines the two-facility location problem on a line where each agent has an arbitrary subset of acceptable facilities and pays only the distance to the closest one among them. The task is to place the facilities to minimize the sum of all agents' costs while making the placement rule strategyproof against misreports of acceptable sets. The authors construct one specific deterministic mechanism that is strategyproof and guarantees the total cost stays at most 2.75 times the optimum, a constant factor that does not grow with the number of agents and improves on the earlier n/2+1 bound.

Core claim

There exists a deterministic strategyproof mechanism for the two-facility location game on a line with optional preferences that achieves an approximation ratio of 2.75.

What carries the argument

The deterministic placement rule that maps reported agent positions and acceptable sets on the line to facility locations while enforcing strategyproofness and the 2.75 cost bound.

If this is right

  • The total cost is at most 2.75 times the minimum achievable cost for any reported preferences.
  • Strategyproofness holds for arbitrary heterogeneous acceptable sets on the line.
  • The approximation ratio remains constant and independent of the number of agents.
  • The mechanism improves the prior guarantee of n/2+1 to a fixed 2.75.

Where Pith is reading between the lines

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

  • The same geometric properties of the line might allow constant-ratio strategyproof mechanisms when more than two facilities are placed.
  • The approach could be tested on instances where acceptable sets are generated from real linear preference data.
  • If the line assumption is relaxed to a tree, the constant ratio may or may not survive.

Load-bearing premise

The agents lie on a line and each accepts an arbitrary subset of the two facilities, with cost defined exactly as distance to the nearest accepted facility.

What would settle it

A concrete set of agent positions and acceptable subsets on the line for which the mechanism either allows an agent to gain by misreporting or produces total cost more than 2.75 times the optimal placement.

Figures

Figures reproduced from arXiv: 1907.08918 by Jialin Zhang, Minming Li, Pinyan Lu, Yuhao Yao.

Figure 1
Figure 1. Figure 1: the case opt1 ≤ smid ≥ |S X1|/2 j=1 min{dist(uj , s`), dist(uj , sr)} = |S X1|/2 j=1 dist(uj , s`). Then we have COST1 − OP T1 ≤ d(S1, s`) − d(S1, opt1) = |S X1|/2 j=1 (d({uj , vj}, s`) − d({uj , vj}, opt1)) = X j:uj is on the right side of s` 2 · dist(uj , s`) ≤ |S X1|/2 j=1 2 · dist(uj , s`) ≤ 2 · BEST1. The analysis for the case that opt1 lies on the left side of s` is similar. Hence, COST1 − OP T1 ≤ 2 … view at source ↗
Figure 2
Figure 2. Figure 2: Case 1. opt1 is on the left side of s` In this case, we divide S1 into four parts: X1, X2, X3 and X4. (See [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Case 2. opt1 is between sc and smid Similarly, we can assume |X1| + |X4| = |X2| + |X3| + |X5|. By the definition of ∆1, using a similar proof as Theorem 2, we have ∆1 = min{d(X1, s`), d(X3, sr) + d(X2, sr)}. In this case, BEST1 = d(X1, s`) + d(X2, sr) + d(X3, s`) + d(X4, s`) + d(X5, sr) ≥ d(X1, s`) + d(X2, sr) + d(X3, s`). Since dist(sc, smid) = c·dist(s` , sc) and dist(s` , smid) = dist(smid, sr), we have… view at source ↗
Figure 4
Figure 4. Figure 4: Case 3. opt1 is between s` and sc. Let α be a constant parameter in (0, 1). We will determine the value of α later. If d(X2, sr) + d(X3, s`) ≥ α · d(X1, s`), we have BEST1 ≥ d(X1, s`) + d(X2, sr) + d(X3, s`) ≥ (1 + α) · d(X1, s`) ≥ (1 + α) · ∆1. This means ∆1 ≤ 1/(1 + α) · BEST1. Otherwise, we have α · d(X1, s`) > d(X2, sr) + d(X3, s`) ≥ d(X2, sr) + |X3| · dist(opt1, s`) ≥ d(X2, sr) + |X3| |X1| · d(X1, s`)… view at source ↗
Figure 5
Figure 5. Figure 5: An example which shows the generalized mechanism is not strategyproof [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
read the original abstract

In this paper, we study the two-facility location game on a line with optional preference where the acceptable set of facilities for each agent could be different and an agent's cost is his distance to the closest facility within his acceptable set. The objective is to minimize the total cost of all agents while achieving strategyproofness. We design a deterministic strategyproof mechanism for the problem with approximation ratio of 2.75, improving upon the earlier best ratio of n/2+1.

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.

Referee Report

0 major / 3 minor

Summary. The paper studies the two-facility location game on a line metric under optional heterogeneous preferences, where each agent's acceptable set may differ and the agent's cost is the distance to the nearest acceptable facility. The objective is to minimize the aggregate cost while ensuring strategyproofness. The central claim is the existence of a deterministic strategyproof mechanism achieving a 2.75-approximation ratio, improving on the prior bound of n/2 + 1.

Significance. If the claimed mechanism and its analysis hold, the result supplies the first constant-factor deterministic strategyproof mechanism for this heterogeneous-preference variant, removing the linear dependence on n that appeared in earlier work. The improvement is load-bearing for the paper's contribution and would be of interest to the algorithmic mechanism design community working on facility location.

minor comments (3)
  1. [Abstract] Abstract, lines 3-5: the problem statement is clear, but the abstract provides no indication of the mechanism's construction or the key geometric argument used to obtain the 2.75 ratio; a one-sentence sketch would improve readability.
  2. The manuscript should include a formal definition of the optional-preference model (acceptable sets) and the precise line-metric distance function before the mechanism is presented, to avoid any ambiguity for readers unfamiliar with the prior n/2+1 result.
  3. Ensure that the proof of strategyproofness explicitly handles the case in which an agent reports an empty acceptable set or reports a set that excludes both facilities.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our work and for recommending minor revision. The referee's summary correctly captures the problem setting, our contribution of a deterministic strategyproof 2.75-approximation mechanism, and its improvement over the prior n/2+1 bound. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; mechanism constructed directly

full rationale

The paper constructs a deterministic strategyproof mechanism for the two-facility line problem under optional heterogeneous preferences and proves a 2.75 approximation ratio. No equations, parameters, or derivations are shown that reduce by construction to fitted inputs, self-definitions, or load-bearing self-citations. The central claim is the existence and analysis of one explicit mechanism; the geometric and preference model is the problem statement itself rather than an imported assumption. This is the normal non-circular outcome for a mechanism-design construction paper.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based on abstract only; no free parameters, invented entities, or explicit axioms beyond the problem definition of strategyproofness and approximation are visible.

axioms (1)
  • domain assumption Strategyproofness must hold for any reported locations and acceptable sets.
    Core requirement of the mechanism design problem stated in abstract.

pith-pipeline@v0.9.0 · 5604 in / 1058 out tokens · 16835 ms · 2026-05-24T18:45:17.784308+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages · 1 internal anchor

  1. [1]

    Mathematics of Operations Research 35(3), 513–526 (2010)

    Alon, N., Feldman, M., Procaccia, A.D., Tennenholtz, M.: Strategyproof approximation of the minimax on networks. Mathematics of Operations Research 35(3), 513–526 (2010)

    work page 2010

  2. [2]

    In: Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AA- MAS)

    Anastasiadis, E., Deligkas, A.: Heterogeneous facility location games. In: Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AA- MAS). pp. 623–631 (2018)

    work page 2018

  3. [3]

    Journal of political economy 58(4), 328–346 (1950)

    Arrow, K.J.: A difficulty in the concept of social welfare. Journal of political economy 58(4), 328–346 (1950)

    work page 1950

  4. [4]

    The Capacity Constrained Facility Location problem

    Aziz, H., Chan, H., Lee, B.E., Parkes, D.C.: The capacity constrained facility location problem. arXiv preprint arXiv:1806.00960 (2018)

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  5. [5]

    In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI)

    Cai, Q., Filos-Ratsikas, A., Tang, P.: Facility location with minimax envy. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI). pp. 137–143 (2016)

    work page 2016

  6. [6]

    In: International Symposium on Algo- rithmic Game Theory

    Chen, X., Hu, X., Jia, X., Li, M., Tang, Z., Wang, C.: Mechanism design for two-opposite- facility location games with penalties on distance. In: International Symposium on Algo- rithmic Game Theory. pp. 256–260. Springer (2018)

    work page 2018

  7. [7]

    In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)

    Chen, X., Li, M., Wang, C., Wang, C., Zhao, Y.: Truthful mechanisms for location games of dual-role facilities. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS). pp. 1470–1478 (2019) 14

    work page 2019

  8. [8]

    In: International Conference on Theory and Applications of Models of Computation

    Cheng, Y., Han, Q., Yu, W., Zhang, G.: Obnoxious facility game with a bounded service range. In: International Conference on Theory and Applications of Models of Computation. pp. 272–281. Springer (2013)

    work page 2013

  9. [9]

    In: Proceedings of the 5th International Conference on Combinatorial Optimization and Ap- plications (COCOA)

    Cheng, Y., Yu, W., Zhang, G.: Mechanisms for obnoxious facility game on a path. In: Proceedings of the 5th International Conference on Combinatorial Optimization and Ap- plications (COCOA). pp. 262–271 (2011)

    work page 2011

  10. [10]

    Theoretical Computer Science 497, 154–163 (2013)

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

    work page 2013

  11. [11]

    In: Proceedings of the 13th ACM Conference on Electronic Commerce (EC)

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

    work page 2012

  12. [12]

    In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)

    Duan, L., Li, B., Li, M., Xu, X.: Heterogeneous two-facility location games with minimum distance requirement. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS). pp. 1461–1469 (2019)

    work page 2019

  13. [13]

    In: Workshops at the 29th AAAI Conference on Artificial Intelligence (2015)

    Feigenbaum, I., Sethuraman, J.: Strategyproof mechanisms for one-dimensional hybrid and obnoxious facility location models. In: Workshops at the 29th AAAI Conference on Artificial Intelligence (2015)

    work page 2015

  14. [14]

    In: Proceedings of the 14th ACM Conference on Electronic Commerce (EC)

    Feldman, M., Wilf, Y.: Strategyproof facility lacation and the least squares objective. In: Proceedings of the 14th ACM Conference on Electronic Commerce (EC). pp. 873–890 (2013)

    work page 2013

  15. [15]

    Autonomous Agents and Multi-Agent Systems 31(6), 1209–1235 (2017)

    Filos-Ratsikas, A., Li, M., Zhang, J., Zhang, Q.: Facility location with double-peaked preferences. Autonomous Agents and Multi-Agent Systems 31(6), 1209–1235 (2017)

    work page 2017

  16. [16]

    In: Proceedings of the 32th AAAI Conference on Artificial Intelligence (AAAI)

    Fong, K.C., Li, M., Lu, P., Todo, T., Yokoo, M.: Facility location games with fractional preferences. In: Proceedings of the 32th AAAI Conference on Artificial Intelligence (AAAI). pp. 1039–1046 (2018)

    work page 2018

  17. [17]

    ACM Transactions on Economics and Computation 2(4), 15:1–15:37 (2014)

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

    work page 2014

  18. [18]

    Algo- rithmica 76(1), 143–167 (2016)

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

    work page 2016

  19. [19]

    Econometrica: Journal of the Econometric Society pp

    Gibbard, A.: Manipulation of voting schemes: a general result. Econometrica: Journal of the Econometric Society pp. 587–601 (1973)

    work page 1973

  20. [20]

    In: Pro- ceedings of the 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

    Ibara, K., Nagamochi, H.: Characterizing mechanisms in obnoxious facility game. In: Pro- ceedings of the 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA). pp. 301–311 (2012)

    work page 2012

  21. [21]

    In: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI)

    Keijzer, B.D., Wojtczak, D.: Facility reallocation on the line. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI). pp. 188–194 (2019)

    work page 2019

  22. [22]

    In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)

    Li, M., Mei, L., Xu, Y., Zhang, G., Zhao, Y.: Facility location games with externalities. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS). pp. 1443–1451 (2019)

    work page 2019

  23. [23]

    In: Proceedings 11th ACM Conference on Electronic Com- merce (EC-2010)

    Lu, P., Sun, X., Wang, Y., Allen Zhu, Z.: Asymptotically optimal strategy-proof mecha- nisms for two-facility games. In: Proceedings 11th ACM Conference on Electronic Com- merce (EC-2010). pp. 315–324 (2010) 15

    work page 2010

  24. [24]

    In: Proceedings of the 5th International Workshop on Internet and Network Economics (WINE)

    Lu, P., Wang, Y., Zhou, Y.: Tighter bounds for facility games. In: Proceedings of the 5th International Workshop on Internet and Network Economics (WINE). pp. 137–148 (2009)

    work page 2009

  25. [25]

    In: Proceedings of the 15th International Conference on Autonomous Agents and Multi-agent System (AAMAS)

    Mei, L., Li, M., Ye, D., Zhang, G.: Strategy-proof mechanism design for facility location games: Revisited (extended abstract). In: Proceedings of the 15th International Conference on Autonomous Agents and Multi-agent System (AAMAS). pp. 1463–1464 (2016)

    work page 2016

  26. [26]

    Theoretical Computer Science 734, 46–57 (2018)

    Mei, L., Ye, D., Zhang, G.: Mechanism design for one-facility location game with obnoxious effects on a line. Theoretical Computer Science 734, 46–57 (2018)

    work page 2018

  27. [27]

    Journal of Combinatorial Optimization 36(2), 549–571 (2018)

    Mei, L., Ye, D., Zhang, Y.: Approximation strategy-proof mechanisms for obnoxious facility location on a line. Journal of Combinatorial Optimization 36(2), 549–571 (2018)

    work page 2018

  28. [28]

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

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

    work page 1980

  29. [29]

    In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

    Nehama, I., Todo, T., Yokoo, M.: Manipulations-resistant facility location mechanisms for zv-line graphs. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems. pp. 1452–1460. International Foundation for Autonomous Agents and Multiagent Systems (2019)

    work page 2019

  30. [30]

    IEICE Transactions on Information and Systems99(3), 615–623 (2016)

    Oomine, M., Nagamochi, H.: Characterizing output locations of gsp mechanisms to obnox- ious facility game in trees. IEICE Transactions on Information and Systems99(3), 615–623 (2016)

    work page 2016

  31. [31]

    In: Proceedings of the 10th ACM Conference on Electronic Eommerce (EC)

    Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. In: Proceedings of the 10th ACM Conference on Electronic Eommerce (EC). pp. 177–186 (2009)

    work page 2009

  32. [32]

    Journal of economic theory 10(2), 187–217 (1975)

    Satterthwaite, M.A.: Strategy-proofness and arrow’s conditions: Existence and correspon- dence theorems for voting procedures and social welfare functions. Journal of economic theory 10(2), 187–217 (1975)

    work page 1975

  33. [33]

    Journal of Economic Theory 104(2), 405–428 (2002)

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

    work page 2002

  34. [34]

    In: Proceedings of the 21st European Conference on Artificial Intelligence (ECAI)

    Serafino, P., Ventre, C.: Heterogeneous facility location without money on the line. In: Proceedings of the 21st European Conference on Artificial Intelligence (ECAI). pp. 807– 812 (2014)

    work page 2014

  35. [35]

    In: Proceedings of the 29th AAAI Conference on Artificial Intelli- gence (AAAI)

    Serafino, P., Ventre, C.: Truthful mechanisms without money for non-utilitarian heteroge- neous facility location. In: Proceedings of the 29th AAAI Conference on Artificial Intelli- gence (AAAI). pp. 1029–1035 (2015)

    work page 2015

  36. [36]

    In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI)

    Sonoda, A., Todo, T., Yokoo, M.: False-name-proof locations of two facilities: Economic and algorithmic approaches. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI). pp. 615–621 (2016)

    work page 2016

  37. [37]

    SIAM Journal on Discrete Mathematics 4(4), 550–567 (1991)

    Tamir, A.: Obnoxious facility location on graphs. SIAM Journal on Discrete Mathematics 4(4), 550–567 (1991)

    work page 1991

  38. [38]

    In: Proceedings of the 6th International Conference on Internet and Network Economics (WINE)

    Thang, T.K.: On (group) strategy-proof mechanisms without payment for facility loca- tion games. In: Proceedings of the 6th International Conference on Internet and Network Economics (WINE). pp. 531–538 (2010)

    work page 2010

  39. [39]

    In: Proceedings of the 10th International Conference on Autonomous Agents and Multi-agent System (AAMAS)

    Todo, T., Iwasaki, A., Yokoo, M.: False-name-proof mechanism design without money. In: Proceedings of the 10th International Conference on Autonomous Agents and Multi-agent System (AAMAS). pp. 651–658 (2011) 16

    work page 2011

  40. [40]

    In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems

    Wada, Y., Ono, T., Todo, T., Yokoo, M.: Facility location with variable and dynamic populations. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. pp. 336–344. International Foundation for Autonomous Agents and Multiagent Systems (2018)

    work page 2018

  41. [41]

    In: Proceedings of the Twenty-second European Conference on Artificial Intelligence

    Yuan, H., Wang, K., Fong, K.C., Zhang, Y., Li, M.: Facility location games with op- tional preference. In: Proceedings of the Twenty-second European Conference on Artificial Intelligence. pp. 1520–1527. IOS Press (2016)

    work page 2016

  42. [42]

    Journal of Combinatorial Optimization 28(4), 756–773 (2014)

    Zhang, Q., Li, M.: Strategyproof mechanism design for facility location games with weighted agents on a line. Journal of Combinatorial Optimization 28(4), 756–773 (2014)

    work page 2014

  43. [43]

    In: Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)

    Zou, S., Li, M.: Facility location games with dual preference. In: Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). pp. 615–623 (2015) 17

    work page 2015