Main content

The Structure of the Space of All Game-Playing Strategies

Show full item record

Title: The Structure of the Space of All Game-Playing Strategies
Author: Tsang, Jeffrey
Department: Department of Mathematics and Statistics
Program: Mathematics and Statistics
Advisor: Pereira, Rajesh
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.
Date: 2014-04

Files in this item

Files Size Format View
Tsang_Jeffrey_201404_PhD.pdf 59.94Mb PDF View/Open

This item appears in the following Collection(s)

Show full item record