Package 'TUGLab'

Description

This function checks if the given game is additive.

Usage

additivecheck(v, binary = FALSE, instance = FALSE)

Arguments

Details

A game $v\in G^N$ is additive if $v(S)=\sum_{i\in S}v(i)$ for all $S\in 2^N$.

Value

TRUE if the game defined by v is additive, FALSE otherwise. If instance=TRUE and the game is not additive, the position (binary order position if binary=TRUE; lexicographic order position otherwise) of a coalition for which additivity is violated is also returned.

See Also

additivegame, superadditivecheck

Examples

v <- c(1, 5, 40, 100, 6, 41, 101, 45, 105, 140, 46, 106, 141, 145, 146)
additivecheck(v)
additivecheck(v, binary = TRUE, instance = TRUE)

Description

Given the value of each player, this function returns the characteristic function of the associated additive game.

Usage

additivegame(a, binary = FALSE)

Arguments

Details

The characteristic function of the additive game given by $a\in \mathbb{R}^n$ is defined for each $S\in 2^N$ by $v(S)=\sum_{i\in S}a_i$.

Value

The characteristic function of the associated additive game, as a vector in binary order if binary=TRUE and in lexicographic order otherwise.

See Also

additivecheck, strategicallyequivalentcheck, superadditivecheck

Examples

a <- c(1,5,10,13,58)
additivegame(a, binary = FALSE)

Description

Given an airfield problem, this function returns the associated airfield game.

Usage

airfieldgame(c, binary = FALSE)

Arguments

Details

Let $N = \{1, \dots, n\}$ denote a set of agents, and let $c \in \mathbb{R}_+^N$ be a cost vector. Each $c_i$ represents the cost of the service required by agent $i$. Segmental costs are defined as the difference between a given cost and the first immediately lower cost: $c_i - c_{i-1}$ for $i \in N \backslash \{1\}$.

Each $c \in \mathbb{R}_+^N$ defines an airfield problem, which is associated to an airfield game $v_{a}\in G^N$, is defined by

$v_{a}(S)=\max\{c_j:j\in S\}\text{ for all }S\in 2^N.$

Airfield games, as defined, are cost games, but they can also be expressed as savings games. Additional tools and methods for addressing airfield problems are available in the AirportProblems package Bernárdez Ferradás et al. (2025).

Value

The characteristic function of the airfield game, as a vector in binary order if binary=TRUE and in lexicographic order otherwise.

References

Bernárdez Ferradás, A., Sánchez Rodríguez, E., Mirás Calvo, M., & Quinteiro Sandomingo, C. (2025). AirportProblems: Analysis of Cost Allocation for Airport Problems. R package version 0.1.0. https://CRAN.R-project.org/package=AirportProblems

Littlechild, S.C., & Owen, G. (1973). A Simple Expression for the Shapely Value in a Special Case. Management Science, 23, 370-372.

See Also

claimsgame, savingsgame

Examples

c <- c(2000,3200,4100,5100)
airfieldgame(c,binary=TRUE)

Description

This function checks if the given game is balanced and computes its balanced cover.

Usage

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

Arguments

Details

Let $v \in G^{N}$. A family $F$ of non-empty coalitions of $N$ is balanced if there exists a weight family $\delta^{F} = \{ \delta^{F}_{S} \}_{S \in F}$ such that $\delta^{F}_{S} > 0$ for each $S \in F$ and $\sum_{S \in F} \delta^{F}_{S} e^{S} = e^{N}$, being $e^{S}$ the characteristic vector of $S$, that is, the vector $(e_{i}^{S})_{i \in N}$ in which $e_{i}^{S}=1$ if $i \in S$ and $e_{i}^{S}=0$ if $i \notin S$).

The game $v$ is balanced if, for each balanced family $F$, it is true that

$\sum_{S \in F} \delta^{F}_{S} v(S) \leq v(N).$

The balanced cover of $v$ is the game $\tilde{v}$ defined by $\tilde{v}(S)=v(S)$ for all $S \neq N$ and

$\tilde{v}(N) = \max_{\delta \in P}{\sum_{S \subset N} \delta_{S} v(S)},$

being $P$ the set of the weight families associated with the balanced families of $N$.

A game is balanced if and only if it coincides with its balanced cover. By the Bondareva-Shapley Theorem, a game has a non-empty core if and only if it is balanced.

Value

TRUE if the game is balanced, FALSE otherwise. If game=TRUE, the balanced cover of the game is also returned.

References

Maschler, M., Solan, E., & Zamir, S. (2013). Game Theory. Cambridge University Press.

See Also

totallybalancedcheck

Examples

balancedcheck(c(12,10,20,20,50,70,70), game=TRUE)
balancedcheck(c(rep(0,4), rep(30,6), rep(0,4), 50))
v <- runif(2^3-1,0,10) # random three-player game
balancedcheck(v, game=TRUE)
balancedcheck(balancedcheck(v, game=TRUE)$game) # balanced cover is indeed balanced
balancedcheck(runif(2^(15)-1,min=10,max=20)) # random game

Description

This function checks if the given family is balanced.

Usage

balancedfamilycheck(Fam, n = NULL, tol = 100 * .Machine$double.eps)

Arguments

