research-article

Incentive-Compatible Selection Mechanisms for Forests

Authors:

Yakov Babichenko,

Moshe TennenholtzAuthors Info & Claims

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

Pages 111 - 131

https://doi.org/10.1145/3391403.3399456

Published: 13 July 2020 Publication History

Abstract

Given a directed forest-graph, a probabilistic selection mechanismis a probability distribution over the vertex set. A selection mechanism is incentive-compatible(IC), if the probability assigned to a vertex does not change when we alter its outgoing edge (or even remove it). The quality of a selection mechanism is the worst-case ratio between the expected progeny under the mechanism's distribution and the maximal progeny in the forest. In this paper we prove an upper bound of 4/5 and a lower bound of 1/łn16 ~0.36 for the quality of any IC selection mechanism. The lower bound is achieved by two novel mechanisms and is a significant improvement to the results of Babichenko et al. (WWW '18). The first, simpler mechanism, has the nice feature of generating distributions which are fair (i.e., monotone and proportional). The downside of this mechanism is that it is not exact (i.e., the probabilities might sum-up to less than 1). Our second, more involved mechanism, is exact but not fair. We also prove an impossibility for an IC mechanism that is both exact and fair and has a positive quality.

References

[1]

Zeinab Abbassi and Vishal Misra. 2011. Multi-level Revenue Sharing for Viral Marketing. In Proceedings of ACM NetEcon 2011.

[2]

Noga Alon, Felix Fischer, Ariel Procaccia, and Moshe Tennenholtz. 2011. Sum of Us: Strategyproof Selection from the Selectors. In Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge (TARK XIII). 101--110. https://doi.org/10.1145/2000378.2000390

Digital Library

[3]

Alon Altman and Moshe Tennenholtz. 2008. Axiomatic Foundations for Ranking Systems. Journal of Artificial Intelligence Research, Vol. 31, 1 (March 2008), 473--495. http://dl.acm.org/citation.cfm?id=1622655.1622669

[4]

Haris Aziz, Omer Lev, Nicholas Mattei, Jeffrey S. Rosenschein, and Toby Walsh. 2016. Strategyproof Peer Selection: Mechanisms, Analyses, and Experiments. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI'16). AAAI Press, 390--396. http://dl.acm.org/citation.cfm?id=3015812.3015872

Digital Library

[5]

Moshe Babaioff, Shahar Dobzinski, Sigal Oren, and Aviv Zohar. 2011. On Bitcoin and Red Balloons. SIGecom Exch., Vol. 10, 3 (Dec. 2011), 5--9. https://doi.org/10.1145/2325702.2325704

Digital Library

[6]

Moshe Babaioff, Moran Feldman, and Moshe Tennenholtz. 2016. Mechanism Design with Strategic Mediators. ACM Trans. Econ. Comput., Vol. 4, 2, Article 7 (Jan. 2016), 48 pages. https://doi.org/10.1145/2841227

Digital Library

[7]

