Best-reply paths, may be cyclic, but there is always at least one path that connects an arbitrary initial point to an equilibrium.

In the case were individuals possess different competitive ability (weighted games) Nash equilibrium may not exist.

Results - Convergence to Equilibrium

The players may reach an equilibrium by some sort of adaptation process. Is such a process bound to converge?

The process will always converge for 2-strategy games or when players have equal payoff functions

In the general case of unweighted congestion games counterexamples for convergence may be shown

However, if the order of deviation is stochastic, convergence is almost surely to occur.

The Model

There are n players sharing a set of r strategies. The strategy played by the player is noted .

The payoff that player i receives for playing strategy j is a monotonically non decreasing function of the number of players playing the same strategy.

The strategy-tuple is a Nash equilibrium iff each is a best-reply strategy.

A congestion game is symmetric iff all players share the same set of payoff functions. These games have exact potential functions (Rosenthal 1973).

The existence of exact potential function implies the Finite Improvement Property(FIP) a sequence in which a single deviator strictly increases the payoff he receives.

Obviously any maximal Finite Improvement Path ends with an equilibrium.

The Two-Strategy Case

Theorem 1:

Congestion games involving only two strategies possess the finite improvement property.

Proof:

Suppose on the contrary that there is an infinite improvement path then for some

WLOG

This implies that player i, the unique deviator in the first step, deviates from 1 to 2; hence

By Monotonicity

Hence player i, never deviates back to strategy 1.

The Finite improvement property is equivalent to the existence of an ordinal potential for the game.

Eg. The potential function assigning each strategy-tuple with the number of strategy-tuples which are initial points of improvement paths leading to .

If a game has no FIP thus no ordinal potential it still may have a Nash Equilibrium.

A two player congestion game with no finite improvement path

Best Reply Paths

A path in which each deviator shifts to the best reply against the strategies played by other players is called Best Reply Paths.

The Finite improvement property (FIP) implies the Finite Best Reply Property (FBRP) but not the converse.

Infinite Best Reply Improvement paths

IBRP require at least 3 players.

Assume by contrary that 2 players suffice.

When player A shifts strategy, the second player B is negatively effected only if A plays the same strategy as B (congestion).

It is this second player B which makes the next move, thus only possibly increasing the payoff of the player A (monotonicity), thus the strategy played by A remains a Best Reply strategy and Equilibrium is reached.

An infinite best-reply improvement path in a 3-player, 3-strategy unweighted congestion game

The Strategy-tuples (3,1,2) and (2,3,1) are equilibria of this game

The Existence of a Pure-Strategy Nash Equilibrium

Theorem 2:

Every (unweighted) congestion game possesses a Nash equilibrium in pure strategies:

First we proof a Lemma (two parts).

Lemma – Part 1

The first part of the Lemma is concerned with paths where each deviator moves to the next deviator’s present position

If is a sequence of strategies, is a best-reply improvement path and results from the deviation of one player from to then .

Lemma – Part 1

Proof:

Let be the congestion vector of and set .

Then holds for all j and k.

Hence by deviation to of the unique deviator in step k brings to its maximum and all other to their minimum.

By monotonicity of payoff , j(k) remains the best reply for that player in all later steps, thus each player deviates at most once and .

Lemma – Part 2

The second part of the Lemma is concerned with paths were each deviator takes the last deviator’s previous position.

If the deviation at step k is from j(k) to j(k-1) (k=1,2….M) then

Lemma – Part 2

Proof:

Here too

By deviating from j(k), the deviator at step k brings to its minimum, this implies that the payoff in is greater than when he deviated to j(k) ,if he did, or that he will get by deviating to j(k) at any later step.

Therefore a player will not return to a strategy he deviated from; each player deviates at most r-1 times.

Proof of Theorem 2

By induction on the number of players n, by reducing an n player game to an n-1 player game.

The proof of Theorem 2 is a by construction of an algorithm. Adding player by player in at most steps. But will we reach the equilibrium in the real?

Theorem 3: Given an arbitrary strategy-tuple in a congestion game , there exists a BRIP such that is an equilibrium and

An “Almost” Equilibrium

Initially . . Suppose that is a best reply for all but maybe not for

Starting from we can find a sequence

of strategies and a BRIP as in Lemma (A) such that M is maximal.

The first deviator is obviously . if then starting from we can find a sequence

and a BRIP connected to it as in Lemma (B) such that N is maximal. If then we set .

Convergence to an Equilibrium

Claim: is an equilibrium. Suppose it is not, then for some player i, is not a best reply for . Suppose the best reply is j. Then if then by construction is best reply against

Then why is j and not a best reply for

?

1.

2. Or Both 1,2

Convergence to an Equilibrium

can be true only if (construction) contradicting the maximality of .

can hold only if

which is impossible by construction (maximality of M)

Therefore must be a best reply for

Convergence to an Equilibrium

The theorem is true for one-player games. To complete the proof by induction on the number of player n, we reduce an initial n-player game to an n-1 player game by restricting the strategy played by player n.

By the induction hypothesis there exists a BRIP in , where the terminal point is an equilibrium of . Back to , is almost an equilibrium of . As shown, this can be extended to reach an equilibrium, and the extension requires at most steps.

This gives the upper bound of the length of the shortest BRIP connecting an arbitrary point to an equilibrium.

Convergence to an Equilibrium

Games in which every strategy-tuple is connected to some NE by a best reply path are called weakly acyclic (WA).

If

The number of strategies is finite

The order of deviators is chosen randomly

Deviators do not deviate simultaneously

Then for WA games a best-reply path almost surely reaches an equilibrium.

Stochastic Convergence Process

Treating the game as a stochastic process, each player not currently in the best reply strategy has a positive probability of at least of being the next deviator.

If each strategy-tuple is connected to an equilibrium by a best reply path of length at most L then the probability that at least one of the strategy tuples

given is an equilibrium is at least, for all k and all histories.

Equilibrium is not reached within the first steps with probability

Coping with lack of Information

If players occasionally make mistakes (play not the best reply strategies), then the concept of equilibrium strategy-tuple should be replaced with stationary distribution.

Mistakes can be the result of lack of information, players starts with a priori estimates of associated payoff which are later modified to a posteriori knowledge of actual gain.

Weighted Congestion Games

Up till now the players had similar influence upon the congestion. This model is generalized by introducing weights and modifying the congestion vector

Weighted Congestion Games

Weighted congestion games involving only two players, involving two strategies or when players have equal payoff functions possess the finite improvement path or (at least) the finite best reply property.

Therefore these games possess a Nash equilibrium in pure strategies, and the equilibrium can be reached by constructing a maximal best-reply improvement path

Weighted Congestion Games The General Case

Weighted congestion games may not possess a pure strategy Nash equilibrium.

Even a three-player, three-strategy weighted congestion game may not possess a pure-strategy Nash equilibrium.

A three-player, three-strategy congestion game with no pure-strategy Nash Equilibrium

A three-player, three-strategy congestion game with no pure-strategy Nash Equilibrium