Optimization Online


Smoothing techniques for computing Nash equilibria of sequential games

Samid Hoda(shoda***at***andrew.cmu.edu)
Andrew Gilpin(gilpin***at***cs.cmu.edu)
Javier Pena(jfp***at***andrew.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society