Selfish Distributed Compression over Networks

Aditya Ramamoorthy, Vwani Roychowdhury, Sudhir Kumar Singh2009 · DOI

TL;DR

This paper investigates the inefficiency caused by selfish network users in distributed compression scenarios with correlated sources. It shows that source correlations can significantly increase the "price of anarchy" (POA) – the ratio of worst-case selfish behavior cost to the optimal cost – compared to independent sources, where POA can often be 1.

What Problem Does This Paper Address?

Imagine a network where multiple sources generate correlated data, and several terminals want to reconstruct all these sources. This is akin to the Slepian-Wolf problem but extended to networks with network coding. In real-world networks, individual users (terminals in this case) often act selfishly to minimize their own costs, even if it leads to a less efficient overall network. This paper tackles the question of how much performance degradation (measured by the Price of Anarchy) arises from this selfish behavior, specifically when the data sources are correlated, and how this compares to the case where sources are independent.

Methods

The authors model the problem as a noncooperative game among the terminals. They use the Wardrop equilibrium (a concept from traffic assignment and selfish routing) as their solution concept, representing a state where no terminal can unilaterally improve its cost. Key technical tools include:

  • Lagrangian duality theory: Used to analyze the optimization problem and derive optimality conditions.
  • Supermodularity of conditional entropy: A property of information theory that is crucial for characterizing the Slepian-Wolf region and its implications.
  • Karush-Kuhn-Tucker (KKT) conditions: Used to characterize the optimal flow and rate allocations.
  • Explicit example construction: Used to demonstrate scenarios where the Price of Anarchy is greater than 1.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Correlation is the culprit for anarchy: The paper's central finding is that source correlations, not just network structure or cost functions, can be a primary driver of inefficiency in selfish distributed compression.
  • Wardrop equilibrium as a practical model: The choice of Wardrop equilibrium is justified by its practicality for scenarios with potentially limited information and computational power at terminals, making it more suitable than a full Nash equilibrium.
  • Slepian-Wolf polytope generalization: The techniques are shown to be applicable beyond Slepian-Wolf problems to a broader class of network information flow problems involving contra-polymatroids.
  • Characterization of optimal solutions: The paper provides a set of four intuitive conditions that precisely characterize socially optimal flow and rate allocations, which is a significant technical contribution.

Key Results

  • The paper establishes that for certain cost-splitting mechanisms, the Price of Anarchy (POA) can be significantly greater than 1 when sources are correlated, whereas for independent sources, the POA can often be 1.
  • Explicit examples are constructed to demonstrate scenarios where POA > 1 due to source correlations.
  • Near-tight upper bounds on the POA are derived.
  • The paper provides a characterization of Wardrop flow-rates and shows their equivalence to optimal solutions under specific cost transformations, which is key to quantifying the POA.

Limitations and Future Work

  • Generalization to other network settings: The authors suggest extending the framework to other network information flow problems beyond network coding, particularly those involving contra-polymatroids.
  • Decentralized algorithms: Designing decentralized algorithms that converge to Wardrop equilibrium in polynomial time is an open problem.
  • Capacity constraints: Investigating the impact of edge capacity constraints on the problem.
  • Approximate Wardrop flow-rates: Exploring scenarios where terminals have limited precision in evaluating costs.
  • Deeper analysis of POA: Further analysis is needed to understand precisely how the structure of the Slepian-Wolf region and correlations affect the POA, especially for simpler cases like two sources.

Summary updated

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. This can be considered as the network generalization of the classical distributed source coding (Slepian-Wolf) problem. 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 solution concept that we adopt for this game is the popular local Nash equilibrium (Waldrop equilibrium) adapted for the scenario with multiple sources. 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 Waldrop 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 make several contributions. We characterize the socially optimal flow and rate allocation in terms of four intuitive conditions. This result is a key technical contribution of this paper and is of independent interest as well. Next, we show that the Waldrop 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. Finally, all the techniques and results in this paper will naturally extend to a large class of network information flow problems where the Slepian-Wolf polytope is replaced by any contra-polymatroid (or more generally polymatroid-like set), leading to a nice class of succinct multi-player games and allow the investigation of other practical and meaningful scenarios beyond network coding as well.
BibTeX
@misc{ramamoorthy2009selfish,
  author = {Aditya Ramamoorthy and Vwani Roychowdhury and Sudhir Kumar Singh},
  title = {{Selfish Distributed Compression over Networks}},
  year = {2009},
  doi = {10.1109/infcom.2009.5062277},
}
Figure