Andrew Gilpin

First-order algorithm with (ln(1/\epsilon))$ convergence for $\epsilonhBcequilibrium in two-person zero-sum games

  • Andrew Gilpin
  • Javier F. Peña
  • Tuomas Sandholm
    • Categories Convex Optimization, Game Theory Tags , ,

    We propose an iterated version of Nesterov’s first-order smoothing method for the two-person zero-sum game equilibrium problem $$\min_{x\in Q_1} \max_{y\in Q_2} \ip{x}{Ay} = \max_{y\in Q_2} \min_{x\in Q_1} \ip{x}{Ay}.$$ This formulation applies to matrix games as well as sequential games. Our new algorithmic scheme computes an $\epsilon$-equilibrium to this min-max problem in $\Oh(\kappa(A) \ln(1/\epsilon))$ first-order iterations, … Read more

    Smoothing techniques for computing Nash equilibria of sequential games

  • Andrew Gilpin
  • Javier F. Peña
  • Samid Hoda
    • Categories Convex Optimization, Game Theory Tags , ,

    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 … Read more

    A gradient-based approach for computing Nash equilibria of large sequential games

  • Andrew Gilpin
  • Javier F. Peña
  • Samid Hoda
    • Categories Convex Optimization, Game Theory, Linear Programming Tags , ,

    We propose a new gradient based scheme to approximate Nash equilibria of large sequential two-player, zero-sum games. The algorithm uses modern smoothing techniques for saddle-point problems tailored specifically for the polytopes used in the Nash equilibrium problem. CitationWorking Paper, Tepper School of Business, Carnegie Mellon UniversityArticleDownload View PDF