Pular para conteúdo

tucoopy.solutions.modiclus

Modiclus.

The modiclus is a nucleolus-type solution concept defined by lexicographic minimization of pairwise excess differences.

ModiclusResult dataclass

Result container for the modiclus computation.

Attributes:

Name Type Description
x list[float]

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

Sequence of lexicographic levels fixed during refinement. Each level is the optimal value of the auxiliary variable t in that round, i.e. the minimized maximum envy.
tight_pairs list[list[tuple[int, int]]] | None

For each round, the list of ordered coalition pairs (S, T) that were tight at the optimum, meaning they achieved the maximum envy level (within tolerance).
lp_rounds list[LinprogDiagnostics] | None

Optional solver diagnostics captured after each LP solve.
Notes

The modiclus is a nucleolus-type selection concept defined on pairwise differences of excesses (often interpreted as "maximum envy" across coalitions). This implementation mirrors the standard lexicographic LP refinement approach used for the nucleolus, but the constraints are indexed by ordered pairs (S, T) rather than coalitions S.

modiclus 

modiclus(
    game,
    *,
    tol=1e-09,
    max_rounds=200,
    max_players=12,
    require_complete=True,
)

Compute the modiclus of a TU cooperative game.

Definition

Let the excess of a coalition S under an allocation x be

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

where \(x(S) = \sum_{i \in S} x_i\).

The modiclus is defined via the envy (difference of excesses) between two coalitions S and T:

\[ \operatorname{envy}(S, T; x) = e(S, x) - e(T, x) = (v(S) - x(S)) - (v(T) - x(T)). \]

The modiclus is the allocation x (typically over the pre-imputation set) that lexicographically minimizes the vector of envies over all ordered pairs \((S, T)\) with \(S \ne T\), sorted from largest to smallest.

Algorithm

This implementation follows a nucleolus-style lexicographic LP refinement:

  1. Solve an LP minimizing the maximum envy over all remaining pairs (S, T).
  2. Identify tight pairs that achieve the maximum envy (within tolerance).
  3. Promote a subset of tight pairs to equality constraints (chosen so as to increase the rank of the equality system over x).
  4. Repeat until x is uniquely determined or no pairs remain.

Parameters:

Name Type Description Default
game GameProtocol

TU game.

 required
tol float

Numerical tolerance for tightness detection and for snapping tiny optimal levels to 0.

 1e-09
max_rounds int

Maximum number of lexicographic refinement rounds.

 200
max_players int

Safety cap. The number of envy constraints scales as \(O((2^n)^2)\), so the problem becomes large very quickly.

 12
require_complete bool

If True, require a complete characteristic function (all 2^n coalition values explicitly present in game.v). If False, missing coalitions are treated as value 0 via game.value.

 True

Returns:

Type Description
ModiclusResult

Allocation, lexicographic envy levels, and optional diagnostics.
Notes
  • This implementation enforces efficiency only (pre-imputation set): \(\sum_i x_i = v(N)\). It does not enforce individual rationality.
  • The modiclus is sensitive to the set of coalitions considered; here we include all proper, non-empty coalitions and all ordered pairs (S, T), S != T.
  • Requires SciPy/HiGHS at runtime (pip install "tucoopy[lp]").
References

The modiclus is introduced in the TU cooperative game theory literature as a nucleolus-type solution defined on pairwise differences of excesses. For a detailed treatment, see standard references on nucleolus-like solution concepts and their variants.