PATHS TO CONSTRAINED NASH EQUILIBRIA

We propose and analyze a primal-dual, infinitesimal method for locatin g Nash equilibria of constrained, non-cooperative games. The main obje ct is a family of nonstandard Lagrangian functions, one for each playe r. With respect to these functions the algorithm yields separately, in differential form, directions of steepest-descent in all decision var iables and steepest-ascent in all multipliers. For convergence we need marginal costs to be monotone and constraints to be convex inequaliti es. The method is largely decomposed and amenable for parallel computi ng. Other noteworthy features are: non-smooth data can be accommodated ; no projection or optimization is needed as subroutines; multipliers converge monotonically upward; and, finally, the implementation amount s, in essence, only to numerical integration.