Name
Abstract | ||
|---|---|---|
A multicast game is a network design game modelling how selfish non-cooperative agents build and maintain one-to-many network communication. There is a special source node and a collection of agents located at corresponding terminals. Each agent is interested in selecting a route from the special source to its terminal minimizing the cost. The mutual influence of the agents is determined by a cost sharing mechanism, which evenly splits the cost of an edge among all the agents using it for routing. The existence of a Nash equilibrium for the game was previously established by the means of Rosenthal potential. Anshelevich et al. [FOCS 2004, SICOMP 2008] introduced a measure of quality of the best Nash equilibrium, the price of stability, as the ratio of its cost to the optimum network cost. While Rosenthal potential is a reasonable measure of the quality of Nash equilibra, finding a Nash equilibrium minimizing this potential is NP-hard. In this paper we provide several algorithmic and complexity results on finding a Nash equilibrium minimizing the value of Rosenthal potential. Let n be the number of agents and G be the communication network. We show that For a given strategy profile s and integer k≥1, there is a local search algorithm which in time nO(k) ·|G|O(1) finds a better strategy profile, if there is any, in a k-exchange neighbourhood of s. In other words, the algorithm decides if Rosenthal potential can be decreased by changing strategies of at most k agents; The running time of our local search algorithm is essentially tight: unless FPT=W[1], for any function f(k), searching of the k-neighbourhood cannot be done in time f(k)·|G|O(1). The key ingredient of our algorithmic result is a subroutine that finds an equilibrium with minimum potential in 3n ·|G|O(1) time. In other words, finding an equilibrium with minimum potential is fixed-parameter tractable when parameterized by the number of agents. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s00224-014-9573-5 | international colloquium on automata languages and programming |
Keywords | DocType | Volume |
Nash Equilibrium,Local Search,Local Search Algorithm,Social Optimum,Strategy Profile | Conference | 57 |
Issue | ISSN | Citations |
1 | 1432-4350 | 0 |
PageRank | References | Authors |
0.34 | 15 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fedor V. Fomin | 1 | 3139 | 192.21 |
| Petr Golovach | 2 | 29 | 2.85 |
| Jesper Nederlof | 3 | 294 | 24.22 |
| michal pilipczuk | 4 | 403 | 51.93 |