TUGLab (version 0.0.1)

nucleolusvalue: Nucleolus

Description

Given a game, this function computes its nucleolus.

Usage

nucleolusvalue(v, binary = FALSE, tol = 100 * .Machine$double.eps)

Value

The nucleolus of the game, as a vector.

Arguments

v

A characteristic function, as a vector.

binary

A logical value. By default, binary=FALSE. Should be set to TRUE if v is introduced in binary order instead of lexicographic order.

tol

A tolerance parameter, as a non-negative number.
By default, tol=100*.Machine$double.eps.

Details

Given a game \(v\in G^N\) and an allocation \(x\), the excess of coalition \(S \in 2^N\) with respect to \(x\) is defined as \(e(v,x,S)=v(S)-x(S)\), where \(x(S)=\sum_{i\in S} x_i\). By sorting the excesses of all coalitions in non-increasing order, a \(2^{|N|}\)-tuple of complaints, denoted by \(\theta(x)\), is obtained. Thus, \(\theta_{i}(x) \geqslant \theta_{j}(x)\) for all \(i,j \in \{1,2,\dots,2^{n}-1\}\) with \(i < j\).

The nucleolus can be computed through the following process. First, consider only the imputations that would minimize the first complaint, that is, find the set \(I_{1} = \{x \in I(v) : \theta_{1}(x) \leqslant \theta_{1}(y) \text{ for all } y \in I(v)\}\). Then, among those imputations, consider only those that would minimize the second complaint, that is, find the set \(I_{2} = \{x \in I_{1} : \theta_{2}(x) \leqslant \theta_{2}(y) \text{ for all } y \in I_{1}\}\). Repeat the same operation with successive complaints. Eventually, a set \(I_{2^{|N|}}\) is reached. This is the nucleolus.

If \(v\) is essential, the nucleolus exists and comprises a single imputation: the only imputation \(\eta\in I(v)\) that satisfies \(e(\eta) \le e(x)\) (lexicographically) for all \(x\in I(v)\).

If the core of \(v\) is not empty, the nucleolus belongs to it.

This function is programmed following the algorithm of Potters, J.A., et al. (1996).

References

Potters, J. A., Reijnierse, J. H., & Ansing, M. (1996). Computing the nucleolus by solving a prolonged simplex algorithm. Mathematics of Operations Research, 21(3), 757-768.

Schmeidler, D. (1969). The nucleolus of a characteristic function game. SIAM Journal on Applied Mathematics, 17(6), 1163-1170.

See Also

excesses, leastcore, nucleoluspcvalue, prenucleolusvalue

Examples

v1 <- c(0,0,3,0,3,8,6,0,6,9,15,8,16,17,20)
nucleolusvalue(v1,binary=TRUE)

v2 <- c(0,0,0.7,0,0.4925,0.68,0.83,0,0.56,0.74,0.64,0.46,0.55,0.57,0.61,0,
0.35,0.56,0.72,0.8125,0.69,0.48,0.95,0.88,0.71,0.91,0.44,0.89,0.37,0.63,1)
nucleolusvalue(v2,binary=TRUE)

# Computing the nucleolus of a random essential game:
n <- 10 # number of players in the game
v3 <- c(rep(0,n),runif(2^(n)-(n+1),min=10,max=20)) # random essential game
nucleolusvalue(v3)

# If the game is 0-monotonic, its nucleolus coincides with its prenucleolus,
# and therefore must pass the Kohlberg criterion for the prenucleolus:
v4 <- c(-2,-2,-2,7,7,7,6)
zeromonotoniccheck(v4)
kohlbergcriterion(v4,nucleolusvalue(v4))

# What if the game is a cost game?
cost.v <- c(2,2,2,3,4,4,5) # cost game
-nucleolusvalue(-cost.v) # nucleolus of the cost game