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 polynomial-time 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 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.

我们探讨贝叶斯主体为实现其最优行动所进行的计算，在最初的私人观察之后，他们会反复观察彼此的行动。我们使用不可行信号的迭代消除（IEIS）来模拟群体决策场景中贝叶斯主体的思维过程以及计算。我们表明IEIS以指数时间运行；然而，当群体结构是一个偏序集时，贝叶斯计算得以简化，并且贝叶斯建议的多项式时间计算是可能的。 接下来，我们将注意力转移到主体在每个决策时刻揭示其信念（而非行动）的情况。我们分析群体中贝叶斯信念形成的计算复杂性，并表明它是NP难的。我们还研究了这种计算复杂性背后的因素，并展示了在特殊网络结构或具有强烈内在对称性的情况下信念计算是如何简化的。最后，我们对信念的统计效率（最优性）及其与计算效率的关系给出了见解。