Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard

Jan Hązła, Ali Jadbabaie, Elchanan Mossel, M. Amin Rahimian
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:1614-1648, 2019.

Abstract

We study the Bayesian model of opinion exchange of fully rational agents arranged on a network. In this model, the agents receive private signals that are indicative of an unknown state of the world. Then, they repeatedly announce the state of the world they consider most likely to their neighbors, at the same time updating their beliefs based on their neighbors’ announcements. This model is extensively studied in economics since the work of Aumann (1976) and Geanakoplos and Polemarchakis (1982). It is known that the agents eventually agree with high probability on any network. It is often argued that the computations needed by agents in this model are difficult, but prior to our results there was no rigorous work showing this hardness. We show that it is $\mathsf{PSPACE}$-hard for the agents to compute their actions in this model. Furthermore, we show that it is equally difficult even to approximate an agent’s posterior: It is $\mathsf{PSPACE}$-hard to distinguish between the posterior being almost entirely concentrated on one state of the world or another.

Cite this Paper

BibTeX
@InProceedings{pmlr-v99-hazla19a, title = {Reasoning in {B}ayesian Opinion Exchange Networks Is {$\mathsf{PSPACE}$}-Hard}, author = {H\k{a}z\l{}a, Jan and Jadbabaie, Ali and Mossel, Elchanan and Rahimian, M.~Amin}, booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {1614--1648}, year = {2019}, editor = {Beygelzimer, Alina and Hsu, Daniel}, volume = {99}, series = {Proceedings of Machine Learning Research}, month = {25--28 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v99/hazla19a/hazla19a.pdf}, url = {https://proceedings.mlr.press/v99/hazla19a.html}, abstract = { We study the Bayesian model of opinion exchange of fully rational agents arranged on a network. In this model, the agents receive private signals that are indicative of an unknown state of the world. Then, they repeatedly announce the state of the world they consider most likely to their neighbors, at the same time updating their beliefs based on their neighbors’ announcements. This model is extensively studied in economics since the work of Aumann (1976) and Geanakoplos and Polemarchakis (1982). It is known that the agents eventually agree with high probability on any network. It is often argued that the computations needed by agents in this model are difficult, but prior to our results there was no rigorous work showing this hardness. We show that it is $\mathsf{PSPACE}$-hard for the agents to compute their actions in this model. Furthermore, we show that it is equally difficult even to approximate an agent’s posterior: It is $\mathsf{PSPACE}$-hard to distinguish between the posterior being almost entirely concentrated on one state of the world or another. } }
Endnote
%0 Conference Paper %T Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard %A Jan Hązła %A Ali Jadbabaie %A Elchanan Mossel %A M. Amin Rahimian %B Proceedings of the Thirty-Second Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Alina Beygelzimer %E Daniel Hsu %F pmlr-v99-hazla19a %I PMLR %P 1614--1648 %U https://proceedings.mlr.press/v99/hazla19a.html %V 99 %X We study the Bayesian model of opinion exchange of fully rational agents arranged on a network. In this model, the agents receive private signals that are indicative of an unknown state of the world. Then, they repeatedly announce the state of the world they consider most likely to their neighbors, at the same time updating their beliefs based on their neighbors’ announcements. This model is extensively studied in economics since the work of Aumann (1976) and Geanakoplos and Polemarchakis (1982). It is known that the agents eventually agree with high probability on any network. It is often argued that the computations needed by agents in this model are difficult, but prior to our results there was no rigorous work showing this hardness. We show that it is $\mathsf{PSPACE}$-hard for the agents to compute their actions in this model. Furthermore, we show that it is equally difficult even to approximate an agent’s posterior: It is $\mathsf{PSPACE}$-hard to distinguish between the posterior being almost entirely concentrated on one state of the world or another.
APA
Hązła, J., Jadbabaie, A., Mossel, E. & Rahimian, M.. (2019). Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:1614-1648 Available from https://proceedings.mlr.press/v99/hazla19a.html.

Related Material