Pular para conteúdo

tucoopy.solutions.nucleolus

Nucleolus and pre-nucleolus.

This module implements lexicographic LP refinement for the nucleolus (and pre-nucleolus).

NucleolusResult dataclass

Result container for the nucleolus / pre-nucleolus computation.

Attributes:

Name Type Description
x list[float]

Allocation vector (length n_players).
levels list[float]

Sequence of epsilon levels fixed during the lexicographic minimization. Each entry corresponds to the maximum excess minimized at that round.
tight_sets list[list[int]] | None

For each round, the list of coalitions that were tight (achieved the maximum excess) at that level.
lp_rounds list[LinprogDiagnostics] | None

Optional diagnostics from each LP solve (HiGHS / SciPy).

disruption_nucleolus 

disruption_nucleolus(game)

Disruption nucleolus.

This variant minimizes the lexicographic vector of disruption ratios:

\[ e_{dis}(S, x) = \frac{v(S) - x(S)}{M(S)}, \]

where \(M\) is the utopia payoff vector and

\[ M(S) = \sum_{i \in S} M_i. \]
Interpretation

The excess of a coalition is scaled by its utopia potential. Coalitions that could potentially demand more (high utopia value) are weighted accordingly.

Notes
  • Closely related to the concept of propensity to disrupt.
  • Used in bargaining and stability analyses.
  • Reduces to the standard nucleolus when utopia payoffs are uniform.

Returns:

Type Description
NucleolusResult

Allocation and diagnostic information.

nucleolus 

nucleolus(game, *, tol=1e-09, max_rounds=200, excess=None)

Compute the nucleolus of a TU cooperative game.

The nucleolus is the allocation in the imputation set that lexicographically minimizes coalition excesses:

\[ e(S, x) = v(S) - x(S), \]

from largest to smallest.

Generalized excess

As in prenucleolus, this implementation supports a generalized excess function through the excess parameter, allowing the computation of several nucleolus variants (per-capita, proportional, disruption-based, etc.) without modifying the core algorithm.

Individual rationality

In addition to efficiency, this version enforces

\[ x_i \ge v(\{i\}) \quad \text{for all players } i, \]

restricting the solution to the imputation set.

Parameters:

Name Type Description Default
game GameProtocol

TU game.

 required
tol float

Numerical tolerance for tightness detection.

 1e-9
max_rounds int

Maximum number of lexicographic refinement rounds.

 200
excess callable

Custom excess function excess(S, xS, game).

 None

Returns:

Type Description
NucleolusResult

Allocation, epsilon levels, and optional diagnostics.

Raises:

Type Description
InvalidGameError

If the imputation set is empty, i.e. \(\sum_i v(\{i\}) > v(N)\).
Notes
  • The nucleolus always lies in the imputation set.
  • It is one of the most important solution concepts in cooperative game theory due to its strong stability properties.
  • Requires SciPy/HiGHS at runtime (pip install "tucoopy[lp]").
  • The algorithm terminates when enough tight coalitions determine the allocation uniquely.

Examples:

>>> nucleolus(g).x

per_capita_nucleolus 

per_capita_nucleolus(game)

Per-capita nucleolus.

Minimizes the lexicographic vector of

\[e_{pc}(S, x) = \frac{v(S) - x(S)}{|S|}.\]

prenucleolus 

prenucleolus(
    game, *, tol=1e-09, max_rounds=200, excess=None
)

Compute the pre-nucleolus of a TU cooperative game.

The pre-nucleolus is defined as the allocation that lexicographically minimizes the vector of coalition excesses:

\[ e(S, x) = v(S) - x(S), \]

ordered from largest to smallest.

Generalized excess

This implementation supports a generalized notion of excess through the excess parameter. Instead of the classical excess, one may supply a custom function

excess(S, xS, game)

allowing the algorithm to minimize lexicographically any transformed excess such as:

  • per-capita excess: \(\fra{v(S)-x(S)}{|S|}\),
  • proportional excess: \(\frac{v(S)-x(S)}{v(S)}\),
  • disruption-based excess, etc.

This turns the routine into a generic lexicographic excess minimization engine.

Algorithm

The method follows the standard lexicographic LP refinement:

  1. Solve an LP minimizing the maximum excess over all coalitions.
  2. Identify coalitions that achieve this maximum excess (tight sets).
  3. Fix their excess as equality constraints.
  4. Repeat on the reduced problem.

Parameters:

Name Type Description Default
game GameProtocol

TU game.

 required
tol float

Numerical tolerance for tightness detection.

 1e-9
max_rounds int

Maximum number of lexicographic refinement rounds.

 200
excess callable

Custom excess function excess(S, xS, game).

 None

Returns:

Type Description
NucleolusResult

Allocation, epsilon levels, and optional diagnostics.
Notes
  • Only efficiency is enforced (no individual rationality).
  • The result may lie outside the imputation set.
  • Requires SciPy/HiGHS at runtime (pip install "tucoopy[lp]").
  • The algorithm terminates when the solution is uniquely determined by the accumulated tight constraints.

Examples:

>>> prenucleolus(g).x

proportional_nucleolus 

proportional_nucleolus(game)

Proportional nucleolus.

This solution minimizes the lexicographic vector of relative (proportional) excesses:

\[ e_{prop}(S, x) = \frac{v(S) - x(S)}{v(S)}. \]

Coalitions are evaluated by how large their dissatisfaction is relative to their own worth.

Notes
  • Coalitions with larger worth are normalized accordingly.
  • Common in bankruptcy and allocation problems where proportional dissatisfaction is more meaningful than absolute dissatisfaction.
  • Coalitions with \(v(S)=0\) are ignored (excess defined as 0).

Returns:

Type Description
NucleolusResult

Allocation and diagnostic information.