Details

A family $F$ of non-empty coalitions of a set of players $N$ is balanced if there exists a weight family $\delta^{F} = \{ \delta^{F}_{S} \}_{S \in F}$ such that $\delta^{F}_{S} > 0$ for each $S \in F$ and $\sum_{S \in F} \delta^{F}_{S} e^{S} = e^{N}$, being $e^{S}$ the characteristic vector of $S$, that is, the vector $(e_{i}^{S})_{i \in N}$ in which $e_{i}^{S}=1$ if $i \in S$ and $e_{i}^{S}=0$ if $i \notin S$).

A balanced family $F$ is said to be minimal if there does not exist a balanced family $F'$ such that $F' \subsetneq F$.

Value

This function returns three outputs: check, minimal and delta. If Fam is not a balanced family: check=FALSE and both minimal and delta are NULL. If Fam is a balanced family: check=TRUE, minimal=TRUE if Fam is minimal (minimal=FALSE otherwise), and delta returns an associated weight family.

References

Maschler, M., Solan, E., & Zamir, S. (2013). Game Theory. Cambridge University Press.

See Also

balancedcheck, kohlbergcriterion, totallybalancedcheck

Examples

balancedfamilycheck(c(3,6,13,8)) # balanced and minimal
balancedfamilycheck(c(3,5,9,4,8,14)) # balanced but not minimal
balancedfamilycheck(c(1,2,4,12,13)) # not balanced

Description

This function checks if an allocation belongs to the core of a game.

Usage

belong2corecheck(v, binary = FALSE, x, instance = FALSE)

Arguments

Details

The core of a game $v\in G^N$ is the set of all its stable imputations:

$C(v)=\{x\in\mathbb{R}^n : x(N)=v(N), x(S)\ge v(S)\ \forall S \in 2^N\},$

where $x(S)=\sum_{i\in S} x_i$.

Value

TRUE if x belongs to the core of v, FALSE otherwise. If instance=TRUE and x does not belong to the core of v, a justification is also provided: if efficiency is violated, not efficient is returned; if efficiency is not violated, the position (binary order position if binary=TRUE; lexicographic order position otherwise) of a coalition for which rationality is violated is returned.

References

Gillies, D. (1953). Some theorems on n-person games. PhD thesis, Princeton, University Press Princeton, New Jersey.

Examples

v <- c(0, 0, 0, 2, 1, 4, 6)
a <- c(3, 1, 2) # an allocation for v
b <- c(2, 2, 2) # egalitarian solution for v
belong2corecheck(v = v, binary = TRUE, x = a, instance = TRUE)
belong2corecheck(v = v, binary = FALSE, x = b, instance = TRUE)

# What if the game is a cost game?
cost.v <- c(2,2,2,3,4,4,5) # cost game
cost.x <- c(1,2,2) # core allocation of cost.v
belong2corecheck(v = -cost.v, x = -cost.x)

Description

Given a characteristic function in binary order, this function returns the characteristic function in lexicographic order.

Usage

bin2lex(v)

Arguments

Details

The binary order position of a coalition $S\in 2^N$ is given by $\sum_{i\in S} 2^{i-1}$. Lexicographic order arranges coalitions in ascending order according to size, and applies lexicographic order to break ties among coalitions of the same size.

Value

The characteristic function, as a vector in lexicographic order.

See Also

codebin2lex, codelex2bin, lex2bin

Examples

v <- seq(1:31)
bin2lex(v)
lex2bin(bin2lex(v))==v

Description

Given a claims problem, this function returns the associated pessimistic claims game.

Usage

claimsgame(E, d, binary = FALSE)

Arguments

Details

A claims problem is a triple $(N,E,d)$ where $E\ge 0$ is an amount to be distributed among a set $N$ of agents and $d\in \mathbb{R}^{|N|}$ is a vector of claims satisfying $\sum_{i=1}^{n} d_i\ge E$.

Given a claims problem $(N,E,d)$, its associated claims game, $v_{E,d}\in G^N$, is defined by

$v_{E,d}(S)=\max\{0, \; E-\sum_{i\in N\backslash S}d_i\}\text{ for all }S\in 2^N.$

For further analysis and computational methods related to conflicting claims problems, see the ClaimsProblems package Sánchez Rodríguez et al. (2025).

Value

The characteristic function of the pessimistic claims game, as a vector in binary order if binary=TRUE and in lexicographic order otherwise.

References

O’Neill, B. (1982). A problem of rights arbitration from the Talmud. Mathematical Social Sciences, 2, 345–371.

Sánchez Rodríguez, E., Núñez Lugilde, I., Mirás Calvo, M., & Quinteiro Sandomingo, C. (2025). ClaimsProblems: Analysis of Conflicting Claims. R package version 1.0.0.

https://CRAN.R-project.org/package=ClaimsProblems

See Also

airfieldgame

Examples

E <- 10
d <- c(2,4,7,8)
claimsgame(E,d)

Description

Given a game and a weight family, this function returns the coalition-weighted Shapley value.

Usage

coalitionweightedshapleyvalue(v, delta, binary = FALSE, game = FALSE)

Arguments

Details

A weight family is a collection of $2^{|N|}-1$ real numbers $\delta=\{\delta_{T}\}_{T \in 2^{N} \setminus \emptyset}$ such that $\delta_{T} \geqslant 0$ for each $T \in 2^{N} \setminus \emptyset$ and $\sum_{T \in 2^{N} \setminus \emptyset}\delta_{T}=1$. For each $v \in G^{N}$ and each $T \in 2^{N}$, the T-marginal game of $v$, denoted $v^{T} \in G^{N}$, is defined as

$v^{T}(S)=v(S \cup (N \setminus T))-v(N \setminus T)+v(S \cap (N \setminus T)), \ S \in 2^{N}.$

For each game $v \in G^{N}$ and each weight family $\delta$, the $\delta$-weighted game $v^{\delta} \in G^{N}$ is defined as

$v^{\delta} = \sum_{T \in 2^{N} \setminus \emptyset}\delta_{T}v^{T}.$

Given a game $v \in G^{N}$, its $\delta$-weighted Shapley value, $\Phi^{\delta}(v)$, is the Shapley value of the $\delta$-weighted game:

$\Phi^{\delta}(v)=Sh(v^{\delta}).$

Value

The coalition-weighted Shapley value, as a vector. If game=TRUE, the coalition-weighted game is also returned, as a vector in binary order if binary=TRUE and in lexicographic order otherwise.

References

Sánchez Rodríguez, E., Mirás Calvo, M. A., Quinteiro Sandomingo, C., & Núñez Lugilde, I. (2024). Coalition-weighted Shapley values. International Journal of Game Theory, 53, 547-577.

See Also

marginalgame, shapleyvalue, weightedshapleyvalue

Examples

v <- c(0,0,0,0,0,0,1,0,0,1,3,4,6,8,10)
delta <- c(0.3,0.1,0,0.6,0,0,0,0,0,0,0,0,0,0,0)
coalitionweightedshapleyvalue(v, delta, binary=TRUE)

v <- c(0,0,0,0,0,0,0,0,1,4,1,3,6,8,10)
delta <- c(0.25,0.25,0.25,0.25)
a <- coalitionweightedshapleyvalue(v, delta, game=TRUE)
b <- coalitionweightedshapleyvalue(a$game, delta, game=TRUE)
c <- coalitionweightedshapleyvalue(b$game, delta, game=TRUE)
plotcoresets(rbind(v, a$game, b$game, c$game), imputations=FALSE)

# Games a, b and c have the same Shapley value:
all(sapply(list(a$value, b$value, c$value, shapleyvalue(v)),
           function(x) all.equal(x, a$value) == TRUE))

Description

Given the binary order position of a coalition, this function returns the corresponding lexicographic order position.

Usage

codebin2lex(n, Nbin)

Arguments

Details

The binary order position of a coalition $S\in 2^N$ is given by $\sum_{i\in S} 2^{i-1}$. Lexicographic order arranges coalitions in ascending order according to size, and applies lexicographic order to break ties among coalitions of the same size.

Value

The corresponding lexicographic order position, as an integer between 1 and $2^{\code{n}}-1$.

See Also

bin2lex, codelex2bin, lex2bin

Examples

codebin2lex(5, 4)

Description

Given the lexicographic order position of a coalition, this function returns the corresponding binary order position.

Usage

codelex2bin(n, Nlex)

Arguments

Details

Lexicographic order arranges coalitions in ascending order according to size, and applies lexicographic order to break ties among coalitions of the same size. The binary order position of a coalition $S\in 2^N$ is given by $\sum_{i\in S} 2^{i-1}$.

Value

The corresponding binary order position, as an integer between 1 and $2^{\code{n}}-1$.

See Also

bin2lex, codebin2lex, lex2bin

Examples

codelex2bin(5, 4)

Description

This function checks if the given game is compromise-admissible.

Usage

compromiseadmissiblecheck(v, binary = FALSE, instance = FALSE)

Arguments

Details

Let $v\in G^N$. The utopia payoff of player $i\in N$ is defined as $M_i(v)=v(N)-v(N\backslash i)$. The minimal right of player $i\in N$ is defined as $m_i(v)=\max_{S:i\in S}(v(S)-\sum_{j\in S\backslash i}M_j(v))$.

The game $v\in G^N$ is said to be compromise-admissible if its core-cover is not empty, that is, if the following conditions hold:

1) $m(v)\leq M(v)$.

2) $\sum_{i\in N}m_{i}(v)\leq v(N)\leq \sum_{i\in N}M_i(v)$.

Value

TRUE if the game is compromise-admissible, FALSE otherwise. If instance=TRUE and $\{i \in N : m_i(v)>M_i(v)\} \neq \emptyset$, one of the players in that set is also returned.

Examples

compromiseadmissiblecheck(c(0,0,0,0,10,40,30,60,10,20,90,90,90,130,160))
compromiseadmissiblecheck(c(1,2,2), instance=TRUE)

# What if the game is a cost game?
cost.v <- c(30, 20, 50, 40, 60, 60, 75) # compromise-admissible cost game
compromiseadmissiblecheck(-c(30, 20, 50, 40, 60, 60, 75))

Description

This function computes the characteristic function of the specified constant sum game.

Usage

constantsumgame(halfv, vN)

Arguments

Details

