Skip to main content
Article
Selfish Distributed Compression Over Networks: Correlation Induces Anarchy
IEEE Transactions on Information Theory
  • Aditya Ramamoorthy, Iowa State University
  • Vwani Roychowdhury, University of California, Los Angeles
  • Sudhir Kumar Singh, University of California, Los Angeles
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
5-1-2012
DOI
10.1109/TIT.2012.2184660
Abstract

We consider the min-cost multicast problem (under network coding) with multiple correlated sources where each terminal wants to losslessly reconstruct all the sources. We study the inefficiency brought forth by the selfish behavior of the terminals in this scenario by modeling it as a noncooperative game among the terminals. The degradation in performance due to the lack of regulation is measured by the Price of Anarchy (POA), which is defined as the ratio between the cost of the worst possible Wardrop equilibrium and the socially optimum cost. Our main result is that in contrast with the case of independent sources, the presence of source correlations can significantly increase the price of anarchy. Toward establishing this result, we first characterize the socially optimal flow and rate allocation in terms of four intuitive conditions. Next, we show that the Wardrop equilibrium is a socially optimal solution for a different set of (related) cost functions. Using this, we construct explicit examples that demonstrate that the POA >; 1 and determine near-tight upper bounds on the POA as well. The main techniques in our analysis are Lagrangian duality theory and the usage of the supermodularity of conditional entropy.

Comments

This is a manuscript of an article from IEEE Transactions on Information Theory 58 (2012): 3182, doi: 10.1109/TIT.2012.2184660. Posted with permission.

Rights
Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Copyright Owner
IEEE
Language
en
File Format
application/pdf
Citation Information
Aditya Ramamoorthy, Vwani Roychowdhury and Sudhir Kumar Singh. "Selfish Distributed Compression Over Networks: Correlation Induces Anarchy" IEEE Transactions on Information Theory Vol. 58 Iss. 5 (2012) p. 3182 - 3197
Available at: http://works.bepress.com/aditya-ramamoorthy/48/