TUGLab (version 0.0.1)

corecenterhitrun: Core-center estimation by hit-and-run

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)

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.

Arguments

v

A characteristic function of a game with, as a vector.

k

The number of points to be generated by the hit-and-run method, as an integer. By default, k=1000.

getpoints

A logical value. By default, getpoints=FALSE. If set togetpoints=TRUE, the points generated by the hit-and-run method are also returned, as a matrix in which each row is a point.

binary

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

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.

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)