nucleolusvalue {TUGLab}R Documentation

Nucleolus

Description

Given a game, this function computes its nucleolus.

Usage

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

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).

Value

The nucleolus of the game, as a vector.

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

[Package TUGLab version 0.0.1 Index]