0. Introduction

In this module we willl develop a mathematical theory of games. The name might suggest games that we play as a child, from the simple such as rock, paper, scissors, to the complex such as chess or bridge.

However, we will apply the term far more widely to more general situations where a group of agents may compete (or collaborate).

These might be companies who wish to maximise their profit, countries who wish to extend their sphere of influence, species of animals competing over a common resource, or simply people in a situation where they can compete or cooperate to try to satisfy their requirements.

Thus we can regard Game Theory as an attempt to provide a logical analysis of situations of conflict and cooperation.

This is an incredibly general claim, and to be able to make some progress we will restrict ourselves to certain more specific situations.

We will define a game to be any situation where

  • There are two or more players.
  • Each player has a number of possible strategies which they can choose between.
  • The combination of the choice of each player’s strategy determines the outcome of the game.
  • To each outcome of the game there is an associated payoff for each player. These are numerical values representing the value of the outcome to each player.

We will also assume that our players are rational: given a choice of actions which determine various outcomes of the game, we assume that each player will pick the action which maximises their payoff.

What makes playing games complicated is that the various players are each trying to choose their own strategy, but have no control over the choices of the other players.

Thus they are trying to maximise their own outcome while knowing that the other players are also trying to do the same. We will see that this can be very hard to analyse.

There are several obstacles to applying Game Theory in the real world.

First, people are not always rational!

Second, real life is very complicated, and hard to model, and many of the relationships between different actions are unknown. So we will have to restrict ourselves to rather simple scenarios.

And third, even in these supposedly simple cases we will see that there may not be a single best choice of strategy.

We begin with some rather simple examples of games which we will analyse later.

In the Prisoner’s Dilemma two criminals are caught by the police. Each is questioned separately, and asked to confess.

If neither man does then they will both be charged with a lesser crime and go to prison for 1 year. If one confesses and the other does not then the confessor will be allowed to go free as his evidence will convict the other prisoner for 10 years.

But if both prisoners confess then they will each be convicted for 5 years (as they have admitted their crime).

In Matching Pennies, a two-outcome version of Rock, Paper, Scissors, each player simultaneously and independently chooses “heads” or “tails”.

If their choices agree then player 1 gives player 2 a penny, and if they differ then player 2 gives player 1 a penny.

In the Game of Chicken two drivers are accelerating towards each other.

If neither swerves then both will be killed, but if one swerves before the other then they will be deemed to be a coward, and the other to be brave. If both swerve then they will both be as before.

This module will be delivered using a combination of lectures, exercise classes, and online material.

There will be more background discussion than in some of your other mathematics modules, particularly in the early stages, and so you will not be expected to take complete notes of the material on the slides (which will be available online).

However, when we consider calculations we will do these live by hand, and you should expect to take notes during those sections. There will also be videos of the live calculations online.

If you would like to consult a textbook, various possibilities are listed in the Reading List on Moodle. These should all be available from the library. However, there is no single book that matches the whole of the module.

The module is assessed by a combination of final exam in the summer and coursework. Your coursework mark will be made up of 2 online tests.

To pass the module overall you must achieve an average of at least 40% on the module. You do not need to pass the coursework and exam separately.

1. Representing a game

We will need a way to convert our given situation into a mathematical formalism. There are two basic approaches that we will consider: the extensive form and the normal form.

In the extensive form we represent a game by a directed graph in the form of a (rooted) tree. This means that we represent the game by a series of nodes and arrows between them.

We will have an initial node representing the start of the game, and terminal nodes representing the various outcomes.

Nodes that are not terminal are called decision nodes, as they represent places where the players have to make a decision, given that the game is in a particular state. The arrows will represent possible actions by one of the players at each stage.

During a game there may be a point at which one of the players does not know exactly which state the game is currently in.

Thus she will have the same set of possible decisions to make at each of these states, and this situation is represented by linking the corresponding nodes into a single information set. This will be represented by dotted lines connecting the nodes in our tree.

If each information set has only one node we say that the game has perfect information (as each player will always know exactly where they are in the tree).

We will represent the value of a given outcome of a game by the payoff that it gives to each player. This will be a number, where the larger the number the more desirable the outcome is.

We will often list payoffs as a vector — for example if there are two players then we may represent their payoffs for a given outcome by the pair \((x,y)\) where \(x\) represents the payoff to player 1 and \(y\) the payoff to player 2.

Example 1.0

To illustrate this we will consider the following example of a real-life scenario, taken from Strategy: An Introduction to Game Theory by Joel Watson.

In autumn 1998 moviegoers had a generous selection of animated feature films from which to choose. Curiously, two of the films were about bugs: Disney’s A Bug’s Life and DreamWorks’ Antz.

Around 1994 Pixar Animation pitched A Bug’s Life to Disney and the film went into production.

At about the same time DreamWorks SKG was formed, a new studio with great expectations. Shortly thereafter, Dreamworks teamed with computer animation firm PDI to produce Antz.

The two studios may have learned about each other’s choices only after they had already made their own decisions.

Disney chose to release A Bug’s Life in the 1998 Thanksgiving season, when Dreamworks’ Prince of Egypt was originally scheduled to open in theatres.

In response, Dreamworks decided to delay the release of Prince of Egypt until the Christmas season and rushed to complete Antz so that it could open before A Bug’s Life and claim the title of “first animated bug movie”.

Example completed by hand in the lecture

For some games there may be an infinite number of possible decisions that can be made at a single node.

As we cannot draw a separate arrow for each possible action, we will represent this by two arrows (indicating the maximum and minimum actions) connected by an arc.

Example 1.1

Suppose that player 1 wishes to sell a painting, which is worth nothing to her. Player 2 values the painting as worth £100. Player 2 will make a single bid, which player 1 will either accept or reject.

Example completed by hand in the lecture