R AA AA AA s (2, 1) s (0, 0) s (1, 2) “Obvious” idea: backward induction

(1)

Introduction to Game Theory and Applications I

Fioravante PATRONE

DIPTEM, University of Genoa

Luxembourg, June 2010

(2)

Summary

Four examples

Fundamental issues

Games in strategic form

Games in extensive form

(3)

Greatest hit among games

Example (prisoner’s dilemma):

I

∖

∖II L R

T 3 3 1 4

B 4 1 2 2

You are player “I ”. What would you choose? T or B?

(4)

The battle of the sexes

Example (battle of the sexes):

I∖

∖II L R

T 2 1 0 0

B 0 0 1 2

Mix of coordination and competition: both prefer the diagonal, but on its cells they have opposite preferences.

(5)

Matching pennies

Example (matching pennies):

I

∖

∖II L R

T −1 1 1 − 1

B 1 − 1 −1 1

I would play T if I knew that II plays R, but if I plays T it would be better for II to play L. On the other hand, if II plays L, then for I it would be better to play B...

(6)

Sequential decisions

Let’s see a game, very small: I_s

T B

@@

@@ s

II L

R AA

AA AA s

(2, 1)

s (0, 0)

s (1, 2)

“Obvious” idea: backward induction. It gives (T, L). But we shall see some problem...

(7)

Relevant characteristics

Decision makers (=players) engaged in an interactivedecision problem:

- more than one decision maker (DM) (=player). [The “easy case”, 1 DM, is left to Decision Theory (DT)]

- the result is determined by the choices made by each player - the decision makers’ preferences w.r.t. outcomes are (generally speaking) diﬀerent.

Classical assumptions about players: rationalandintelligent.

(8)

Relevant “parameters”

- in all examples, but the last one, choices are “contemporary”

- players know the relevant data of the interaction decision problem:

- - available strategies - - payoﬀs (!)

- - rationality and intelligence of each player

- each player knows that all players know what is listed above - each player knows that each player knows...

COMMON KNOWLEDGE - not available the possibility of binding agreements:

NON COOPERATIVE GAMES

(9)

Game form

A game form (in strategic form), with two players, is: (X, Y , E , h).

New aspects w.r.t. decision theory:

- two DMs (we shall call them “players”), so two sets of available alternatives (choices, but here we use the word “strategies”) - h : X × Y → E is the map that converts a couple of strategies (one for each player) into an outcome.

Easy to generalize to a ﬁnite set of players N: (N, (Xi)_{i ∈N}, E , h).

With h :∏

i ∈NXi → E .

(10)

Preferences of the players

To get a game we need a second ingredient, the preferences of the players.

If we have two players (called I and II ), each will have his preferences.

So: ⊒I, ⊒II.

Each one is a total preorder on E .

We shall represent them by utility functions: u and v .

We shall often make the assumption that these utility functions are vNM.

(11)

Game in strategic form

Patching all together (game form + preferences)...

We use utility functions. In the 2 players case:

(X, Y , E , h, u, v ).

The corresponding diagram:

X × Y ^h -

E 3 u QQ

QQs v

ℝ

(12)

Game in strategic form: squeezed

Still in the 2 players case:

(X, Y , f , g ).

Where f = u ∘ h and g = v ∘ h.

The squeezed diagram:

X × Y 1 PPPPPP

PPPq f

g

ℝ

(13)

Matching pennies revisited

Let us redeﬁne the rules of the game.

- ﬁrst player I chooses, T or B - then, II chooses: L or R Is it ok? Is it the same game?

It depends.

Essential is not the chronological (physical) time, but the informationthat II has when he must decide.

So, II can see (know) the choice of I before deciding?

(14)

Matching pennies revisited

Ic

T B

@@

@@ s

L

R AA

AA AA

s L

R AA

AA AA II

s (−1, 1)

s (1, −1)

s (−1, 1)

(15)

Trees

We have introduced two important aspects:

- the dynamic structure of the interaction - the role of info on past events (on the history) To represent them it is appropriate a tree structure.

Ic

T

B

HHHH

HHHH HH

0 s

1/4 3/4

@@

@

sII

L R

@@

@@ s @

I earns 5 $ II earns 5 $

s I earns 10 $ II earns 5 $

(16)

Matches

Matches’ game Introduction to Game Theory and Applications 1

Figure 3.

c𝐼 1𝑓

@@

@ 2𝑓

𝐼𝐼_s 1𝑓

@@

@ 2𝑓

s𝐼𝐼 1𝑓

AA AA

A 2𝑓

𝐼_s

1𝑓

2𝑓 AA

AA A

s𝐼 1𝑓

𝐼_s 1𝑓

s 𝐼 wins

𝐼𝐼 _s 1𝑓

s 𝐼𝐼 wins

s 𝐼 wins

(17)

Nothing new...

Every game in extensive form can be converted into a game in strategic form, using a (natural) idea of strategy for a player.

Remark: the assumption on the intelligence of the players is essential!

So, we can say that the strategic form is, somehow, fundamental (see vN ’28). At least, for the non-cooperative case.

We can apply solution concepts for games in strategic form to games in extensive form.

It seems that everything is so easy...

(18)

Backward induction

Consider the “matches” game. We can easily “solve” it.

Look at the “penultimate” nodes. There the choice is easy, it is a single DM that has all of the power to enforce the outcome he prefers.

Having done this, look at the pre-penultimate nodes. Taking into account the choices that will be made by the player who follows, the choice for the player at the pre-penultimate node becomes obvious too.

And so on, till we reach the root of the tree.

The method we followed is called backward induction and works for games withperfect information(i.e.: information sets are all singletons).

Well, we get a strategy proﬁle that has good chances to be considered asolution! We’ll see, it is a Nash equilibrium.