Title :
The price of selfishness in network coding
Author :
Marden, Jason R. ; Effros, Michelle
Author_Institution :
Social & Informational Sci. Lab., California Inst. of Technol., Pasadena, CA, USA
Abstract :
We introduce a game theoretic framework for studying a restricted form of network coding in a general wireless network. The network is fixed and known, and the system performance is measured as the number of wireless transmissions required to meet n unicast demands. Game theory is here employed as a tool for improving distributed network coding solutions. We propose a framework that allows each unicast session to independently adjust his routing decision in response to local information. Specifically, we model the interactions of the unicast sessions as a noncooperative game. This approach involves designing both local cost functions and decision rules for the unicast sessions so that the resulting collective behavior achieves a desirable system performance in a shared network environment. We propose a family of cost functions and compare the performance of the resulting distributed algorithms to the best performance that could be found and implemented using a centralized controller. We focus on the performance of stable solutions - where stability here refers to a form of Nash equilibrium defined below. Results include bounds on the bestand worst-case stable solutions as compared to the optimal centralized solution. Results in learning in games prove that the best-case stable solution can be learned by self-interested players with probability approaching 1.
Keywords :
computer networks; encoding; game theory; radiocommunication; telecommunication network routing; distributed algorithms; game theoretic framework; network coding; routing decision; unicast demands; wireless network; wireless transmissions; Centralized control; Cost function; Distributed algorithms; Game theory; Network coding; Routing; Stability; System performance; Unicast; Wireless networks;
Conference_Titel :
Network Coding, Theory, and Applications, 2009. NetCod '09. Workshop on
Conference_Location :
Lausanne
Print_ISBN :
978-1-4244-4723-7
Electronic_ISBN :
978-1-4244-4724-4
DOI :
10.1109/NETCOD.2009.5191388