Matrix Game theory

by Julien Ugon(*) and Nigel Backhouse(**),
* CUST, Universit Blaise Pascal, France.
ugon@ucfma.univ-bpclermont.fr

** Dept. Math'l Sciences, University of Liverpool, UK

sx52@liv.ac.uk

NOTE: This package provides Maple functions for the analysis of two players matrix games. Functions applicable to zero-sum and non-zero-sum games are included.

Introduction

Game theory is the area of Applied Mathematics which attempts to model competition and conflict. This includes not only the classical games, like chess or poker, but also applications as diverse as economics, military strategy and evolutionary biology.

A common feature of most games is that the players can utilize a number of pure strategies. Each player, as a rational being, tries to maximize his expected payoff by a suitable mixture of his pure strategies - assuming the game can be played many times, so that averages make sense.

In the game of chess the best payoff is winning, although no one knows a strategy to achieve this! In the general theory, an individual's payoffs are measured in terms of the values of a utility function, reflecting personal preference relations. Sometimes this corresponds to a material or financial benefit, but as in the game of chess, it can simply be a measure of pleasure.
In this package we concentrate on 2-player games, where each player has a finite number of pure strategies. Furthermore, it is assumed that each game is characterized by the bimatrix of payoff pairs corresponding to each player using a pure strategy against the other - conventionally the first player's strategies label the rows, and tha second player's strategies label the columns.

The most simply analyzed games are the so-called zero sum (ZS) games, in which the players are completely antagonistic - one player's gains are the other's losses and vice versa. Such a game is defined by a single matrix, whose elements are the pure strategy payoffs to the first player - those for the column player are the negative of these values. The mathematics of such games was first developed by John von Neumann, who founded the whole subject of game theory in collaboration with economist Oskar Morgenstern. We provide the following functions in Maple to analyse ZS games:

1. The function dominate eliminates dominated pure strategies - a rational player would not use any pure strategy dominated by another;

2. If saddlepoints exist, saddle finds these simple pure strategy solutions;

3. If one player only has two pure strategies, the game can be solved graphically - graphsolve achieves this;

4. If the first player knows that the second player will repeatedly play a certain strategy, bestanswer gives his best response as the mixed strategy which maximizes his expected payoff - the use of this function is not restricted to ZS games;

5. If all else fails, solution finds optimal strategies by solving the equivalent linear programming problem - a revised simplex algorithm, revsimp, for use in a matrix formulation, is invoked.

The analysis of non-ZS games is more interesting and varied - the Prisoners' Dilemma, the Battle of the Sexes, and Chicken, are famous and applicable examples. Clearly, since ZS games are totally antagonistic, there is no possible advantage to be gained by collaboration. In contrast, in a non-ZS game, the players can either play independently, each loking after his own interests, or can agree to cooperate, with a view to improving separate and/or joint payoffs.

Whether a game is played cooperatively or not, any method of solution must lead to results within the so-called payoff region. This is the set of all payoff pairs, plotted on a 2-d diagram. This set contains the finite collection of points defined by the elements of the bimatrix - the extreme points of this set form the extreme set. If the game is played cooperatively - players can coordinate their strategies - then the payoff region is the convex hull of the extreme set. In the noncooperative version of the game, the payoff region is a subset of this convex hull, but does not have to be convex itself. In the limit of a ZS game, the payoff region degenerates to a straight line.

Solution methods for cooperative games often use some notion of bargaining. This involves restricting attention to a subset of the payoff set, usually called the bargaining set or negotiation set, relative to a status quo payoff, and then applying the Nash algorithm.

For noncooperative games, the important solution concepts are based on the analysis of Nash equilibria - the corresponding strategy vectors are mutual best responses. The finding of Nash equilibria is difficult mathematically, partly because of a lack of uniqueness. Before starting, the elimination of dominated strategies should be considered. However, it is known that unless the domination is strict, the reduction process can remove some Nash equilibria.

The following functions are supplied for the analysis of non-ZS games:

1. The function bargreg returns the extreme set, from which the cooperative payoff region can be obtained by a polygon plot;

2. payoff and payoff2 provide the payoff region for 2 x 2 noncooperative games;

3. bargset returns the extreme points of the bargaining set for cooperative games;

4 minimax returns the status quo payoffs used in Nash bargaining , and nashcoop provides the corresponding Nash solutions;

5. strictdomi and reduce remove strictly dominated and non-strictly dominated strategies, respectively.

6. isnash tests a strategy pair to see if it belongs to the set of Nash equilibria;

7. The functions lemkehowson, lemkehowson2, allnasheq and allnasheq2 return one, several or all Nash equilibria - in some cases this means the extreme points of a set of convex polytopes of equilibria.

For every function listed above, there is a help page containing syntax and examples

Installation Instructions

Save the files maple.hdb, maple.ind and maple.lib (available in WinZip format by clicking the "Download Code" X on the Application Center) in a directory of your choosing, for instance C:/mylib/gametheory. Then execute the following:

> #libname:="C:/mylib/gametheory", libname;

> #march('create', libname[1],100);

> #savelib('matrixgames');

This saves the matrixgames package as a Maple library on your machine. From now on, in any worksheet where you want to use the matrix games package, execute the commands:

> #libname:="C:/mylib/gametheory", libname;

> #with(matrixgames);

Conclusion:

This package contains most of the functions needed to study 2-player matrix games. They can also be used as building blocks for more complex research applications. The selection of functions and the coverage of the package is based on an undergraduate course given by one of us, NBB, at the University of Liverpool, UK. The computation algorithms for finding Nash equilibria are, however, of a considerable more advanced nature and of continuing research interest. We are planning another package with functions appropriate to the analysis of n-person coalition games.

References:

P.Morris , I ntroduction to Game theory - Springer-Verlag, 1994.

L.C.Thomas, Games, Theory and Applications, Ellis-Horwood, 1984.

J. von Neumann and O. Morgenstern, Theory of Games and Economic Behaviour, Princeton University Press, 1944.

R.D.Luce and H.Raiffa, Games and Decisions: Introduction and Critical Survey, John Wiley & Sons, 1957.

J.Dickhaut and T.Kaplan, A Program for Finding Nash Equilibria, in Economic and Financial Modelling with Mathematica, Editor: Hal Varian, Springer-Verlag, 1993.

R.D.McKelvey and A.McLennan, Computation of equilibria in finite games in Handbook of Computational Economics, vol. 1, Elsevier Science, 1996.

Disclaimer: While every effort has been made to validate the solutions in this worksheet, Waterloo Maple Inc. and the contributors are not responsible for any errors contained and are not liable for any damages resulting from the use of this material.