# Bayesian Decision Making in Groups is Hard

arXiv: https://arxiv.org/abs/1705.04770 · HTML: https://mlsanity.com/paper/1705.04770/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 May 2017.

## Built on by (most cited first, 4 of 4)

- [Leveraging Large Language Models for Collective Decision-Making](https://mlsanity.com/paper/2311.04928/) (2023)
- [Policy Evaluation in Decentralized POMDPs with Belief Sharing](https://mlsanity.com/paper/2302.04151/) (2023)
- [Causal Influences over Social Learning Networks](https://mlsanity.com/paper/2307.09575/) (2023)
- [Tell Me Why: Incentivizing Explanations](https://mlsanity.com/paper/2502.13410/) (2025)

## Abstract (arXiv)

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.