Smoothing techniques for computing Nash equilibria of sequential games

Samid Hoda(shodaandrew.cmu.edu)
Andrew Gilpin(gilpincs.cmu.edu)
Javier Pena(jfpandrew.cmu.edu)

Abstract: We develop first-order smoothing techniques for saddle-point problems that arise in the Nash equilibria computation of sequential games. The crux of our work is a construction of suitable prox-functions for a certain class of polytopes that encode the sequential nature of the games. An implementation based on our smoothing techniques computes approximate Nash equilibria for games that are four orders of magnitude larger than what conventional computational approaches can handle.

Keywords: smoothing, Nash equilibrium, sequential games

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Other Topics (Game Theory )

Citation: Working Paper, Carnegie Mellon University, 2008.

Download: [PDF]

Entry Submitted: 04/09/2008
Entry Accepted: 04/09/2008
Entry Last Modified: 04/09/2008

Modify/Update this entry