1998/04/03 by David A. Meyer · 4 citations
Physics and Astronomy · #quant-ph
paper · pdf · doi:10.1103/physrevlett.82.1052
published as Phys.Rev.Lett. 82 (1999) 1052-1055 · 8 pages, plain TeX, 1 figure
arxiv created 1998/04/03 · arxiv updated 2009/12/01
We consider game theory from the perspective of quantum algorithms. Strategies in classical game theory are either pure (deterministic) or mixed (probabilistic). We introduce these basic ideas in the context of a simple example, closely related to the traditional Matching Pennies game. While not every two-person zero-sum finite game has an equilibrium in the set of pure strategies, von Neumann showed that there is always an equilibrium at which each player follows a mixed strategy. A mixed strategy deviating from the equilibrium strategy cannot increase a player's expected payoff. We show, however, that in our example a player who implements a quantum strategy can increase his expected payoff, and explain the relation to efficient quantum algorithms. We prove that in general a quantum strategy is always at least as good as a classical one, and furthermore that when both players use quantum strategies there need not be any equilibrium, but if both are allowed mixed quantum strategies there must be.