A kernel point of a transferable-utility game by Stearns' transfers

The maximum surplus of i over j at x is \(s_{ij}(x) = \max\{v(S) - x(S) : i \in S, j \notin S\}\). An imputation is in the kernel (Davis and Maschler 1965) when \(s_{ij} > s_{ji}\) implies \(x_j = v(\{j\})\); the prekernel asks \(s_{ij} = s_{ji}\). Starting from x0 (default: the equal split of \(v(N) - \sum v(\{i\})\) on top of the singleton worths), each step moves \(\min((s_{ij} - s_{ji})/2, x_j - v(\{j\}))\) (no bound for the prekernel) from j to i for the pair where that amount is largest; Stearns (1968) shows the scheme converges to a kernel point.

Usage

KernelPoint(v, x0 = NULL, pre = FALSE, tol = 1e-10, max_iter = 100000L)

Arguments

v

Worths in binary order, length \(2^n - 1\).

x0

Starting imputation.

pre

Prekernel instead of kernel.

tol

Stop when no pair can transfer more than tol.

max_iter

Maximum number of transfers.

Value

List with x, surplus (matrix of \(s_{ij}\)), in_kernel (the membership test at tolerance 100 * tol), iterations and converged.

References

Davis, M. and Maschler, M. (1965). The kernel of a cooperative game. Naval Research Logistics Quarterly 12, 223-259.

Stearns, R. E. (1968). Convergent transfer schemes for n-person games. Transactions of the American Mathematical Society 134, 449-459.

Examples

KernelPoint(c(0, 0, 60, 0, 60, 60, 72))$x
#> [1] 24 24 24