Name
Abstract | ||
|---|---|---|
We consider the atomic version of congestion games with affine cost functions, and analyze the quality of worst case Nash equilibria when the strategy spaces of the players are the set of bases of a k-uniform matroid. In this setting, for some parameter k, each player is to choose k out of a finite set of resources, and the cost of a player for choosing a resource depends affine linearly on the number of players choosing the same resource. Earlier work shows that the price of anarchy for this class of games is larger than 1.34 but at most 2.15. We determine a tight bound on the asymptotic price of anarchy equal to (approx )1.35188. Here, asymptotic refers to the fact that the bound holds for all instances with sufficiently many players. In particular, the asymptotic price of anarchy is bounded away from 4 / 3. Our analysis also yields an upper bound on the price of anarchy u003c1.4131, for all instances. |
Year | Venue | Field |
|---|---|---|
2017 | WAOA | Matroid,Affine transformation,Combinatorics,Finite set,Computer science,Upper and lower bounds,Price of anarchy,Nash equilibrium,Uniform matroid,Bounded function |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jasper de Jong | 1 | 12 | 3.10 |
| Walter Kern | 2 | 6 | 2.13 |
| Berend Steenhuisen | 3 | 0 | 0.34 |
| Marc Uetz | 4 | 456 | 43.99 |