A Short Introduction to Game Theory

A Short Introduction to Game Theory

Heiko Hotz

CONTENTS

1

Contents

1 Introduction

2

1.1 Game Theory ? What is it? . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Game Theory ? Where is it applied? . . . . . . . . . . . . . . . . . . . . . . 2

2 Definitions

3

2.1 Normal Form Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 Extensive Form Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.3 Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.3.1 Best Response . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.3.2 Localizing a Nash Equilibrium in a Payoff-matrix . . . . . . . . . . . 4

2.4 Mixed Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Games

5

3.1 Prisoner's Dilemma (PD) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3.1.1 Other Interesting Two-person Games . . . . . . . . . . . . . . . . . . 6

3.2 The Ultimatum Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.3 Public Good Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.4 Rock, Paper, Scissors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4 Evolutionary Game Theory

8

4.1 Why EGT? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4.2 Evolutionary Stable Strategies . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.2.1 ESS and Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . 9

4.2.2 The Hawk-Dove Game . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.2.3 ESS of the Hawk-Dove Game . . . . . . . . . . . . . . . . . . . . . . 10

4.3 The Replicator Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4.4 ESS and Replicator Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . 11

5 Applications

12

5.1 Evolution of cooperation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

5.2 Biodiversity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

A Mathematical Derivation

14

A.1 Normal form games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

A.2 Nash equilibrium and best answer . . . . . . . . . . . . . . . . . . . . . . . 14

A.3 Evolutionary stable strategies (ESS) . . . . . . . . . . . . . . . . . . . . . . 14

A.4 Replicator equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

A.5 Evolutionary stable state of the Hawk-Dove game . . . . . . . . . . . . . . . 15

B Pogram Code

17

B.1 Spatial PD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

B.2 Hawk-Dove game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1 INTRODUCTION

1 Introduction

This paper gives a brief overview of game theory. Therefore in the first section I want to outline what game theory generally is and where it is applied.

In the next section, I introduce some of the most important terms used in game theory, such as normal form games and Nash equilibrium as well as some of the most popular games, e.g. the Prisoner's Dilemma or the Ultimatum Game.

I then present the basic concepts of evolutionary game theory (EGT), a more specialized branch of game theory. We will see how EGT uses new concepts such as evolutionary stable strategies (ESS) and replicator dynamics, and its importance to sciences like biology and physics.

At last I present two examples, programmed in the language NetLogo, which will demonstrate the applications of EGT and the similarities to condensed matter physics.

1.1 Game Theory ? What is it?

The concepts of game theory provide a common language to formulate, structure, analyse and eventually understand different strategical scenarios. Generally, game theory investigates conflict situations, the interaction between the agents and their decisions.

A game in the sense of game theory is given by a (mostly finite) number of players, who interact according to given rules. Those players might be individuals, groups, companies, associations and so on. Their interactions will have an impact on each of the players and on the whole group of players, i.e. they are interdependent.

To be more precise: A game is described by a set of players and their possibilities to play the game according to the rules, i.e. their set of strategies.

2

This description leads to a widespred definition of game theory:

The subject of game theory are situations, where the result for a player does not only depend on his own decisions, but also on the behaviour of the other players.

Game theory has its historical origin in 1928. By analysing parlour games, John von Neumann realised very quickly the practicability of his approaches for the analysis of economic problems.

In his book Theory of Games and Economic Behavior, which he wrote together with Oskar Morgenstern in 1944, he already applied his mathematical theory to economic applications.

The publication of this book is generally seen as the initial point of modern game theory.

1.2 Game Theory ? Where is it applied?

As we have seen in the previous section, game theory is a branch of mathematics. Mathematics provide a common language to describe these games. We have also seen that game theory was already applied to economics by von Neumann. When there is competition for a resource to be analysed, game theory can be used either to explain existing behaviour or to improve strategies.

The first is especially applied by sciences which analyse long-term situations, like biology or sociology. In animality, for example, one can find situations, where cooperation has developed for the sake of mutual benefits.

The latter is a crucial tool in sciences like economics. Companies use game theory to improve their strategical situation in the market.

2 DEFINITIONS

3

Despite the deep insights he gained from game theory's applications to economics, von Neumann was mostly interested in applying his methods to politics and warfare, perhaps descending from his favorite childhood game, Kriegspiel, a chess-like military simulation. He used his methods to model the Cold War interaction between the U.S. and the USSR, picturing them as two players in a zero-sum game.

