Imitation games and computation
Date
2010
Authors
McLennan, Andrew
Tourky, Rabee
Journal Title
Journal ISSN
Volume Title
Publisher
Academic Press
Abstract
An imitation game is a finite two person normal form game in which the two players have the same set of pure strategies and the goal of the second player is to choose the same pure strategy as the first player. We explain how, in two different settings, observations obtained from imitation games complete a circle of ideas, showing that phenomena that had for many years seemed to be distinct are actually superficially different manifestations of a single structure. First, one can pass from a given two person finite game to an imitation game whose Nash equilibria are in one-to-one correspondence with the Nash equilibria of the given game. Second, each of the paths of the procedure described in Lemke (1965) for solving a linear complementarity problem is the projection of the path of the Lemke-Howson algorithm applied to an imitation game.
Description
Keywords
Keywords: 2-Nash; Computational complexity; Computational economics; Imitation games; Lemke paths; Lemke-Howson algorithm; Nash equilibrium; Symmetric games; Two person games
Citation
Collections
Source
Games and Economic Behavior
Type
Journal article
Book Title
Entity type
Access Statement
License Rights
Restricted until
2037-12-31
Downloads
File
Description