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, |
tol |
A tolerance parameter, as a non-negative number. |
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