A game $v\in G^N$ is a constant sum game if, for each $S \in 2^{N}$, $v(S) + v(N \setminus S) = v(N)$. Thus, if $v$ is a constant sum game and $F$ is a family of $2^{n-1}-1$ coalitions such that $S \cup T \neq N$ for any $S,T \in F$, the full characteristic function of $v$ is strictly determined by the utilities of the coalitions in $F$ and the utility of the grand coalition.

Value

The characteristic function of the constant sum game. It is to be interpreted according to the order that halfv is introduced in.

Examples

constantsumgame(c(0,0,0), 1) # the dollar game
# Building a random constant sum game:
players <- sample(3:6,1) # random number of players between three and six
halfv <- runif(2^(players-1)-1, 0, 10) # random halfv
vN <- runif(1,30,50) # random vN
constantsumgame(halfv, vN)

Description

This function checks if the given game is convex.

Usage

convexcheck(v, binary = FALSE, instance = FALSE)

Arguments

Details

A game $v\in G^N$ is convex if $v(S \cap T) + v(S \cup T) \ge v(S)+v(T)$ for all $S,T \in 2^N$. Zumsteg, S. (1995) shows that $v$ is convex if $v(S \cup {i}\cup {j}) + v(S) \ge v(S\cup {i})+v(S\cup {j})$ for all $S\in 2^N$ and $i,j\in N\backslash S$ such that $i\not=j$.

A game $v\in G^N$ is concave if $-v$ is convex.

Value

TRUE if the game is convex, FALSE otherwise. If instance=TRUE and the game is not convex, the function also returns the positions (binary order positions if binary=TRUE; lexicographic order positions otherwise) of a pair of coalitions violating the Zumsteg convexity characterization.

References

Zumsteg, S. (1995). Non-cooperative aspects of cooperative game theory and related computational problems. PhD thesis, ETH Zurich.

See Also

strategicallyequivalentcheck, superadditivecheck

Examples

v1 <- c(5, 2, 2, 1, 8, 8, 6, 4, 3, 3, 12, 10, 10, 6, 14)
convexcheck(v1)
v2 <- c(0, 0, 0, 2, 2, 1, 3)
convexcheck(v2, binary = FALSE, instance = TRUE)

# How to check if a game is concave:
v.conc <- c(4, 3, 3, 2, 6, 6, 5, 5, 4, 4, 7, 6, 6, 6, 7) # concave game
convexcheck(-v.conc)

Description

Given a game with a full-dimensional core, this function computes a hit-and-run estimation of its core center.

Usage

corecenterhitrun(v, k = 1000, getpoints = FALSE, binary = FALSE)

Arguments

Details

The core of a game $v\in G^N$ is the set of all its stable imputations:

$C(v)=\{x\in\mathbb{R}^n : x(N)=v(N), x(S)\ge v(S)\ \forall S \in 2^N\},$

where $x(S)=\sum_{i\in S} x_i$. A game is said to be balanced if its core is not empty.

The core-center of a balanced game $v$, $CC(v)$, is defined as the expectation of the uniform distribution over $C(v)$, and thus can be interpreted as the centroid or center of gravity of $C(v)$. Let $\mu$ be the $(n-1)$-dimensional Lebesgue measure and let $V(C)=\mu(C(v))$ be the volume (measure) of the core. If $V(C)>0$, then, for each $i\in N$,

$CC_i(v)=\frac{1}{V(C)}\int_{C(v)}x_i d\mu$

.

The hit-and-run method (Smith, 1984) is a Monte Carlo algorithm that generates uniformly distributed random points within a bounded and convex region, such as a polytope or a convex body in high-dimensional space.

The hit-and-run method is based on the following process. Step 0: choose a point inside the convex body. Step 1: choose a uniformly distributed random direction from the unit sphere in the given dimension. Step 2: determine the longest line segment that, starting from the chosen point and taking the chosen direction, remains entirely within the convex body. Step 3: choose a uniformly distributed along the line segment random point. Step 4: go to Step 1.

Value

A hit-and-run estimation of the core-center, as a vector; and, if getpoints=TRUE, a matrix containing the points generated by the hit-and-run method.

References

Gonzalez-Díaz, J. & Sánchez-Rodríguez, E. (2007). A natural selection from the core of a TU game: the core-center. International Journal of Game Theory, 36(1), 27-46.

Espinoza-Burgos, N. H. (2020). Comparación de métodos exactos y aproximados para calcular el core-center del juego del aeropuerto. TFM, Máster en Técnicas Estadísticas, http://eio.usc.es/pub/mte/descargas/ProyectosFinMaster/Proyecto_1791.pdf.

Smith, R. L. (1984). Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions. Operations Research, 32(6), 1296-1308.

See Also

balancedcheck, corecentervalue, coredimension, corevertices, corevertices234

Examples

v1 <- claimsgame(E=8,d=c(3,5,6))
corecenterhitrun(v1,k=1e5)

v2 <- c(0,0,0,0,0,0,0,0,1,4,1,3,6,8,10)
corecenterhitrun(v2,k=1e5)

# Plotting the corecenter and its hit-and-run estimation:
plotcoreset(v2,solutions="corecenter",allocations=corecenterhitrun(v2))

