In this talk I will discuss the problem of finding ε-equilibria in two-person zero-sum games. Both matrix games and sequential games will be considered. I will describe our algorithm based on Nesterov's excessive gap technique. This was the first O(1/ε) gradient-based algorithm for finding ε-equilibria in sequential games. Then I will discuss our newer O(log (1/ε)) algorithms for matrix and sequential games. This is the first O(log (1/ε)) gradient-based algorithm for this problem, and it matches the performance guarantees of interior-point methods in terms of the dependence on ε.

There often exists a large complexity gap between the difficulty of solving two and three-player zero-sum games. For example, two-player zero-sum matrix games can be solved in polynomial time by linear programming while solving three-player zero-sum matrix games is PPAD-complete. Furthermore, while it has been known for decades that an equilibrium exists in two-player zero-sum undiscounted stochastic games, it is still unknown whether one exists in such games with more than two players. In this talk I will discuss several new algorithms for computing an equilibrium in multiplayer stochastic games of imperfect information and present experimental results on a three-player poker tournament (which is modeled as a stochastic game).

Traditional prediction markets answer "Who?" or "What?"; an assassination market is a prediction market which answers "When?" or "How Many?". In this talk, I will discuss the failures of current assassination markets and offer my solution: a novel method of market interaction that is both powerful and simple. Central to my talk is the elegant result of Robin Hanson which turns scoring rules used in expert elicitation into automated market makers for prediction markets. I will give a derivation of this result and discuss its implications. Finally, my talk will end with a proposal to run an assassination market on when the new Gates Center for Computer Science will open.

More often than not, companies choose to walk away from their contracts due to unexpected business environments (e.g., subprime crisis). It is therefore strategic for managers to anticipate the financial outcome of breach of contacts and renegotiation possibilities. This talk first provides a review of game theoretic literature about the issue of breach of contract. We then move to focus on two most recent models: a model dealing with breach remedy and renegotiation design for innovation and capacity; a repeated game model quantifying the impact of the value of future cooperation on the building of mutual-trust. Finally, a multi-agent model with commitment flexibility is introduced, which is still under the phase of initial development.

In repeated games with incomplete information, rational agents must carefully weigh the tradeoffs of advantageously exploiting their information to achieve a short-term gain versus carefully concealing their information so as not to give up a long-term informed advantage. The theory of infinitely-repeated two-player zero-sum games with incomplete information has been carefully studied, beginning with the seminal work of Aumann and Maschler. While this theoretical work has produced a characterization of optimal strategies, algorithms for solving for optimal strategies have not yet been studied. For the case where one player is informed about the true state of the world and the other player is uninformed, we provide a non-convex mathematical programming formulation for computing the value of the game, as well as optimal strategies for the informed player. We then describe an efficient algorithm for solving this difficult optimization problem to within arbitrary accuracy. We also discuss how to efficiently compute optimal strategies for the uninformed player using the output of our algorithm.