BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Reasoning in Bayesian Opinion exchange Networks is Computationally
  Hard
DTSTART:20190221T163000
DTEND:20190221T173000
DTSTAMP:20260415T191202Z
UID:8b4b1b830e1dfbfeccebec6678c4ec27bee4a6d25eec289cdc74cb25
CATEGORIES:Conferences - Seminars
DESCRIPTION: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 c
 omputer 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 Ma
 thematical Sciences in Kigali\, Rwanda. He is interested in problems in pr
 obability theory motivated by applications in computer science and social 
 choice theory.\nBayesian models of opinion exchange are extensively studie
 d in economics\, dating back to the work of Aumann on the agreement theore
 m. \nAn important class of such models features agents arranged on a netw
 ork (representing\, e.g.\, social interactions)\, with the network structu
 re \ndetermining which agents communicate with each other. It is often ar
 gued that the Bayesian computations needed by agents in those models are 
 \ndifficult\, but prior to our work there were no rigorous arguments for s
 uch hardness.\n\nWe consider a well-studied model where fully rational age
 nts receive private signals indicative of an unknown state of the world. T
 hen\, they \nrepeatedly announce the state of the world they consider mos
 t likely to their neighbors\, at the same time updating their beliefs base
 d on their \nneighbors' announcements.\n\nI will discuss complexity-theor
 etic results establishing hardness of agents' computations in this model. 
 Specifically\, we show that these \ncomputations are NP-hard and extend t
 his result to PSPACE-hardness. We show hardness not only for exact computa
 tions\, but also that it is \ncomputationally difficult even to approxima
 te the rational opinion in any meaningful way.\n\nJoint work with Ali Jadb
 ababie\, Elchanan Mossel and Amin Rahimian.
LOCATION:INM 203 https://plan.epfl.ch/?room=INM203
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR