`tucoopy.geometry.kernel_set`¶

Kernel and pre-kernel (set-valued, sampling-based diagnostics).¶

This module provides KernelSet / PreKernelSet helpers aimed at "small n" usage and diagnostics workflows.

The kernel and pre-kernel are defined via pairwise surplus comparisons and are not polyhedral in general. The implementation therefore relies on:

fast surplus evaluation helpers, and
sampling points from the imputation set to probe membership / produce examples.

Notes

For large games, kernel/pre-kernel computations can be expensive. This module exposes explicit iteration limits and sampling limits to keep the runtime under control.

Examples:

Instantiate the set-valued helpers for a small 3-player game:

>>> from tucoopy import Game
>>> from tucoopy.geometry.kernel_set import PreKernelSet, KernelSet
>>> g = Game.from_coalitions(n_players=3, values={
...     0: 0.0,
...     1: 1.0, 2: 1.0, 4: 1.0,
...     3: 2.0, 5: 2.0, 6: 2.0,
...     7: 4.0,
... })
>>> isinstance(PreKernelSet(g), PreKernelSet)
True
>>> isinstance(KernelSet(g), KernelSet)
True

KernelCheckResult `dataclass` ¶

Result of a kernel membership check.

Attributes:

Name	Type	Description
`in_set`	`bool`	True if the point passes the kernel test within tolerance.
`efficient`	`bool`	Efficiency flag (sum x = v(N)).
`imputation`	`bool`	Imputation flag (efficiency + individual rationality).
`max_violation`	`float`	Maximum kernel complementarity violation detected.
`required_bounds`	`list[int]`	List of players that, according to dominance relations, must be at their individual rationality bound (x_i = v({i})) for kernel membership.
`pairs`	`list[PairSurplusDiagnostics]`	A (possibly truncated) list of per-pair surplus diagnostics, sorted by decreasing \|delta\|.

Notes

Kernel membership (for imputations) can be stated as:

x is an imputation
for each pair (i, j): if :math:s_{ij}(x) > s_{ji}(x) then player j must be at its lower bound :math:x_j = v(\{j\}).

Equivalently, whenever both i and j are interior (strictly above bounds), we must have :math:s_{ij}(x)=s_{ji}(x) within tolerance.

Examples:

>>> from tucoopy.geometry.kernel_set import KernelCheckResult
>>> res = KernelCheckResult(in_set=False, efficient=True, imputation=False, max_violation=1.0, required_bounds=[0], pairs=[])
>>> res.in_set
False

to_dict ¶

to_dict()

Convert to a JSON-friendly dict.

KernelResult `dataclass` ¶

Result container for the kernel iteration (imputation-constrained).

Attributes:

Name	Type	Description
`x`	`list[float]`	Candidate kernel allocation (length `n_players`), intended to lie in the imputation set (efficiency + individual rationality).
`iterations`	`int`	Number of outer iterations performed.
`residual`	`float`	A measure of kernel complementarity violation used as stopping criterion.
`delta`	`float`	Maximum absolute coordinate update in the last iteration.
`argmax`	`dict[tuple[int, int], int]`	Dictionary mapping ordered pairs (i, j) to an argmax coalition mask achieving \(s_{ij}(x)\) at the returned point.
`active_bounds`	`set[int]`	Active-set of players clamped at individual rationality bounds (\(x_i = v(\{i\})\)) at the returned point.

KernelSet `dataclass` ¶

Kernel set (set-valued).

Definition

Kernel membership (for imputations) can be stated as:

x is an imputation (efficiency + individual rationality)
for each pair (i, j): if :math:s_{ij}(x) > s_{ji}(x) (by more than tolerance), then player j must be at its lower bound: :math:x_j = v(\{j\}).

Equivalently, whenever both i and j are interior (:math:x_i > v(\{i\}) and :math:x_j > v(\{j\})), we must have :math:s_{ij}(x) = s_{ji}(x) within tolerance.

Practical notes

Checking membership is exponential in n (coalition enumeration).
This class is intended for small-n diagnostics/visualization.

Parameters:

