Accession Number:

ADA202158

Title:

Convergence Characteristics of Fictitious Play in a Search Game

Descriptive Note:

Master's thesis

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

1988-09-01

Pagination or Media Count:

43.0

Abstract:

In this thesis the convergence characteristics of an iterative meth od for solving area search games were investigated. This method, Fictitious Play, was first introduced by G. W. Brown and solves two-person zero-sum games by having each player sequentially select a pure strategy based on the combined past actions of his opponent. The Fictitious Play method was successfully implemented for an area search game in which two players, a searcher and a target, move independently through and area. In this game, the payoff is the number of detections of the target by the searcher. For each iteration of the game, an upper and lower bound on the value of the game were determined and as the number of iterations of the game increased, these bounds converged to the actual solution. In the games examined, the convergence of the bounds was closely approximated by a power function, with large games converging more slowly. Because of the observed symmetrical convergence of the bounds, an accurate approximation of the value of the game was obtainable from the average of the upper and lower bounds.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE