Computation of equilibriain noncooperative games


Journal Article

This paper presents algorithms for finding equilibria of mixed strategy in multistage noncooperative games of incomplete information (like probabilistic blindfold chess, where at every opportunity a player can perform different moves with some probability). These algorithms accept input games in extensive form. Our main result is an algorithm for computing aeguential equilibrium, which is the most widely accepted notion of equilibrium (for mixed strategies of noncooperative probabilistic games) in mainstream economic game theory. Previously, there were no known algorithms for computing sequential equilibria strategies (except for the special case of single stage games). The computational aspects of passage from a recursive presentation of a game to its extensive form are also discussed. For nontrivial inputs the concatenation of this procedure with the equilibrium computation is time intensive, but has low spatial requirements. Given a recursively represented game, with a position space bound S(n) and a log space computable next move relation, we can compute an example mixed strategy satisfying the sequential equilibria condition, all in space bound O(S(n)2), Furthermore, in space O(S(n)3), we can compute the connected components of mixed strategies satisfying sequential equilibria. © 2005 Elsevier Ltd. All rights reserved.

Full Text

Duke Authors

Cited Authors

  • Azhar, S; McLennan, A; Reif, JH

Published Date

  • September 1, 2005

Published In

Volume / Issue

  • 50 / 5-6

Start / End Page

  • 823 - 854

International Standard Serial Number (ISSN)

  • 0898-1221

Digital Object Identifier (DOI)

  • 10.1016/j.camwa.2005.02.015

Citation Source

  • Scopus