`tucoopy.base.coalition`¶

Coalition (bitmask) utilities.¶

In tucoopy, a coalition is represented as a non-negative integer bitmask:

Player \(i\) corresponds to bit (1 << i).
The empty coalition \(\varnothing\) is 0.
The grand coalition \(N\) is (1 << n_players) - 1.

This convention is used across the package (games, solutions, geometry, and diagnostics) because it is compact and fast.

The helpers in this module implement the basic iteration patterns needed by cooperative game algorithms:

Iterate all coalitions: all_coalitions
Iterate subcoalitions (submasks): subcoalitions
Convert between bitmasks and player lists: players, mask_from_players
Efficiently compute coalition sums: coalition_sum, coalition_sums

Notes

All functions assume 0-indexed players.

Examples:

Basic coalition encoding:

>>> from tucoopy.base.coalition import mask_from_players, players
>>> S = mask_from_players([0, 2])  # players {0,2}
>>> S
5
>>> players(S)
[0, 2]

all_coalitions ¶

all_coalitions(n_players)

Iterate over all coalitions of n_players as integer bitmasks.

Coalitions are represented as bitmasks in the range

\[ 0, 1, \dots, 2^n - 1, \]

where bit i indicates whether player \(i\) is in the coalition.

Parameters:

Name	Type	Description	Default
`n_players`	`int`	Number of players `n` (must be >= 0).	required

Yields:

Type	Description
`Coalition`	Coalition bitmask (an `int`).

Raises:

Type	Description
`InvalidCoalitionError`	If `n_players < 0`.

Examples:

All coalitions for n=2::

>>> list(all_coalitions(2))
[0, 1, 2, 3]

Notes

The number of yielded masks is 2**n_players.

coalition_sum ¶

coalition_sum(coalition, x, *, n_players)

Sum an allocation vector over a coalition.

Computes:

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

Parameters:

Name	Type	Description	Default
`coalition`	`Coalition`	Coalition bitmask `S`.	required
`x`	`Iterable[float]`	Allocation vector (iterable of length `n_players`).	required
`n_players`	`int`	Number of players `n`. Used to validate the length of `x` and to decide which bits are considered.	required

Returns:

Type	Description
`float`	The coalition sum `x(S)`.

Raises:

Type	Description
`InvalidCoalitionError`	If `x` has length different from `n_players`.

Examples:

>>> coalition_sum(0b101, [1.0, 2.0, 3.0], n_players=3)
4.0
>>> coalition_sum(0, [1.0, 2.0], n_players=2)
0.0

coalition_sums ¶

coalition_sums(x, *, n_players)

Precompute coalition sums \(x(S)\) for all coalitions \(S\).

Returns an array out of length 2**n_players such that:

\[ \text{out}[S] = x(S) = \sum_{i \in S} x_i. \]

Implementation

Uses an \(O(2^n)\) dynamic program based on the least-significant bit:

\[ x(S) = x(S \setminus \{i\}) + x_i, \]

where \(i\) is the index of the least-significant set bit of \(S\).

Parameters:

Name	Type	Description	Default
`x`	`Iterable[float]`	Allocation vector (iterable of length `n_players`).	required
`n_players`	`int`	Number of players `n`.	required

Returns:

Type	Description
`list[float]`	List `out` with `out[mask] = x(mask)` for all masks in `0..(1<<n_players)-1`.

Raises:

Type	Description
`InvalidCoalitionError`	If `x` has length different from `n_players`.

Examples:

>>> out = coalition_sums([1.0, 2.0, 3.0], n_players=3)
>>> out[0]          # empty coalition
0.0
>>> out[0b101]      # players {0,2}
4.0
>>> out[0b111]      # grand coalition
6.0

Notes

This is a building block for excess/surplus computations, where many coalition sums are needed repeatedly.

grand_coalition ¶

grand_coalition(n_players)

Return the grand coalition mask (1<<n) - 1.

Parameters:

Name	Type	Description	Default
`n_players`	`int`	Number of players `n` (must be >= 0).	required

Returns:

Type	Description
`Coalition`	Bitmask for the grand coalition (all players included).

Raises:

Type	Description
`InvalidCoalitionError`	If `n_players < 0`.

Examples:

>>> grand_coalition(3)
7
>>> bin(grand_coalition(4))
'0b1111'

mask_from_players ¶

mask_from_players(ps)

Build a coalition mask from an iterable of player indices.

Parameters:

Name	Type	Description	Default
`ps`	`Iterable[int]`	Iterable of player indices (each must be >= 0).	required

Returns:

Type	Description
`Coalition`	Coalition bitmask.

Raises:

Type	Description
`InvalidCoalitionError`	If any player index is negative.

Examples:

>>> mask_from_players([0, 2])
5
>>> mask_from_players([])
0

Notes

Duplicate indices are harmless (bitwise OR).

players ¶

players(coalition, *, n_players)

Convert a coalition mask to the sorted list of player indices.

Parameters:

Name	Type	Description	Default
`coalition`	`Coalition`	Coalition bitmask (must be >= 0).	required
`n_players`	`int`	Number of players `n` (must be >= 0). Bits above `n-1` are ignored.	required

Returns:

Type	Description
`list[int]`	Sorted list of player indices included in the coalition.

Raises:

Type	Description
`InvalidCoalitionError`	If `coalition < 0` or `n_players < 0`.

Examples:

>>> players(0b101, n_players=3)
[0, 2]
>>> players(0b101, n_players=2)  # ignores bit 2 because n_players=2
[0]

size ¶

size(coalition)

Return the number of players in a coalition (popcount).

Parameters:

Name	Type	Description	Default
`coalition`	`Coalition`	Coalition bitmask (must be >= 0).	required

Returns:

Type	Description
`int`	The coalition cardinality `\|S\|`.

Raises:

Type	Description
`InvalidCoalitionError`	If `coalition < 0`.

Examples:

>>> size(0b101)
2
>>> size(0)
0

subcoalitions ¶

subcoalitions(coalition)

Iterate over all subcoalitions \(T \subseteq S\) of a coalition \(S\) (as submasks).

This yields all submasks of \(S\) (including \(S\) itself and the empty coalition \(\varnothing\)) using the classic bit-trick:

T = S
while True:
    yield T
    if T == 0: break
    T = (T - 1) & S

Parameters:

Name	Type	Description	Default
`coalition`	`Coalition`	Coalition bitmask `S` (must be >= 0).	required

Yields:

Type	Description
`Coalition`	Subcoalition bitmask `T`.

Raises:

Type	Description
`InvalidCoalitionError`	If `coalition < 0`.

Examples:

Subcoalitions of S = 0b101 (players {0,2})::

>>> list(subcoalitions(0b101))
[5, 4, 1, 0]

Notes

The order is descending by construction (starting at S down to 0).
Number of yielded masks is 2**k where k = popcount(S).

tucoopy.base.coalition¶

Coalition (bitmask) utilities.¶

all_coalitions ¶

coalition_sum ¶

coalition_sums ¶

grand_coalition ¶

mask_from_players ¶

players ¶

size ¶

subcoalitions ¶

`tucoopy.base.coalition`¶