Attaining Fairness in Communication for Omniscience †

This paper studies how to attain fairness in communication for omniscience that models the multi-terminal compress sensing problem and the coded cooperative data exchange problem where a set of users exchange their observations of a discrete multiple random source to attain omniscience—the state that all users recover the entire source. The optimal rate region containing all source coding rate vectors that achieve omniscience with the minimum sum rate is shown to coincide with the core (the solution set) of a coalitional game. Two game-theoretic fairness solutions are studied: the Shapley value and the egalitarian solution. It is shown that the Shapley value assigns each user the source coding rate measured by their remaining information of the multiple source given the common randomness that is shared by all users, while the egalitarian solution simply distributes the rates as evenly as possible in the core. To avoid the exponentially growing complexity of obtaining the Shapley value, a polynomial-time approximation method is proposed which utilizes the fact that the Shapley value is the mean value over all extreme points in the core. In addition, a steepest descent algorithm is proposed that converges in polynomial time on the fractional egalitarian solution in the core, which can be implemented by network coding schemes. Finally, it is shown that the game can be decomposed into subgames so that both the Shapley value and the egalitarian solution can be obtained within each subgame in a distributed manner with reduced complexity.