en>Chongkian at 17:19, 25 December 2013

2013-12-25T17:19:10Z

New page

Congestion games are a class of games in [[game theory]] first proposed by [[Robert W. Rosenthal|Rosenthal]] in 1973. In a '''Congestion game''' we define players and resources, where 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]]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 ''O'' and need to get to point ''T''. Suppose that node ''O'' is connected to node ''T'' via connection points ''A'' and ''B'', where ''A'' is a little closer than ''B'' (i.e. ''A'' 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 <math>E</math>;
* <math>n</math> players;
* A finite set of strategies <math>S_i</math> for each player, where each strategy <math>P \in S_i</math> is a subset of <math>E</math>;
* For each element <math>e</math> and a vector of strategies <math>(P_1, P_2, \ldots, P_n)</math>, a load <math>x_e = \#\{ i : e \in P_i \}</math>;
* For each element <math>e</math>, a delay function <math>d_e : \mathbb{N} \longrightarrow \mathbb{R}</math>;
* Given a strategy <math>P_i</math>, player <math>i</math> experiences delay <math>\textstyle \sum_{e \in P_i} d_e(x_e)</math>. Assume that each <math>d_e</math> is positive and monotone increasing.

==Example==
Let's consider the following directed graph where each player has two available strategies - going though A or going through B - leading to a total of four possibilities. The following matrix expresses the costs of the players in terms of delays depending on their choices:
[[File:Congestion-diagram.svg|thumb|right|300px|The directed graph for a simple congestion game.]]
{| class="wikitable" style="text-align:center; width:150px; height:150px" border="1"
|+Cost Matrix
|-
! p1/p2 !! A !! B
|-
! A
| (5,5) || (2,3)
|-
! B
| (3,2) || (6,6)
|}
Both (A,B) and (B,A) are pure [[Nash equilibria]] in this game.

==Existence of Nash equilibria==
The existence of [[Nash equilibria]] 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]] finds a Nash equilibrium.
Define <math>\textstyle\Phi = \sum_{e \in E} \sum_{k=1}^{x_e} d_e(k)</math>. Note that this function is ''not'' the social welfare
<math>\textstyle\sum_{e \in E} x_e d_e(x_e)</math>, 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 <math>i</math> switches from <math>P_i</math> to <math>Q_i</math>. Elements that are in both of the strategies
remain unaffected, elements that the player leaves (i.e. <math>e \in P_i - Q_i</math>) decrease the potential by <math>d_e (x_e)</math>, and the elements the player joins
(i.e. <math>e \in Q_i - P_i</math>) increase the potential by <math>d_e(x_e+1)</math>. This change in potential is precisely the change in delay for player <math>i</math>,
so <math>\Phi</math> is in fact a potential function.

Now observe that any minimum of <math>\Phi</math> is a pure Nash equilibrium. Fixing all but one player, any improvement in strategy by that player corresponds to
decreasing <math>\Phi</math>, which cannot happen at a minimum. Now since there are a finite number of configurations and each <math>d_e</math> is monotone, there exists
an equilibrium.

==Continuous congestion games==
Continuous congestion games are the limiting case as <math>n \rightarrow \infty</math>. In this setup, we consider players as "infinitesimally small." We keep
<math>E</math> a ''finite'' set of congestible elements. Instead of recognizing <math>n</math> players, as in the discrete case, we have <math>n</math> ''types'' of players,
where each type <math>i</math> is associated with a number <math>r_i</math>, representing the ''rate'' of traffic for that type. Each type picks a strategy from
a strategy set <math>S_i</math>, which we assume are disjoint. As before, assume that the <math>d_e</math> are monotone and positive, but add the assumption that they are [[Continuous function|continuous]] as well.
Finally, we allow players in a type to distribute fractionally over their strategy set. That is, for <math>P \in S_i</math>, let <math>f_P</math> denote the fraction
of players in type <math>i</math> using strategy <math>P</math>. Assume that <math>\textstyle \sum_{P\in S_i} f_P = r_i</math>.