Yakov Babichenko, Oren Dean, and Moshe Tennenholtz. 2018. Incentive-Compatible Diffusion. In Proceedings of the 2018 World Wide Web Conference (WWW '18). 1379--1388. https://doi.org/10.1145/3178876.3186043

[8]

Antje Bjelde, Felix Fischer, and Max Klimm. 2017. Impartial Selection and the Power of Up to Two Choices. ACM Trans. Econ. Comput., Vol. 5, 4, Article 21 (Dec. 2017), 20 pages. https://doi.org/10.1145/3107922

Digital Library

[9]

Nicolas Bousquet, Sergey Norin, and Adrian Vetta. 2014. A Near-Optimal Mechanism for Impartial Selection. In Web and Internet Economics, Tie-Yan Liu, Qi Qi, and Yinyu Ye (Eds.). Springer International Publishing, Cham, 133--146.

[10]

Guido Caldarelli. 2007. Scale-Free Networks .Oxford University Press.

[11]

John R. Douceur and Thomas Moscibroda. 2007. Lottery Trees: Motivational Deployment of Networked Systems. SIGCOMM Comput. Commun. Rev., Vol. 37, 4 (Aug. 2007), 121--132. https://doi.org/10.1145/1282427.1282395

Digital Library

[12]

Yuval Emek, Ron Karidi, Moshe Tennenholtz, and Aviv Zohar. 2011. Mechanisms for Multi-level Marketing. In Proceedings of the 12th ACM Conference on Electronic Commerce (EC '11). 209--218. https://doi.org/10.1145/1993574.1993606

Digital Library

[13]

Felix Fischer and Max Klimm. 2014. Optimal Impartial Selection. In Proceedings of the Fifteenth ACM Conference on Economics and Computation (EC '14). 803--820. https://doi.org/10.1145/2600057.2602836

Digital Library

[14]

Ron Holzman and Hervé Moulin. 2013. Impartial Nominations for a Prize. Econometrica, Vol. 81, 1 (2013), 173--196. https://doi.org/10.3982/ECTA10523

[15]

David Kurokawa, Omer Lev, Jamie Morgenstern, and Ariel D. Procaccia. 2015. Impartial Peer Review. In Proceedings of the 24th International Conference on Artificial Intelligence (IJCAI'15). AAAI Press, 582--588. http://dl.acm.org/citation.cfm?id=2832249.2832330

Digital Library

[16]

Andrew Mackenzie. 2015. Symmetry and impartial lotteries. Games and Economic Behavior, Vol. 94 (2015), 15--28. https://doi.org/10.1016/j.geb.2015.08.007

[17]

Ariel D. Procaccia and Moshe Tennenholtz. 2013. Approximate Mechanism Design Without Money. ACM Trans. Econ. Comput., Vol. 1, 4, Article 18 (Dec. 2013), 26 pages. https://doi.org/10.1145/2542174.2542175

Digital Library

Cited By

Cembrano JGriesbach SStahlberg M(2024)Deterministic Impartial Selection with WeightsACM Transactions on Economics and Computation10.1145/367717712:3(1-22)Online publication date: 6-Sep-2024
https://dl.acm.org/doi/10.1145/3677177
Cembrano JFischer FHannon DKlimm M(2024)Impartial Selection with Additive Guarantees via Iterated DeletionGames and Economic Behavior10.1016/j.geb.2024.01.008Online publication date: Feb-2024
https://doi.org/10.1016/j.geb.2024.01.008
Olckers MWalsh T(2024)Manipulation and Peer Mechanisms: A SurveyArtificial Intelligence10.1016/j.artint.2024.104196(104196)Online publication date: Aug-2024
https://doi.org/10.1016/j.artint.2024.104196
Show More Cited By

Index Terms

Incentive-Compatible Selection Mechanisms for Forests
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Algorithmic mechanism design

Recommendations

Incentive Compatible Mechanism for Influential Agent Selection
Algorithmic Game Theory
Abstract
Selecting the most influential agent in a network has huge practical value in applications. However, in many scenarios, the graph structure can only be known from agents’ reports on their connections. In a self-interested setting, agents may ...
Collusion-resistant, incentive-compatible feedback payments
EC '07: Proceedings of the 8th ACM conference on Electronic commerce

Online reputation mechanisms need honest feedback to function effectively. Self-interested agents report the truth only when explicit rewards offset the potential gains obtained from lying. Feedback payment schemes (monetary rewardsfor submitted ...
Incentive Compatible Mechanisms Without Money

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

European Research Council

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

9
Total Citations
View Citations
113
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cembrano JGriesbach SStahlberg M(2024)Deterministic Impartial Selection with WeightsACM Transactions on Economics and Computation10.1145/367717712:3(1-22)Online publication date: 6-Sep-2024
https://dl.acm.org/doi/10.1145/3677177
Cembrano JFischer FHannon DKlimm M(2024)Impartial Selection with Additive Guarantees via Iterated DeletionGames and Economic Behavior10.1016/j.geb.2024.01.008Online publication date: Feb-2024
https://doi.org/10.1016/j.geb.2024.01.008
Olckers MWalsh T(2024)Manipulation and Peer Mechanisms: A SurveyArtificial Intelligence10.1016/j.artint.2024.104196(104196)Online publication date: Aug-2024
https://doi.org/10.1016/j.artint.2024.104196
Zhao YZhang YZhao DElkind E(2023)Incentive-compatible selection for one or two influentialsProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/327(2931-2938)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/327
Caragiannis IChristodoulou GProtopapas N(2023)Impartial Selection with Prior InformationProceedings of the ACM Web Conference 202310.1145/3543507.3583553(3614-3624)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583553
Cembrano JGriesbach SStahlberg M(2023)Deterministic Impartial Selection with WeightsWeb and Internet Economics10.1007/978-3-031-48974-7_9(151-168)Online publication date: 31-Dec-2023
https://doi.org/10.1007/978-3-031-48974-7_9
Cembrano JFischer FKlimm M(2022)Optimal Impartial CorrespondencesWeb and Internet Economics10.1007/978-3-031-22832-2_11(187-203)Online publication date: 9-Dec-2022
https://doi.org/10.1007/978-3-031-22832-2_11
Su WRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)You are the best reviewer of your own papersProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3542400(27929-27939)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3542400
Zhang XZhang YZhao D(2021)Incentive Compatible Mechanism for Influential Agent SelectionAlgorithmic Game Theory10.1007/978-3-030-85947-3_6(79-93)Online publication date: 14-Sep-2021
https://doi.org/10.1007/978-3-030-85947-3_6

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents