How to Reach Correlated Equilibrium

Silvio Micali
Computer Science and Artificial Intelligence Laboratory
Massachusetts Institute of Technology


Tuesday, November 16, 2004
4:30 - 5:45 PM
Terman Engineering Center, Room 453


Abstract:

In game theory, correlated equilibria generalize traditional Nash ones with significant advantages: they are always easy to compute and yield higher and more flexible payoffs. So far, however, REACHING such equilibria without the assistance of an external party or device has been problematic.

All known protocols to reach correlated equilibrium not only

(1) rely on EMPTY THREATS to handle the deviation of a single player, but
(2) always enable a COALITION of deviating players to determine everyone's payoff as they please.

We exhibit a cryptographic protocol enabling the players of ANY non-cooperative game to reach correlated equilibrium, in POLYNOMIAL TIME, WITHOUT EMPTY THREATS, and WITHSTANDING THE ACTIONS OF ANY COALITION.

Joint work with Matt Lepinski, Chris Peikert, and Abhi Shelat.


Bio:

Silvio Micali is a professor of Computer Science at MIT since 1983. He works on the complexity theoretic foundations of pseudo-random generation, cryptography, and secure protocols. He was awarded the Gödel Prize in theoretical computer science in 1993 for his work on Interactive and Zero-Knowledge proofs.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html