Skip to content

tucoopy.geometry.least_core_set

Least-core (set-valued object + LP helpers).

The least-core is the epsilon-core with the smallest feasible epsilon*. This module defines LeastCore as a thin wrapper that:

  • computes/stores the optimal epsilon* (when an LP backend is available),
  • exposes a corresponding tucoopy.geometry.EpsilonCore / polyhedron, and
  • provides convenience methods for membership and small-n geometry operations.

In addition, this module provides LP-based helpers to compute epsilon* and select representative points from the least-core polytope.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import LeastCore
>>> g = Game.from_coalitions(n_players=2, values={0: 0, 3: 1})
>>> lc = LeastCore(g)
>>> lc.contains([0.5, 0.5])
True

LeastCore dataclass

Least-core as a set-valued object.

Background

For a TU game, the (standard) core is the set of efficient allocations that satisfy all coalitional constraints:

\[ \sum_i x_i = v(N), \qquad x(S) \ge v(S) \; \text{for all } \varnothing \ne S \subsetneq N. \]

When the core is empty, a common relaxation is the epsilon-core:

\[ \sum_i x_i = v(N), \qquad x(S) \ge v(S) - \varepsilon \; \text{for all } \varnothing \ne S \subsetneq N. \]

The least-core is the epsilon-core at the smallest relaxation level \(\varepsilon^*\) for which the epsilon-core becomes non-empty:

\[ \varepsilon^* = \min\{\varepsilon \ge 0 : \text{epsilon-core}(\varepsilon) \ne \varnothing\}. \]

This class is a thin wrapper around EpsilonCore(game, epsilon*), computed lazily on first access.

Lazy evaluation / dependencies

The value epsilon is computed on demand via least_core_epsilon_star in this module (which requires an LP backend at runtime, typically via pip install "tucoopy[lp]"). Once computed, it is cached in _epsilon.

Parameters:

Name Type Description Default
game GameProtocol

TU game.

 required
restrict_to_imputation bool

If True, additionally enforce individual rationality x_i >= v({i}) (handled as bounds) when forming the underlying polyhedron. This selects the least-core within the imputation set.

 False
tol float

Numerical tolerance forwarded to the LP solver and set-membership checks.

 DEFAULT_GEOMETRY_TOL
_epsilon float | None

Optional cached value for epsilon (internal). If provided, the LP solve is skipped.

 None

Attributes:

Name Type Description
epsilon float

The least-core value epsilon* (computed lazily and cached).
epsilon_core EpsilonCore

The epsilon-core object at epsilon*.
poly PolyhedralSet

The underlying polyhedral representation (PolyhedralSet) of the least-core.
Notes
  • LeastCore is set-valued. If you need a single-valued selector, use a routine like least_core_point (e.g., Chebyshev center) on top of this set.
  • The method vertices enumerates vertices using a brute-force routine intended for small n (visualization).

Examples:

Minimal example (may have empty core; least-core always exists for TU games under this LP formulation):

>>> from tucoopy import Game
>>> from tucoopy.geometry import LeastCore
>>> g = Game.from_value_function(n_players=3, value_fn=lambda S: float(len(S)))
>>> lc = LeastCore(g)
>>> eps = lc.epsilon
>>> eps
0.0
>>> lc.sample_point()  # one least-core point (here also core point)
[1.0, 1.0, 1.0]

epsilon property 

epsilon

Least-core value epsilon* (computed lazily).

Notes

This requires an LP backend (typically SciPy/HiGHS via tucoopy[lp]).

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import LeastCore
>>> g = Game.from_coalitions(n_players=2, values={0: 0, 3: 1})
>>> LeastCore(g).epsilon
0.0

epsilon_core property 

epsilon_core

Epsilon-core object at epsilon*.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import LeastCore
>>> g = Game.from_coalitions(n_players=2, values={0: 0, 3: 1})
>>> lc = LeastCore(g)
>>> lc.epsilon_core.epsilon
0.0

poly property 

poly

Underlying polyhedral representation of the least-core.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import LeastCore
>>> g = Game.from_coalitions(n_players=2, values={0: 0, 3: 1})
>>> LeastCore(g).poly.n_vars
2

chebyshev_center 

chebyshev_center()

Compute the Chebyshev center of the least-core polytope.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import LeastCore
>>> g = Game.from_coalitions(n_players=2, values={0: 0, 3: 1})
>>> LeastCore(g).chebyshev_center()
([0.5, 0.5], 0.0)

check 

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

Return least-core membership diagnostics for \(x\).

Notes

This delegates to tucoopy.diagnostics.least_core_diagnostics.least_core_diagnostics. If the LP backend is unavailable, the returned diagnostics will have available=False.

contains 

contains(x, *, tol=None)

Check whether x lies in the least-core (within tolerance).

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import LeastCore
>>> g = Game.from_coalitions(n_players=2, values={0: 0, 3: 1})
>>> LeastCore(g).contains([0.5, 0.5])
True

explain 

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

Return a short human-readable explanation of least-core membership.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import LeastCore
>>> g = Game.from_coalitions(n_players=2, values={0: 0, 3: 1})
>>> LeastCore(g).explain([0.5, 0.5])[0]
'In the least-core (epsilon*=0).'

extreme_points 

extreme_points(
    *,
    tol=DEFAULT_GEOMETRY_TOL,
    max_dim=DEFAULT_GEOMETRY_MAX_DIM,
)

Enumerate extreme points of the least-core (small dimension).

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import LeastCore
>>> g = Game.from_coalitions(n_players=2, values={0: 0, 3: 1})
>>> LeastCore(g).extreme_points(max_dim=2)
[[0.0, 1.0], [1.0, 0.0]]

is_empty 

is_empty()

Return True if the least-core polytope is empty.

Notes

This delegates to the underlying epsilon-core polyhedron. Requires an LP backend.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import LeastCore
>>> g = Game.from_coalitions(n_players=2, values={0: 0, 3: 1})
>>> LeastCore(g).is_empty()
False

project 

project(
    dims,
    *,
    tol=DEFAULT_GEOMETRY_TOL,
    max_dim=DEFAULT_GEOMETRY_MAX_DIM,
)

Project the least-core to selected coordinates.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import LeastCore
>>> g = Game.from_coalitions(n_players=2, values={0: 0, 3: 1})
>>> LeastCore(g).project((0,), max_dim=2)
[[0.0], [1.0]]

sample_point 

sample_point()

Attempt to sample one point from the least-core.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import LeastCore
>>> g = Game.from_coalitions(n_players=2, values={0: 0, 3: 1})
>>> LeastCore(g).sample_point()
[0.5, 0.5]

vertices 

vertices(
    *,
    tol=DEFAULT_GEOMETRY_TOL,
    max_players=DEFAULT_GEOMETRY_MAX_PLAYERS,
    max_dim=DEFAULT_GEOMETRY_MAX_DIM,
)

Enumerate vertices of the least-core polytope (small dimension).

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import LeastCore
>>> g = Game.from_coalitions(n_players=2, values={0: 0, 3: 1})
>>> LeastCore(g).vertices(max_dim=2)
[[0.0, 1.0], [1.0, 0.0]]

least_core 

least_core(game, *, tol=1e-09)

Compute a least-core allocation and the least-core epsilon.

Notes

Requires an LP backend at runtime (pip install "tucoopy[lp]").

least_core_epsilon_star 

least_core_epsilon_star(game, *, tol=1e-09)

Compute the least-core value epsilon*.

least_core_point 

least_core_point(
    game,
    *,
    restrict_to_imputation=False,
    tol=1e-09,
    method="chebyshev_center",
)

Select a single allocation from the least-core set.