The set coincidence game: Complexity, attainability, and symmetric strategies

摘要

We develop two closely related aspects of the complexity theory of the Set Coincidence Game G(V, W), in which two players alternately choose elements not previously chosen from a finite, nonempty set V, and W is a given family of nonempty subsets of V (the “inning sets”). The game is won by that player who first adds an element to the set of “chosen” elements S, so that S ϵ W. We first show that the Set Coincidence Game (in an efficient encoding) is complete in PSPACE. We then develop the theory of attainability which we use to give intuition about the structure of minimal forced wins for either player, and about the “difficulty” of the game. We also show that a well-known type of strategy (“Symmetric” or “pairing”) is optimal in the context of our definition of attainability.