$\newcommand{\lyxlock}{}$

Warning: MathJax requires JavaScript to correctly process the mathematics on this page. Please enable JavaScript on your browser.

Prev Section: OK, I have a beautiful game now, so what? Up Main page Section: What about sequential games? Next

Solution concepts

In non-cooperative games, the individual rationality principle (IRP) is the sole guide of of players’ decision making. Consequently, each player tries to determine the best actions for herself by comparing her payoffs between different outcomes

BUT

The final outcome will also depend on the decisions of other players. This is where the interactive dimension comes to complicate the decision process.

In general, each player needs to form expectations about the potential decisions of other player(s), in order to make her decisions.

Hence the need for strategic thinking.

This is in general different from a pure optimization-based decision problems!

A first concept of solution

In some games, it can happen that a player always gets less with strategy

than a strategy

, whatever the strategies chosen by other players.

When

is available, she would never choose

without even caring about what other players could decide

We say in this case that the strategy

is dominated by the strategy

for this player

The domination is strict if the first inequality is strict: player

losses if she chooses the strategy

over

, whatever may be the decisions of other players.

We can expect that a rational player would never choose

instead of

and hence, we can eliminate

from the game. We can do this sequentially for all players, and if we are very lucky, only one outcome may end up by surviving.

We can expect in this case that our players would necessarily choose the strategies corresponding to this outcome.

This would give us the outcome we can expect for this game (only if we are very lucky!)

Another example: Bonnie & Clyde

Bonnie and Clyde are two bandits who really existed in the South of the USA (Texas, Iowa, Oklahoma), going from town to town and robbing banks between 1930 and 1934. They are killed by the Police at Louisiana, in 1934.

The historical Bonnie & Clyde

Bonnie & Clyde in Arthur Penn’s 1967 movie (Faye Dunnaway & Warren Beaty)

After a robbery, they get arrested at the vicinity of the town,
but after having already hidden the money, and without any incriminating proof
Sheriff Clint puts them in two separated cells to interrogate them separately
Each can either
[D]eny to have anything to do with the robbery or
[C]onfess and bring the proof of culpability of the other person

And, they may get what they deserve...

If both deny, the judge has no real proof of culpability and they are condemned to a light sentence (1 year)
If both confess, their crime is established and they are condemned to a heavy sentence (8 years)
If only one confess, the sheriff assures that
the confessing person will be released (0 year)
while the denounced one will get the heaviest sentence as the sole perpetrator (10 years)

What should each do under these conditions?

Lets put their problem in a normal form. Their payoff will simply be: the negative of the number of years in jail in different outcomes, their objective being to minimize the number of years of course.

		Clyde

Bonnie

A priori, the sentence for Bonnie depends on what Clyde would do
but
We observe for Bonnie that and
and Bonnie prefers to Confess whatever the choice of of Clyde
The strategy D is strictly dominated by the strategy C
In fact, this is also true for Clyde

		Clyde

Bonnie

The only outcome we can expect in this situation is: (C,C)

Both confess and bring the proof of culpability of the other and get a heavy sentence, while by denying they could get away with only one year of jail.

A paradox of the individual rationality principle, but a very robust outcome in this particular situation.

In fact we don’t need much strategic reasoning in such a situation, but such situations are rare!

(You are invited to check such strategies in the Lockdown game above)

We need a more general concept of solution.

Nash equilibrium

In his Ph.D. thesis [Nash, 1950], John Nash proposes a general concept of solution for non-cooperative games.

The idea is looking for a situation similar to a physical “equilibrium” in the game:

An outcome

such that, if attained, it would persist because no player would like to change her strategy anymore.

No player could get a better payoff by changing strategy from the equilibrium outcome:

We call such an outcome as

a Nash equilibrium

How to determine Nash equilibria in a game?

A first approach: Brute force algorithm by elimination:

Consider each potential outcome and check if at least one player want to move from this outcome (deviate from the outcome)
If yes, this outcome cannot be a Nash equilibrium and must be eliminated
Any outcome that survives to this selection, if any, is a Nash equilibrium.

This approach may quickly become quite cumbersome for complex games with many potential outcomes.

A more direct and constructive method

Nash equilibrium: An outcome in which each player

is already playing her best strategy given the strategies played by the others.

She is already playing her best reply,

, to the strategies of the others. For

and

We can hence determine

, and the intersection between them, if it exists, must be a Nash equilibrium

Consequently, a Nash equilibrium is a fixed point in the strategy space, and its existence conditions are given by fixed point theorems.

Reconsidering the Lockdown game


		S

Has the lockdown game a Nash equilibrium?

We can determine the best replies and check if they have an intersection. We represent these best replies using simple symbols:

for my best replies and

for the policeman’s.

No possible intersection between our best replies. Hence, no possible compatibility between the motivations of these players.

No Nash equilibrium in this game

This is an important shortcoming of this concept solution: In many games a Nash equilibrium in action–based strategies like here does not exist

And Bonnie & Clyde?

We proceed in the same manner, by analyzing their best replies.

Best replies of Bonnie

Best replies of Clyde

		C

B

		C

B

is at the intersection between these best replies
is the only Nash equilibrium of this game

Even if collectively the best outcome would be

, Bonnie and Clyde end up in the worst collective outcome, because of their individual incentives.

This is what makes this game a canonical game representing many social and economic interaction situations:

Public spending policy choices between countries;
Inflation strategy of a central bank facing households
Firms trying to form a cartel...

The coordination assumed by the Nash equilibrium does not drive the decisions towards the socially most efficient solution.

This is another property of the Nash equilibrium concept:

A Nash equilibrium outcome is not necessarily socially optimal

We have already seen that a NE does not necessarily exist in all games.

When it exists, Nash equilibria very commonly are not unique but, if there are two (or more) Nash equilibria, how to know on which one the agents would coordinate? Hence many supplementary equilibrium concepts in order to reduce this multiplicity by eliminating some of these equilibria by imposing more and more stringent conditions on the rationality of the agents.

Last but not least: Even if it exists and it is unique, the equilibrium concept itself does not say anything on how the agents may (or may not) coordinate on the corresponding outcome.

This equilibrium concept is not limited to simultaneous games.

Prev Section: OK, I have a beautiful game now, so what? Up Main page Section: What about sequential games? Next

Sommaire
(c) Murat Yildizoglu, 2021-