Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-061 | 30th June 2004 00:00

The Complexity of Agreement


Authors: Scott Aaronson
Publication: 26th July 2004 21:01
Downloads: 1162


A celebrated 1976 theorem of Aumann asserts that honest, rational
Bayesian agents with common priors will never "agree to disagree": if
their opinions about any topic are common knowledge, then those
opinions must be equal. Economists have written numerous papers
examining the assumptions behind this theorem. 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 first show that, for two agents with a common prior to agree within
epsilon about the expectation of a [0,1] variable with high probability
over their prior, it suffices for them to exchange order 1/epsilon^2
bits. This bound is completely independent of the number of bits n of
relevant knowledge that the agents have. We then extend the bound to
three or more agents; and we give an example where the economists'
"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 epsilon after exchanging order
1/epsilon^2 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/epsilon^6 but not
in n.

ISSN 1433-8092 | Imprint