Core, Least core and nucleolus

Question

I am trying to understand these concepts of game theory. I have the following example :-

Example

1. I understand that this example does not have a core. This can be seen from fact that the Grand coalition has v(S) = 1, whereas the sets {1,2} and {2,3} also have v(S) = 1, meaning that they are better off forming groups of two to get a better cut than a group of {1, 2, 3}.

2. The least core is basically a set of payoff vectors for all the non-empty ϵ-cores. If we solve the inequality x(S) >= v(S) - ϵ, we get the ϵ value for the given payoff vector. In the example, we take:- 3/4 >= 1 - x and solve for x (we choose 3/4 as the coalition {1,2} has the lowest excess value). So for various ϵ values, you can have different x(s) vectors and hence different payoff vectors, which will all be inside the least core as long as the above inequality is satisfied.

3. There is a unique nucleolus, which is basically an efficient payoff vector which maximizes the largest excess vector lexicographically.

Sorry for the long question. What I want to know is that:-

• Is my understanding of 1) and 2) correct?
• How do we find the nucleolus from the example given?

EDIT

I had some follow up questions.

1. So for all instances where core exists, the least core would simply be a part of it?
2. In the example, the ϵ core was 0 as the core already existed. In instances where the core does not exist, what would the nucleus be? For instance, consider the simple game where N = {1,2,3} and v(S) = 1 only when |S| > 1 and v(S) = 0 for others. In this instance, the core does not exist and I calculated the value of ϵ to be 1/3 and the payoff vector (1/3, 1/3, 1/3) satisfies this ϵ value. In this instance, would the nucleolus also be (1/3, 1/3, 1/3)?

Answer 1

1.) This is not correct. The example game is a gloves game, which has a veto-player, namely player one. A game with a veto-player has a core. The problem with your approach is that you just focus on the coalitional values, but you have also to take into account the imputation satisfying the system of inequalities $x(S) \ge v(S)$ for all $S \subseteq N$. There is only one imputation satisfying this system of inequalities, which is $(1,0,0)$.

2.) You are right that the least core is the intersection of all non-empty strong $\epsilon$-cores. Thus, it is the smallest non-empty strong $\epsilon$-core, that can be determined by $\epsilon_{0}(v):=\min_{x \in I(v)} \max_{S \neq \emptyset, N} (v(S)-x(S))$, whereas $I(v)$ is the imputation set. In the example above, we have $\epsilon_{0}(v)=0$, thus, the least-core coincides with the core, and is formed by a single point.

3.) For each game, the nucleolus is contained in the least-core, this implies for the example that the nucleolus must be equal to $(1,0,0)$.

Answer 2

I shall give you a new answer, since I suppose your edit requires a separate post.

In both cases, you are right. However, to compute the nucleolus under 2.) of your edit, it is sufficient to get the least-core at $\epsilon_{0}(v)=1/3$, since it consists of a single point.

Thus, the issue is more complex, if the least-core consists of infinite many points. For more complex games, the common method is to solve a sequence of LPs in order to find the nucleolus of a game. Fortunately, the nucleolus is part of the kernel, and if the kernel is single-valued, it is given by the nucleolus. This means, that for those classes of games, the nucleolus can be determined by methods that are designed to determine a kernel element, which are much easier to handle than solving sequences of LPs. Hence, you can apply the approach that was described in the following post

Finding the Nucleolus

to get the nucleolus for these classes of games. I suppose that this shall give you some insight where are the pitfalls in finding the nucleolus.