Congestion Games with Player-Specific Payoff Functions
Igal Milchtaich, Department of Mathematics, The Hebrew University of Jerusalem, 1993
Presentation By: Eran Werner
Computational Issues in Game Theory Seminar (2002/3)
Congestion Games with Player Specific Payoff Functions
The paper describes a set of noncooperative games where players share a common set of strategies.
The payoff a player receives for playing a particular strategy depends only on the number of players playing the same strategy.
The payoff decreases as more players play the same strategy, but in a manner which is specific to every player.
Such games have realizations in economics, traffic flow, and ecology.
Result – Existence of Equilibrium
It is shown that each game in this class possesses at least one Nash equilibrium in pure strategies.
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.
Is called the congestion vector
corresponding to .
The Symmetric Case
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.
Contradicting the assumption that
Games without the Finite Improvement Property
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
IBRP with Nash Equilibrium
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.
Proof omitted, we will see a more interesting result, using the same Lemma.
Convergence to an Equilibrium
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