Name	Type	Description	Default
`game`	`GameProtocol`	TU game.	required
`tol`	`float`	Default tolerance used in membership tests.	`DEFAULT_KERNEL_TOL`
`max_iter`	`int`	Iteration limit used by `element()` (solver).	`DEFAULT_KERNEL_MAX_ITER`
`max_players`	`int`	Safety cap for exponential routines.	`DEFAULT_KERNEL_MAX_PLAYERS`
`approx_max_coalitions_per_pair`	`int \| None`	If provided, approximate each pairwise surplus by checking only this many random coalitions per ordered pair (i, j).	`DEFAULT_KERNEL_APPROX_MAX_COALITIONS_PER_PAIR`
`approx_seed`	`int \| None`	Random seed used for the approximation.	`DEFAULT_KERNEL_APPROX_SEED`

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry.kernel_set import KernelSet
>>> g = Game.from_coalitions(n_players=3, values={
...     0: 0.0,
...     1: 1.0, 2: 1.0, 4: 1.0,
...     3: 2.0, 5: 2.0, 6: 2.0,
...     7: 4.0,
... })
>>> ks = KernelSet(g)
>>> out = ks.check([1.0, 1.0, 2.0], top_k=2)
>>> isinstance(out.in_set, bool)
True

check ¶

check(x, *, tol=None, top_k=8)

Compute a kernel membership check plus pairwise surplus diagnostics.

Parameters:

Name	Type	Description	Default
`x`	`list[float]`	Candidate allocation (length `n_players`).	required
`tol`	`float \| None`	Optional override tolerance.	`None`
`top_k`	`int`	Include at most this many (i, j) diagnostic entries.	`8`

Returns:

Type	Description
`KernelCheckResult`	Membership result + diagnostics.

Raises:

Type	Description
`NotSupportedError`	If `n_players` is above `max_players`.
`InvalidParameterError`	If `x` has the wrong length.

Examples:

Minimal 2-player game (kernel coincides with the imputation segment):

>>> from tucoopy import Game
>>> from tucoopy.geometry.kernel_set import KernelSet
>>> g = Game.from_coalitions(n_players=2, values={0:0, 1:0, 2:0, 3:1})
>>> ks = KernelSet(g)
>>> ks.check([0.5, 0.5]).imputation
True

contains ¶

contains(x, *, tol=None)

Return True iff x is in the kernel (within tolerance).

Parameters:

Name	Type	Description	Default
`x`	`list[float]`	Candidate allocation.	required
`tol`	`float \| None`	Optional override tolerance.	`None`

Returns:

Type	Description
`bool`

element ¶

element()

Compute one representative kernel element using the iterative solver.

Returns:

Type	Description
`list[float]`	A candidate kernel allocation (intended to lie in the imputation set).

Notes

Uses the iterative solver implemented in this module.

explain ¶

explain(x, *, tol=None, top_k=3)

Return a short human-readable explanation of kernel membership.

Notes

This is a thin wrapper around check.

sample_point ¶

sample_point(
    *, n_samples=5000, seed=None, max_points=50, tol=None
)

Return one kernel point found by sampling, or None.

Parameters:

Name	Type	Description	Default
`n_samples`	`int`	Forwarded to `sample_points`.	`5000`
`seed`	`int`	Forwarded to `sample_points`.	`5000`
`max_points`	`int`	Forwarded to `sample_points`.	`5000`
`tol`	`int`	Forwarded to `sample_points`.	`5000`

Returns:

Type	Description
`list[float] \| None`

sample_points ¶

sample_points(
    *, n_samples=5000, seed=None, max_points=50, tol=None
)

Heuristically search for kernel points by sampling the imputation set.

Parameters:

Name	Type	Description	Default
`n_samples`	`int`	Number of imputations to sample.	`5000`
`seed`	`int \| None`	Optional RNG seed.	`None`
`max_points`	`int`	Stop once this many passing points are found.	`50`
`tol`	`float \| None`	Optional override tolerance for membership testing.	`None`

Returns:

Type	Description
`list[list[float]]`	Up to `max_points` candidate kernel points found by sampling.

Notes

Intended for visualization and debugging (small n).
Does not guarantee finding any point, even if the kernel is non-empty.
Points are de-duplicated with a cheap L-infinity rule within tolerance.

