Abstract | ||
---|---|---|
We consider a special case of weighted congestion games with playerspecific latency functions where each player uses for each particular resource a fixed (non-decreasing) delay function together with a player-specific constant. For each particular resource, the resource-specific delay function and the playerspecific constant (for that resource) are composed by means of a group operation (such as addition or multiplication) into a player-specific latency function. We assume that the underlying group is a totally ordered abelian group. In this way, we obtain the class of weighted congestion games with player-specific constants; we observe that this class is contained in the new intuitive class of dominance weighted congestion games. We obtain the following results: Games on parallel links: - Every unweighted congestion game has a generalized ordinal potential. - There is a weighted congestion game with 3 players on 3 parallel links that does not have the Finite Best-Improvement Property. - There is a particular best-improvement cycle for general weighted congestion games with player-specific latency functions and 3 players whose outlaw implies the existence of a pure Nash equilibrium. This cycle is indeed outlawed for dominance weighted congestion games with 3 players - and hence for weighted congestion games with player-specific constants and 3 players. Network congestion games: For unweighted symmetric network congestion games with player-specific additive constants, it is PLS-complete to find a pure Nash equilibrium. Arbitrary (non-network) congestion games: Every weighted congestion game with linear delay functions and player-specific additive constants has a weighted potential. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-74456-6_56 | MFCS |
Keywords | Field | DocType |
network congestion game,player-specific latency function,congestion game,dominance weighted congestion game,player-specific constant,weighted congestion game,unweighted symmetric network congestion,player-specific additive constant,unweighted congestion game,general weighted congestion game,nash equilibrium,network congestion,nash equilibria,total order,computational complexity,abelian group | Abelian group,Discrete mathematics,Combinatorics,Congestion game,Mathematical optimization,Computer science,Ordinal number,Best response,Multiplication,Network congestion,Nash equilibrium,Special case | Conference |
Volume | ISSN | ISBN |
4708 | 0302-9743 | 3-540-74455-X |
Citations | PageRank | References |
34 | 1.45 | 11 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marios Mavronicolas | 1 | 1010 | 115.73 |
Igal Milchtaich | 2 | 228 | 40.35 |
Burkhard Monien | 3 | 2199 | 279.35 |
Karsten Tiemann | 4 | 110 | 7.71 |