Conferences - Seminars

  Thursday 21 February 2019 16:30 - 17:30 INM 203

Reasoning in Bayesian Opinion exchange Networks is Computationally Hard

By Dr. Jan Hazla, MIT Jan Hązła is a Postdoctoral Associate at MIT Institute for Data, Systems and Society (IDSS). He received MSc in computer science from Jagiellonian University (Kraków, Poland) and PhD in computer science from ETH Zurich (Switzerland). Directly before coming to MIT, he spent a year as a teaching assistant at African Institute for Mathematical Sciences in Kigali, Rwanda. He is interested in problems in probability theory motivated by applications in computer science and social choice theory.

Bayesian models of opinion exchange are extensively studied in economics, dating back to the work of Aumann on the agreement theorem. 
An important class of such models features agents arranged on a network (representing, e.g., social interactions), with the network structure 
determining which agents communicate with each other. It is often argued that the Bayesian computations needed by agents in those models are 
difficult, but prior to our work there were no rigorous arguments for such hardness.

We consider a well-studied model where fully rational agents receive private signals indicative of an unknown state of the world. Then, they 
repeatedly announce the state of the world they consider most likely to their neighbors, at the same time updating their beliefs based on their 
neighbors' announcements.

I will discuss complexity-theoretic results establishing hardness of agents' computations in this model. Specifically, we show that these 
computations are NP-hard and extend this result to PSPACE-hardness. We show hardness not only for exact computations, but also that it is 
computationally difficult even to approximate the rational opinion in any meaningful way.

Joint work with Ali Jadbababie, Elchanan Mossel and Amin Rahimian.

Organization IPG Seminar

Contact Olivier Lévêque

Accessibility Informed public

Admittance Free