Concepts of Strategic Complexity and Specifications of Automata in Extensive-Form Unanimity Bargaining∗

In an earlier paper, we showed that a new complexity measure on strategies, response complexity, implied that strategies chosen in equilibrium were stationary or minimally complex, in the unanimity bargaining game. In this paper, we explore alternative specifications of machines and the standard complexity measure, that of counting the number of states, and show that, except for two-player games, state complexity is not strong enough to reflect the intuition that costs of complexity lead to stationary strategies being played. ∗This paper is part of a larger project on strategic complexity that we began in 1994. One part of this has appeared in Chatterjee and Sabourian (2000). We thank Ani Das-gupta, Vijay Krishna and Ariel Rubinstein for comments on drafts of work related to this project over the years. †This paper was written for the conference in honour of Ken Binmore’s 65th birthday. Binmore has been a pioneer in the understanding and use of complexity in game theory. 1