Finding the Nucleolus

Question

Given the following table of values and excesses of coalitions S and imputation $\vec{x} = (9,6,9)$:

How do I find the Nucleolus? My book wasnt clear on the method of calculating it, so Id like to find a general approach. The vector $\vec{x}$ was chosen by me from the imputation set

$\begin{align*} I = \{ (x_{1}, x_{2}, x_{3}) \in \mathbb{R}^{3} \; | & \; x_{1} \geq 2, x_{2} \geq 5, x_{3} \geq 4 \\ & \; x_{1} + x_{2} + x_{3} = 24 \} \end{align*}$

as originally only the values of the coalitions were given.

Answer 1

In general, the nucleolus can be specified while applying its axiomatization, or for more complex games, while solving a sequence of linear programs. Since your game is a three person permutation game which is zero-monotonic, the kernel is a sole point, and it coincides with the nucleolus of the game. Therefore, we can use the search process for finding a pre-kernel element that is described in more details by my book

http://www.springer.com/economics/game+theory/book/978-3-642-39548-2

Here, I can only sketch this approach. Notice, that this approach is applicable for the (pre-)nucleolus computation for games where the (pre-)nucleolus coincides with the (pre-)kernel. This is the case, for instance, for three person games or convex games.

To start with let us focus on the pre-selected imputation vector $\mathbf{y}=\{9,6,9\}$ to see how we can apply this approach for this specific example. From this vector $\mathbf{y}$, we get -- as you correctly calculated -- the following excess vector $exc_y=\{0,-7,-1,-5,-1,0,-6,0\}$.

In the next step, we look on the maximum surpluses for all pair of players. For any pair of players $i,j \in N, i\neq j$, the maximum surplus of player $i$ over player $j$ with respect to any pre-imputation $\mathbf{x}$ is given by the maximum excess at $\mathbf{x}$ over the set of coalitions containing player $i$ but not player $j$, thus

\begin{equation} s_{ij}(\mathbf{x},v):= \max_{S \in \mathcal{G}_{ij}} e^{v}(S,\mathbf{x}) \qquad\text{where}\; \mathcal{G}_{ij}:= \{S \;\arrowvert\; i \in S\; \text{and}\; j \notin S \}. \end{equation}

The expression $s_{ij}(\mathbf{x},v)$ describes the maximum amount at the pre-imputation $\mathbf{x}$ that player $i$ can gain without the cooperation of player $j$.

From this excess vector $exc_y$ we get now the following set of most effective coalitions for each pair of players:

\begin{equation} \mathcal{S}(\mathbf{y}) = \{\{1,3\},\{1,2\},\{2\},\{2\},\{3\},\{1,3\}\} \end{equation} whereas the order of the pairs of players in $\mathcal{S}(\mathbf{y})$ is given by $\{[1,2],[1,3],[2,3],[2,1],[3,1],[3,2]\}$

