Computing Winning Strategies for Poset Games

Abstract

<p>The problem of computing winning strategies in games has yielded many important results with applications in fields such as computer science, economics, and mathematics. For example, "Online" games, where the input is received on the fly are used to model process scheduling and paging algorithms. The concept of Nash Equilibrium has implications in economic theory, and Ehrenfeuct-Frass games are used to check whether two structures are isomorphic.</p> <p>In this thesis we are concerned with Partially-Ordered Set (Poset) games. We present two new methods for proving that computing winning strategies for the game of Chomp is in PSPACE. \Ne also present the idea of "Game Completeness", and give an overview of efforts to translate any poset game into an equivalent configuration of Chomp. Finally, we show how Skelley's bounded arithmetic theory W¹₁ can be applied to Chomp, and the consequences of expressing the existence of a winning strategy for the first player in Chomp in simpler arithmetic theories. In short, the contributions of this thesis are as follows:</p> <p>1. A new method for showing poset games in PSPACE, via a polynomial-time (logarithmic-space) reduction to the game of Geography.</p> <p>2. Attempts at a reduction from Geography to poset games, and implications to whether poset games are PSPACE-complete.</p> <p>3. A bounded-arithmetic formulation of the existence of a winning strategy for the first player in Chomp.</p> <p>4. A definition of the concept of Game Completeness, and a translation from treelike poset games to a modified version of Chomp.</p>