# Plotting the points generated by the hit-and-run method:
hrpoints <- corecenterhitrun(v2,k=100,getpoints=TRUE)$points
plotcoreset(v2,allocations=hrpoints)

# What if the game is not full-dimensional because of a dummy player?
v3 <- c(440,0,0,0,440,440,440,15,14,7,455,454,447,60,500)
# For coredimension to detect that, tolerance has to be appropriate:
coredimension(v3,tol=100*.Machine$double.eps) # tolerance too small
coredimension(v3) # default tolerance, 1e-12, big enough

# Now how to compute the hit-and-run estimation of the core-center?
# Knowing that player 1 is a dummy and that the core-center assigns
# dummies their individual worth...
v3.without1 <- subgame(v3,S=14) # subgame without player 1
( cc.hr <- c(v3[1],corecenterhitrun(v3.without1,k=100)) )

# Plotting the points when there is a dummy player:
points.without1 <- corecenterhitrun(v3.without1,k=100,getpoints=TRUE)$points
points.with1 <- cbind(v3[1],points.without1)
plotcoreset(v3,allocations=points.with1)

# This function does not work if the core is not full-dimensional:
v4 <- c(0,0,0,0,2,5,0,5,0,0,10,2,5,5,10)
corecenterhitrun(v4,k=1e5)

Description

Given a game, this function computes its core center.

Usage

corecentervalue(v, binary = FALSE, tol = 1e-12)

Arguments

Details

The core of a game $v\in G^N$ is the set of all its stable imputations:

$C(v)=\{x\in\mathbb{R}^n : x(N)=v(N), x(S)\ge v(S)\ \forall S \in 2^N\},$

where $x(S)=\sum_{i\in S} x_i$. A game is said to be balanced if its core is not empty.

The core-center of a balanced game $v$, $CC(v)$, is defined as the expectation of the uniform distribution over $C(v)$, and thus can be interpreted as the centroid or center of gravity of $C(v)$. Let $\mu$ be the $(n-1)$-dimensional Lebesgue measure and let $V(C)=\mu(C(v))$ be the volume (measure) of the core. If $V(C)>0$, then, for each $i\in N$,

$CC_i(v)=\frac{1}{V(C)}\int_{C(v)}x_i d\mu$

.

Value

The core-center, as a vector.

References

Gonzalez-Díaz, J. & Sánchez-Rodríguez, E. (2007). A natural selection from the core of a TU game: the core-center. International Journal of Game Theory, 36(1), 27-46.

See Also

balancedcheck, corecenterhitrun, coredimension, corevertices, corevertices234

Examples

v1 <- claimsgame(E=8,d=c(3,5,6))
corecentervalue(v1)
plotcoreset(v1,solutions="corecenter")

v2 <- c(0,0,0,0,0,0,0,0,1,4,1,3,6,8,10)
corecentervalue(v2)
plotcoreset(v2,solutions="corecenter")

# What if the game is not full-dimensional because of a dummy player?
v3 <- c(440,0,0,0,440,440,440,15,14,7,455,454,447,60,500)
dummynull(v3) # player 1 is a dummy in v3, so the core is degenerate
# For coredimension to detect that, tolerance has to be appropriate:
coredimension(v=v3,tol=100*.Machine$double.eps) # tolerance too small
coredimension(v=v3) # default tolerance, 1e-12, big enough

# Now how to compute the corecenter?
# When given a degenerate game, corecentervalue computes an approximation:
( cc.approx <- corecentervalue(v=v3) ) # approximate core-center
# However, knowing that player 1 is a dummy and that the core-center assigns
# dummies their individual worth...
v3.without1 <- subgame(v=v3,S=14) # subgame without player 1
( cc.exact <- c(v3[1],corecentervalue(v3.without1)) ) # "exact" core-center

# Plotting both results:
plotcoreset(v3,allocations=rbind(cc.approx,cc.exact),projected=TRUE)

Description

Given a game, this function computes the dimension of its core.

Usage

coredimension(v, binary = FALSE, tol = 1e-12)

Arguments

Details

The core of a game $v\in G^N$ is the set of all its stable imputations:

$C(v)=\{x\in\mathbb{R}^n : x(N)=v(N), x(S)\ge v(S)\ \forall S \in 2^N\},$

where $x(S)=\sum_{i\in S} x_i$.

Value

The dimension of the core of v, as an integer.

References

Edgeworth, F. Y. (1881). Mathematical psychics: An essay on the application of mathematics to the moral sciences. CK Paul.

Gillies, D. (1953). Some theorems on n-person games. PhD thesis, Princeton, University Press Princeton, New Jersey.

See Also

balancedcheck, corevertices, corevertices234, plotcoreset, plotcoresets

Examples

v1 <- c(rep(0,5),rep(1,4),0,rep(1,3),2,2)
plotcoreset(v1)
coredimension(v1)

v2 <- c(rep(0,5),rep(1,4),0,rep(1,4),2)
plotcoreset(v2)
coredimension(v2)

v3 <- marginalgame(c(0,0,0,0,0,0,0,0,1,4,1,3,6,8,10),1)
plotcoreset(v3)
coredimension(v3)

