Maximal information propagation via lotteries

Jing Chen; Bo Li

doi:10.55092/blockchain20230003

Article

Open Access

Maximal information propagation via lotteries

Jing Chen¹^,∗Bo Li²^,∗

¹ Algorand Inc, Boston, USA

² Department of Computing, Hong Kong Polytechnic University, Hong Kong, China

* jing@algorand.com; comp-bo.li@polyu.edu.hk

Volume
Volume 1 Issue 1, 2023
Citation
Chen J, Li B. Maximal information propagation via lotteries. Blockchain 2023(1):0003, https://doi.org/10.55092/blockchain20230003.
DOI
10.55092/blockchain20230003
Copyright
Copyright2023 by the authors. Published by ELSP.

Abstract

Propagating information to more people through their friends is becoming an increasingly important technology used in domains such as blockchain, advertising, and social media. To incentivize people to broadcast the information, the designer may use a monetary rewarding scheme, which specifies who gets how much, to compensate for the propagation. Several properties are desirable for the rewarding scheme, such as budget feasible, individually rational, incentive compatible, and Sybil-proof. In this work, we design a free market with lotteries, where every participant can decide by herself how much of the reward she wants to withhold before propagating to others. We show that in the free market, the participants have a strong incentive to maximally propagate the information and all the above properties are satisfied automatically.

Keywords

Information propagation, Nash equilibrium, free market design

Preview

view pdf

References

[1]Drucker F, Fleischer L. Simpler sybil-proof mechanisms for multi-level marketing. In EC ’12: Proceedings of the 13th ACM Conference on Electronic Commerce, New York: ACM, 2012. 441–458.
[2]Babaioff M, Dobzinski S, Oren S, Zohar A. On bitcoin and red balloons. In EC Please spell out the conference name, New York: ACM, 2012. 56–73.
[3]Ersoy O, Erkin Z, Lagendijk R. L. Decentralized incentive-compatible and sybilproof transaction advertisement. In Mathematical Research for Blockchain Economy, Cham: Springer, 2019. 151–165.
[4]Shi H, Zhang Y, Si Z, Wang L, Zhao D. Maximal information propagation with budgets. Front Artif Intell Appl 2020, 325, 211–218.
[5]Chen B B, Chan M C. Mobicent: a credit-based incentive system for disruption tolerant network. In INFOCOM, New York: IEEE, 2010.875–883.
[6]Nakamoto S. Bitcoin: A peer-to-peer electronic cash system. 2008.
[7]Bernheim B D, Peleg B, Whinston M D Coalition-proof nash equilibria i. concepts. J Econ Theory 1987, 42(1):1–12.
[8]Myerson R B. Graphs and cooperation in games. Math Oper Res 1977, 2(3):225–229.
[9]Douceur J R. The sybil attack. Lect Notes Comput Sci 2002, 2429, 251–260.
[10]Ersoy O, Ren Z, Erkin Z, Lagendijk R L. Transaction propagation on permissionless blockchains: Incentive and routing mechanisms. In 2018 Crypto Valley Conference on Blockchain Technology, New York: IEEE, 2018. 20–30.
[11]Abraham I, Malkhi D, Nayak K, Ren L, Spiegelman A. Solidus: An incentivecompatible cryptocurrency based on permissionless byzantine consensus. In arXiv 2016 arXiv:1612.02916.
[12]Chen J, Gilad Y. A relay market for the algorand blockchain. Manuscript, 2018.
[13]Chen X, Papadimitriou C H, Roughgarden T. An axiomatic approach to block rewards. In AFT ’19: Proceedings of the 1st ACM Conference on Advances in Financial Technologies, New York: ACM, 2019. 124–131.
[14]Eyal I, Sirer E G Majority is not enough: Bitcoin mining is vulnerable. N. Christin and R. Safavi-Naini, Eds, In Financial Cryptography and Data Security, Berlin/Heidelberg: Springer, 2014. 436–454.
[15]Kiayias A, Koutsoupias E, Kyropoulou M, Tselekounis Y Blockchain mining games. In Proceedings of the 2016 ACM Conference on Economics and Computation, New York: ACM, 2016. 365–382.
[16]Koutsoupias E, Lazos P, Ogunlana F, Serafino P. Blockchain mining games with pay forward. In WWW ’19: The World Wide Web Conference,New York: ACM, 2019. 917–927.
[17]Cossío F J M, Brigham E, Sela B, Katz J. Competing (semi-)selfish miners in bitcoin. In AFT ’19: Proceedings of the 1st ACM Conference on Advances in Financial Technologies, New York: ACM, 2019. 89–109.
[18]Rosenfeld M. Analysis of bitcoin pooled mining reward systems. Computing Research Repository 2011, abs/1112.4980.
[19]Schrijvers O, Bonneau J, Boneh D, Roughgarden T. Incentive compatibility of bitcoin mining pool reward functions. Lect Notes Comp Sci 2016, 9603, 477–498.
[20]Johnson B, Laszka A, Grossklags J, Vasek M, Moore T. Game-theoretic analysis of ddos attacks against bitcoin mining pools. In International Conference on Financial Cryptography and Data Security, Berlin/Heidelberg: Springer, 2014. 72–86.
[21]Lewenberg Y, Bachrach Y, Sompolinsky Y, Zohar A, Rosenschein J S. Bitcoin mining pools: A cooperative game theoretic analysis. In AAMAS ’15: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, New York: ACM, 2015. 919–927.
[22]Emek Y, Karidi R,Tennenholtz M, Zohar A. Mechanisms for multi-level marketing. In EC ’11: Proceedings of the 12th ACM conference on Electronic commerce, New York: ACM, 2011. 209–218.
[23]Kleinberg J M, Raghavan P Query incentive networks. Annual Asian Computing Science Conference, Berlin/Heidelberg: Springer, 2005.132–141.
[24]Arcaute E, Kirsch A, Kumar R, Liben-Nowell D, Vassilvitskii, S. On threshold behavior in query incentive networks. In EC ’07: Proceedings of the 8th ACM conference on Electronic commerce, New York: ACM, 2007. 66–74.
[25]Cebrián M, Coviello L, Vattani A, Voulgaris P. Finding red balloons with split contracts: robustness to individuals’ selfishness. In STOC ’12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing, New York: ACM, 2012. 775–788.
[26]Chen W, Wang Y, Yu D, Zhang L. Sybil-proof mechanisms in query incentive networks. In EC’13: Proceedings of the fourteenth ACM conference on Electronic commerce, New York: ACM, 2013. 197–214.