Selfish Distributed Compression Over Networks: Correlation Induces Anarchy

Aditya Ramamoorthy, Vwani P. Roychowdhury, Sudhir Kumar Singh

TL;DR

This paper investigates the inefficiency arising from selfish behavior in distributed source coding over networks, specifically when sources are correlated. The authors demonstrate that unlike the independent source case where anarchy can be avoided, source correlations can significantly increase the "Price of Anarchy" (POA), indicating a substantial performance degradation due to selfish routing.

What Problem Does This Paper Address?

The paper tackles the problem of multicasting correlated sources over a network where multiple terminals aim to reconstruct all sources. This is framed as a generalization of the classical Slepian-Wolf problem to a network setting with network coding capabilities. The core challenge lies in understanding the performance loss when the participating terminals act selfishly, optimizing their own costs (for network resources) rather than contributing to a globally optimal solution. This selfish behavior is modeled as a noncooperative game, and the inefficiency is quantified by the Price of Anarchy (POA), which measures the ratio of the worst-case selfish outcome to the socially optimal outcome. The paper specifically addresses the question of whether source correlations exacerbate this inefficiency compared to the independent source case, where it's often possible to achieve a POA of one.

Methods

The authors employ a combination of game theory and information theory to model and analyze the problem. Key techniques include:

  • Noncooperative Game Theory: The scenario is modeled as a "Distributed Compression Game" (DCG) where terminals are players, and their strategies involve choosing flow rates and source rates.
  • Nash and Wardrop Equilibria: Two solution concepts are used to characterize the outcome of the game:
  • Nash Equilibrium: A complete information concept where each player chooses their best response to others' strategies. However, the authors note this might be computationally demanding.
  • Wardrop Equilibrium (Local Nash Equilibrium): A more practical concept for scenarios with partial information and computational constraints, widely used in traffic routing. This is the primary focus for analyzing the Price of Anarchy.
  • Lagrangian Duality and KKT Conditions: These are used to characterize the socially optimal flow and rate allocation.
  • Supermodularity of Conditional Entropy: This information-theoretic property is crucial for analyzing the Slepian-Wolf region and its implications.
  • Explicit Example Construction: The paper constructs specific network scenarios and cost functions to demonstrate the theoretical results, particularly to show when POA > 1.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Correlation is the Anarchy Driver: The most significant insight is that while independent sources can often be managed to avoid anarchy (POA=1), the presence of correlations among sources can fundamentally increase the Price of Anarchy, leading to substantial performance degradation.
  • Wardrop Equilibrium as a Practical Benchmark: The paper argues for the suitability of Wardrop equilibrium as a more realistic solution concept for analyzing selfish behavior in networks, especially when computational constraints are considered.
  • Characterization of Social Optimality: The authors provide a precise characterization of the conditions for socially optimal flow and rate allocation, which is a key technical contribution.
  • Equivalence of Equilibria and Optimal Solutions: A crucial finding is the demonstration that Wardrop equilibrium solutions can be equivalent to socially optimal solutions for slightly modified cost functions, which is instrumental in quantifying the POA.

Key Results

  • POA > 1 due to Correlation: The paper provides explicit examples and theoretical arguments demonstrating that for correlated sources, the Price of Anarchy can be greater than one, even for simple network structures and cost functions. This contrasts with the independent source case where POA can often be one.
  • Near-Tight Upper Bounds on POA: The authors derive upper bounds on the POA that are shown to be nearly achievable, providing a quantitative understanding of the potential inefficiency.
  • Characterization of Optimal Flows and Rates: A set of four conditions is established that characterize optimal flow-rate solutions, which are also shown to be necessary under strict convexity.
  • Existence of Nash and Wardrop Equilibria: The paper proves the existence of both Nash and Wardrop equilibria under certain convexity assumptions.

Limitations and Future Work

  • Assumptions on Cost Functions: The analysis relies on assumptions about cost functions being convex, positive, differentiable, and monotonically increasing. The behavior with other types of cost functions might differ.
  • Network Coding Assumptions: The paper assumes the network is capable of network coding and that terminals can perform appropriate decoding.
  • Future Directions: The authors highlight several important open problems:
  • Generalizing to Polymatroids: Extending the framework to a broader class of network information flow problems beyond Slepian-Wolf polytopes.
  • Decentralized Algorithms: Designing decentralized algorithms that converge to Wardrop equilibrium in polynomial time.
  • Finer POA Analysis: Investigating how POA depends on the specific structure of the Slepian-Wolf region and correlation patterns, especially for two sources.
  • Capacity Constraints: Incorporating edge capacity constraints into the model.
  • Approximate Equilibria: Developing notions of approximate Wardrop flow-rates for scenarios where terminals have limited precision.

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. 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.
BibTeX
@article{ramamoorthy2012selfish,
  author = {Aditya Ramamoorthy and Vwani P. Roychowdhury and Sudhir Kumar Singh},
  title = {{Selfish Distributed Compression Over Networks: Correlation Induces Anarchy}},
  journal = {IEEE Trans. Information Theory},
  year = {2012},
  doi = {10.1109/tit.2012.2184660},
}
Figure