More Web Proxy on the site http://driver.im/

research-article

On Voting and Facility Location

Authors:

Michal Feldman,

Iddan GolombAuthors Info & Claims

EC '16: Proceedings of the 2016 ACM Conference on Economics and Computation

Pages 269 - 286

https://doi.org/10.1145/2940716.2940725

Published: 21 July 2016 Publication History

Abstract

We study mechanisms for candidate selection that seek to minimize the social cost, where voters and candidates are associated with points in some underlying metric space. The social cost of a candidate is the sum of its distances to each voter. Some of our work assumes that these points can be modeled on the real line, but other results of ours are more general.

A question closely related to candidate selection is that of minimizing the sum of distances for facility location. The difference is that in our setting there is a fixed set of candidates, whereas the large body of work on facility location considers every point in the metric space to be a possible candidate. This setting gives rise to three types of candidate selection mechanisms which differ in the granularity of their input space (single candidate, ranking and location mechanisms). We study the relationships between these three classes of mechanisms.

While it may seem that Black's 1948 median algorithm is optimal for candidate selection on the line, this is not the case. We give matching upper and lower bounds for a variety of settings. In particular, when candidates and voters are on the line, our universally truthful spike mechanism gives a [tight] approximation of two. When assessing candidate selection mechanisms, we seek several desirable properties: (a) efficiency (minimizing the social cost) (b) truthfulness (dominant strategy incentive compatibility) and (c) simplicity (a smaller input space). We quantify the effect that truthfulness and simplicity impose on the efficiency.

References

[1]

Noga Alon, Michal Feldman, Ariel D Procaccia, and Moshe Tennenholtz. 2009. Strategyproof approximation mechanisms for location on networks. arXiv preprint arXiv:0907.2049 (2009).

[2]

Noga Alon, Michal Feldman, Ariel D Procaccia, and Moshe Tennenholtz. 2010. Walking in circles. Discrete Mathematics 310, 23 (2010), 3432--3435.

Digital Library

[3]

Elliot Anshelevich, Onkar Bhardwaj, and John Postl. 2014. Approximating Optimal Social Choice under Metric Preferences. (2014).

[4]

Elliot Anshelevich and John Postl. 2015. Randomized Social Choice Functions Under Metric Preferences. arXiv preprint arXiv:1512.07590 (2015).

[5]

Haris Aziz, Florian Brandl, and Felix Brandt. 2014. On the Incompatibility of Efficiency and Strategyproofness in Randomized Social Choice. In AAAI. Citeseer, 545--551.

Digital Library

[6]

Duncan Black. 1948. On the rationale of group decision-making. The Journal of Political Economy (1948), 23--34.

[7]

Anna Bogomolnaia and Hervé Moulin. 2001. A new solution to the random assignment problem. Journal of Economic theory 100, 2 (2001), 295--328.

[8]

Craig Boutilier, Ioannis Caragiannis, Simi Haber, Tyler Lu, Ariel D Procaccia, and Or Sheffet. 2012. Optimal social choice functions: A utilitarian view. In Proceedings of the 13th ACM Conference on Electronic Commerce. ACM, 197--214.

Digital Library

[9]

Felix Brandt, Vincent Conitzer, and Ulle Endriss. 2012. Computational social choice. Multiagent systems (2012), 213--283.

[10]

Ioannis Caragiannis and Ariel D Procaccia. 2011. Voting almost maximizes social welfare despite limited communication. Artificial Intelligence 175, 9 (2011), 1655--1671.

Digital Library

[11]

Yukun Cheng, Wei Yu, and Guochuan Zhang. 2013. Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theoretical Computer Science 497 (2013), 154--163.

Digital Library

[12]

Elad Dokow, Michal Feldman, Reshef Meir, and Ilan Nehama. 2012. Mechanism design on discrete lines and cycles. In Proceedings of the 13th ACM Conference on Electronic Commerce. ACM, 423--440.

Digital Library

[13]

Anthony Downs. 1957. An economic theory of political action in a democracy. The journal of political economy (1957), 135--150.

[14]

Joan Feigenbaum, Aaron D Jaggard, and Michael Schapira. 2010. Approximate privacy: foundations and quantification. In Proceedings of the 11th ACM conference on Electronic commerce. ACM, 167--178.

Digital Library

[15]

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

[16]

Marcus Fleming. 1952. A cardinal concept of welfare. The Quarterly Journal of Economics (1952), 366--384.

[17]

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

[18]

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

Digital Library

[19]

Dimitris Fotakis, Christos Tzamos, and Emmanouil Zampetakis. 2015. Who to Trust for Truthfully Maximizing Welfare? arXiv preprint arXiv:1507.02301 (2015).

[20]

Allan Gibbard. 1973. Manipulation of voting schemes: a general result. Econometrica: journal of the Econometric Society (1973), 587--601.

[21]

J Harsanyi. 1955. ICardinal Welfare, Individualistic Ethics, and Interpersonal Comparisons of Welfare. J. Polit. Econ 63 (1955).

[22]

Harold Hotelling. 1990. Stability in competition. Springer.

[23]

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

[24]

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

[25]

Noam Nisan. 2007. Introduction to mechanism design (for computer scientists). Algorithmic game theory 209 (2007), 242.

[26]

