DocumentCode :
2881269
Title :
A Game-Theoretic Analysis of Inter-Session Network Coding
Author :
Mohsenian-Rad, A. Hamed ; Huang, Jianwei ; Wong, Vincent W S ; Jaggi, Sidharth ; Schober, Robert
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of British Columbia, Vancouver, BC, Canada
fYear :
2009
fDate :
14-18 June 2009
Firstpage :
1
Lastpage :
6
Abstract :
A common assumption in the network coding literature is that the users are cooperative and will not pursue their own interests. However, this assumption can be violated in practice. In this paper, we analyze inter-session network coding in a wired network, assuming that the users are selfish and act as strategic players to maximize their own utility. We prove the existence of Nash equilibria for a wide range of utility functions. The number of Nash equilibria can be large (even infinite) under certain conditions, which is in sharp contrast to a similar game setting with traditional packet forwarding. We then characterize the worst-case efficiency bounds, i.e., the price-of-anarchy (PoA), compared to an optimal and cooperative network design. We show that by using a novel discriminatory pricing scheme that charges encoded and forwarded packets differently, we can improve PoA in comparison with the case where a single pricing scheme is being used. However, PoA is still worse than the case when network coding is not applied. This implies that inter-session network coding is more sensitive to strategic behavior. For example, for the case where only two network coding flows share a single bottleneck link, the efficiency at certain Nash equilibria can be as low as 48%. These results generalize the well-known result of guaranteed 67% efficiency bounds shown by Johari and Tsitsiklis for traditional packet forwarding networks.
Keywords :
encoding; game theory; packet radio networks; Nash equilibria; cooperative network design; discriminatory pricing scheme; game-theoretic analysis; intersession network coding; packet forwarding network; utility function; wired network; worst-case efficiency bound; Communications Society; Electronic mail; Encoding; Game theory; Nash equilibrium; Network coding; Pricing; Resource management; Routing; Wireless networks;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Communications, 2009. ICC '09. IEEE International Conference on
Conference_Location :
Dresden
ISSN :
1938-1883
Print_ISBN :
978-1-4244-3435-0
Electronic_ISBN :
1938-1883
Type :
conf
DOI :
10.1109/ICC.2009.5198609
Filename :
5198609
Link To Document :
بازگشت