Good General Strategy For Solving For The Core In A Coalitional Game?

Question

Does anyone have a good general approach to solving for the core of a coalitional game (or finding that there is no core)?

Answer 1

There may be approaches for specific instances of cooperative games. In general, it is unlikely that there is a good and easy approach for computing the core. Deciding whether the core is non-empty is $\textsf{NP}$-complete.

See for instance:

• http://www.cs.cmu.edu/~sandholm/core_complexity.ijcai03.pdf
• https://www.cs.cmu.edu/~sandholm/computing_shapley.aaai04.pdf
• https://www.mimuw.edu.pl/~oski/atgk/slides/ATGK_6_Representations.pdf

The Nucleolus may be of interest. The key idea is that the Nucleolus allocates resources in a way that minimizes the unhappines of each coalition. The Nucleolus is unique and polynomial-time computable. If the core is non-empty, then the Nucleolus belongs to the core.

There are other solution concepts in cooperative games, such as the Shapley Value, the Kernel, and Bargaining Sets. See for instance (http://lcm.csa.iisc.ernet.in/gametheory/ln/web-cp6-othertopics.pdf).

Note that the Shapley Value (which is the most common solution concept to discuss in Game Theory courses) is $\textsf{NP}$-hard to compute in general, as well as $\textsf{#P}$-hard for many classes of games (https://arxiv.org/ftp/arxiv/papers/1402/1402.0567.pdf).

Answer 2

As it was correctly mentioned in the previous answer, the task to check whether the core of a game is non-empty is NP-complete, which is much easier to accomplish than the computation of the core itself. However, to directly check that the core is non-empty is still NP-hard, it requires in general to solve a LP.

It was also emphasized in the previous answer to focus on indirect strategies to infer that the core is empty or not. This is certainly the better way, but I cannot recommend the proposed strategies in that answer. To focus on other solution concepts may be much more harder than solving the non-emptiness issue directly. For instance, finding the nucleolus is in general much harder than to determine that the core is empty or not, since one has to solve iteratively a sequence of LPs. Thereafter, one has to check that the array of excesses is on each coordinate negative to conclude that the nucleolus is inside of the core or not. In negation of the latter case, this allows us to conclude that the core does not exist. Contrasted to the Shapley value, which may not belong to the core even if the core exists. Hence, the Shapley value is not suitable as an indirect device to infer on the non-emptiness of the core. The bargaining set is the hardest problem to solve of the listed problems, and gives also no indication about the existence of the core, since it may exist even if the core is empty. To compute an element of the Kernel is from the listed problems the easiest solution to determine. However, similar to the nucleolus, one has to determine the excess array to infer that it is a core element.

I recommend to referring to some game properties like convexity, average-convexity, or on the veto rich player property as an indirect device to conclude on the existence of the core. This is much easier to accomplish and more save. Though this approach does not cover all possible cases. Thus, sometimes one is forced to use the direct method.