A celebrated 1976 theorem of Aumann asserts that honest 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. 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? In this talk I'll answer both questions in the affirmative, thereby strengthening Aumann's original conclusion.
Paper (from STOC'05) is available at http://www.scottaaronson.com/papers/agreestoc.ps