Bayesian Group Decisions: Algorithms and Complexity
This topic contains 0 replies, has 1 voice, and was last updated by arXiv 1 year, 9 months ago.

Bayesian Group Decisions: Algorithms and Complexity
We address the computations that Bayesian agents undertake to realize their optimal actions, as they repeatedly observe each other’s actions, following an initial private observation. We use iterated eliminations of infeasible signals (IEIS) to model the thinking process as well as the calculations of a Bayesian agent in a group decision scenario. We show that IEIS runs in exponential time; however, when the group structure is a partially ordered set, the Bayesian calculations simplify and polynomialtime computation of the Bayesian recommendations is possible. We next shift attention to the case where agents reveal their beliefs (instead of actions) at every decision epoch. We analyze the computational complexity of the Bayesian belief formation in groups and show that it is NPhard. 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.
Bayesian Group Decisions: Algorithms and Complexity
by Ali Jadbabaie, Elchanan Mossel, M. Amin Rahimian
https://arxiv.org/pdf/1705.04770v2.pdf
You must be logged in to reply to this topic.