The Complexity of Agreement

COMPUTER SCIENCE/DISCRETE MATH, II
Topic:The Complexity of Agreement
Speaker:Scott Aaronson
Affiliation:IAS
Date:Tuesday, October 5
Time/Room:10:30am - 12:30pm/S-101

A celebrated 1976 theorem of Aumann asserts that honest, rational Bayesian agents 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 talk will answer both questions in the affirmative, thereby strengthening Aumann's original conclusion.