Coalitional Games, Infeasibility Certificates, and the Complexity of the Core
Zusammenfassung
Details
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 is actually harder. We shall show that this open problem is solved 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, for which a compact representation is proposed 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 Sigma^P_2 -complete.