Name
Abstract | ||
|---|---|---|
We devise the first polynomial time algorithm computing a pure Nash equilibrium for atomic splittable congestion games with singleton strategies and player-specific affine cost functions. Our algorithm is purely combinatorial and computes the exact equilibrium assuming rational input. The idea is to compute a pure Nash equilibrium for an associated integrally-splittable singleton congestion game in which the players can only split their demands in integral multiples of a common packet size. While integral games have been considered in the literature before, no polynomial time algorithm computing an equilibrium was known. Also for this class, we devise the first polynomial time algorithm and use it as a building block for our main algorithm. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-59250-3_36 | INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2017 |
Field | DocType | Volume |
Affine transformation,Mathematical optimization,Congestion game,Computer science,Network packet,Singleton,Nash equilibrium,Time complexity,Computation | Conference | 10328 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
17 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tobias Harks | 1 | 0 | 2.37 |
| Veerle Timmermans | 2 | 0 | 1.01 |