Back to search

Monterey, California ; Naval Postgraduate School

Iterative algorithms for two-person zero-sum games

Abstract

dc:description.abstract

In 1951, G.W. Brown proposed an iterative algorithm called fictitious play for solving two-person zero-sum games. Although it is an effective method, the fictitious play algorithm converges slowly to the value of the game. Recently, Gass, Zafra, and Qiu proposed a modification that applies to symmetric games, i.e., games with skew-symmetric payoff matrices. To solve non-symmetric games via their modification, the games must be made symmetric via a transformation. Gass, Zafra, and Qiu reported that their modified algorithm converges faster than the original fictitious play on a collection of randomly generated games. However, their results on non-symmetric games only apply to games whose values are near zero. When game values are far away from zero, this thesis empirically shows that the original fictitious play algorithm can outperform the modified one. Gass, Zafra, and Qiu's method is static, in that the symmetric transformation is done once prior to the start of their modified algorithm. However, they suggested the exploration of dynamic methods where the transformation is periodically revised. This thesis proposes and investigates the convergence behavior of one dynamic transformation technique for solving general two-person zero-sum games.

Degree

thesis:*
Name thesis:degree_name
M.S. in Operations Research
Level thesis:degree_level
Masters
Discipline thesis:degree_discipline
Operations Research
Grantor dc:publisher
Monterey, California ; Naval Postgraduate School
Year dc:date.issued
1999

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Limsakul, Piya
Advisors dc:contributor.advisor
  • Eagle, James N.
  • Washburn, Alan R.

Rights

dc:rights
Statement dc:rights
  • Approved for public release; distribution is unlimited.

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10945/13622

Chain of custody

source
Harvested from
Naval Postgraduate School
Base URL
calhoun.nps.edu/server/oai/request
Last updated
2026-11-21
Source record
OAI-PMH GetRecord
related terms
citation

Limsakul, Piya. Iterative algorithms for two-person zero-sum games. Masters thesis, Monterey, California ; Naval Postgraduate School, 1999. https://hdl.handle.net/10945/13622