Shortcuts:
*Course notes ·
Test yourself ·
Exams ·
Slides ·
Content*

I have written a short piece on why to choose (or not to choose) COMP30191.

Games are not only something people take part in to pass the time in a
pleasant way; they have also become a widely-used model in a variety
of disciplines. Even in areas which typically do not lend themselves
to traditional mathematical modelling, such as economics, biology and
the social sciences, they have had somewhat surprising successes, and
the use of game models has led to entire sub-disciplines being
created, such as `traditional game theory' in economics (most books
with *Game Theory* in the title will fit into that area) or
`evolutionary game theory' in biology.

Computers are widely used in this kind of modelling, either to `solve' games, that is to find an optimal strategy, or to simulate playing (often many) such games as a way of exploring the predictions a given game model will make. Additionally, game models can be applied to model computer systems--for example, machines competing for slots on a network to transmit data.

In this course I will give an overview into methods for `solving
games' as well as give examples for how games are used to model
various scenarios. I would like to stress here that this course will
require *dealing with abstract entities*; if you hated the
theoretical or mathematical components of modules you have taken in
the past this may not be a good choice for you. It should also be
emphasized that this course has nothing whatsoever to do with
computer games. More details regarding the are given below.

This course is taught in a **non-traditional
way**. There is a full set of notes with exercises for the
course, and the expectation is **that every student will each week
work through a set number of pages**. This activity is supported by
weekly sessions that serve two purposes:

- Students can ask questions about the set reading for the previous weeks.
- I introduce the general ideas for the reading for the present week.

When Week 1 Weeks 1-5, 7-12 Weeks A (3, 5, 8, 10) Week 12 |
What Introduction Question sessions Examples classes Assessment |
Where Mo 4.00pm in 1.4 Mo 4.00pm in 1.4 We 9.00am in LF15 We 10.00am in LF15 We 9.00am in LF15 We 10.00am in LF15 |
Who All All Surnames ending A-L Surnames ending M-Z Surnames ending A-L Surnames ending M-Z |

Some frequently asked questions (and their answers) regarding the course.

The course notes cover the part of the material that is fairly mathematical. Everything that is in the notes is examinable, but there is material that will be covered by the exam that is not in the notes (see above). I appreciate any feedback on the course in general as well as on the material handed out. For this purpose please email me at A.Schalk at cs.manchester.ac.uk.

Please do not print the notes as they appear here. You will get
copies in the first week of term. **Also note that the rooms given
in the notes are incorrect!** The ones
given above, and on the official timetable, are the ones you should
adhere to.

gzipped postscript, postscript, pdf version.

Here is a timetable regarding the set material for each week. It is important to work through the material in the week given in order not to fall behind. Bear in mind that there are no labs associated with this course. In the second year, students learn a lot during the labs - in the third year, they need to have more initiative!

Week Theme Pages |
1 Games 1-15 |
2 Strategies 13-22 |
3 Equilibria 23-33 |
4 Non 0-sum 34-42 |
5 Mixed strats 42-48 |
6 Solving games 48-59 |

Week Theme Pages |
7 Game models 60--75 |
8 Evolution I 76--88 |
9 Evolution II 88--97 |
10 Medium game 98--110 |
11 Large games 111--130 |
12 Catch-up |

To give you a chance to test your understanding I have produced some tests. We may make use of these in the question sessions - I'm not sure about that yet.

postscript Test 1 Test 2 Test 3 Test 4 |
pdf Test 1 Test 2 Test 3 Test 4 |

There is no book which will cover the entire course, which is somewhat innovative in its conception. There are references at the end of each section of the lecture notes.

**Question 1.** As in previous years, this consists of me
giving you a description of a zero-sum game and asking you to draw
the game tree, determine all strategies for both players, give the
matrix for the game and determine its equilibrium points. This is a
good question if you have practiced the techniques required, and
usually very popular.

**Question 2.** As in previous years, this consists of asking
you to solve (find equilibrium points for) various games given in
normal form. This is another good question if you have practiced the
techniques required, and has always been the most popular
question.

**Question 3.** This is the wild card question. I feel free to
do anything I like with that one. It's not for the faint of heart,
and you should only tackle it if you're sure you can solve it.

**Question 4.** This covers the material on game-playing
programs, and how they work.

**Question 5.** This covers the material on game models and
evolutionary game theory

Note that the course was taught as CS3192 and CS3191 in the past. The University has decided only to provide access to exam papers from the past three years. There used to be a legacy server that provided papers from pre-2005/6, but this has now been taken out of commission. Here are direct links to my papers from 2005/2006, 2006/2007, and 2007/2008.

The material for this course has been **slightly reduced** over
time. So if you find part of an exam question which uses concepts
that have not been covered **just ignore it**.

Lecturers are now asked to give feedback on exam performance. This allows students to find out what happened in previous exams. This is my 2002/2003 feedback, my 2003/2004 feedback, my 2004/2005 feedback, my 2005/2006 feedback, my 2006/2007 feedback, and my 2007/2008 feedback.

