Design a site like this with WordPress.com
Get started

Universal Solvers Game Theory

Foundations of Game Theory - Universal Solvers

First paper in Footnotes on the Foundations of Game Theory. It provides verifiable information of a universal solver g[], for finite pure-strategy Nash Equilibria, without disclosing code. In doing so, theory at work is displayed. In particular, this feat exploits a bridge between static games and Replicator dynamics to show that only predicted symmetric NE are stable fixed points. A theoretical discussion from the perspective of a Machiavellian ruler accompanies this mathematical treatment.

The second part establishes a link between the number of solutions and their character in terms of symmetric (diagonal) solutions and coupled (off-diagonal) in symmetric matrices with heuristics. Data generated with g[] is used to test hypotheses. This method is improved on with a statistical model to predict the distribution of the number of solutions. Data supports the model. All results follow from simple or common-knowledge concepts and definitions. More general solvers will be discussed in future work.

Keywords:

Game Theory, Applied Mathematics, Social Science, Evolution.

Please note: This paper is a first draft, revision may result in major updates. Comments, requests or questions are welcome.

You may contact me at manuel.echeverria.q@gmail.com

UNIVERSAL SOLVERS [1/2]

This text belongs in the series Footnotes on the Foundations of Game Theory. It introduces the universal solver g[] for pure-strategy Nash Equilibria in static finite games[1]. This presentation establishes the feasibility of the project, and provides glimpses of its scientific potential, beyond the ability of solving thousands of games instantly. In particular, it is feasible to make and test predictions about a large number of games or huge ones. Ultimately, this paper embarks on a route to explore the set of all possible games, in turn the basis for a wide range of thought experiments and theorems within the Sciences, Mathematics and Philosophy. Theory is discussed alongside the solver, from the perspective of a Machiavellian ruler.

It is known mathematicians are able to provide proofs without revealing much about of the underpinnings of their work. Likewise, this paper does not print code but provides information to check the following constraints:

  • Proposed solutions indeed are NE.
  • All other outcomes are unstable.
  • Games are not rigged in order to falsely emulate a solver.
  • Provide data to check all of the above.

The reader will also be introduced to fundamental connections between seemingly disparate fields. In particular, this paper explores the connection between static and dynamic games, with implications on a much heated debate. Satisfying a-d amounts to problem solving, which displays theory at work in the process.

This Footnote starts by generating of data from known distributions, and then proceeds with automated solving by virtue of g[]. The cost of deception (c), is high and increasing because manipulations nevertheless must (i) be such that all pure-strategy NE are found (ii) conform to a well-known distribution with specified parameters. In addition (iii), big enough games will be computed in sizeable quantities. This combination will work as a deterrent burdening deception in proportion to the number of games solved with transparency. Future Footnotes on the Foundations of Game Theory will expand on universal mixed-strategy solvers, dynamic games, Markov processes and Evolutionary Game Theory. In addition, predicting NE outcomes from a particular distribution of the incentive structure has theoretical appeal. This paper takes important steps in that direction, and will be expanded on in updates and future footnotes.

To check large games is cumbersome and arguably requires a similar device in the hands of the readers. In order to address this while respecting a-d, Evolutionary Game Theory will be used to provide means to evaluate results. Articulation of games in terms of Replicator Dynamics bridges symmetric NE and fixed points, where myopic players adapt to the average (field) play. In this manner I effectively provide data and well-known equations to check the solution, without disclosing crucial information about g[] etc. I will demand some goodwill and/or effort from the readers when evaluating a batch of 50, seven-player randomly generated games and their solutions. The sheer size should be enough to deter manipulation and/or manual search. The Replicator Dynamics approach is introduced with a (50×50) 2-player game in order to avoid more theorems or analysis resulting from n>2 players. In this setting, the strategies can be interpreted as types of a population.

Elusive topics such as the stark connection between method, theory and ruminations on society are given systematic treatment. In similar fashion, informal reasoning on the correspondence between evolution, myopic behaviour and rational behaviour in society is given sound theoretical basis.

DATA g [ ]

50 games with seven players are solved. The number of strategies for each player is drawn from a Uniform Distribution[1,3]. The incentive structure is generated with a Poisson of mean 3 for each player strategy; and at each contingency of the game. All relevant data is uploaded with description.

RESULTS 1

Strategy indexed are reserved for each player with indexes: ABC, DEF,… STU. Table 1 provides all the states & NE for the first of the 50 games.

T1. NE Game 1/50

STATEP1P2P3P4P5P6P7STATEP1P2P3P4P5P6P7
ADGJMPS4125524CDGJOPS2233212
ADGJNPS5314947CDGKMPS5243122
ADGJOPS2244246CDGKNPS3352341
ADGKMPS6224230CDGKOPS5455711
ADGKNPS6333226CDGLMPS4443722
ADGKOPS3222641CDGLNPS2322052
ADGLMPS3121253CDGLOPS3361514
ADGLNPS7203261CDHJMPS2213374
ADGLOPS3702536CDHJNPS1212413
ADHJMPS4333122CDHJOPS1332233
ADHJNPS2123554CDHKMPS1242214
ADHJOPS4244351CDHKNPS2732821
ADHKMPS6325523CDHKOPS11041563
ADHKNPS5411423CDHLMPS3436311
ADHKOPS4414142CDHLNPS3522312
ADHLMPS7331142CDHLOPS4353442
ADHLNPS4125132CEGJMPS4421553
ADHLOPS2501174CEGJNPS2142338
AEGJMPS3650236CEGJOPS1111234
AEGJNPS2431244CEGKMPS2437422
AEGJOPS5316203CEGKNPS2411043
AEGKMPS5136241CEGKOPS1213144
AEGKNPS4422423CEGLMPS3412434
AEGKOPS7431022CEGLNPS5325445
AEGLMPS6262340CEGLOPS4532223
AEGLNPS3513223CEHJMPS1313321
AEGLOPS2414234CEHJNPS3435343
AEHJMPS2350231CEHJOPS4433263
AEHJNPS9303503CEHKMPS2233112
AEHJOPS5443053CEHKNPS2532430
AEHKMPS4336014CEHKOPS3122037
AEHKNPS4156336CEHLMPS2441653
AEHKOPS2324731CEHLNPS3313659
AEHLMPS1122450CEHLOPS5333344
AEHLNPS4143353NEADHKMPS; CDGLMPS; CEGLNPS; CDGKOPS
AEHLOPS4023345Strat{{A,B,C},{D,E},{G,H},{J,K,L},{M,N,O},{P},{S}}
BDGJMPS3252434 
BDGJNPS2423241 
BDGJOPS4213012 
BDGKMPS2831204
BDGKNPS2433202
BDGKOPS2233330
BDGLMPS4234446
BDGLNPS5862656
BDGLOPS2284355
BDHJMPS1123435
BDHJNPS3114145
BDHJOPS2533332
BDHKMPS3544514
BDHKNPS5420342
BDHKOPS2423244
BDHLMPS3212343
BDHLNPS6352221
BDHLOPS2428325
BEGJMPS2347132
BEGJNPS5243433
BEGJOPS4425313
BEGKMPS4211164
BEGKNPS2531322
BEGKOPS4245511
BEGLMPS6251323
BEGLNPS2520116
BEGLOPS4117346
BEHJMPS1312043
BEHJNPS3332173
BEHJOPS4132424
BEHKMPS2231235
BEHKNPS3641441
BEHKOPS1834552
BEHLMPS6625134
BEHLNPS3635142
BEHLOPS3112333
CDGJMPS2341353
CDGJNPS2323334

The strategy set is {{A,B,C},{D,E},{G,H},{J,K,L},{M,N,O},{P},{S}}. The solutions for the 50 games are:

Full dataset is provided online.  Note some sets are empty, which means at least a mixed-strategy equilibrium. Recall games are restricted to pure-strategy play by assumption. Such games are however common in the literature with countless applications. A Footnote on a mixed-strategy solver will accompany these findings in the future.

CONCLUDING REMARKS 1

g[] deals with finite pure-strategy games. The solutions of 50 games were computed instantly with obsolete hardware. Thus, students or researchers with limited resources also benefit from this software. The statistical approach taken so far does not only safeguard code, but provides glimpses of future venues for research. Regularities such as the number of equilibria and their properties, given distributions underpinning incentives, is an arena for statistical inference and analysis. Huge games can be predicted or explored in this manner. Such feats are relevant in applications for purpose of institutional design, theory creation, and hypothesis testing. Statistical models and predictions about how many equilibria are to be expected given distributions underpinning incentives are treated in Statistical Properties of NE.

EVOLUTIONARY GAME THEORY g[]

More realistic assumptions concerning the behavioural dispositions of isolated individuals and groups have gained traction over the years. One of the reasons is quite fierce critique of perfect rationality, especially unrealistic calculation prowess, presumably envisaged by Nash or Von Neuman. However, the duality between equilibria reached by perfectly rational individuals on one hand; and myopic ones through trial and error on the other, was emphasised from the outset. Such remarks remain relevant to understand one of the more powerful aspects of Game Theory. As I have argued elsewhere, multiplicity of equilibria can be used for purposes of institutional design and, among other things, be conceptualised as expressions of intent from a rational planer.

Moreover, critique of systems and outdated theory in their defence is not aided by discarding this link by means of hand waving. This connection provides clues to why systems prevail, in particular why flawed apologetic theories persist. In this setting myopic individuals converge to an important set of NE, guided by trial and error. Furthermore, more realistic assumptions about the psychology of individuals and non-pecuniary motives may have negligible impact on patterns of interaction and final outcomes, when not compatible with overarching economic structures. Nevertheless, it is easy to introduce them when employing universal solvers.

Replicator dynamics starts with a population consisting of n different types. The shares of the population playing (being) one of these types is denoted xi, and expressed in the vector x containing the population distribution of these shares. The evolution of x is given by the following n-1 differential equations at any point of time

