Repeated Intersession Network Coding Games: Efficiency and Min-Max Bargaining Solution

Mohsenian-Rad H, Huang J, Wong VW, Schober R (2013)

Publication Language: English

Publication Type: Journal article

Publication year: 2013

Journal

IEEE-ACM Transactions on Networking Institute of Electrical and Electronics Engineers (IEEE) / Association for Computing Machinery (ACM)

Book Volume: 22

Pages Range: 1121 - 1135

Journal Issue: 4

DOI: 10.1109/TNET.2013.2271038

Abstract

Recent results have shown that selfish users do not have an incentive to participate in intersession network coding in a static noncooperative game setting. Because of this, the worst-case network efficiency (i.e., the price-of-anarchy) can be as low as 20%. In this paper, we show that if the same game is played repeatedly, then the price-of-anarchy can be improved to 36%. We design a grim-trigger strategy that encourages users to cooperate and participate in the intersession network coding. A key challenge is to determine a common cooperative coding rate that the users should mutually agree on. We resolve the conflict of interest among the users through a bargaining process and obtain tight upper bounds for the price-of-anarchy that are valid for any possible bargaining scheme. Moreover, we propose a simple and efficient min-max bargaining solution that can achieve these upper bounds, as confirmed through simulation studies. The coexistence of multiple selfish network coding sessions as well as the coexistence of selfish network coding and routing sessions are also investigated. Our results represent a first step toward designing practical intersession network coding schemes that achieve reasonable performance for selfish users.

Authors with CRIS profile

Robert Schober Lehrstuhl für Digitale Übertragung (IDC)

Involved external institutions

The Chinese University of Hong Kong (CUHK) CN China (CN) University of British Columbia CA Canada (CA) University of California, Riverside (UCR) US United States (USA) (US)

How to cite

APA:

Mohsenian-Rad, H., Huang, J., Wong, V.W., & Schober, R. (2013). Repeated Intersession Network Coding Games: Efficiency and Min-Max Bargaining Solution. IEEE-ACM Transactions on Networking, 22(4), 1121 - 1135. https://doi.org/10.1109/TNET.2013.2271038

MLA:

Mohsenian-Rad, Hamed, et al. "Repeated Intersession Network Coding Games: Efficiency and Min-Max Bargaining Solution." IEEE-ACM Transactions on Networking 22.4 (2013): 1121 - 1135.

BibTeX: Download