Downloads & Free Reading Options - Results

Consider a repeated two-person game. The question is how much smarter a player must be in order to effectively predict the moves of the other player. The answer depends on the formal definition of effective prediction, the number of actions each player has in the stage game, as well as on the measure of smartness. Effective prediction means that, no matter what the stage-game payoff function, the player can play (with high probability) a best reply in most stages. Neyman and Spencer [4] provide a complete asymptotic solution when smartness is measured by the size of the automata that implement the strategies: Let G = hI, J, gi be a two-person zero-sum game; I and J are the set of actions of player 1 and player 2 respectively, and g : I × J ! R is the payoff function to player 1. Consider the repeated two-person zero-sum game G(k,m) where player 1’s possible strategies are those implementable by an automaton with k states and player 2’s possible strategies are those implementable by an automaton with m states. We say that player 2 can effectively predict the moves of player 1 if for every reaction function r : I ! J player 2 has a strategy (in G(k,m)) such that for every strategy of player 1 the expected empirical distribution of the action pairs (i, j) is essentially supported on the set of action pairs of the form (i, r(i)). [4] characterizes. ©2007 Microsoft Corporation. All rights reserved.