tucoopy.properties.balancedness¶
Balancedness (Bondareva–Shapley) checks via linear programming.¶
This module implements an LP-based check of balancedness, which by the Bondareva–Shapley theorem is equivalent to core non-emptiness for TU games.
Notes
The LP has one variable per non-empty, non-grand coalition, i.e. 2^n - 2. This grows quickly with n and typically requires an LP backend (SciPy HiGHS).
Examples:
>>> from tucoopy.base.game import Game
>>> from tucoopy.properties.balancedness import balancedness_check
>>> g = Game.from_coalitions(n_players=2, values={(): 0.0, (0,): 0.0, (1,): 0.0, (0, 1): 1.0})
>>> result = balancedness_check(g)
>>> result.core_nonempty
True
BalancednessResult dataclass ¶
Result of a Bondareva–Shapley balancedness check.
balancedness_check ¶
balancedness_check(game, *, tol=DEFAULT_LP_TOL)
Bondareva–Shapley theorem (LP check for core non-emptiness).
Solve:
\[\text{maximize } \sum_{\{S \neq N, S \neq \varnothing\}} \lambda_S v(S)\]
s.t.
\[ \begin{cases} \sum\limits_{S \ni i} \lambda_S = 1 \text{ for each player } i \\ \lambda_S \geq 0 \end{cases} \]
If \(\argmax > v(N) + \text{tol}\), the core is empty and \(\lambda\) is a certificate.
Warning
Requires: SciPy (pip install "tucoopy[lp]")