Schalk A., The Theory of Games and Game Models Lctn.pdf

CS3191

The Theory of Games and Game Models

Andrea Schalk

A.Schalk@cs.man.ac.uk

Department of Computer Science

University of Manchester

September 1, 2003

About this course

This is an introduction into the theory of games and the use of games to model a variety of

situations. It is directed at third year computer science students. As such it contains some

proofs, as well as quite a bit of material which is not part of what is classically understood

as game theory. This course is usually taught as CS3192 in the second semester, so most

references you'll nd will be to that (for example regarding old papers).

What this course is about

Games have been used with great success to describe a variety of situations where one or more

entities referred to as players interact with each other according to various rules. Because

the concept is so broad, it is very exible and that is the reason why applications range from

the social sciences and economics to biology and mathematics or computer science (games

correspond to proofs in logic, to statements regarding the `fairness' of concurrent systems,

they are used to give a semantics for programs and to establish the bisimulation property

for processes). As such the theory of games has proved to be particularly fruitful for areas

which are notoriously inaccessible to other methods of mathematical analysis. There is no

set of equations which describes the goings-on of the stock-market (or if there is, it's far too

complicated to be easily discoverable). Single transactions, however, can be described using

(fairly simple) games, and from these components a bigger picture can be assembled. This is

a rather dierent paradigm from the one which seeks to identify forces that can be viewed as

the variables of an equation. Games have also been successfully studied as models of conict,

for example in biology as well as in sociology (animals or plants competing for resources or

mating partners). In particular in the early days of the theory of games a lot of work was

funded by the military.

When playing games it is typically assumed that there is some sort of punishment/reward

system in place, so that some outcomes of a game are better for a player than others. This

is typically described by assigning numbers to these outcomes (one for each player), and it

is assumed that each player wishes to maximise his number. This is typically meant when it

is stipulated that all players are assumed to behave rationally. Games are then analysed in

order to nd the actions a given player should take to achieve this aim.

It should be pointed out that this is what is referred to as a game theoretic analysis|

there are dierent ways of analysing the behaviour of players. Sociologists, psychologists and

political scientists, for example, are more likely to be interested what people actually do when

playing various games, not in what they should be doing to maximize their gains. The only

way of nding out about people's behaviour is to run experiments and watch, which is a very

dierent activity from the one this course engages in.

To give a practical example, assume you are given a coin and, when observing it being

thrown, you notice that it shows heads about 75% of the time, and tails the remaining 25%.

When asked to bet on such a coin, a player's chances are maximized by betting on heads

every single time. It turns out, however, that people typically bet on heads 75% of the time

only!

Economists, on the other hand, often are interested in maximizing gains under the as-

sumption that everybody else behaves `as usual', which may lead to dierent results than if

one assumes that all players play to maximize their gains. Provided the `typical' behaviour

is known, such an analysis can be carried out with game-theoretic means.

In mathematics, and in this course, games are analysed under the assumption that people

behave rationally (that is, to their best advantage). Depending on the size of the game

in question, this analysis will take dierent forms: Games which are small enough allow a

complete analysis, while games which consist of a great many dierent positions (such as

Chess or Go) can not be handled in that way.

In this course we will examine games of dierent sizes and appropriate tools for analysing

them, as well as a number of applications.

Organization

The material of the course will be presented in traditional lectures, supported by these notes.

Since the course has run once before most of the mistakes should have been eliminated. I

would appreciate the readers' help in order to eliminate the remaining ones. If you spot

something that seems wrong, or doubtful, and which goes beyond being a simple mistake of

spelling or grammar then please let me know by sending email to A.Schalk@cs.man.ac.uk .

I will keep a list of corrigenda available on the course's webpage at

http://www.cs.man.ac.uk/~schalk/3192/index.html .

I would like to thank David MacIntosh, Isaac Wilcox, Robert Isenberg and Roy Schestowitz

from previous years' courses for helping me improve the course material.

As part of the notes there are a number of exercises designed to familiarize you with the

various concepts and techniques. These exercises typically consist of two parts which are

fairly similar. The rst of these will be covered in the examples sessions, while the second

part should serve revision purposes. The examples sessions will take the place of some of the

lectures|we will decide as a group when it is time for another one. Under no circumstances

will they be turned over into another lecture|instead, I expect the discussion of exercises to

be driven by you. This worked very well last year, with contributions by the students to each

exercise.

While I will not teach this course as I might, say, in a maths department, game theory is

a mathematical discipline. As such it is fairly abstract, and experience shows that to learn

such material, an active mode of learning is required, where students try to solve exercises

by themselves (rather than just `consuming' what is being presented to them by somebody

else). Or, as somebody else put it, mathematics is not a spectator sport.

All the material in the notes is examinable, including the exercises. The 2002 exam is

available on-line at http://www.intranet.man.ac.uk/past-papers/2002/science/comp_

sci/Sem2/CS3192.pdf , and last year's should soon follow.

Literature

This course was newly created last year, and is, to the best of my knowledge, the rst such

in a computer science department. Hence there is no one text book which covers everything

I will lecture on. Within the text I give references for specic topics to allow you to read up

on something using a source other than the notes, or for further reading if something should

nd your particular interest.

Contents

About this course

1 Games and strategies 6

1.1 So what's a game? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2 Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3 Games via strategies|matrix games . . . . . . . . . . . . . . . . . . . . . . . 18

1.4 The pay-o of playing a game . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.5 Simple two person games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2 Small (non-cooperative) games 26

2.1 2-person zero-sum games: equilibria . . . . . . . . . . . . . . . . . . . . . . . 26

2.2 General non-cooperative games: equilibria . . . . . . . . . . . . . . . . . . . . 36

2.3 Are equilibria really the answer? . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.4 Mixed strategies and the Minimax Theorem . . . . . . . . . . . . . . . . . . . 42

2.5 Finding equilibria in 2-person zero-sum games . . . . . . . . . . . . . . . . . . 47

2.6 An extended example: Simplied Poker . . . . . . . . . . . . . . . . . . . . . 52

3 Medium games 60

3.1 The algorithmic point of view . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.2 Beyond small games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.3 The minimax algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.4 Alpha-beta pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

4 Large games 73

4.1 Writing game-playing programs . . . . . . . . . . . . . . . . . . . . . . . . . . 73

4.2 Representing positions and moves . . . . . . . . . . . . . . . . . . . . . . . . . 73

4.3 Evaluation functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

4.4 Alpha-beta search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

4.5 The history of Chess programs . . . . . . . . . . . . . . . . . . . . . . . . . . 86

5 Game models 93

5.1 The Prisoner's Dilemma revisited . . . . . . . . . . . . . . . . . . . . . . . . . 93

5.2 Generalizing the game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

5.3 Variations on a theme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

5.4 Repeated games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

5.5 A computer tournament . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

5.6 A second computer tournament . . . . . . . . . . . . . . . . . . . . . . . . . . 104

5.7 Innitely and indenitely repeated versions . . . . . . . . . . . . . . . . . . . 108

5.8 Prisoner's Dilemma-type situations in real life . . . . . . . . . . . . . . . . . . 109

6 Games and evolution 112

6.1 An ecological tournament . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

6.2 Invaders and collective stability . . . . . . . . . . . . . . . . . . . . . . . . . . 113

6.3 Invasion by clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

6.4 Territorial systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

6.5 Beyond Axelrod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

6.6 More biological games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

7 Exercises

135

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: