In this thesis we present a new foundation for game theory. Our model for a game is defined precisely by the response graph, a natural object underlying all classical games. We call this model a preference game. Preference games generalise classical games in that all classical games have an associated preference game. Preference games also have a natural choice of solution concept: the sink equilibria, which are the sink strongly connected components of this graph. These exist in all games, and generalise pure Nash equilibria. We argue that preference games and sink equilibria form a predictive and well-founded model of strategic interaction that both clarifies problems from classical game theory and presents new solutions and predictions. Our approach is three-pronged. First, we show preference games are axiomatically well-motivated and so are broadly-applicable models of strategic interaction. We obtain these games by weakening the classical formulation of game theory with two axioms: ordinality, asserting the model requires only that players know a discrete order over the outcomes; and relevance, asserting that our model depends only on preferences over outcomes players can choose between. We give a new discussion of the Prisoner's Dilemma, where we show that the paradox can be rephrased as a consequence of Nash equilibria satisfying the relevance axiom, while Pareto efficiency satisfies only the ordinality axiom. We show further that preference games implicitly capture in their graph structure the equivalences caused by renaming players or strategies, while expressing these equivalences in classical games is cumbersome. Second, we show preference games give new insight into strategic interaction. We examine two-player games, with a focus on zero-sum and potential games. Despite both being classically defined in terms of utility functions, we show that their strategic structure can be easily understood through preference games, which make clear the duality between these two classes. We use this to prove a new theorem of classical game theory: in every two-player game, every non-iteratively-dominated strategy takes part in a 2x2 subgame with the preference structure of Matching Pennies or 2x2 Coordination. As a consequence, any two-player game sharing a response graph with both a zero-sum game and a potential game is dominance-solvable. The proofs are combinatorial. Thirdly, we show preference games are compatible with game dynamics, while classical games and mixed Nash equilibria are not. Game dynamics---the mathematical model of strategic adjustment used in evolutionary game theory---cannot generically converge to mixed Nash equilibria. By contrast, pure Nash equilibria are attracting fixed-points; the natural generalisation of this dynamic concept is the sink chain components, a topological object defined by the Fundamental Theorem of Dynamical Systems. While these do not exist in general, we prove an open problem establishing their existence under the replicator dynamic, the best-known game dynamic. We prove that sink chain components under the replicator always contain sink equilibria, and we conjecture that this relationship is always one-to-one. Thus we obtain the surprising result that the complex, sometimes chaotic, behaviour of the replicator dynamic is governed in the long run by the response graph of the game, with the outcome determined by a simple combinatorial object---sink equilibria. Sink equilibria also describe the long-run outcomes of all discrete dynamics defined by Markov chains on the response graph. We conclude with a number of open problems that emerge from preference games.
Game Theory, response graphs, game dynamics, machine learning
Networked Digital Library of Theses and Dissertations