A game-theoretic analysis of inter-session network coding

Mohsenian-Rad AH, Huang J, Wong VW, Jaggi S, Schober R (2009)

Publication Type: Conference contribution

Publication year: 2009

Journal

Conference Record - International Conference on Communications Institute of Electrical and Electronics Engineers

Conference Proceedings Title: IEEE International Conference on Communications

Event location: Dresden DE

ISBN: 9781424434350

DOI: 10.1109/ICC.2009.5198609

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 intersession 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. ©2009 IEEE.

Authors with CRIS profile

Robert Schober

Involved external institutions

University of British Columbia CA Canada (CA) The Chinese University of Hong Kong (CUHK) CN China (CN)

How to cite

APA:

Mohsenian-Rad, A.H., Huang, J., Wong, V.W., Jaggi, S., & Schober, R. (2009). A game-theoretic analysis of inter-session network coding. In IEEE International Conference on Communications. Dresden, DE.

MLA:

Mohsenian-Rad, A. Hamed, et al. "A game-theoretic analysis of inter-session network coding." Proceedings of the 2009 IEEE International Conference on Communications, ICC 2009, Dresden 2009.

BibTeX: Download