Cited By
View all- 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
Incentive-compatible selection for one or two influentials
AUTHORs: 
Yuxin Zhao, Yao Zhang, Dengji ZhaoAuthors Info & Claims
Article No.: 327, Pages 2931 - 2938
Abstract
Selecting influentials in networks against strategic manipulations has attracted many researchers' attention and it also has many practical applications. Here, we aim to select one or two influentials in terms of progeny (the influential power) and prevent agents from manipulating their edges (incentive compatibility). The existing studies mostly focused on selecting a single influential for this setting. Zhang et al. [2021] studied the problem of selecting one agent and proved an upper bound of 1/(1 + ln 2) to approximate the optimal selection. In this paper, we first design a mechanism to actually reach the bound. Then, we move this forward to choosing two agents and propose a mechanism to achieve an approximation ratio of (3 + ln 2)/(4(1 + ln 2)) (≈ 0.54).
References
[1]
Noga Alon, Felix Fischer, Ariel Procaccia, and Moshe Tennenholtz. Sum of us: Strategyproof selection from the selectors. In Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, pages 101-110, 2011.
[2]
Yakov Babichenko, Oren Dean, and Moshe Tennenholtz. Incentive-compatible diffusion. In Proceedings of the 2018 World Wide Web Conference, pages 1379-1388, 2018.
[3]
Yakov Babichenko, Oren Dean, and Moshe Tennenholtz. Incentive-compatible classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7055-7062, 2020.
[4]
Yakov Babichenko, Oren Dean, and Moshe Tennenholtz. Incentive-compatible selection mechanisms for forests. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 111- 131, 2020.
[5]
Antje Bjelde, Felix Fischer, and Max Klimm. Impartial selection and the power of up to two choices. ACM Transactions on Economics and Computation (TEAC), 5(4):1-20, 2017.
[6]
Nicolas Bousquet, Sergey Norin, and Adrian Vetta. A near-optimal mechanism for impartial selection. In International Conference on Web and Internet Economics, pages 133-146. Springer, 2014.
[7]
Ioannis Caragiannis, George Christodoulou, and Nicos Protopapas. Impartial selection with prior information. arXiv preprint arXiv:2102.09002, 2021.
[8]
Ioannis Caragiannis, George Christodoulou, and Nicos Protopapas. Impartial selection with additive approximation guarantees. Theory of Computing Systems, pages 1-22, 2022.
[9]
Javier Cembrano, Felix A. Fischer, David Hannon, and Max Klimm. Impartial selection with additive guarantees via iterated deletion. In EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022, pages 1104-1105. ACM, 2022.
[10]
Felix Fischer and Max Klimm. Optimal impartial selection. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 803-820, 2014.
[11]
Ganesh Ghalme, Sujit Gujar, Amleshwar Kumar, Shweta Jain, and Y Narahari. Design of coalition resistant credit score functions for online discussion forums. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 95-103, 2018.
[12]
Ron Holzman and Hervé Moulin. Impartial nominations for a prize. Econometrica, 81(1):173-196, 2013.
[13]
Anson Kahng, Yasmine Kotturi, Chinmay Kulkarni, David Kurokawa, and Ariel Procaccia. Ranking wily people who rank each other. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[14]
Yasmine Kotturi, Anson Kahng, Ariel Procaccia, and Chinmay Kulkarni. Hirepeer: Impartial peer-assessed hiring at scale in expert crowdsourcing markets. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 2577-2584, 2020.
[15]
David Kurokawa, Omer Lev, Jamie Morgenstern, and Ariel D Procaccia. Impartial peer review. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
[16]
Andrew Mackenzie. Symmetry and impartial lotteries. Games and Economic Behavior, 94:15- 28, 2015.
[17]
Nicholas Mattei, Paolo Turrini, and Stanislav Zhydkov. Peernomination: Relaxing exactness for increased accuracy in peer selection. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 393-399. ijcai.org, 2020.
[18]
Matthew Olckers and Toby Walsh. Manipulation and peer mechanisms: A survey. arXiv preprint arXiv:2210.01984, 2022.
[19]
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
[20]
Yufeng Wang, Hui Fang, Chonghu Cheng, and Qun Jin. Tsp: Truthful grading-based strategyproof peer selection for moocs. In 2018 IEEE International Conference on Teaching, Assessment, and Learning for Engineering (TALE), pages 679-684. IEEE, 2018.
[21]
Xiuzhen Zhang, Yao Zhang, and Dengji Zhao. Incentive compatible mechanism for influential agent selection. In International Symposium on Algorithmic Game Theory, pages 79-93. Springer, 2021.
Index Terms
- Incentive-compatible selection for one or two influentials
Index terms have been assigned to the content through auto-classification.
Recommendations
Incentive compatible budget elicitation in multi-unit auctions
SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithmsIn this paper, we consider the problem of designing incentive compatible auctions for multiple (homogeneous) units of a good, when bidders have private valuations and private budget constraints. When only the valuations are private and the budgets are ...
Incentive-Compatible Learning of Reserve Prices for Repeated Auctions
How can an auctioneer optimize revenue by learning the reserve prices from the bids in the previous auctions? How should the long-term incentives and strategic behavior of the bidders be taken into account? Motivated in part by applications in online ...
Large fractions of online advertisements are sold via repeated second-price auctions. In these auctions, the reserve price is the main tool for the auctioneer to boost revenues. In this work, we investigate the following question: how can the auctioneer ...
Incentive Compatible Mechanism for Influential Agent Selection
Algorithmic Game TheoryAbstractSelecting 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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2023 International Joint Conferences on Artificial Intelligence.
Sponsors
- International Joint Conferences on Artifical Intelligence (IJCAI)
Publisher
Unknown publishers
Publication History
Published: 19 August 2023
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 10 Nov 2024
Other Metrics
Citations
Cited By
View all- 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