Optimization using Weighted Fictitious Play

Bradley A. Belsky and Theodore J. Lambert III
Department of Industrial and Operations Engineering
University of Michigan, Ann Arbor, MI
bbelsky@umich.edu, lambertt@umich.edu

Abstract

Fictitious play is a model traditionally used to describe
learning.  Players in a game assume that their opponents
have a fixed, but unknown mixed strategy.  At each stage,
each player plays their best strategy assuming that every
other player uses as their mixed strategy the empirical
distribution of their past plays.  A recent development of
fictitious play is its use as an optimization heuristic.
The belief distributions from the fictitious play heuristic
converge to the set of Nash Equilibrium, which we view as a
local optimum.

In this paper we investigate a modification to the
fictitious play optimization heuristic.  When calculating
the empirical distribution of each player using standard
fictitious play, each stage is weighted equally.  Players in
a game have no initial knowledge of their opponents mixed
strategies and are more likely to make strategic mistakes in
earlier stages.  As the game progresses, the player begins
to learn their opponents mixed strategies as they converge
to the set of Nash Equilibrium.  This intuition leads us to
believe that weighting later stages more than earlier stages
when calculating the empirical mixed strategy of all players
may lead to faster convergence.

This paper investigates truncating weighting schemes.  In a
truncating weighting scheme weights are assigned to each
stages, however, at some point, the amount of weight
assigned to each play will be fixed.  Numerous truncating
weighting schemes are investigated using randomly generated
games of various sizes.  We compare results of the different
weighting schemes against standard fictitious play.