Thumbnail
Access Restriction
Open

Author Ramamoorthy, Aditya ♦ Roychowdhury, Vwani ♦ Singh, Sudhir Kumar
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Lagrangian Duality Theory ♦ Meaningful Scenario ♦ Multiple Correlated Source ♦ Possible Wardrop Equilibrium ♦ Wardrop Equilibrium ♦ Near-tight Upper Bound ♦ Selfish Behavior ♦ Cost Function ♦ Succinct Multi-player Game ♦ Optimal Flow ♦ Min-cost Multicast Problem ♦ Optimal Solution ♦ Large Class ♦ Main Result ♦ Rate Allocation ♦ Explicit Example ♦ Popular Local Nash Equilibrium ♦ Independent Interest ♦ Polymatroid-like Set ♦ Network Generalization ♦ Network Information Flow Problem ♦ Noncooperative Game ♦ Conditional Entropy ♦ Main Technique ♦ Source Correlation ♦ Intuitive Condition ♦ Multiple Source ♦ Optimum Cost ♦ Independent Source ♦ Nice Class ♦ Key Technical Contribution ♦ Different Set ♦ Network Coding ♦ Several Contribution ♦ Slepian-wolf Polytope ♦ Solution Concept
Description 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 (Wardrop 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 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 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 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. 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. 1
in Proc. 28th IEEE Int. Conf. Comput. Commun. (INFOCOM) Mini-Conf., 2009
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article