On a Local Heuristic for a Reverse Multicast Forwarding Game

We consider the problem of incentive compatible topology control for selfish all-to-one (reverse multicast) routing as modeled by a locally minimum cost forwarding game, with new focus in this work on efficient local implementability in the absence of complete global information for realistic scenarios. In this work we consider a new locally computable heuristic ¿recommendation algorithm¿, which we refer to as LocalHeur for convenience. LocalHeur lies within the class of location based routing methods with particular similarity to the Nearest Forward Progress algorithm though from the perspective of game-theoretic reverse multicast routing. We find that LocalHeur actually outperforms DeltaHeur in terms of global optimality in random Euclidean power instances which model wireless networks, though at the expense of loosening the Nash equilibrium condition. Nonetheless, we find that the relaxation of the Nash condition is strongly bounded in multiple ways, with high probability: The vast majority of players are provably playing a best response, while simulation results demonstrate that the average deviation ratio from a best response is within a decimal point of 1. Furthermore, the player deviating most from his best response is provably still within O(log n) of the cost of his best response, while simulation results support a much smaller maximum deviation from the best response.