PairSurplusDiagnostics `dataclass` ¶

Diagnostics for a player pair (i, j) at an allocation x.

Fields correspond to:

s_ij: :math:\max_{S: i\in S,\ j\notin S} e(S,x)
s_ji: :math:\max_{S: j\in S,\ i\notin S} e(S,x)
delta: s_ij - s_ji
argmax_ij / argmax_ji: coalition masks achieving the maxima (tie-broken by smaller mask)

Notes

The argmax masks are useful to understand which coalitions witness the surplus imbalance for a given pair.

Examples:

>>> from tucoopy.geometry.kernel_set import PairSurplusDiagnostics
>>> d = PairSurplusDiagnostics(i=0, j=1, s_ij=0.5, s_ji=0.25, delta=0.25, argmax_ij=3, argmax_ji=5)
>>> d.delta
0.25
>>> isinstance(d.to_dict(), dict)
True

to_dict ¶

to_dict()

Convert to a JSON-friendly dict.

PreKernelCheckResult `dataclass` ¶

Result of a pre-kernel membership check.

Attributes:

Name	Type	Description
`in_set`	`bool`	True if the point passes the pre-kernel test within tolerance.
`efficient`	`bool`	Efficiency flag (sum x = v(N)).
`max_abs_delta`	`float`	Maximum absolute surplus imbalance: .. math:: `\max_{i<j} \|s_{ij}(x) - s_{ji}(x)\|.`
`pairs`	`list[PairSurplusDiagnostics]`	A (possibly truncated) list of per-pair diagnostics, sorted by decreasing \|delta\|.

Notes

The pre-kernel condition requires efficiency and the equalities :math:s_{ij}(x)=s_{ji}(x) for all i != j.
pairs is intended for debugging/visualization: it contains the worst offending pairs.

Examples:

>>> from tucoopy.geometry.kernel_set import PairSurplusDiagnostics, PreKernelCheckResult
>>> pairs = [PairSurplusDiagnostics(i=0, j=1, s_ij=0.0, s_ji=0.0, delta=0.0, argmax_ij=1, argmax_ji=2)]
>>> res = PreKernelCheckResult(in_set=True, efficient=True, max_abs_delta=0.0, pairs=pairs)
>>> res.in_set
True

to_dict ¶

to_dict()

Convert to a JSON-friendly dict.

PreKernelResult `dataclass` ¶

Result container for the pre-kernel iteration.

Attributes:

Name	Type	Description
`x`	`list[float]`	Candidate pre-kernel allocation (length `n_players`).
`iterations`	`int`	Number of outer iterations performed.
`residual`	`float`	Final maximum surplus imbalance: \[ \max_{i<j} \|s_{ij}(x) - s_{ji}(x)\|. \]
`delta`	`float`	Maximum absolute coordinate update in the last iteration.
`argmax`	`dict[tuple[int, int], int]`	Dictionary mapping ordered pairs (i, j) to an argmax coalition mask achieving \(s_{ij}(x)\) at the returned point.

PreKernelSet `dataclass` ¶

Pre-kernel set (set-valued).

Definition

A (pre-)kernel element x (typically in the pre-imputation set) satisfies:

efficiency: :math:\sum_i x_i = v(N)
pairwise surplus equalities: :math:s_{ij}(x) = s_{ji}(x) for all i != j

where :math:s_{ij}(x) is the maximum excess over coalitions containing i and excluding j.

Practical notes

Checking membership is exponential in n because it enumerates coalitions to compute argmax surpluses.
This class is meant for small-n visualization and diagnostics.

Parameters:

Name	Type	Description	Default
`game`	`GameProtocol`	TU game.	required
`tol`	`float`	Default tolerance used in membership tests.	`DEFAULT_KERNEL_TOL`
`max_iter`	`int`	Iteration limit used by `element()` (solver).	`DEFAULT_KERNEL_MAX_ITER`
`max_players`	`int`	Safety cap for exponential routines.	`DEFAULT_KERNEL_MAX_PLAYERS`
`approx_max_coalitions_per_pair`	`int \| None`	If provided, approximate each pairwise surplus by checking only this many random coalitions per ordered pair (i, j). This keeps `O(2^n)` DP for coalition sums but avoids scanning all admissible coalitions per pair.	`DEFAULT_KERNEL_APPROX_MAX_COALITIONS_PER_PAIR`
`approx_seed`	`int \| None`	Random seed used for the approximation.	`DEFAULT_KERNEL_APPROX_SEED`

