Learning and Competition with Finite Automata

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.

Speaker Details

Abraham Neyman is Professor of Mathematics at the Hebrew University of Jerusalem and member of its Center for Rationality. Main research interest is game theory in general, and repeated games and games played by boundedly rational players/machines in particular.More detailed bio data and publications is available at www.ration.huji.ac.il/neyman

Date:
Speakers:
Abraham Neyman
Affiliation:
Hebrew University of Jerusalem
    • Portrait of Jeff Running

      Jeff Running