The complexity of agreement

ABSTRACT

A celebrated 1976 theorem of Aumann asserts that Bayesian agents with common priors can never "agree to disagree": if their opinions about any topic are common knowledge, then those opinions must be equal. But two key questions went unaddressed: first, can the agents reach agreement after a conversation of reasonable length? Second, can the computations needed for that conversation be performed efficiently? This paper answers both questions in the affirmative, thereby strengthening Aumann's original conclusion.We show that for two agents with a common prior to agree within ε about the expectation of a [0,1] variable with high probability over their prior, it suffices for them to exchange O(1/ε²) bits. This bound is completely independent of the number of bits n of relevant knowledge that the agents have. We also extend the bound to three or more agents; and we give an example where the "standard protocol" (which consists of repeatedly announcing one's current expectation) nearly saturates the bound, while a new "attenuated protocol" does better. Finally, we give a protocol that would cause two Bayesians to agree within ε after exchanging O(1/ε²) messages, and that can be simulated by agents with limited computational resources. By this we mean that, after examining the agents' knowledge and a transcript of their conversation, no one would be able to distinguish the agents from perfect Bayesians. The time used by the simulation procedure is exponential in 1/ε⁶ but not in n.

REFERENCES

• 1: R. J. Aumann. Agreeing to disagree. Annals of Statistics, 4(6):1236--1239, 1976.
• 2: R. J. Aumann. Reply to Gul. Econometrica, 66(4):929--938, 1998.
• 3: R. J. Aumann. Interactive epistemology I: knowledge. International J. Game Theory, 28:263--300, 1999.
• 4: A. Brandenburger and E. Dekel. Common knowledge with probability 1. Journal of Mathematical Economics, 16:237--245, 1987.
• 5: J. A. K. Cave. Learning to agree. Economics Letters, 12:147--152, 1983.
• 6: T. Cowen and R. Hanson. Are disagreements honest? At http://hanson.gmu.edu/deceive.pdf, 2004.
• 7: J. D. Geanakoplos and H. M. Polemarchakis. We can't disagree forever. J. Economic Theory, 28:192--200, 1982.
• 8: F. Gul. A comment on Aumann's Bayesian view. Econometrica, 66(4):923--927, 1998.
• 9: R. Hanson. Disagreement is unpredictable. Economics Letters, 77(3):365--369, 2002.
• 10: R. Hanson. For savvy Bayesian wannabes, are disagreements not about information? Theory and Decision, 54(2):105--123, 2003.
• 11: R. Hanson. Uncommon priors require origin disputes. To appear, 2005.
• 12: Y. Moses J. Y. Halpern, R. Fagin and M. Y. Vardi. Reasoning About Knowledge. Cambridge, 1996.
• 13: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 14: D. Monderer and D. Samet. Approximating common knowledge with common beliefs. Games and Economic Behavior, 1:170--190, 1989.
• 15: Christos H. Papadimitriou , Mihalis Yannakakis, On complexity as bounded rationality (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.726-733, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195445]
• 16: R. Parikh and P. Krasucki. Communication, consensus, and knowledge. J. Economic Theory, 52:178--189, 1990.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Economics, Theory

Keywords:
Bayesian agents, agreement, bounded rationality, common priors, communication, random walks