==Existence of equilibria in the continuous case==
Note that strategies are now collections of strategy profiles <math>f_P</math>.
For a strategy set <math>S_i</math> of size <math>n</math>, the collection
of all valid profiles is a [[Compact space|compact subset]] of <math>[0,r_i]^n</math>. As before, define the potential function as
<math>\textstyle \Phi = \sum_{e\in E} \int_0^{x_e} d_e(z) \, dz</math>, replacing
the discrete integral with the standard one.

As a function of the strategy,
<math>\Phi</math> is continuous: <math>d_e</math> is continuous, and
<math>x_e</math> is a continuous function of the strategy. Then by the
[[extreme value theorem]], <math>\Phi</math> attains its global minimum.

The final step is to show that a minimum of <math>\Phi</math> is indeed
a Nash equilibrium. Assume for contradiction that there exists a collection
of <math>f_P</math> that minimize <math>\Phi</math> but are not a Nash equilibrium.
Then for some type <math>i</math>, there exists some improvement <math>Q</math> over
the current choice <math>P</math>. That is, <math>\textstyle \sum_{e \in P} d_e(x_e) > \sum_{e \in Q} d_e(x_e)</math>.
The idea now is to take a small amount <math>\delta < f_P</math> of players using strategy
<math>P</math> and move them to strategy <math>Q</math>. Now for any <math>x_e \in Q</math>, we
have increased its load by <math>\delta</math>, so its term in <math>\Phi</math> is now <math>\textstyle \int_0^{x_e+\delta} d_e(z)dz</math>.
Differentiating the integral, this change is approximately <math>\delta \cdot d_e(x_e)</math>, with error <math>\delta^2</math>.
The equivalent analysis of the change holds when we look at edges in <math>P</math>.

Therefore, the change in potential is approximately <math>\textstyle \delta (\sum_{e \in Q} d_e(x_e) - \sum_{e \in P} d_e(x_e))</math>, which is
less than zero. This is a contradiction, as then <math>\Phi</math> was not minimized. Therefore, a minimum of <math>\Phi</math> 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]]. First, we begin with a technical condition on the delay functions.

'''Definition''' The delay is <math>(\lambda, \mu)</math> smooth if for all <math>x,y > 0</math>, <math>y d(x) \leq \lambda y d(y) + \mu x d(x)</math>.

Now if the delay is <math>(\lambda, \mu)</math> smooth, <math>f</math> is a Nash equilibrium, and <math>f^*</math> is an optimal allocation, then
<math>\textstyle \sum_e x_ed_e(x_e) \leq \frac{\lambda}{1 - \mu} \sum_e x_e^* d_e(x_e^*)</math>. In other words, the price of anarchy is <math>\textstyle \frac{\lambda}{1- \mu}</math>.
See these [http://www.cs.cornell.edu/courses/cs6840/2012sp/1-30-2012.pdf lecture notes] for a proof.

==References==
*{{citation
| last1 = Vazirani | first1 = Vijay V. | author1-link = Vijay Vazirani
| last2 = Nisan | first2 = Noam | author2-link = Noam Nisan
| last3 = Roughgarden | first3 = Tim | author3-link = Tim Roughgarden
| last4 = Tardos | first4 = Éva | author4-link = Éva Tardos
| isbn = 0-521-87282-0
| location = Cambridge, UK
| pages = 28, 62, & 519
| publisher = Cambridge University Press
| title = Algorithmic Game Theory
| url = http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf
| year = 2007}}.
*Lecture notes of Michal Feldman and Noam Nisan about [http://hujieconcs.wordpress.com/lecture-notes/ Potential and congestion games]
*{{citation
| last = Rosenthal | first = Robert W.
| doi = 10.1007/BF01737559
| journal = International Journal of Game Theory
| mr = 0319584
| pages = 65–67
| title = A class of games possessing pure-strategy Nash equilibria
| volume = 2
| year = 1973}}.

==External links==
* Lecture notes of Yishay Mansour about [http://www.math.tau.ac.il/~mansour/course_games/scribe/lecture6.pdf Potential and congestion games]

[[Category:Game theory]]

Utilization factor - Revision history

en>Chongkian at 17:19, 25 December 2013