v4 <- c(0,0,0,0,0,0,0,0,1,4,1,3,6,8,10)
plotcoreset(v4)
coredimension(v4)

Description

Given a game, this function computes its core vertices.

Usage

corevertices(v, binary = FALSE)

Arguments

Details

The core of a game $v\in G^N$ is the set of all its stable imputations:

$C(v)=\{x\in\mathbb{R}^n : x(N)=v(N), x(S)\ge v(S)\ \forall S \in 2^N\},$

where $x(S)=\sum_{i\in S} x_i$.

Value

If the core of v is non-empty, the core vertices are returned, as a matrix in which each row is a vertex.

Note

Function corevertices234 can also compute the core vertices of games with less than five players, but takes a different approach.

References

Edgeworth, F. Y. (1881). Mathematical psychics: An essay on the application of mathematics to the moral sciences. CK Paul.

Gillies, D. (1953). Some theorems on n-person games. PhD thesis, Princeton, University Press Princeton, New Jersey.

See Also

balancedcheck, corevertices234, plotcoreset, plotcoresets

Examples

v=c(0,0,0,0,0,0,0,0,1,4,1,3,6,8,10)
corevertices(v)

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

Description

Given a game with no more than four players, this function computes its core vertices.

Usage

corevertices234(v, binary = FALSE)

Arguments

Details

The core of a game $v\in G^N$ is the set of all its stable imputations:

$C(v)=\{x\in\mathbb{R}^n : x(N)=v(N), x(S)\ge v(S)\ \forall S \in 2^N\},$

where $x(S)=\sum_{i\in S} x_i$.

Value

If the core of v is non-empty, the core vertices are returned, as a matrix in which each row is a vertex.

Note

Function corevertices can also compute the core vertices of games with less than five players, but takes a different approach.

See Also

balancedcheck, corevertices, plotcoreset,

Examples

# 2 players:
corevertices234(c(-58,4,13))

# 3 players:
corevertices234(c(1,5,10,6,11,15,16)) # additive game

# 4 players:
corevertices234(c(0,0,0,0,4,3,5,2,4,5,10,19,20,30,100)) # convex game
corevertices234(c(0,0,0,0,1,2,1,1,1,1,4,3,2,1,7)) # not convex game

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

Description

This function checks if the given game is degenerate.

Usage

degeneratecheck(v, binary = FALSE)

Arguments

Details

A game $v\in G^N$ is degenerate if $v(N)=\sum_{i \in N} v(i)$.

Value

TRUE if the game is degenerate, FALSE otherwise.

See Also

essentialcheck

Examples

v <- c(1, 5, 10, 0, 0, 0, 16)
degeneratecheck(v)
w <- c(1, 5, 10, 0, 0, 0, 15)
degeneratecheck(w)

Description

Given the characteristic function of a game, this function returns the characteristic function of the dual game.

Usage

dualgame(v)

Arguments

Details

The dual game of $v\in G^N$ is defined by $v^D(S)=v(N)-v(N\backslash S)$ for all $S \in 2^N$.

Value

The characteristic function of the dual game. It is to be interpreted according to the order that v is introduced in.

Examples

v <- c(rep(0,4),rep(5,6),rep(20,4),40)
dualgame(v)
v <- seq(1:31)
dualgame(v)
dualgame(dualgame(v)) == v

Description

Given a game, this function identifies its dummy players and null players.

Usage

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

Arguments

Details

Given a game $v\in G^N$, $i \in N$ is said to be a dummy player if $v(S) + v(\{i\}) = v(S \cup \{i\})$ for all $S \subset N \setminus \{i\}$.

A dummy player $i \in N$ is said to be a null player if $v(\{i\})=0$.

Value

Two different vectors are returned: one containing the dummy players and the other containing the null players.

Examples

v <- c(0,1,0,1,0,1,1)
dummynull(v)
# Checking if a particular player is a dummy player:
2 %in% dummynull(v)$dummy # player 2 is a dummy player in v
2 %in% dummynull(v)$null # player 2 is not a null player in v

Description

This function checks if the given game is essential.

Usage

essentialcheck(v, binary = FALSE)

Arguments

Details

A game $v\in G^N$ is essential if its set of imputations is non-empty, that is, if $v(N)\ge \sum_{i \in N} v(i)$.

Value

TRUE if the game is essential, FALSE otherwise.

See Also

degeneratecheck

Examples

v <- c(0, 0, 0, 2, 3, 4, 1)
essentialcheck(v, binary = TRUE)
essentialcheck(v, binary = FALSE)

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

Description

Given a game and an allocation, this function computes the excess of each coalition.

Usage

excesses(v, binary = FALSE, x)

Arguments

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(x,S)=v(S)-x(S)$, where $x(S)=\sum_{i\in S} x_i$.

Value

The excesses of all coalitions, as a vector in binary order if binary=TRUE and in lexicographic order otherwise.

See Also

nucleolusvalue, nucleoluspcvalue

Examples

excesses(v=c(0,0,3,0,3,8,6,0,6,9,15,8,16,17,20), binary=TRUE, x=c(8,7,2,3))
excesses(v=c(1,5,10,6,11,15,16), x=c(1,5,10)) <= 0 # core allocation

Description

This function returns the players that form the coalition whose binary order position coincides with the given integer.