Examples:

Run a basic check (the returned object contains detailed diagnostics):

>>> from tucoopy import Game
>>> from tucoopy.geometry.kernel_set import PreKernelSet
>>> g = Game.from_coalitions(n_players=3, values={
...     0: 0.0,
...     1: 1.0, 2: 1.0, 4: 1.0,
...     3: 2.0, 5: 2.0, 6: 2.0,
...     7: 4.0,
... })
>>> pk = PreKernelSet(g)
>>> out = pk.check([1.0, 1.0, 2.0], top_k=2)
>>> isinstance(out.in_set, bool)
True

check ¶

check(x, *, tol=None, top_k=8)

Compute a pre-kernel membership check plus pairwise surplus diagnostics.

Parameters:

Name	Type	Description	Default
`x`	`list[float]`	Candidate allocation (length `n_players`).	required
`tol`	`float \| None`	Optional override tolerance.	`None`
`top_k`	`int`	Include at most this many (i, j) diagnostic entries (largest imbalances).	`8`

Returns:

Type	Description
`PreKernelCheckResult`	Membership result + diagnostics.

Raises:

Type	Description
`NotSupportedError`	If `n_players` is above `max_players`.
`InvalidParameterError`	If `x` has the wrong length.

Examples:

Minimal 3-player example (complete characteristic function):

>>> from tucoopy import Game
>>> from tucoopy.geometry.kernel_set import PreKernelSet
>>> g = Game.from_coalitions(n_players=3, values={
...     0:0, 1:0, 2:0, 4:0,
...     3:0, 5:0, 6:0,
...     7:1,
... })
>>> pk = PreKernelSet(g)
>>> x = [1/3, 1/3, 1/3]
>>> pk.check(x).efficient
True

contains ¶

contains(x, *, tol=None)

Return True iff x is in the pre-kernel (within tolerance).

Parameters:

Name	Type	Description	Default
`x`	`list[float]`	Candidate allocation.	required
`tol`	`float \| None`	Optional override tolerance.	`None`

Returns:

Type	Description
`bool`

element ¶

element()

Compute one representative pre-kernel element using the iterative solver.

Returns:

Type	Description
`list[float]`	A candidate pre-kernel allocation.

Notes

Uses the iterative solver implemented in this module.

explain ¶

explain(x, *, tol=None, top_k=3)

Return a short human-readable explanation of pre-kernel membership.

Notes

This is a thin wrapper around check.

sample_point ¶

sample_point(
    *, n_samples=2000, seed=None, max_points=50, tol=None
)

Return one pre-kernel point found by sampling, or None.

Parameters:

Name	Type	Description	Default
`n_samples`	`int`	Forwarded to `sample_points`.	`2000`
`seed`	`int`	Forwarded to `sample_points`.	`2000`
`max_points`	`int`	Forwarded to `sample_points`.	`2000`
`tol`	`int`	Forwarded to `sample_points`.	`2000`

Returns:

Type	Description
`list[float] \| None`

sample_points ¶

sample_points(
    *, n_samples=2000, seed=None, max_points=50, tol=None
)

Heuristically search for pre-kernel points by sampling the imputation set.

This routine draws random imputations and returns those that pass the pre-kernel test (within tolerance).

Parameters:

Name	Type	Description	Default
`n_samples`	`int`	Number of imputations to sample.	`2000`
`seed`	`int \| None`	Optional RNG seed.	`None`
`max_points`	`int`	Stop once this many passing points are found.	`50`
`tol`	`float \| None`	Optional override tolerance for membership testing.	`None`

Returns:

Type	Description
`list[list[float]]`	Up to `max_points` candidate pre-kernel points found by sampling.

Notes

Intended for visualization and debugging (small n).
Does not guarantee finding any point, even if the set is non-empty.

kernel ¶

