Distributed computation of Kernel-stable coalition payoff distributions

The Kernel is a practically useful stability criteria as it always exists and is non-empty. One key problem with the Kernel, however, is the exponential cost involved in computing a payoff distribution in the Kernel. When the coalition size is bounded, there exists an algorithm that runs in polynomial time [6]. We propose a distributed algorithm to compute a Kernel-stable payoff distribution where each agent analyzes a subset of the set of all coalitions, and shares the coalitions that contribute to the payoff distribution. Even with a distributed computation, it may not be feasible to compute an exact Kernel-stable payoff distribution. We consider an approximation that studies only a subset of all coalitions. We first consider cooperative environments where agents collaborate to compute the Kernel. We also investigate non-cooperative environments where agents know about a private set of CSs and want to disclose as little private information as possible and try to maximize their payoff based on its private information. We consider how such strategic behavior impacts the equilibrium and discuss two negotiations schemes in this context.