Usage

getcoalition(num)

Arguments

Details

A coalition $S\in 2^N$ can be represented by the $n$-digit binary number $s_1\dots s_n$ in which $s_i=1$ if $i\in S$ and $s_i=0$ otherwise. The binary order position of a coalition $S\in 2^N$ is given by $\sum_{i\in S} 2^{i-1}$.

Value

The players that form the coalition whose binary order position is the given integer, as a vector.

See Also

codebin2lex, codelex2bin, getcoalitionnumber

Examples

num <- 5
getcoalition(num)
n <- 4
for (i in 1:(2^n - 1)){
  cat("[", i, "]", paste(getcoalition(i)),"\n")
}

Description

This function returns the binary order position of the coalition formed by the given players.

Usage

getcoalitionnumber(S)

Arguments

Details

A coalition $S\in 2^N$ can be represented by the $n$-digit binary number $s_1\dots s_n$ where $s_i=1$ if $i\in S$ and $0$ otherwise. The binary order position of a coalition $S\in 2^N$ is given by $\sum_{i\in S} 2^{i-1}$.

Value

The binary order position of the coalition formed by the given players.

See Also

codebin2lex, codelex2bin, getcoalition

Examples

N <- c(1:5)
S <- c(1, 2, 3)
getcoalitionnumber(S)
n <- length(N) # number of players
NS <- setdiff(N,S) # complementary coalition
getcoalitionnumber(S) + getcoalitionnumber(NS) == 2^n - 1

Description

Given a number of players and a position, this function returns the permutation of players that occupies the given position when permutations are arranged according to the Lehmer code.

Usage

getpermutation(n, pos)

Arguments

Details

The Lehmer code makes use of the fact that there are $n!$ permutations of a sequence of $n$ numbers. If a permutation $\sigma$ is specified by the sequence $(\sigma_{i})_{i=1}^{n}$, its Lehmer code is the sequence $L(\sigma)=(L(\sigma)_{i})_{i=1}^{n}$, where $L(\sigma)_i=|\{j>i:\sigma_j<\sigma_i\}|$.

The position of permutation $\sigma$ according to the Lehmer code order is

$L_{\sigma}=1 + \sum_{i=1}^{n} (n-i)! L(\sigma)_i$

.

Value

The permutation of n players whose Lehmer code position is pos, as a vector.

See Also

getpermutationnumber

Examples

getpermutation(4, 5)
n <- 4
for (i in 1:factorial(n)) {
  cat("[", i, "]", paste(getpermutation(n,i)), "\n")
}

Description

Given a permutation, this function returns its position in the Lehmer code order.

Usage

getpermutationnumber(permutation)

Arguments

Details

The Lehmer code makes use of the fact that there are $n!$ permutations of a sequence of $n$ numbers. If a permutation $\sigma$ is specified by the sequence $(\sigma_{i})_{i=1}^{n}$, its Lehmer code is the sequence $L(\sigma)=(L(\sigma)_{i})_{i=1}^{n}$, where $L(\sigma)_i=|\{j>i:\sigma_j<\sigma_i\}|$.

The position of permutation $\sigma$ according to the Lehmer code order is

$L_{\sigma}=1 + \sum_{i=1}^{n} (n-i)! L(\sigma)_i$

.

Value

The position of the permutation according to the Lehmer code order, as an integer.

See Also

getpermutation

Examples

getpermutationnumber(c(1, 2, 5, 4, 3))

Description

This function computes the Harsanyi dividend of the given coalition in the given game.

Usage

harsanyidividend(v, S, binary = FALSE)

Arguments

Details

The Harsanyi dividends of $v\in G^N$ are the coordinates of the game in the base of unanimity games. They are defined, for all $S\in 2^N$, by