kernel(
    game,
    *,
    x0=None,
    tol=DEFAULT_KERNEL_TOL,
    max_iter=DEFAULT_KERNEL_MAX_ITER,
    approx_max_coalitions_per_pair=DEFAULT_KERNEL_APPROX_MAX_COALITIONS_PER_PAIR,
    approx_seed=DEFAULT_KERNEL_APPROX_SEED,
)

Compute a (candidate) kernel element.

Background

The kernel refines the pre-kernel by imposing a complementarity condition with respect to the imputation set. Using the same surplus definition \(s_{ij}(x)\) as in the pre-kernel, the kernel condition can be stated as:

For each pair \((i, j)\), if player \(i\) has strictly larger surplus against \(j\), i.e. \(s_{ij}(x) > s_{ji}(x)\), then player \(j\) must be at its individual rationality bound: \(x_j = v(\{j\})\).

This prevents a player with "weaker bargaining position" from receiving more than their minimal guaranteed payoff.

Method (active-set heuristic)

This implementation is a practical small-n solver:

Maintain \(x\) in the imputation set (efficiency + individual rationality), using projection.
Maintain an active-set active_bounds of players clamped at their individual rationality bounds.
From the current \(x\), derive which bounds must be active based on surplus dominance relations.
With a fixed active-set, solve pre-kernel equalities (in least-squares form) for the remaining free players, then project back to the imputation set.
Repeat until:
argmax selections stabilize,
the active-set stabilizes,
kernel violations are below tolerance.

Parameters:

Name	Type	Description	Default
`game`	`GameProtocol`	TU game.	required
`x0`	`list[float] \| None`	Optional initial allocation. If omitted, the Shapley value is used as a starting point, then projected into the imputation set.	`None`
`tol`	`float`	Tolerance used for dominance comparisons and stopping conditions.	`DEFAULT_KERNEL_TOL`
`max_iter`	`int`	Maximum number of iterations.	`DEFAULT_KERNEL_MAX_ITER`
`approx_max_coalitions_per_pair`	`int \| None`	If provided, approximate each surplus `s_ij(x)` by evaluating at most this many candidate coalitions for each ordered pair (i, j).	`DEFAULT_KERNEL_APPROX_MAX_COALITIONS_PER_PAIR`
`approx_seed`	`int \| None`	Random seed used when `approx_max_coalitions_per_pair` is set.	`DEFAULT_KERNEL_APPROX_SEED`

Returns:

Type	Description
`KernelResult`	Candidate kernel point and iteration diagnostics.

Raises:

Type	Description
`InvalidGameError`	If the imputation set is empty (i.e. \(\sum_i v(\{i\}) > v(N)\)).

Notes

This is a heuristic implementation intended primarily for small games (e.g. \(n \leq 4\)) and visualization use-cases.
Requires NumPy (pip install "tucoopy[fast]") for least-squares solves.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry.kernel_set import kernel
>>>
>>> # Additive game: kernel is the equal split
>>> g = Game.from_value_function(
...     n_players=3,
...     value_fn=lambda ps: float(len(ps)),
... )
>>> res = kernel(g, tol=1e-10, max_iter=200)
>>> [round(v, 8) for v in res.x]
[1.0, 1.0, 1.0]
>>> res.residual <= 1e-8
True
>>>
>>> # If the imputation set is empty, kernel() raises InvalidGameError:
>>> bad = Game.from_coalitions(
...     n_players=2,
...     values={
...         (): 0.0,
...         (0,): 2.0,
...         (1,): 2.0,
...         (0, 1): 1.0,  # v(N) < v({0}) + v({1})
...     },
... )
>>> kernel(bad)
Traceback (most recent call last):
    ...
InvalidGameError: kernel undefined: imputation set is empty (sum v({i}) > v(N))

prekernel ¶

prekernel(
    game,
    *,
    x0=None,
    tol=DEFAULT_KERNEL_TOL,
    max_iter=DEFAULT_KERNEL_MAX_ITER,
    relax=1.0,
    approx_max_coalitions_per_pair=DEFAULT_KERNEL_APPROX_MAX_COALITIONS_PER_PAIR,
    approx_seed=DEFAULT_KERNEL_APPROX_SEED,
)

