-

 

 

 




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

 

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