Minimizing Rosenthal Potential in Multicast Games

摘要

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 1. For a given strategy profile s and integer k ≥ 1, there is a local search algorithm which in time n~(O(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; 2. 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 3~n · |G|~(O(1)) time. In other words, finding an equilibrium with minimum potential is fixed-parameter tractable when parameterized by the number of agents.