Skip to content

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).