Selfish Distributed Compression over Networks: Correlation Induces Anarchy - Computer Science > Computer Science and Game TheoryReport as inadecuate




Selfish Distributed Compression over Networks: Correlation Induces Anarchy - Computer Science > Computer Science and Game Theory - Download this document for free, or read online. Document in PDF available to download.

Abstract: We consider the min-cost multicast problem under network coding withmultiple correlated sources where each terminal wants to losslessly reconstructall the sources. We study the inefficiency brought forth by the selfishbehavior of the terminals in this scenario by modeling it as a noncooperativegame among the terminals. The degradation in performance due to the lack ofregulation is measured by the {\it Price of Anarchy} POA, which is defined asthe ratio between the cost of the worst possible \textit{Wardrop equilibrium}and the socially optimum cost. Our main result is that in contrast with thecase of independent sources, the presence of source correlations cansignificantly increase the price of anarchy. Towards establishing this result,we first characterize the socially optimal flow and rate allocation in terms offour intuitive conditions. Next, we show that the Wardrop equilibrium is asocially 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 techniquesin our analysis are Lagrangian duality theory and the usage of thesupermodularity of conditional entropy.



Author: Aditya Ramamoorthy, Vwani Roychowdhury, Sudhir Kumar Singh

Source: https://arxiv.org/







Related documents