Selfish Distributed Compression over Networks: Correlation Induces Anarchy

Details Selfish Distributed Compression over Networks: Correlation Induces Anarchy Selfish Distributed Compression over Networks: Correlation Induces Anarchy

2008-04-11

arxiv.org/abs/0804.1840v2

Computer Science

Computer Science and Game Theory

replaced with revised version, 32 pages, 2 figures

Scientific paper

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 {\it Price of Anarchy} (POA), which is defined as the ratio between the cost of the worst possible \textit{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. Towards 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.

Affiliated with

Also associated with

No associations

Rating

Selfish Distributed Compression over Networks: Correlation Induces Anarchy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Selfish Distributed Compression over Networks: Correlation Induces Anarchy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Selfish Distributed Compression over Networks: Correlation Induces Anarchy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-705810