research-article

Public Access

Characterization of Group-strategyproof Mechanisms for Facility Location in Strictly Convex Space

Authors:

Pingzhong Tang,

Shengyu ZhaoAuthors Info & Claims

EC '20: Proceedings of the 21st ACM Conference on Economics and Computation

Pages 133 - 157

https://doi.org/10.1145/3391403.3399471

Published: 13 July 2020 Publication History

Abstract

We characterize the class of group-strategyproof mechanisms for the single facility location game in any unconstrained strictly convex space. A mechanism is group-strategyproof,if no group of agents can misreport so that all its members are strictlybetter off. A strictly convex space is a normed vector space where |x+y|<2 holds for any pair of different unit vectors x ≠ y, e.g., any Lp space with p∈ (1,∞).

We show that any deterministic, unanimous, group-strategyproof mechanism must be dictatorial, and that any randomized, unanimous, translation-invariant, group-strategyproof mechanism must be 2-dictatorial.Here a randomized mechanism is 2-dictatorial if the lottery output of the mechanism must be distributed on the line segment between two dictators' inputs. A mechanism is translation-invariant if the output of the mechanism follows the same translation of the input.

Our characterization directly implies that any (randomized) translation-invariant approximation algorithm satisfying the group-strategyproofness property has a lower bound of 2-approximation for maximum cost (whenever n ≥ 3), and n/2 - 1 for social cost. We also find an algorithm that 2-approximates the maximum cost and n/2-approximates the social cost, proving the bounds to be (almost) tight.

References

[1]

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

[2]

Salvador Barberà, Faruk Gul, and Ennio Stacchetti. 1993. Generalized median voter schemes and committees. Journal of Economic Theory, Vol. 61, 2 (1993), 262--289.

[3]

Salvador Barberà, Jordi Massó, and Shigehiro Serizawa. 1998. Strategy-proof voting on compact ranges. games and economic behavior, Vol. 25, 2 (1998), 272--291.

[4]

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

[5]

G Bordes, G Laffond, and M Le Breton. 1990. Strategy-proofness issues in some economic and political domains. Unpublished Manuscript, University of Bordeaux (1990).

[6]

Georges Bordes, Gilbert Laffond, and Michel Le Breton. 2011. Euclidean preferences, option sets and strategyproofness. SERIEs, Vol. 2, 4 (2011), 469--483.

[7]

Qingpeng Cai, Aris Filos-Ratsikas, and Pingzhong Tang. 2016. Facility location with minimax envy. AAAI Press/International Joint Conferences on Artificial Intelligence.

[8]

Bruno Escoffier, Laurent Gourves, Nguyen Kim Thang, Fanny Pascual, and Olivier Spanjaard. 2011. Strategy-proof mechanisms for facility location games with many facilities. In International Conference on Algorithmic Decision Theory. Springer, 67--81.

Digital Library

[9]

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

Digital Library

[10]

Michal Feldman, Amos Fiat, and Iddan Golomb. 2016. On voting and facility location. In Proceedings of the 2016 ACM Conference on Economics and Computation. ACM, 269--286.

Digital Library

[11]

Michal Feldman and Yoav Wilf. 2013. Strategyproof facility location and the least squares objective. In Proceedings of the fourteenth ACM conference on Electronic commerce. ACM, 873--890.

Digital Library

[12]

Aris Filos-Ratsikas, Minming Li, Jie Zhang, and Qiang Zhang. 2017. Facility location with double-peaked preferences. Autonomous Agents and Multi-Agent Systems, Vol. 31, 6 (2017), 1209--1235.

Digital Library

[13]

Chi Kit Ken Fong, Minming Li, Pinyan Lu, Taiki Todo, and Makoto Yokoo. 2018. Facility location games with fractional preferences. In Thirty-Second AAAI Conference on Artificial Intelligence .

[14]

Dimitris Fotakis and Christos Tzamos. 2013. Strategyproof facility location for concave cost functions. In Proceedings of the fourteenth ACM conference on Electronic commerce. ACM, 435--452.

Digital Library

[15]

Dimitris Fotakis and Christos Tzamos. 2014. On the power of deterministic mechanisms for facility location games. ACM Transactions on Economics and Computation, Vol. 2, 4 (2014), 15.

Digital Library

[16]

Allan Gibbard et al. 1977. Manipulation of schemes that mix voting with chance. Econometrica, Vol. 45, 3 (1977), 665--681.

[17]

Noah Golowich, Harikrishna Narasimhan, and David C Parkes. 2018. Deep Learning for Multi-Facility Location Mechanism Design. In IJCAI. 261--267.

[18]

Pinyan Lu, Xiaorui Sun, Yajun Wang, and Zeyuan Allen Zhu. 2010. Asymptotically optimal strategy-proof mechanisms for two-facility games. In Proceedings of the 11th ACM conference on Electronic commerce. ACM, 315--324.

Digital Library

[19]

Hervé Moulin. 1980. On strategy-proofness and single peakedness. Public Choice, Vol. 35, 4 (1980), 437--455.

[20]

