Congestion games are a class of games in
game theory first proposed by American economist
Robert W. Rosenthal in 1973. In a congestion game the
payoff of each player depends on the resources it chooses and the number of players choosing the same resource. Congestion games are a special case of
potential game
In game theory, a game is said to be a potential game if the incentive of all players to change their strategy can be expressed using a single global function called the potential function. The concept originated in a 1996 paper by Dov Monderer and ...
s. Rosenthal proved that any congestion game is a potential game and Monderer and Shapley (1996) proved the converse: for any potential game, there is a congestion game with the same potential function.
Motivation
Consider a traffic net where two players originate at point
and need to get to point
. Suppose that node
is connected to node
via connection points
and
, where
is a little closer than
(i.e.
is more likely to be chosen by each player). However, both connection points get easily congested, meaning the more players pass through a point the greater the delay of each player becomes, so having both players go through the same connection point causes extra delay. Good outcome in this game will be for the two players to "coordinate" and pass through different connection points.
Can such outcome be achieved? And if so, what will the cost be for each player?
Definition
Discrete congestion games are games with the following components.
* A base set of congestible elements
;
*
players;
* A finite set of strategies
for each player, where each strategy
is a subset of
;
* For each element
and a vector of strategies
, a load
;
* For each element
, a delay function
;
* Given a strategy
, player
experiences delay
. Assume that each
is positive and monotone increasing.
Example
Consider the following directed graph where each player has two available strategies – going through
or going through
– leading to a total of four possibilities. The following matrix expresses the costs of the players in terms of delays depending on their choices:
Both (A,B) and (B,A) are pure
Nash equilibria
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
in this game, since any uni-lateral change by one of the players increases the cost of this player (note that the values in the table are costs, so players prefer them to be smaller).
Existence of Nash equilibria
The existence of
Nash equilibria
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
can be shown by constructing a ''potential function'' that assigns a value to each outcome.
Moreover, this construction will also show that iterated
best response
In game theory, the best response is the strategy (or strategies) which produces the most favorable outcome for a player, taking other players' strategies as given (; ). The concept of a best response is central to John Nash's best-known contribu ...
finds a Nash equilibrium.
Define
. Note that this function is ''not'' the social welfare
, but rather a discrete integral of sorts. The critical property of a potential function for a congestion
game is that if one player switches strategy, the change in his delay is equal to the change in the potential function.
Consider the case when player
switches from
to
. Elements that are in both of the strategies
remain unaffected, elements that the player leaves (i.e.
) decrease the potential by
, and the elements the player joins
(i.e.
) increase the potential by
. This change in potential is precisely the change in delay for player
,
so
is in fact a potential function.
Now observe that any minimum of
is a pure Nash equilibrium. Fixing all but one player, any improvement in strategy by that player corresponds to
decreasing
, which cannot happen at a minimum. Now since there are a finite number of configurations and each
is monotone, there exists
an equilibrium.
Continuous congestion games
Continuous congestion games are the limiting case as
. In this setup, we consider players as "infinitesimally small." We keep
a ''finite'' set of congestible elements. Instead of recognizing
players, as in the discrete case, we have
''types'' of players,
where each type
is associated with a number
, representing the ''rate'' of traffic for that type. Each type picks a strategy from
a strategy set
, which we assume are disjoint. As before, assume that the
are monotone and positive, but add the assumption that they are
continuous as well.
Finally, we allow players in a type to distribute fractionally over their strategy set. That is, for
, let
denote the fraction
of players in type
using strategy
. Assume that
.
Existence of equilibria in the continuous case
Note that strategies are now collections of strategy profiles
.
For a strategy set
of size
, the collection
of all valid profiles is a
compact subset
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i. ...
of
. As before, define the potential function as
, replacing
the discrete integral with the standard one.
As a function of the strategy,
is continuous:
is continuous, and
is a continuous function of the strategy. Then by the
extreme value theorem
In calculus, the extreme value theorem states that if a real-valued function f is continuous on the closed interval ,b/math>, then f must attain a maximum and a minimum, each at least once. That is, there exist numbers c and d in ,b/math> su ...
,
attains its global minimum.
The final step is to show that a minimum of
is indeed
a Nash equilibrium. Assume for contradiction that there exists a collection
of
that minimize
but are not a Nash equilibrium.
Then for some type
, there exists some improvement
over
the current choice
. That is,
.
The idea now is to take a small amount
of players using strategy
and move them to strategy
. Now for any
, we
have increased its load by
, so its term in
is now
.
Differentiating the integral, this change is approximately
, with error
.
The equivalent analysis of the change holds when we look at edges in
.
Therefore, the change in potential is approximately
, which is
less than zero. This is a contradiction, as then
was not minimized. Therefore, a minimum of
must be a Nash equilibrium.
Quality of solutions and Price of anarchy
Since there exist Nash equilibria in continuous congestion games, the next natural
topic is to analyze their quality. We will derive bounds on the ratio between
the delay at Nash and the optimal delay, otherwise known as the
Price of Anarchy The Price of Anarchy (PoA) is a concept in economics and game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. It is a general notion that can be extended to diverse systems and notions of effici ...
. First, we begin with a technical condition on the delay functions.
Definition The delay is
smooth if for all
,
.
Now if the delay is
smooth,
is a Nash equilibrium, and
is an optimal allocation, then
. In other words, the price of anarchy is
.
See thes
lecture notesfor a proof.
See also
*
Potential game
In game theory, a game is said to be a potential game if the incentive of all players to change their strategy can be expressed using a single global function called the potential function. The concept originated in a 1996 paper by Dov Monderer and ...
References
*
*Lecture notes of
Michal Feldman and Noam Nisan abou
Potential and congestion games*.
External links
* Lecture notes of Yishay Mansour abou
Potential and congestion games* ּResource allocation games
[{{Cite journal, doi= 10.1007/BF01128293, title= Resource allocation games, journal= Computational Mathematics and Modeling, volume= 1, issue= 4, pages= 433, year= 1990, last1= Kukushkin, first1= N. S., last2= Men'Shikov, first2= I. S., last3= Men'Shikova, first3= O. R., last4= Morozov, first4= V. V.] are somewhat related to congestion games.
Game theory game classes