Document Open Access Logo

False Consensus, Information Theory, and Prediction Markets

Authors Yuqing Kong , Grant Schoenebeck

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.81.pdf
  • Filesize: 1.06 MB
  • 23 pages

Document Identifiers

Author Details

Yuqing Kong
  • The Center on Frontiers of Computing Studies, School of Computer Science, Peking University, China
Grant Schoenebeck
  • School of Information, University of Michigan, Ann Arbor, MI, USA

Funding

  • Kong, Yuqing: This work is supported by National Natural Science Foundation of China award number 62002001.
  • Schoenebeck, Grant: This work is supported by NSF CAREER 1452915 and NSF CCF 2007256.

Cite AsGet BibTex

Yuqing Kong and Grant Schoenebeck. False Consensus, Information Theory, and Prediction Markets. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 81:1-81:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.81

Abstract

We study a setting where Bayesian agents with a common prior have private information related to an event’s outcome and sequentially make public announcements relating to their information. Our main result shows that when agents' private information is independent conditioning on the event’s outcome whenever agents have similar beliefs about the outcome, their information is aggregated. That is, there is no false consensus. Our main result has a short proof based on a natural information-theoretic framework. A key ingredient of the framework is the equivalence between the sign of the "interaction information" and a super/sub-additive property of the value of people’s information. This provides an intuitive interpretation and an interesting application of the interaction information, which measures the amount of information shared by three random variables. We illustrate the power of this information-theoretic framework by reproving two additional results within it: 1) that agents quickly agree when announcing (summaries of) beliefs in round-robin fashion [Aaronson 2005], and 2) results from [Chen et al 2010] on when prediction market agents should release information to maximize their payment. We also interpret the information-theoretic framework and the above results in prediction markets by proving that the expected reward of revealing information is the conditional mutual information of the information revealed.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory and mechanism design
Keywords
  • Agreeing to disagree
  • false consensus
  • information theory
  • prediction market

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Scott Aaronson. The complexity of agreement. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pages 634-643. ACM, 2005. Google Scholar
  2. Jacob D Abernethy and Rafael Frongillo. A collaborative mechanism for crowdsourcing prediction problems. Advances in Neural Information Processing Systems, 24, 2011. Google Scholar
  3. Daron Acemoglu and Asuman Ozdaglar. Opinion dynamics and learning in social networks. Dynamic Games and Applications, 1(1):3-49, 2011. Google Scholar
  4. Jerry Anunrojwong, Yiling Chen, Bo Waggoner, and Haifeng Xu. Computing equilibria of prediction markets via persuasion. In International Conference on Web and Internet Economics, pages 45-56. Springer, 2019. Google Scholar
  5. Robert J Aumann. Agreeing to disagree. The annals of statistics, pages 1236-1239, 1976. Google Scholar
  6. A V Banerjee. A simple model of herd behavior. Q. J. Econ., 107(3):797-817, 1992. Google Scholar
  7. Sushil Bikhchandani, David Hirshleifer, and Ivo Welch. A theory of fads, fashion, custom, and cultural change as informational cascades. Journal of political Economy, 100(5):992-1026, 1992. Google Scholar
  8. Yiling Chen, Stanko Dimitrov, Rahul Sami, Daniel M Reeves, David M Pennock, Robin D Hanson, Lance Fortnow, and Rica Gonen. Gaming prediction markets: Equilibrium strategies with a market maker. Algorithmica, 58(4):930-969, 2010. Google Scholar
  9. Yiling Chen and David M Pennock. A utility framework for bounded-loss market makers. In 23rd Conference on Uncertainty in Artificial Intelligence (UAI), 2007. Most recent version: arXiv preprint https://arxiv.org/abs/1206.5252, 2012.
  10. Yiling Chen and Bo Waggoner. Informational substitutes. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 239-247. IEEE, 2016. Google Scholar
  11. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory 2nd Edition (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, July 2006. Google Scholar
  12. M.H. DeGroot. Reaching a consensus. Journal of the American Statistical Association, pages 118-121, 1974. Google Scholar
  13. Richard Durrett, James P Gleeson, Alun L Lloyd, Peter J Mucha, Feng Shi, David Sivakoff, Joshua ES Socolar, and Chris Varghese. Graph fission in an evolving voter model. Proceedings of the National Academy of Sciences, 109(10):3682-3687, 2012. Google Scholar
  14. Benjamin Enke and Florian Zimmermann. Correlation neglect in belief formation. The Review of Economic Studies, 86(1):313-332, 2019. Google Scholar
  15. Rafael Frongillo, Eric Neyman, and Bo Waggoner. Agreement implies accuracy for substitutable signals. arXiv preprint arXiv:2111.03278, 2021. Google Scholar
  16. Rafael M Frongillo, Grant Schoenebeck, and Omer Tamuz. Social learning in a changing world. In International Workshop on Internet and Network Economics, pages 146-157. Springer, 2011. Google Scholar
  17. Jie Gao, Bo Li, Grant Schoenebeck, and Fang-Yi Yu. Engineering agreement: The naming game with asymmetric and heterogeneous agents. In Satinder Singh and Shaul Markovitch, editors, Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, pages 537-543. AAAI Press, 2017. URL: http://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14986.
  18. Jie Gao, Grant Schoenebeck, and Fang-Yi Yu. The volatility of weak ties: Co-evolution of selection and influence in social networks. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 619-627, 2019. Google Scholar
  19. John D Geanakoplos and Heraklis M Polemarchakis. We can't disagree forever. Journal of Economic theory, 28(1):192-200, 1982. Google Scholar
  20. Benjamin Golub and Evan Sadler. Learning in social networks. The Oxford Handbook of the Economics of Networks, 2016. Google Scholar
  21. I. J. Good. Rational decisions. Journal of the Royal Statistical Society: Series B (Methodological), 14(1):107-114, 1952. Google Scholar
  22. Robin Hanson. Combinatorial information market design. Information Systems Frontiers, 5(1):107-119, 2003. Google Scholar
  23. Robin Hanson. Logarithmic markets coring rules for modular combinatorial information aggregation. The Journal of Prediction Markets, 1(1):3-15, 2012. Google Scholar
  24. Matthew O Jackson. Social and economic networks. Princeton university press, 2010. Google Scholar
  25. Yuqing Kong and Grant Schoenebeck. Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:20, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  26. Yuqing Kong and Grant Schoenebeck. An information theoretic framework for designing information elicitation mechanisms that reward truth-telling. ACM Trans. Econ. Comput., 7(1):2:1-2:33, January 2019. Google Scholar
  27. Ilan Lobel and Evan Sadler. Preferences, homophily, and social learning. Operations Research, 64(3):564-584, 2016. Google Scholar
  28. Elchanan Mossel and Grant Schoenebeck. Arriving at consensus in social networks. In The First Symposium on Innovations in Computer Science (ICS 2010), January 2010. Google Scholar
  29. Rohit Parikh and Paul Krasucki. Communication, consensus, and knowledge. Journal of Economic Theory, 52(1):178-189, 1990. Google Scholar
  30. Grant Schoenebeck and Fang-Yi Yu. Consensus of interacting particle systems on erdös-rényi graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1945-1964. SIAM, 2018. Google Scholar
  31. Claude Elwood Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3):379-423, 1948. Google Scholar
  32. Lones Smith and Peter Sorensen. Pathological outcomes of observational learning. Econometrica, 68(2):371-398, 2000. Google Scholar
  33. Hu Kuo Ting. On the amount of information. Theory of Probability & Its Applications, 7(4):439-447, 1962. Google Scholar
  34. Ercan Yildiz, Asuman Ozdaglar, Daron Acemoglu, Amin Saberi, and Anna Scaglione. Binary opinion dynamics with stubborn agents. ACM Transactions on Economics and Computation (TEAC), 1(4):1-30, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact