Representation of finite games as network congestion games
- PDF / 243,898 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 65 Downloads / 233 Views
Representation of finite games as network congestion games Igal Milchtaich
Accepted: 5 December 2012 © Springer-Verlag Berlin Heidelberg 2012
Abstract Weighted network congestion games are a natural model for interactions involving finitely many non-identical users of network resources, such as road segments or communication links. However, in spite of their special form, these games are not fundamentally special: every finite game can be represented as a weighted network congestion game. The same is true for the class of (unweighted) network congestion games with player-specific costs, in which the players differ in their cost functions rather than their weights. The intersection of the two classes consists of the unweighted network congestion games. These games are special: a finite game can be represented in this form if and only if it is an exact potential game. Keywords Network games · Congestion games · Potential games · Game isomorphism JEL classification
C72
1 Introduction In a (finite) congestion game, finitely many players share a finite set E of resources but may differ in which resources they are allowed to use. Specifically, each player’s set of strategies is a particular collection of nonempty subsets of E. The player’s payoff from using a strategy is the negative of the total cost of using the resources included in the strategy. The cost of a resource depends only on its identity and on the number of users. The cost does not necessarily increase with congestion, and it may be negative,
I. Milchtaich (B) Department of Economics, Bar-Ilan University, 52900 Ramat Gan, Israel e-mail: [email protected] http://faculty.biu.ac.il/∼milchti
123
I. Milchtaich
in which case using the resource contributes positively to the payoff. Rosenthal (1973) showed that every congestion game admits an exact potential, which is a function P on strategy profiles that exactly reflects the players’ incentives to unilaterally change their strategies. Whenever a single player moves to a different strategy, his gain or loss is equal to the corresponding change in P. Monderer and Shapley (1996) proved the converse: essentially, only congestion games are exact potential games. More precisely, every finite game that admits an exact potential can be represented as (in other words, it is isomorphic to) a congestion game. One of this paper’s findings strengths Monderer and Shapley’s (1996) result by showing that an exact potential game can always be represented as a particular kind of congestion game, namely, an unweighted network congestion game. A restriction or expansion of the meaning of ‘congestion game’ potentially has the same effect on the class of representable games. Examples of restriction are: congestion games with nondecreasing cost functions, in which increasing congestion never makes users better off; singleton congestion games, in which each strategy includes a single resource; and network congestion games, in which resources are represented by edges in a graph and strategies correspond to routes, which
Data Loading...
