Infeasibility Certificates and the Complexity of the Core in Coalitional Games

Francesco Scarcello, Enrico Malizia, Luigi Palopoli

This paper characterizes the complexity of the core in coalitional games. There are different proposals for representing coalitional games in a compact way, where the worths of coalitions may be computed in polynomial time. In all those frameworks, it was shown that core non-emptiness is a co-NP-hard problem. However, for the most general of them, it was left as an open problem whether it belongs to co-NP or it actually is an harder problem. We solve this open problem in a positive way; indeed, we are able to show that, for the case of transferable payoffs, the problem belongs to co-NP for any compact representation of the game where the worths of coalitions may be computed in polynomial time (also, non-deterministic polynomial time), encompassing all previous proposals of this kind. This is proved by showing that games with empty cores have small infeasibility certificates. The picture is completed by looking at coalitional games with non-transferable payoffs. We propose a compact representation based on marginal contribution nets. Also in this case, we are able to settle the precise complexity of core non-emptiness, which turns out to be Σ_2-complete.