tucoopy.properties.convexity¶
Convexity and concavity checks for TU cooperative games.¶
This module provides recognizers for:
- Convex (supermodular) games, and
- Concave (submodular) games.
Notes
Checking convexity/concavity is exponential, but can be done with a local condition on pairs of players, yielding an O(n^2 2^n) check.
Examples:
>>> from tucoopy.base.game import Game
>>> from tucoopy.properties.convexity import is_convex, is_concave
>>> g = Game.from_coalitions(n_players=2, values={(): 0.0, (0,): 1.0, (1,): 1.0, (0, 1): 3.0})
>>> is_convex(g)
True
>>> is_concave(g)
False
is_concave ¶
is_concave(game, *, eps=1e-12, max_players=12)
Concavity (submodularity): for all \(S\),\(T\),
\[v(S) + v(T) \geq v(S \cup T) + v(S \cap T)\]
is_convex ¶
is_convex(game, *, eps=1e-12, max_players=12)
Convexity (supermodularity): for all \(S\),\(T\),
\[v(S) + v(T) \leq v(S \cup T) + v(S \cap T)\]