Hans Peters, Hans van der Stel, and Ton Storcken. 1993. Range convexity, continuity, and strategy-proofness of voting schemes. Zeitschrift für Operations Research, Vol. 38, 2 (1993), 213--229.

[21]

Ariel D Procaccia and Moshe Tennenholtz. 2009. Approximate mechanism design without money. In Proceedings of the 10th ACM conference on Electronic commerce. ACM, 177--186.

Digital Library

[22]

James Schummer and Rakesh V Vohra. 2002. Strategy-proof location on a network. Journal of Economic Theory, Vol. 104, 2 (2002), 405--428.

[23]

Xin Sui. 2015. Mechanism Design for Multi-dimensional Facility Location Problems: A Computational and Informational Perspective. Ph.D. Dissertation. University of Toronto (Canada).

Cited By

Fang JLiu WDastani MSichman JAlechina NDignum V(2024)Facility Location Games with Fractional Preferences and Limited ResourcesProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662906(553-561)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662906
Auricchio GZhang J(2024)The k-Facility Location Problem via Optimal Transport: A Bayesian Study of the Percentile MechanismsAlgorithmic Game Theory10.1007/978-3-031-71033-9_9(147-164)Online publication date: 31-Aug-2024
https://doi.org/10.1007/978-3-031-71033-9_9
Xu XZhang JXie L(2023)Minmax for facility location game with optional preference under minimum distance requirementJournal of Combinatorial Optimization10.1007/s10878-023-01087-646:4Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1007/s10878-023-01087-6
Show More Cited By

Index Terms

Characterization of Group-strategyproof Mechanisms for Facility Location in Strictly Convex Space
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Algorithmic game theory
      2. Algorithmic mechanism design

Recommendations

Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing Lp Norm of Costs

This paper is concerned with the problem of locating a facility on a line in the presence of strategic agents, also located on that line. Each agent incurs a cost equal to her distance to the facility whereas the planner wishes to minimize the L_p norm ...
Facility location games with ordinal preferences
Abstract
In this paper we study a novel model of facility location games with ordinal preferences. There is a set of self-interested agents and a set of heterogeneous facilities. Each agent is located on a line and has an ordinal preference over the ...
Nearly Complete Characterization of 2-Agent Deterministic Strategyproof Mechanisms for Single Facility Location in $L_{p}$ Space
Combinatorial Optimization and Applications
Abstract
We consider the problem of locating a single facility for 2 agents in $L_{p}$ space ( $1 < p < \infty$ ) and give a nearly complete characterization of such deterministic strategyproof mechanisms. We use the distance between an agent and the facility in $L_{p}$ space to ...
$_{}$
$_{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '20: Proceedings of the 21st ACM Conference on Economics and Computation

July 2020

937 pages

ISBN:9781450379755

DOI:10.1145/3391403

General Chairs:
Péter Biró
Hungarian Academy of Sciences
,
Jason Hartline
Northwestern University
,
Program Chairs:
Michael Ostrovsky
Stanford University
,
Ariel Procaccia
Harvard University

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Beijing Academy of Artificial Intelligence (BAAI)
NSF
Science and Technology Innovation 2030 - "New GenerationArtificial Intelligence" Major Project

Conference

EC '20

Sponsor:

SIGecom

EC '20: The 21st ACM Conference on Economics and Computation

July 13 - 17, 2020

Virtual Event, Hungary

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
256
Total Downloads

Downloads (Last 12 months)76
Downloads (Last 6 weeks)8

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fang JLiu WDastani MSichman JAlechina NDignum V(2024)Facility Location Games with Fractional Preferences and Limited ResourcesProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662906(553-561)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662906
Auricchio GZhang J(2024)The k-Facility Location Problem via Optimal Transport: A Bayesian Study of the Percentile MechanismsAlgorithmic Game Theory10.1007/978-3-031-71033-9_9(147-164)Online publication date: 31-Aug-2024
https://doi.org/10.1007/978-3-031-71033-9_9
Xu XZhang JXie L(2023)Minmax for facility location game with optional preference under minimum distance requirementJournal of Combinatorial Optimization10.1007/s10878-023-01087-646:4Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1007/s10878-023-01087-6
Goel SHann-Caruthers W(2022)Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensionsSocial Choice and Welfare10.1007/s00355-022-01435-161:1(11-34)Online publication date: 25-Oct-2022
https://doi.org/10.1007/s00355-022-01435-1
Duan LGong ZLi MWang CWu X(2021)Mechanism Design for Facility Location with Fractional Preferences and Minimum DistanceComputing and Combinatorics10.1007/978-3-030-89543-3_42(499-511)Online publication date: 20-Oct-2021
https://doi.org/10.1007/978-3-030-89543-3_42
Lin J(2020)Nearly Complete Characterization of 2-Agent Deterministic Strategyproof Mechanisms for Single Facility Location in $$L_p$$ SpaceCombinatorial Optimization and Applications10.1007/978-3-030-64843-5_28(411-425)Online publication date: 4-Dec-2020
https://doi.org/10.1007/978-3-030-64843-5_28

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents