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.

Speakers

• Luigi Palopolia, Università della Calabria, Rende, Italy

Curious about our other news? Subscribe to our news feed, calendar, or newsletter, or follow us on social media.

Note: This is one of the thousands of items we imported from the old website. We’re in the process of reviewing each and every one, but if you notice something strange about this particular one, please let us know. — Thanks!