The electronic slides I have used in lectures in the past are available here. The pdf version is the one I used in the lectures, containing all the step-by-step overlays. The ps versions are printer-friendly: They produce all the overlays for a slide on a page, cutting down the number of pages that have to be printed. I'm not sure how useful these would be without lectures.

If you use `lpr -o number-up=2' or `lpr -o number-up=4 -o number-up-layout=btlr' on departmental machines under Linux then you can print them 2 or 4 slides on a page. No printed copy of the slides will be handed out.

pdf version Introduction Small games Medium games Large games Game models Games and evolution |
gzipped postscript Introduction Small games Medium games Large games Game models Games and evolution |
postscript Introduction Small games Medium games Large games Game models Games and evolution |

There are also slides I used to explain the unassessed exercises.

Covering Exercises 1-5 Exercises 6-11 Exercises 12-17 Exercises 20-24 |
pdf Slides First Collection Second Collection Third Collection Fourth Collection |
gzipped ps Slides First Collection Second Collection Third Collection Fourth Collection |
ps Slides First Collection Second Collection Third Collection Fourth Collection |

Official Syllabus for COMP30191, Theory of Games and Game Models.

A *game* is given by a set of *rules* describing the
allowed actions by one or more players in a given position. In
particular such rules fix whose turn it is at any given moment, and
what moves they may choose to play. Typically games can be described
using a so-called *game tree*. Here a node is a given position,
and it is precisely one player who is allowed to make any move in that
position (there are ways of getting around games where players make
their moves at the same time, such as Scissors, Stone, Paper). For
each alternative such move, there is a branch leading to a new
position. The game is over when nobody can move. Often the
*outcome* of a game is given by describing some kind of pay-off
that takes place as the game ends, that is at the leaves of the
tree.

How we tackle a game is largely dependent on its *size*.

At first sight, this has nothing to do with how games are played -
indeed, it seems to be a rather boring game where our only move
consists in choosing a strategy, and then have somebody calculate what
final result that gets us! However, this is the method traditionally
used for `solving games', that is, for finding optimal strategies for
all players. However, this way of proceeding is viable only for games
so small that for the most part, they are not interesting to
play. (Games following this pattern which are played `in the real
world' often consist of one move per player only, such as the above
mentioned Scissors, Stone, Paper, or games where each player chooses a
number, and the pay-off is then determined by some relation between
the two numbers.) However, such games turn out to be very useful in
modelling certain decision processes, which is why their analysis is
of interest. And such games can become even more interesting when one
models a situation by *assuming that a great number of such simple
games are played in some environment*--this is how, for example, -->
--the stock market can be modelled.

**Medium games** are ones which are too large to be submitted to
the above treatment, but which we can still hope to explore fully
with the use of a computer program. What is of interest here is an
intelligent choice of exploring the game tree to find the best move
in a given situation, without having to store the entire game tree at
any given time. The methods used here are popular as *search
techniques* in Artificial Intelligence.

**Large games** are those which do not yield to the methods
typically employed for medium games. Examples of these are games such
as Chess and Go. Here finding the best move in a given position by
exploring the game tree is hopeless because we can never hope to do so
fully. In this course we will look at the principles underlying all
competitive game-playing programs for games such as Chess or
Checkers.

**Game models** have done a lot to increase the interest in games
since there are now useful applications in a number of fields. We will
look at some of these, in particular in the social sciences and in
biology. As part of that we will look at what happens if the same game
is *repeated*, which typically makes even small games much more
interesting. Modelling social interaction, or the evolution of certain
behaviours depends on the idea that the issue in question is something
that occurs many times, so there are consequences beyond a single game
from the choices that were made in playing it. We will look at ways of
drawing lessons from this taken from *evolutionary game
theory*.

Games are categorized according to a number of criteria, but we will not have the time to cover all of the options listed here.

**Full information.** Games of full information are those where at
each stage, both sides know precisely what the state of the game is,
there are no hidden components. Examples for this are games such as
Chess, Go, Noughts and Crosses, Checkers. Many games played for
entertainment do have a component of information that is hidden from
all but one player (typically card players only know the cards they
hold themselves). We will look at both versions.

**Chance.** Many games, typically those played with card or dice,
contain *elements of chance*. The rolling of the dice, or the dealing
of the cards are chance experiments. We will consider such games, but
on a level where we don't require more knowledge regarding
combinatorics than the level that is taught at A-level maths, or the
maths courses you have taken in your first year.

**Cooperation.** The usual assumption when considering games is
that each player is trying to play for him- or herself, for example
maximizing the number of points to be gained. In real life, people
often form coalitions to improve what the can get out of a given
situation. Again, allowing for this makes an analysis much more
complicated. We will *not* consider games where the players are
allowed to cooperate.

**Skill.** There is no good way, really, of handling games of skill
such as darts, or most of computer games of the 'shoot 'em up'
type. That requires some way of modelling players' skills, and that
turns out to be difficult in itself. We will therefore *not*
treat these games at all.

22 September 2008