Skip to main content
Unpublished Paper
A Decomposition Algorithm for N-Player Games
Stanford Business School Research Paper #1967 (2007)
  • Robert B Wilson, Stanford University
  • Srihari Govindan, University of Iowa
Abstract

An N-player game can be decomposed by adding a coordinator who interacts bilaterally with each player. The coordinator proposes profiles of strategies to the players, and his payoff is maximized when players' optimal replies agree with his proposal. When the feasible set of proposals is finite, a solution of an associated linear complementarity problem yields an equilibrium of the approximate game and thus an approximate equilibrium of the original game. Computational efficiency is improved by using vertices of a triangulation of the players' strategy space for the coordinator's pure strategies. Computational experience is reported.

Keywords
  • game theory,
  • computation,
  • equilibrium,
  • decomposition,
  • triangulation
Disciplines
Publication Date
August, 2007
Citation Information
Robert B Wilson and Srihari Govindan. "A Decomposition Algorithm for N-Player Games" Stanford Business School Research Paper #1967 (2007)
Available at: http://works.bepress.com/wilson_robert/5/