Compute a (candidate) pre-kernel element.

Background

For an allocation \(x \in \mathbb{R}^n\), define the pairwise surplus:

\[ s_{ij}(x) = \max_{S: i \in S,\ j \notin S} \left[v(S) - x(S)\right]. \]

The pre-kernel is the set of allocations \(x\) such that

\[ s_{ij}(x) = s_{ji}(x) \quad \text{for all } i \ne j. \]

Method

This routine implements a practical fixed-point style iteration:

Given the current allocation \(x\), compute argmax coalitions \(S_{ij}\) for each ordered pair \((i,j)\) (so that \(S_{ij}\) achieves \(s_{ij}(x)\)).
Freeze these argmax coalitions and enforce the equalities

\[ s_{ij}(x) = s_{ji}(x) \iff x(S_{ji}) - x(S_{ij}) = v(S_{ji}) - v(S_{ij}) \]

for all \(i<j\).

Solve the resulting (typically overdetermined) linear system in a least-squares sense, adding the efficiency constraint \(\sum_i x_i = v(N)\).
Optionally apply a damped update controlled by relax.
Repeat until argmax selections stabilize and the maximum surplus imbalance is below tolerance.

Parameters:

Name	Type	Description	Default
`game`	`GameProtocol`	TU game.	required
`x0`	`list[float] \| None`	Optional initial allocation. If omitted, the Shapley value is used as a starting point.	`None`
`tol`	`float`	Stopping tolerance for both surplus imbalance and coordinate changes.	`DEFAULT_KERNEL_TOL`
`max_iter`	`int`	Maximum number of iterations.	`DEFAULT_KERNEL_MAX_ITER`
`relax`	`float`	Relaxation parameter in (0, 1]. Values below 1 damp updates and can improve stability in degenerate cases.	`1.0`
`approx_max_coalitions_per_pair`	`int \| None`	If provided, approximate each surplus `s_ij(x)` by evaluating at most this many candidate coalitions for each ordered pair (i, j), sampled uniformly without replacement from the admissible set `{S: i in S, j not in S}`. This reduces per-iteration cost substantially for n > ~10.	`DEFAULT_KERNEL_APPROX_MAX_COALITIONS_PER_PAIR`
`approx_seed`	`int \| None`	Random seed used when `approx_max_coalitions_per_pair` is set.	`DEFAULT_KERNEL_APPROX_SEED`

Returns:

Type	Description
`PreKernelResult`	Candidate pre-kernel point and iteration diagnostics.

Notes

This is a numerical heuristic intended for small games and visualization. Convergence is not guaranteed for all games.
Requires NumPy (pip install "tucoopy[fast]") for least-squares solves.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry.kernel_set import prekernel
>>>
>>> # Additive game: v(S) = |S|
>>> g = Game.from_value_function(
...     n_players=3,
...     value_fn=lambda ps: float(len(ps)),
... )
>>> res = prekernel(g, tol=1e-10, max_iter=200)
>>> [round(v, 8) for v in res.x]
[1.0, 1.0, 1.0]
>>> res.residual <= 1e-8
True

tucoopy.geometry.kernel_set¶

Kernel and pre-kernel (set-valued, sampling-based diagnostics).¶

KernelCheckResult dataclass ¶

to_dict ¶

KernelResult dataclass ¶

KernelSet dataclass ¶

check ¶

contains ¶

element ¶

explain ¶

sample_point ¶

sample_points ¶

PairSurplusDiagnostics dataclass ¶

to_dict ¶

PreKernelCheckResult dataclass ¶

to_dict ¶

PreKernelResult dataclass ¶

PreKernelSet dataclass ¶

check ¶

contains ¶

element ¶

explain ¶

sample_point ¶

sample_points ¶

kernel ¶

prekernel ¶

`tucoopy.geometry.kernel_set`¶

KernelCheckResult `dataclass` ¶

KernelResult `dataclass` ¶

KernelSet `dataclass` ¶

PairSurplusDiagnostics `dataclass` ¶

PreKernelCheckResult `dataclass` ¶

PreKernelResult `dataclass` ¶

PreKernelSet `dataclass` ¶