x’i = xi[π(si,x) – π(x)]

These state that the share of the population using a particular strategy/being a type is determined by the difference between the payoff of such strategy π(si,x) and the average payoff in the population π(x). The former payoff simply is the expected value of si given the population distribution x. The latter is computed from the former by taking the expected value of π(si,x) instead. By convention, time (t) is suppressed in notation.

This two-player setting can be interpreted as follows: a pure strategy si of player one gives rise to a payoff (π) which reflects how it fares against nature. The latter plays some type with certain probability reflecting the population distribution. Therefore, symmetric matrices are readily consistent with this setup. Note however, that types can be interpreted as subsets of one entity.

The evolutionary game is constructed as follows. A symmetric nxn matrix (n=50) is generated with a Poisson[3] distribution until a symmetric solution emerges. Payoffs when two of the same type meet are the same for both. A game of this size is costly to generate with correct distribution and solutions, without a device such as g[]. This holds trueeven with a corresponding system of replicator-dynamics differential equations. The existence of symmetric NE must still be confirmed with such roundabout way, which in effect becomes taxing constraint in terms of time and computation.

Symmetric pure-strategy NE are fixed point in the corresponding Replicator-Dynamics systems for n>2. This setup and result is common-knowledge within Evolutionary Game Theory. Hence, the reader is encouraged to consult the mathematical research literature on this topic if needed.

RESULTS 2

Data for this experiment is provided at online. There are three pure-strategy NE. One chooses 22 and the other 29; or both choose strategy 37.

In the first experiment, the latter symmetric NE is given a share of x37(0)= 99%. The rest are given the uniform distribution[2]. As figure 1 shows, there is immediate convergence and stability throughout t  [0,500]. This system would have reached steady state fast if simulation ruled out negative values, i.e. in any conceivable (non-subjective) realistic setting interpreting xi as shares in [0,1]. But the results are nevertheless strengthened as such detours may induce drifts, which can make the NE drop to zero, if the mean becomes negative. Otherwise, once a share reaches zero it stays there. In effect, the absence of a [0, 1] restriction makes the stability test more demanding.

F1. Myopic Evolution & Symmetric NE (X37)

The state vector x evolves to a homogenous population with a single type, namely x37 which is the symmetric pure-strategy Nash Equilibrium of the corresponding 50×50 static game.

The second experiment searches for a lower bound for stability. At x37(0)  95 %, and the rest uniformly distributed, the equilibrium holds until t=120. At x37(0)  4/5 there is an initial convergence, followed by a sharp decline towards zero at t  [24, 29].

Instead it is x36 which stabilises between [1/5, 2/5], suggesting a polymorphic equilibrium, which may correspond to a mixed-strategy NE. Analysis of such cases is postponed until the mixed-strategy solver is presented.

F2. Stability Period & Initial Conditions

Clearly, steady-state time increases dramatically about a 95 % threshold.

The third experiment takes a random sample of size 10 from the set of types and checks convergence with initial conditions x­i(0)  99%, and the rest uniformly distributed as above. The favoured types are

{18, 43, 35, 33, 23, 17, 42, 14, 46, 32}

None of the types in the sample, which consists of 1/5 of the total, are stable. Oddly enough, x37 increases and approaches 1 when x17 is favoured. Table 3 below shows these in groups.

Counting begins at the first column and proceeds downwards, i.e. 18 is in column 1, row 1; and 17 in column 2, row 1. No stable NE-convergence detected at t = 500.

F3. 10 Favoured & Stability

The reader is encouraged to consider a more analytical route, e.g. linearisation, or simulate the full sample of alternatives to the symmetric NE.

CONCLUDING REMARKS 2

This section utilised a bridge between Evolutionary Game Theory and symmetric NE. This take also highlights a link between dynamics with myopic agents on one hand; and static one-shot games, with equilibria sustained by perfectly rational players, on the other. In doing so, I have provided verifiable information of a universal solver without disclosing code.

Replicator Dynamics confirmed the stability of a symmetric pure-strategy equilibrium, and the instability of others. Allowing negative state-variables of type distributions is unrealistic but makes the result more robust. In essence this relaxation of restrictions works as noise which perturb equilibria. Notwithstanding, there is a sharp exponential increase in steady-state time when the symmetric NE is given a share above 95%. A methodological point is made. Useful inferences about application of a class of models may be drawn from a particular conceptually flawed one, effectively unsuitable for realistic applications, at a fundamental mathematical level. Of course, it is not unthinkable idiosyncratic beliefs assign negative probabilities or shares.


[1] Coded by me at the outset this side-project, starting April 2022. I want students to learn and create with the principles of social science by constructing, and using, universal solvers.

[2] The uniform distribution is adapted to the initial condition of the NE type. Each type’s initial condition is random e.g. xi ~ U[0,1/a], and a must be s.t. x satisfies a certain Kolmogorov condition.

Advertisement

Published by Manuel Echeverría

Licentiate of Philosophy. Independent Researcher.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: