Excludability and Bounded Computational Capacity Strategies

Ehud Lehrer and Eilon Solan

We study the notion of excludability in repeated games with vector payoffs, when one of the players is restricted to strategies with bounded computational capacity. We show that a closed set that does not contain a convex approachable set is excludable by player 2 when player 1 is restricted to use only bounded-recall strategies. We also show that when player 1 is restricted to use strategies that can be implemented by finite automata, player 2 can exclude him from any closed, non-convex set whose convex hull is minimal convex approachable.