Fairness in Multiterminal Data Compression: Decomposition of Shapley Value

Abstract

We consider the problem of how to attain fairness in the multiterminal data compression problem by a game-theoretic approach and present a decomposition method for obtaining the Shapley value, a fair source coding rate vector in the Slepian-Wolf achievable region. We model a discrete memoryless multiple random source (DMMS) by a coalitional game where the entropy function quantifies the cost incurred by the source coding rates in each coalition. In the typical case for which the game is decomposable, we show that the Shapley value can be obtained separately for each subgame. The complexity of this decomposition method is determined by the maximum size of subgames, which is strictly smaller than the total number of terminals in the DMMS and contributes to a considerable reduction in computational complexity. An experimental result demonstrates large complexity reduction when the number of terminals in the DMMS becomes large.