On Nash Equilibria for Multicast Transmissions in Ad-Hoc Wireless Networks

We study a multicast game in ad-hoc wireless networks in which a source sends the same message or service to a set of receiving stations via multi-hop communications and the overall transmission cost is divided among the receivers according to given cost sharing methods. We assume that each receiver gets a certain utility from the transmission and enjoys a benefit equal to the difference between his utility and the shared cost he is asked to pay. Assuming a selfish and rational behavior, each user is willing to receive the transmission if and only if his shared cost does not exceed his utility. Moreover, given the strategies of the other users, he wants to select a strategy of minimum shared cost. A Nash equilibrium is a solution in which no user can increase his benefit by choosing to adopt a different strategy. We consider the following reasonable cost sharing methods: egalitarian, semi-egalitarian next-hop-proportional, path-proportional, egalitarian-path-proportional and Shapley value. We prove that, while the first five cost sharing methods in general do not admit a Nash equilibrium, the Shapley value yields games always converging to a Nash equilibrium. We then turn our attention to the special case in which the receivers’ set R is part of the input (that is only the stations belonging to R have a positive utility which is set equal to infinity) and show that in such a case also the egalitarian and the egalitarian-path-proportional methods yield convergent games. In such a framework, we show that the price of anarchy is unbounded for the game yielded by the egalitarian method and provide matching upper and lower bounds for the price of anarchy of the other two convergent games with respect to two different global cost functions, that is the overall cost of the power assignment, that coincides with the sum of all the shared costs, and the maximum shared cost paid by the receivers. Finally, in all cases we show that finding the best Nash equilibrium is computationally intractable, that is NP-hard.