Yakov Babichenko
Moshe Tennenholtz
ABSTRACT
Our work bridges the literature on incentive-compatible mechanism design and the literature on diffusion algorithms. We introduce the study of finding an incentive-compatible (strategy-proof) mechanism for selecting an influential vertex in a directed graph (e.g. Twitter»s network). The goal is to devise a mechanism with a bounded ratio between the maximal influence and the influence of the selected user, and in which no user can improve its probability of being selected by following or unfollowing other users. We introduce the Two Path mechanism which is based on the idea of selecting the vertex that is the first intersection of two independent random walks in the network. The Two Path mechanism is incentive compatible on directed acyclic graphs (DAGs), and has a finite approximation ratio on natural subfamilies of DAGs. Simulations indicate that this mechanism is suitable for practical uses.
- 2017. Wikipedia. (October 2017 2017). http://en.wikipedia.org/wiki/PageRank# Simplified_algorithmGoogle Scholar
- 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). ACM, New York, NY, USA, 101--110. Google ScholarDigital Library
- Reid Andersen, Christian Borgs, Jennifer Chayes, Uriel Feige, Abraham Flaxman, Adam Kalai, Vahab Mirrokni, and Moshe Tennenholtz. 2008. Trust-based Recommendation Systems: An Axiomatic Approach. In Proceedings of the 17th International Conference on World Wide Web (WWW '08). ACM, New York, NY, USA, 199--208. Google ScholarDigital Library
- Sofía Aparicio, Javier Villazón-Terrazas, and Gonzalo Álvarez. 2015. A Model for Scale-Free Networks: Application to Twitter. Entropy 17 (2015), 5848--5867.Google ScholarCross Ref
- 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 Google ScholarDigital Library
- Albert-László Barabási and Réka Albert. 1999. Emergence of Scaling in Random Networks. Science 286, 5439 (1999), 509--512. arXiv:http://science.sciencemag.org/content/286/5439/509.full.pdfGoogle Scholar
- Stefan Bornholdt and Heinz Georg Schuster (Eds.). 2003. Handbook of Graphs and Networks: From the Genome to the Internet. John Wiley & Sons, Inc., New York, NY, USA. Google ScholarDigital Library
- Sergey Brin and Lawrence Page. 1998. The Anatomy of a Large-scale Hypertextual Web Search Engine. Comput. Netw. ISDN Syst. 30, 1--7 (April 1998), 107--117. Google ScholarDigital Library
- Guido Caldarelli. 2007. Scale-Free Networks. Oxford University Press.Google Scholar
- S. N. Dorogovtsev and J. F. F. Mendes. 2002. Evolution of networks. Advances in Physics 51 (June 2002), 1079--1187. arXiv:cond-mat/0106144Google Scholar
- S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin. 2000. Structure of Growing Networks with Preferential Linking. Physical Review Letters 85 (Nov. 2000), 4633-- 4636. arXiv:cond-mat/0004434Google Scholar
- David Easley and Jon Kleinberg. 2010. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press. Google ScholarDigital Library
- Scott L. Feld. 1991. Why Your Friends Have More Friends Than You Do. Amer. J. Sociology 96, 6 (1991), 1464--1477. http://www.jstor.org/stable/2781907Google ScholarCross Ref
- Felix Fischer and Max Klimm. 2014. Optimal Impartial Selection. In Proceedings of the Fifteenth ACM Conference on Economics and Computation (EC '14). ACM, New York, NY, USA, 803--820. Google ScholarDigital Library
- J. Goldenberg, B. Libai, and Muller. 2001. Using complex systems analysis to advance marketing theory development. Academy of Marketing Science Review (2001).Google Scholar
- Jacob Goldenberg, Barak Libai, and Eitan Muller. 2001. Talk of the Network: A Complex Systems Look at the Underlying Process of Word-of-Mouth. Marketing Letters 12, 3 (2001), 211--223.Google ScholarCross Ref
- S. Gualdi, M. Medo, and Y.-C. Zhang. 2011. Influence, originality and similarity in directed acyclic graphs. EPL (Europhysics Letters) 96, 1 (2011), 18004. http: //stacks.iop.org/0295--5075/96/i=1/a=18004Google ScholarCross Ref
- Ron Holzman and Hervé Moulin. 2013. Impartial Nominations for a Prize. Econometrica 81, issue 1 (2013), 173-196.Google Scholar
- David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the Spread of Influence Through a Social Network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '03). ACM, New York, NY, USA, 137--146. Google ScholarDigital Library
- 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 Google ScholarDigital Library
- Silvio Lattanzi and Yaron Singer. 2015. The Power of Random Neighbors in Social Networks. In Proceedings of the Eighth ACM International Conference on Web Search and Data Mining (WSDM '15). ACM, New York, NY, USA, 77--86. Google ScholarDigital Library
- Beiming Sun and Vincent TY Ng. 2012. Identifying Influential Users by Their Postings in Social Networks. In Proceedings of the 3rd International Workshop on Modeling Social Media (MSM '12). ACM, New York, NY, USA, 1--8. Google ScholarDigital Library
- Shohei Tamura. 2016. Characterizing minimal impartial rules for awarding prizes. Games and Economic Behavior 95, Supplement C (2016), 41 -- 46.Google ScholarCross Ref
- Michael Trusov, Anand V. Bodapati, and Randolph E. Bucklin. 2010. Determining Influential Users in Internet Social Networks. Journal of Marketing Research 47, 4 (2010), 643--658.Google ScholarCross Ref
- Yufeng Wang, Athanasios V. Vasilakos, Qun Jin, and Jianhua Ma. 2015. PPRank: Economically Selecting Initial Users for Influence Maximization in Social Networks. IEEE Systems Journal PP (Jan. 2015), 1--12. Issue 99.Google Scholar
Index Terms
- Incentive-Compatible Diffusion
Recommendations
Incentive-compatible diffusion auctions
IJCAI'20: Proceedings of the Twenty-Ninth International Joint Conference on Artificial IntelligenceDiffusion auction is a new model in auction design. It can incentivize the buyers who have already joined in the auction to further diffuse the sale information to others via social relations, whereby both the seller's revenue and the social welfare can ...
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
WWW '19: Companion Proceedings of The 2019 World Wide Web ConferenceMotivated by online advertising market, we consider a seller who repeatedly sells ex ante identical items via the second-price auction. Buyers’ valuations for each item are drawn i.i.d. from a distribution F that is unknown to the seller. We find that ...
Comments