Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published April 2012 | public
Journal Article

The Price of Selfishness in Network Coding

Abstract

A game-theoretic framework is introduced for studying selfish user behavior in shared wireless networks. The investigation treats an n-unicast problem in a wireless network that employs a restricted form of network coding called reverse carpooling. Unicast sessions independently choose routes through the network. The cost of a set of unicast routes is the number of wireless transmissions required to establish those connections using those routes. Game theory is employed as a tool for analyzing the impact of cost sharing mechanisms on the global system performance when each unicast independently and selfishly chooses its route to minimize its individual cost. The investigation focuses on the performance of stable solutions, where a stable solution is one in which no single unicast can improve its individual cost by changing its route. The results include bounds on the best- and worst-case stable solutions compared to the best performance that could be found and implemented using a centralized controller. The optimal cost sharing protocol is derived and the worst-case solution is bounded. That worst-case stable performance cannot be improved using cost-sharing protocols that are independent of the network structure.

Additional Information

© 2012 IEEE. Manuscript received June 29, 2009; revised February 17, 2011; accepted October 06, 2011. Date of current version March 13, 2012. This work was supported by the Social and Information Sciences Laboratory at the California Institute of Technology, DARPA ITMANET Grant W911NF-07-1-0029, and the Lee Center for Advanced Networking at the California Institute of Technology.

Additional details

Created:
August 19, 2023
Modified:
October 17, 2023