Bayesian Decision Making in Groups is Hard

Jan Hązła (), Ali Jadbabaie (), Elchanan Mossel () and M. Amin Rahimian ()
Additional contact information
Jan Hązła: Institutes of Mathematics and Computer Science, École polytechnique fédérale de Lausanne (EPFL), CH-1015 Lausanne, Switzerland;
Ali Jadbabaie: Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139;
Elchanan Mossel: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139;
M. Amin Rahimian: Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15260

Operations Research, 2021, vol. 69, issue 2, 632-654

Abstract: 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.

Keywords: observational learning; Bayesian decision theory; computational complexity; group decision making; computational social choice; inference over graphs (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/opre.2020.2000 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:2:p:632-654

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().