Bayesian Decision Making in Groups is Hard
  We study the computations that Bayesian agents undertake when exchanging
opinions over a network. The agents act repeatedly on their private information
and take myopic actions that maximize their expected utility according to a
fully rational posterior belief. We show that such computations are NP-hard for
two natural utility functions: one with binary actions, and another where
agents reveal their posterior beliefs. In fact, we show that distinguishing
between posteriors that are concentrated on different states of the world is
NP-hard. Therefore, even approximating the Bayesian posterior beliefs is hard.
We also describe a natural search algorithm to compute agents' actions, which
we call elimination of impossible signals, and show that if the network is
transitive, the algorithm can be modified to run in polynomial time.