For instance, for the pair of players $[1,2]$, we find out these coalitions that support the claim of player $1$ without counting on the cooperation of player $2$, these are the coalitions $\mathcal{G}_{12} =\{\{1\},\{1,3\}\}$ having excess $\{-7,0\}$. We see here that coalition $\{1,3\}$ has maximum surplus. If this set is not unique, we determine the coalitions that have smallest cardinality, and from this set the coalition that has lexicographical minimum. To observe this, let us assume that $n=4$, then the set of coalitions supporting player $1$ without counting on the cooperation of player $2$ is $\mathcal{G}_{12}=\{\{1\},\{1,3\},\{1,4\},\{1,3,4\}\}$. Moreover, let us assume that the coalitions $\{\{1,3\},\{1,4\},\{1,3,4\}\}$ have maximum surpluses, then the smallest cardinality is $2$ and we single out the coalitions $\{\{1,3\},\{1,4\}$, and taking finally the lexicographical minimum, which is $\{1,3\}$.

For the reverse pair $[2,1]$ we find out that the singleton coalition $\{2\}$ supports best the claim of player $2$ without taking into account the cooperation of player $1$. Then we derive a matrix $\mathbf{E}$ by $\mathbf{E}_{ij}=\mathbf{1}_{S_{ij}} - \mathbf{1}_{S_{ji}}$ for each $i,j \in N, i < j$, and $\mathbf{E}_{0}=\mathbf{1}_{N}$. Notice that $\mathbf{1}_{S}:N \mapsto \{0,1\}$ is the characteristic vector given by $\mathbf{1}_{S}(k):=1$ if $k \in S$, otherwise $\mathbf{1}_{S}(k):=0$. Then Matrix $\mathbf{E}$ is defined by

\begin{equation} \mathbf{E} := [\mathbf{E}_{1,2}, \ldots ,\mathbf{E}_{n-1,n},\mathbf{E}_{0}] \in \mathbb{R}^{^{n \times q}}. \end{equation}

We realize that vector $\mathbf{E}_{1,2}$ is given by $\{0,1,0\}-\{1,0,1\}=\{-1,1,-1\}$ and $\mathbf{E}_{0}=\{1,1,1\}$. Proceeding in an analogous way for the remaining pair of players $[1,3]$ and $[2,3]$, matrix $\mathbf{E}$ is quantified by

\begin{equation} \mathbf{E}= \begin{bmatrix} -1 & -1 & 1 & 1 \\ 1 & -1 & -1 & 1 \\ -1 & 1 & 1 & 1 \end{bmatrix}. \end{equation}

A column vector $\mathbf{a}$ can be obtained by $\mathbf{E} \; \vec{\alpha} \in \mathbb{R}^{n}$ whereas the vector $\vec{\alpha}$ is given by $\alpha_{ij} := (v(S_{ij}) - v(S_{ji})) \in \mathbb{R} $ for all $i,j \in N, i < j $, and $\alpha_{0} := v(N)$. Therefore, vector $\vec{\alpha}$ is given by $\{-13,-10,13,24\}$.

From this matrix we construct matrix $\mathbf{Q}$ by $\mathbf{E} \; \mathbf{E}^{\top}$, inserting the numeric values, matrix $\mathbf{Q}$ is specified by

\begin{equation} \mathbf{Q}= \begin{bmatrix} 4 & 0 & 2 \\ 0 & 4 & -2 \\ 2 & -2 & 4 \end{bmatrix}. \end{equation}

The column vector $\mathbf{a}$ is given by $\mathbf{a}=\{60,8,40\}$.

Solving this system of linear equations $\mathbf{Q}\;\mathbf{x} + \mathbf{a} = \mathbf{0}$, or alternatively $\mathbf{E}^{\top}\;\mathbf{x} + \vec{\alpha} = \mathbf{0}$, we get the nucleolus for this game, which is $\nu(v)=\{23/2,11/2,7\}$. The corresponding excess vector is given through $$excv=\{0,-19/2,-1/2,-3,-3,-1/2,-7/2,0\}.$$

You can check out that the maximum surpluses are balanced, or that $\theta(\nu(v))$ is lexicographically smaller than $\theta(\mathbf{y})$. The vectors $\theta(\mathbf{y})$ and $\theta(\nu(v))$ are the so-called complaint or dissatisfaction vectors. See a textbook for the exact definition. Notice, that in this specific case, we needed only one iteration step. For more complex games, the search process stops after at most $\binom{n}{2}-1$ iteration steps. According to the empirical evidence the search process is generically terminated for less than $n+1$ iteration steps.

UPDATE 28.05.2018

Based on the discussion conducted with Aleksas Domarkas below, I decided to provide a computer based approach to determine and to verify the nucleolus of the following game

$w=[0,0,0,0,17/25,6/25,3/4,13/50,51/100,7/100,103/100,153/100,51/50,3/4,189/100]]$