$c_S=\sum_{S'\subset S}(-1)^{|S|-|S'|}v(S')$

.

Value

The Harsanyi dividend of the coalition that occupies the given position in the given order.

References

Hammer, P.J., Peled, U.N., & Sorensen, S. (1977). Pseudo-boolean function and game theory I. Core elements and Shapley value. Cahiers du Centre d'Etudes de Recherche Opérationnelle, 19, 156-176.

See Also

unanimitygame

Examples

n <- 3
v <- c(1, 5, 10, 7, 11, 15, 16) # introduced in lexicographic order

coalitionsvector<-character()
dividendsvector<-numeric()

for (i in 1:(2^n-1)){
  coalitionsvector <- c(coalitionsvector,
                        paste(getcoalition(i)[getcoalition(i) != 0],collapse = " "))
  dividendsvector <- c(dividendsvector,
                       harsanyidividend(v, codelex2bin(n,i), binary = FALSE))
}

data.frame(Coalition = coalitionsvector, Dividend = dividendsvector)
data.frame(Coalition = bin2lex(coalitionsvector), Dividend = bin2lex(dividendsvector))

Description

This function applies the Kohlberg criterion to check if the given efficient allocation is the prenucleolus of the given game.

Usage

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

Arguments

Details

Given $v \in G^{N}$ and $x \in \mathbb{R}^{n}$ with $\sum_{i \in N} x_{i} = v(N)$, let $k(x)$ be the number of different excesses in $x$. According to the Kohlberg criterion for the prenucleolus, $x$ is the prenucleolus of $v$ if and only if, for each $j \in \{1,\dots,k(x)\}$, $\bigcup_{t=1}^{j} F^{t}$ is a balanced family, being $F^{t}$ the set of coalitions associated with the excess that occupies position $t$ when excesses are arranged in decreasing order.

Value

TRUE if x is the prenucleolus of v, FALSE otherwise.

References

Kohlberg, E. (1971). On the Nucleolus of a Characteristic Function Game. SIAM Journal on Applied Mathematics, 20(1), 62–66.

See Also

balancedfamilycheck, excesses, prenucleolusvalue

Examples

v <- c(0,0,0,0,10,40,30,60,10,20,90,90,90,130,160)
x <- prenucleolusvalue(v)
kohlbergcriterion(v, x) # x is the prenucleolus of v
y <- prenucleolusvalue(v) + c(1,-1,0,0)
kohlbergcriterion(v, y) # y is not the prenucleolus of v

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

Description

Given a game, this function computes its least core.

Usage

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

Arguments

Details

Given a game $v\in G^N$ and a number $\varepsilon \in \mathbb{R}$, the $\varepsilon$-core of $v$ is defined as

$C_{\varepsilon}(v)= \{ x\in \mathbb{R}^n : x(N)=v(N) \text{ and } x(S) \ge v(S)-\varepsilon \ \forall S \in 2^N \setminus \{\emptyset,N\} \},$

where $x(S)=\sum_{i\in S} x_i$. The least core of $v$ is defined as the intersection of all non-empty $\varepsilon$-cores of $v$:

$LC(v) = \{ \bigcap_{\varepsilon \in \mathbb{R} \ : \ C_{\varepsilon}(v) \neq \emptyset} C_{\varepsilon}(v) \}.$

The implementation of this function is based on the algorithm presented in Derks and Kuipers (1997) and on the MATLAB package WCGT2005 by J. Derks.

Value

This function returns four outputs:

References

Derks, J. & Kuipers, J. (1997). Implementing the simplex method for computing the prenucleolus of transferable utility games.

Software by J. Derks (Copyright 2005 Universiteit Maastricht, dept. of Mathematics), available in package MatTuGames,

https://www.shorturl.at/i6aTF.

See Also

excesses, nucleoluspcvalue, nucleolusvalue, prenucleolusvalue

Examples

v <- c(0,0,0,0,10,40,30,60,10,20,90,90,90,130,160)
( vt <- leastcore(v)$vt )
# Plotting the core and the least core of v:
plotcoresets(games = rbind(v,vt), imputations = FALSE)

# What if the game is a cost game?
cost.v <- c(2,2,2,3,4,4,5) # characteristic function of the cost game
-leastcore(-cost.v)$t # the excess value that defines the least core of cost.v
leastcore(-cost.v)$sat # the saturated coalitions
-leastcore(-cost.v)$x # a least core allocation
-leastcore(-cost.v)$vt # the cost game whose core is the least core of cost.v

Description

Given a characteristic function in lexicographic order, this function returns the characteristic function in binary order.

Usage

lex2bin(v)

Arguments

Details

Lexicographic order arranges coalitions in ascending order according to size, and applies lexicographic order to break ties among coalitions of the same size. The binary order position of a coalition $S\in 2^N$ is given by $\sum_{i\in S} 2^{i-1}$.

Value

The characteristic function, as a vector in binary order.

See Also

bin2lex, codebin2lex, codelex2bin

Examples

v <- seq(1:31)
lex2bin(v)
bin2lex(lex2bin(v))==v

Description

Given two awards vectors, this function returns the Lorenz dominance relation between them.

Usage

lorenzdominancerelation(x, y)

Arguments

Details

In order to compare two vectors $x,y\in \mathbb{R}^n$ through the Lorenz criterion, both of them must be rearranged in non-decreasing order; thus, let $\bar{x}$ and $\bar{y}$ be the vectors obtained by rearranging $x$ and $y$, respectively, in non-decreasing order. It is said that $x$ Lorenz-dominates $y$ (or that $y$ is Lorenz-dominated by $x$) if all the cumulative sums of $\bar{x}$ are not less than those of $\bar{y}$. That is, $x$ Lorenz-dominates $y$ if $\sum_{j=1}^{n}\bar{x}_j=\sum_{j=1}^{n}\bar{y}_j$ and, for each $k=1,\dots,n-1$,

$\sum_{j=1}^{k}\bar{x}_j \geq \sum_{j=1}^{k}\bar{y}_j.$

If $x$ Lorenz-dominates $y$ and $y$ Lorenz-dominates $x$, then $x$ and $y$ are said to be Lorenz-equal.

If $x$ does not Lorenz-dominate $y$ and $y$ does not Lorenz-dominate $x$, then $x$ and $y$ are not Lorenz-comparable.

Value

There are four possible outputs:

References

Lorenz, M. O. (1905). Methods of Measuring the Concentration of Wealth. Publications of the American Statistical Association, 9(70), 209-219.

Examples

lorenzdominancerelation(c(1,2,3), c(1,1,4))
lorenzdominancerelation(c(1,2,7,2), c(1,1,4,6))