Repeated Matching Pennies with Sublinear Randomness

Lance Fortnow
Northwestern University

Playing an repeated matching pennies has a simple mixed equilibrium where both players play uniformly at random in each round. This equilibrium requires that both players have as many bits of randomness as rounds of play. We show that in a computationally-bounded setting with the right assumptions, one can have an near equilibrium with much less randomness. We also explore the limits of this approach.

Back to Algorithmic Game Theory