Bayesian decision making in groups is hard

DOI10.1287/OPRE.2020.2000MaRDI QIDQ4994179zbMATH OpenOpenAlexFDO

Authors Jan Hązła, Ali Jadbabaie, Elchanan Mossel, Mohammad Amin Rahimian

Publication date 17 June 2021

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.04770, http://d-scholarship.pitt.edu/40256/1/SSRN-id3055954.pdf

zbMATH Keywords

Bayesian decision theorycomputational complexitycomputational social choicegroup decision makinginference over graphsobservational learning

Mathematics Subject Classification ID

Management decision making, including multiple objectives (90B50)

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.

Recommendations

• Bayesian group belief
• Does one Bayesian make a difference?
• Toward rational social decisions: a review and some results
• Asymptotic learning on Bayesian social networks
• scientific article; zbMATH DE number 4068051

Cites work

• A general framework for rational learning in social networks
• A theory of non-Bayesian social learning
• Agreeing to disagree
• Asymptotic learning on Bayesian social networks
• Average-Case Complexity
• Bayesian learning in social networks
• Bayesian learning in social networks.
• Clustering to minimize the maximum intercluster distance
• Computable economics. The Arne Ryde memorial lectures
• Computational Complexity
• Dynamics of information exchange in endogenous social networks
• Extensive imitation is irrational and harmful
• Herding with costly information
• Informational externalities and emergence of consensus
• Learning from Neighbours
• Locally Bayesian learning in networks
• Merging of Opinions with Increasing Information
• Non-Bayesian social learning
• Opinion dynamics and learning in social networks
• Opinion exchange dynamics
• Pathological Outcomes of Observational Learning
• Persuasion Bias, Social Influence, and Unidimensional Opinions
• Reaching a Consensus
• Strategic learning and the topology of social networks
• The complexity of agreement
• The Complexity of Markov Decision Processes
• The Folk Theorem in Repeated Games with Discounting or with Incomplete Information
• We can't disagree forever

Cited in

(10)

• Robust learning in social networks via matrix scaling
• Virtually additive learning
• Interval generalization of the Bayesian model of collective decision-making in conflict situations
• Distributed decision making by categorically-thinking agents
• Bayesian evidence accumulation on social networks
• Naive Learning Through Probability Overmatching
• Bayesian generalized network design
• Opinion dynamics in communities with major influencers and implicit social influence via mean-field approximation
• Granular degroot dynamics -- a model for robust naive learning in social networks
• Social network-based overlapping community clustering and feedback mechanism for large-scale group decision making

This page was built for publication: Bayesian decision making in groups is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4994179)