corecenterhitrun {TUGLab} | R Documentation |
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)
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, |
getpoints |
A logical value. By default, |
binary |
A logical value. By default, |
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)