Bargaining and price-of-anarchy in repeated inter-session network coding games

Mohsenian-Rad AH, Huang J, Wong VW, Schober R (2010)


Publication Type: Conference contribution

Publication year: 2010

Journal

Publisher: Institute of Electrical and Electronics Engineers Inc.

Conference Proceedings Title: Proceedings - IEEE INFOCOM

Event location: San Diego, CA US

ISBN: 9781424458363

DOI: 10.1109/INFCOM.2010.5462014

Abstract

Most of the previous work on network coding has assumed that the users are not selfish and always follow the designed coding schemes. However, recent results have shown that selfish users do not have the incentive to participate in inter-session network coding in a static non-cooperative game setting. As a result, the worst-case network efficiency (i.e., the price-of-anarchy) can be as low as 22%. In this paper, we show that if the same game is played repeatedly, then the price-of-anarchy can be significantly improved to 48%. We propose a grim-trigger strategy that encourages users to cooperate and participate in the inter-session network coding. A key challenge is to determine a common cooperative coding rate that the users should mutually agree on. We propose to resolve the conflict of interest among the users through a bargaining process. We derive a tight upper bound for the price-of-anarchy which is valid for any bargaining scheme. Moreover, we propose a simple and efficient min-max bargaining solution that can achieve this upper bound. Our results represent one of the first steps towards designing practical inter-session network coding schemes that can achieve reasonable performance for selfish users. ©2010 IEEE.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Mohsenian-Rad, A.H., Huang, J., Wong, V.W., & Schober, R. (2010). Bargaining and price-of-anarchy in repeated inter-session network coding games. In Proceedings - IEEE INFOCOM. San Diego, CA, US: Institute of Electrical and Electronics Engineers Inc..

MLA:

Mohsenian-Rad, Amir Hamed, et al. "Bargaining and price-of-anarchy in repeated inter-session network coding games." Proceedings of the IEEE INFOCOM 2010, San Diego, CA Institute of Electrical and Electronics Engineers Inc., 2010.

BibTeX: Download