Complexity of Bayesian Belief Exchange over a Network
Many important real-world decision making prob- lems involve group interactions among individuals with purely informational externalities, such situations arise for example in jury deliberations, expert committees, medical diagnosis, etc. In this paper, we will use the framework of iterated eliminat...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/116568 |
| _version_ | 1811096433444519936 |
|---|---|
| author | Mossel, Elchanan Rahimian, Mohammad Amin Jadbabaie-Moghadam, Ali |
| author2 | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Mossel, Elchanan Rahimian, Mohammad Amin Jadbabaie-Moghadam, Ali |
| author_sort | Mossel, Elchanan |
| collection | MIT |
| description | Many important real-world decision making prob- lems involve group interactions among individuals with purely informational externalities, such situations arise for example in jury deliberations, expert committees, medical diagnosis, etc. In this paper, we will use the framework of iterated eliminations to model the decision problem as well as the thinking process of a Bayesian agent in a group decision/discussion scenario. We model the purely informational interactions of rational agents in a group, where they receive private information and act based upon that information while also observing other people’s beliefs. As the Bayesian agent attempts to infer the true state of the world from her sequence of observations which include her neighbors’ beliefs as well as her own private signal, she recursively refines her belief about the signals that other players could have observed and beliefs that they would have hold given the assumption that other players are also rational. We further analyze the computational complexity of the Bayesian belief formation in groups and show that it is NP -hard. We also investigate the factors underlying this computational complexity and show how belief calculations simplify in special network structures or cases with strong inherent symmetries. We finally give insights about the statistical efficiency (optimality) of the beliefs and its relations to computational efficiency. |
| first_indexed | 2024-09-23T16:43:35Z |
| format | Article |
| id | mit-1721.1/116568 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:43:35Z |
| publishDate | 2018 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1165682022-10-03T07:52:15Z Complexity of Bayesian Belief Exchange over a Network Mossel, Elchanan Rahimian, Mohammad Amin Jadbabaie-Moghadam, Ali Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Massachusetts Institute of Technology. Department of Mathematics Massachusetts Institute of Technology. Institute for Data, Systems, and Society Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Mossel, Elchanan Rahimian, Mohammad Amin Jadbabaie-Moghadam, Ali Many important real-world decision making prob- lems involve group interactions among individuals with purely informational externalities, such situations arise for example in jury deliberations, expert committees, medical diagnosis, etc. In this paper, we will use the framework of iterated eliminations to model the decision problem as well as the thinking process of a Bayesian agent in a group decision/discussion scenario. We model the purely informational interactions of rational agents in a group, where they receive private information and act based upon that information while also observing other people’s beliefs. As the Bayesian agent attempts to infer the true state of the world from her sequence of observations which include her neighbors’ beliefs as well as her own private signal, she recursively refines her belief about the signals that other players could have observed and beliefs that they would have hold given the assumption that other players are also rational. We further analyze the computational complexity of the Bayesian belief formation in groups and show that it is NP -hard. We also investigate the factors underlying this computational complexity and show how belief calculations simplify in special network structures or cases with strong inherent symmetries. We finally give insights about the statistical efficiency (optimality) of the beliefs and its relations to computational efficiency. United States. Army Research Office (grant MURI W911NF-12- 1-0509) National Science Foundation (U.S.). Computing and Communication Foundation (grant CCF 1665252) United States. Department of Defense (ONR grant N00014-17-1-2598) National Science Foundation (U.S.) (grant DMS-1737944) 2018-06-25T17:37:38Z 2018-06-25T17:37:38Z 2017-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-5090-2873-3 http://hdl.handle.net/1721.1/116568 Rahimian, M. Amin, Ali Jadbabaie, and Elchanan Mossel. “Complexity of Bayesian Belief Exchange over a Network.” 2017 IEEE 56th Annual Conference on Decision and Control (CDC) (December 2017). en_US http://doi.org/10.1109/CDC.2017.8264038 2017 IEEE 56th Annual Conference on Decision and Control (CDC) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) Prof. Mossel via Michael Noga |
| spellingShingle | Mossel, Elchanan Rahimian, Mohammad Amin Jadbabaie-Moghadam, Ali Complexity of Bayesian Belief Exchange over a Network |
| title | Complexity of Bayesian Belief Exchange over a Network |
| title_full | Complexity of Bayesian Belief Exchange over a Network |
| title_fullStr | Complexity of Bayesian Belief Exchange over a Network |
| title_full_unstemmed | Complexity of Bayesian Belief Exchange over a Network |
| title_short | Complexity of Bayesian Belief Exchange over a Network |
| title_sort | complexity of bayesian belief exchange over a network |
| url | http://hdl.handle.net/1721.1/116568 |
| work_keys_str_mv | AT mosselelchanan complexityofbayesianbeliefexchangeoveranetwork AT rahimianmohammadamin complexityofbayesianbeliefexchangeoveranetwork AT jadbabaiemoghadamali complexityofbayesianbeliefexchangeoveranetwork |