He sketched out a mathematical model of the conflict from which he deduced that the Allies would win, applying some of the methods of game theory to his predictions.

There are many more applications in the sciences, which have already been mentioned, and in many more sciences like sociology, philosophy, psychology and cultural anthropology. It is not possible to list them all in this paper, more information can be obtained in the references at the end of this paper.

3. A payoff function, which assigns a certain payoff to each player depending on his strategy and the strategy of the other players (e.g. in the Prisoner's Dilemma the time each of the players has to spend in prison).

The payoff function assigns each player a certain payoff depending on his strategy and the strategy of the other players. If the number of players is limited to two and if their sets of strategies consist of only a few elements, the outcome of the payoff function can be represented in a matrix, the so-called payoff matrix, which shows the two players, their strategies and their payoffs.

Example:

Player1\Player2 L R

U

1, 3 2, 4

D

1, 0 3, 3

2 Definitions

I now introduce some of the basic definitions of game theory. I use a non-mathematical description as far as possible, since mathematics is not really required to understand the basic concepts of game theory.

However, a mathematical derivation is given in appendix A.1 and A.2.

2.1 Normal Form Games

A game in normal form consists of:

1. A finite number of players.

2. A strategy set assigned to each player. (e.g. in the Prisoner's Dilemma each player has the possibility to cooperate (C) and to defect (D). Thus his strategy set consists of the elements C and D.)

In this example, player 1 (vertical) has two different strategies: Up (U) and Down (D). Player 2 (horizontal) also has two different strategies, namely Left (L) and Right (R).

The elements of the matrix are the outcomes for the two players for playing certain strategies, i.e. supposing, player 1 chooses strategy U and player 2 chooses strategy R, the outcome is (2, 4), i.e. the payoff for player 1 is 2 and for player 2 is 4.

2.2 Extensive Form Games

Contrary to the normal form game, the rules of an extensive form game are described such that the agents of the game execute their moves consecutively.

This game is represented by a game tree, where each node represents every possible stage of the game as it is played. There is a unique node called the initial

2 DEFINITIONS

4

node that represents the start of the game. Any node that has only one edge connected to it is a terminal node and represents the end of the game (and also a strategy profile). Every non-terminal node belongs to a player in the sense that it represents a stage in the game in which it is that player's move. Every edge represents a possible action that can be taken by a player. Every terminal node has a payoff for every player associated with it. These are the payoffs for every player if the combination of actions required to reach that terminal node are actually played.

Example:

Figure 1: A game in extensive form

In figure 1 the payoff for player 1 will be 2 and for player 2 will be 1, provided that player 1 plays strategy U and player 2 plays strategy D'.

2.3 Nash Equilibrium

In game theory, the Nash equilibrium (named after John Nash, who first described it) is a kind of solution concepts of a game involving two or more players, where no player has anything to gain by changing only his own strategy.

If each player has chosen a strategy and no player can benefit by changing his strategy while the other players keep theirs unchanged, then the current set of

strategy choices and the corresponding payoffs constitute a Nash equilibrium.

John Nash showed in 1950, that every game with a finite number of players and finite number of strategies has at least one mixed strategy Nash equilibrium.

2.3.1 Best Response

The best response is the strategy (or strategies) which produces the most favorable immediate outcome for the current player, taking other players' strategies as given.

With this definition , we can now determine the Nash equilibrium in a normal form game very easily by using the payoff matrix.

The formal proof that this procedure leads to the desired result is given in appendix A.2.

2.3.2 Localizing a Nash Equilibrium in a Payoff-matrix

Let us use the payoff matrix of the Prisoner's Dilemma, which will be introduced in 3.1, to determine the Nash equilibrium:

Player1\Player2 C D

C

3, 3 0, 5

D

5, 0 1, 1

The procedure is the following: First we consider the options for player 1 by a given strategy of player 2, i.e. we look for the best answer to a given strategy of player 2.

If player 2 plays C, the payoff for player 1 for coosing C will be 3, for choosing D it will be 5, so we highlight his best answer, D:

CD C 3, 3 0, 5 D 5 , 0 1, 1

Now we repeat this procedure for the case,

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download