  This paper studies how to attain fairness in communication for omniscience,
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 the 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 his/her 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 by utilizing 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 which converges in
polynomial time to the fractional egalitarian solution in the core that 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.