that was borrowed from the documentation of the gt2.mac package written by Aleksas Domarkas. The computations were accomplished by the Matlab toolbox MatTuGames that can be found from the URL

Matlab Toolbox

To start with, we need to rearrange the order of coalitions from a lexicographical order to its unique integers. This is simply done by

v=gameToMatlab(w)

v =

     0         0    0.6800         0    0.2400    0.2600    1.0300         0    0.7500    0.5100    1.5300    0.0700    1.0200    0.7500    1.8900

We check first some game properties. Convexity is denied through

convex_gameQ(v)

ans =

logical

0

However, we observe that the game fulfills a weak convexity condition, namely average-convexity by

average_convexQ(v)

ans =

logical

1

Hence, the nucleolus is identical to the pre-nucleolus. We compute then the pre-nucleolus by

pn_v=PreNucl(v)

pn_v =

0.7533    0.4833    0.1800    0.4733

rats(pn_v)

ans =

'    113/150        29/60          9/50         71/150   '

Due to floating point arithmetic's it is always a good idea to impose some cross-checks on a computed solution. To check that this is indeed the pre-nucleolus, we have to impose one of Kohlberg's criteria on the computed solution

balancedCollectionQ(v,pn_v)

ans =

logical

1

And indeed, from the returned result we observe that a Kohlberg criterion is satisfied. This gives us some evidence that the solution is correct. In order to investigate this issue further, we have to recall that the pre-nucleolus can be characterized by the following axiomatization: SIVA, ETP, COV, and RGP (cf. B. Peleg and P. Sudhoelter (2007)).

In the sequel, we just rely on COV and RGP. We start with the latter property. The reduced game property is simply checked by

[RGP RGPC]=Reduced_game_propertyQ(v,pn_v,'PRN')

RGP =

struct with fields:

rgpQ: 1
rgpq: [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]

RGPC =

1x4 cell array

{'vS'}    {2x14 cell}    {'impVec'}    {1x15 cell}

By the first field structure RGP.rgpQ, we can retrieve the information that RGP is met. Now let us turn to covariance under strategic equivalence (COV). Again, we get a confirmation while executing

COV=COV_propertyQ(v,pn_v)

COV =

struct with fields:

  covQ: 1
sol_v2: [1.7533 1.4833 1.1800 1.4733]
   sgm: [1.7533 1.4833 1.1800 1.4733]
    v2: [1 1 2.6800 1 2.2400 2.2600 4.0300 1 2.7500 2.5100 4.5300 2.0700 4.0200 3.7500 5.8900]
     x: [0.7533 0.4833 0.1800 0.4733]

Finally, let us consider the following payoff

x=[387/500 247/500 9/50 221/500]

x =

0.7740    0.4940    0.1800    0.4420

that was classified by an older version of the gt.mac package written by Aleksas Domarkas as the nucleolus of the game. We apply the same procedure to see if we can discard this vector as the nucleolus of the game. Again we check if this payoff will also fulfill one of Kohlberg's criteria, RGP and COV. By the next computation, we realize that the implemented criterion of Kohlberg is not met.

balancedCollectionQ(v,x)

ans =

logical

0

Similar, for RGP

RGP_x=Reduced_game_propertyQ(v,x,'PRN')

RGP_x =

struct with fields:

rgpQ: 0
rgpq: [1 1 0 1 1 1 0 1 0 0 0 1 0 0 0]

and finally for COV by

COV_x=COV_propertyQ(v,x)

COV_x =

struct with fields:

  covQ: 0
sol_v2: [1.7533 1.4833 1.1800 1.4733]
   sgm: [1.7740 1.4940 1.1800 1.4420]
    v2: [1 1 2.6800 1 2.2400 2.2600 4.0300 1 2.7500 2.5100 4.5300 2.0700 4.0200 3.7500 5.8900]
     x: [0.7740 0.4940 0.1800 0.4420]

By these computations, we infer that the payoff $pn_{v}$ is the pre-nucleolus of the game.