Bayesian models of opinion exchange are extensively studied
in economics\, dating back to the work of Aumann on the agreement theorem
.

\nAn important class of such models features agents arranged on a n
etwork (representing\, e.g.\, social interactions)\, with the network stru
cture

\ndetermining which agents communicate with each other. It is o
ften argued that the Bayesian computations needed by agents in those model
s are

\ndifficult\, but prior to our work there were no rigorous argu
ments for such hardness.

\n

\nWe consider a well-studied model where
fully rational agents receive private signals indicative of an unknown st
ate of the world. Then\, they

\nrepeatedly announce the state of the
world they consider most likely to their neighbors\, at the same time upda
ting their beliefs based on their

\nneighbors' announcements.

\n**\nI will discuss complexity-theoretic results establishing hardness of a
gents' computations in this model. Specifically\, we show that these
\ncomputations are NP-hard and extend this result to PSPACE-hardness. We s
how hardness not only for exact computations\, but also that it is \n
computationally difficult even to approximate the rational opinion in any
meaningful way.\n\nJoint work with Ali Jadbababie\, Elchanan Mosse
l and Amin Rahimian.**