Ariel D Procaccia and Jeffrey S Rosenschein. 2006. The distortion of cardinal preferences in voting. In Cooperative Information Agents X. Springer, 317--331.

Digital Library

[27]

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

[28]

Mark Allen Satterthwaite. 1975. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of economic theory 10, 2 (1975), 187--217.

[29]

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

[30]

Xin Sui and Craig Boutilier. 2011. Efficiency and Privacy Tradeoffs in Mechanism Design. In AAAI.

Digital Library

[31]

Xin Sui and Craig Boutilier. 2015. Approximately Strategy-proof Mechanisms for (Constrained) Facility Location. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 605--613.

Digital Library

[32]

Xin Sui, Craig Boutilier, and Tuomas W Sandholm. 2013. Analysis and optimization of multi-dimensional percentile mechanisms. AAAI.

Digital Library

Cited By

Voudouris A(2025)Metric Distortion of Obnoxious Distributed VotingInformation Processing Letters10.1016/j.ipl.2025.106559(106559)Online publication date: Jan-2025
https://doi.org/10.1016/j.ipl.2025.106559
Deligkas ALotfi MVoudouris A(2025)Agent-constrained truthful facility location gamesJournal of Combinatorial Optimization10.1007/s10878-025-01258-749:2Online publication date: 20-Jan-2025
https://doi.org/10.1007/s10878-025-01258-7
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
Show More Cited By

Index Terms

On Voting and Facility Location

Recommendations

Asymptotically optimal strategy-proof mechanisms for two-facility games
EC '10: Proceedings of the 11th ACM conference on Electronic commerce

We consider the problem of locating facilities in a metric space to serve a set of selfish agents. The cost of an agent is the distance between her own location and the nearest facility. The social cost is the total cost of the agents. We are interested ...
On the Power of Deterministic Mechanisms for Facility Location Games

We consider K-Facility Location games, where n strategic agents report their locations in a metric space and a mechanism maps them to K facilities. The agents seek to minimize their connection cost, namely the distance of their true location to the ...
Mechanisms for obnoxious facility game on a path
COCOA'11: Proceedings of the 5th international conference on Combinatorial optimization and applications

We consider a new facility game, namely, an obnoxious facility game where the facility is undesirable and all agents try to be as far away from the facility as possible. The social cost is the total distance between the agents and the facility. However, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '16: Proceedings of the 2016 ACM Conference on Economics and Computation

July 2016

874 pages

ISBN:9781450339360

DOI:10.1145/2940716

General Chair:
Vincent Conitzer
Duke University, USA
,
Program Chairs:
Dirk Bergemann
Yale University, USA
,
Yiling Chen
Harvard University, USA

Copyright © 2016 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: 21 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

ERC

Conference

EC '16

Sponsor:

SIGecom

EC '16: ACM Conference on Economics and Computation

July 24 - 28, 2016

Maastricht, The Netherlands

Acceptance Rates

EC '16 Paper Acceptance Rate 80 of 242 submissions, 33%;

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

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

70
Total Citations
View Citations
369
Total Downloads

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

Reflects downloads up to 26 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Voudouris A(2025)Metric Distortion of Obnoxious Distributed VotingInformation Processing Letters10.1016/j.ipl.2025.106559(106559)Online publication date: Jan-2025
https://doi.org/10.1016/j.ipl.2025.106559
Deligkas ALotfi MVoudouris A(2025)Agent-constrained truthful facility location gamesJournal of Combinatorial Optimization10.1007/s10878-025-01258-749:2Online publication date: 20-Jan-2025
https://doi.org/10.1007/s10878-025-01258-7
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 JZhang MDastani MSichman JAlechina NDignum V(2024)Extended Ranking Mechanisms for the m-Capacitated Facility Location Problem in Bayesian Mechanism DesignProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662855(87-95)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662855
Castro FRodilitz S(2024)Optimal Design of Default DonationsSSRN Electronic Journal10.2139/ssrn.4733483Online publication date: 2024
https://doi.org/10.2139/ssrn.4733483
Charikar MRamakrishnan PWang KWu H(2024)Breaking the Metric Voting Distortion BarrierJournal of the ACM10.1145/368962571:6(1-33)Online publication date: 20-Sep-2024
https://dl.acm.org/doi/10.1145/3689625
Kanellopoulos PVoudouris AZhang R(2024)Truthful Two-Facility Location with Candidate LocationsTheoretical Computer Science10.1016/j.tcs.2024.114913(114913)Online publication date: Oct-2024
https://doi.org/10.1016/j.tcs.2024.114913
Borodin ALev OShah NStrangway T(2024)Primarily About PrimariesArtificial Intelligence10.1016/j.artint.2024.104095(104095)Online publication date: Feb-2024
https://doi.org/10.1016/j.artint.2024.104095
Filos-Ratsikas AKanellopoulos PVoudouris AZhang R(2024)The Distortion of Distributed Facility LocationArtificial Intelligence10.1016/j.artint.2024.104066(104066)Online publication date: Jan-2024
https://doi.org/10.1016/j.artint.2024.104066
Zhao QLiu WNong QFang Q(2024)Constrained heterogeneous two-facility location games with sum-variantJournal of Combinatorial Optimization10.1007/s10878-024-01163-547:4Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1007/s10878-024-01163-5
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten