The Structure of the Space of All Game-Playing Strategies

Date

2014-05-12

Authors

Tsang, Jeffrey

Journal Title

Journal ISSN

Volume Title

Publisher

University of Guelph

Abstract

Offering a well-developed setting, mathematical games have been used in the behavioural sciences as a model for studying interactions between agents; proposals have been made that humans act according to particular strategies. However, the inability to quantitatively measure the difference between strategies, especially the observed and the hypothesized, casts doubt on the validity of these purported explanations. This thesis begins by defining the fingerprint, an operator that turns an arbitrary game-playing strategy into a functional summary of its behaviour via recording its geometrically-weighted average result against a parametrized probabilistic memoryless opponent. Various properties, including analyticity, equicontinuity, indistinguishability and symmetry are proven, improving upon prior work. A visualization technique using standard RGB colour space is also provided, with applications to studying the game-theoretical optimal strategy against known reactive opponents. The natural metric on the space of strategies is defined, and computational issues studied. Amongst the proofs are that N derivatives are necessary for order N+1 convergence in quadrature, that the intuitive solution to classical multidimensional scaling is heavily suboptimal, and a strategy for reducing the space requirements for matrix multiplication, directly used to implement the SMACOF scaling algorithm in asymptotically minimal space. A fast multilateration algorithm was developed to embed strategies into Euclidean space, to enable automated analysis of evolutionary simulations. Several representational subspaces, of sizes advancing the frontier of high-performance computing software, were used to study the space of all possible strategies in iterated Prisoner’s Dilemma. The three leading principal components of each subspace are impeccably consistent across representations: they correspond to cooperativity, responsiveness, and initialism of the strategies. From this, a simple to compute summary of strategies was constructed, one which directly predicts the distance between arbitrary strategies. Using the data gathered, this predictor achieved a correlation beyond 0.977 on a testing set of over 6.6 billion. An operational recommendation to experimental scientists: pair the test subject with a confederate playing uniformly at random, the data from which can be used in the predictor; along with analogous values from the theorized model, this finally allows for quantitative assessment of the consistency of the model.

Description

Keywords

game theory, iterated Prisoner's Dilemma, optimal strategies, evolutionary computation, evolutionary game theory, fingerprint, mathematical analysis, finite state transducers, Markov chains, Markov decision process, numerical analysis, algorithms, high-performance computing, dimensionality reduction, multidimensional scaling, visualization, experimental design

Citation