Congestion game
They represent situations which commonly occur in roads, communication networks, oligopoly markets and natural habitats.
The research of congestion games was initiated by the American economist Robert W. Rosenthal in 1973.
Later research focused on questions such as: 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 two paths: O-A-T and O-B-T, where A is a little closer than B (i.e. A is more likely to be chosen by each player), as in the picture at the right.
A good outcome in this game will be for the two players to "coordinate" and pass through different connection points.
In this example, the Nash equilibrium is efficient - the players choose different lanes and the sum of costs is minimal.
The existence of a potential function has an additional implication, called the finite improvement property (FIP).
Splittable CGs were first analyzed by Ariel Orda, Raphael Rom and Nachum Shimkin in 1993, in the context of communication networks.
[7][8] They show that, for a simple network with two nodes and multiple parallel links, the Nash equilibrium is unique under reasonable convexity conditions, and has some interesting monotonicity properties.
For general network topologies, more complex conditions are required to guarantee the uniqueness of Nash equilibrium.
The following is proved: Milchtaich considered the special case of weighted CGs in which each strategy is a path in a given undirected graph ("network CG").
Concrete examples of weighted CGs without PNE are given by Libman and Orda,[11] as well as Goemans Mirrokni and Vetta.
Milchtaich[14] characterized networks that guarantee the existence of PNE, as well as the finite-improvement property, with the additional condition that a player with a lower weight has weakly more allowed strategies (formally,
Richman and Shimkin[18] characterize the networks that guarantee that every splittable CG has a unique PNE.
[23][24][25] The basic CG model can be extended by allowing the delay function of each resource to depend on the player.
For example, suppose there are three resources x,y,z and two players A and B with the following delay functions: The following is a cyclic improvement path:
Moreover, every CG is weakly acyclic: for any initial strategy-vector, at least one best-response path starting at this vector has a length of at most
However, if a crowding game is replicated m times, then the set of PNEs converges to a single point as m goes to infinity.
There are two sub-cases: When only pure-strategies are considered, these two notions are equivalent, since the logarithm of a product is a sum.
Games with separable cost functions occur in load-balancing,[30] M/M/1 queueing,[31] and habitat selection.
[33][2] Milchtaich considered the special case of CGs with player-specific costs, in which each strategy is a path in a given graph ("network CG").
[10] A complete characterization of networks that guarantee the existence of PNE in such CGs is posed as an open problem.
Fabrikant, Papadimitriou and Talwar[38] proved: Even-Dar, Kesselman and Mansour[30] analyze the number of steps required for convergence to equilibrium in a load-balancing setting.
Caragiannis, Fanelli, Gravin and Skopalik[39] present an algorithm that computes a constant-factor approximation PNE.
In particular: Their algorithm identifies a short sequence of best-response moves, that leads to an approximate equilibrium.
They also show that, for more general CGs, attaining any polynomial approximation of PNE is PLS-complete.
Fotakis, Kontogiannis and Spirakis[19] present an algorithm that, in any weighted network CG with linear delay functions, finds a PNE in pseudo-polynomial time (polynomial in the number of players n and the sum of players' weights W).
Panagopoulou and Spirakis[20] show empirical evidence that the algorithm of Fotakis, Kontogiannis and Spirakis in fact runs in time polynomial in n and log W. They also propose an initial strategy-vector that dramatically speeds this algorithm.
Milchtaich[14] proves that deciding whether a given weighted network CG has a PNE is NP-hard even in the following cases: The proof is by reduction from the directed edge-disjoint paths problem.
[40] Caragiannis, Fanelli, Gravin and Skopalik[41] present an algorithm that computes a constant-factor approximation PNE in weighted CGs.
Their algorithm identifies a short sequence of best-response moves, that leads to such an approximate PNE.
