Pular para conteúdo

tucoopy.transforms.communication

Communication constraints and restricted games.

This module currently provides the Myerson restriction induced by a communication graph. It constructs a new TU game where a coalition's worth is the sum of the worths of its connected components in the communication graph.

myerson_restriction 

myerson_restriction(
    game, *, edges, require_complete=True, max_players=16
)

Compute the Myerson restriction of a TU game induced by a communication graph.

In cooperative games with communication constraints, players can only cooperate effectively within connected components of the communication graph. Given an undirected graph \(G=(N,E)\) and a coalition \(S \subseteq N\), let \(\{C_1, \dots, C_k\}\) be the connected components of the subgraph induced by \(S\). The Myerson restricted game \(v_G\) is defined by:

\[ v_G(S) = \sum_{C \in \mathrm{components}_G(S)} v(C), \]

with the TU convention \(v_G(\varnothing)=0\).

Intuition: A coalition \(S\) can only realize the value of the groups that can actually communicate (the connected components). The total value is the sum of the values generated by each communicating group.

Parameters:

Name Type Description Default
game Game

Original TU game \(v\) on the player set \(N\).

 required
edges Iterable[tuple[int, int]]

Undirected edges of the communication graph \(G\) as pairs of player indices. Self-loops are ignored. Duplicate edges are allowed.

 required
require_complete bool

If True, require game to specify a complete characteristic function, i.e. values for all \(2^n\) coalitions. This restriction is useful to avoid silently treating missing coalitions as 0 when Game.value() is used.

 True
max_players int

Safety limit for the number of players. This routine enumerates all coalitions and is therefore exponential in n_players.

 16

Returns:

Type Description
Game

A new complete TU game with characteristic function \(v_G\).

Raises:

Type Description
NotSupportedError

If n_players > max_players.
InvalidGameError

If require_complete=True and the game does not specify all \(2^n\) coalition values.
InvalidParameterError

If any edge endpoint is out of range.
Notes
  • Complexity: This function enumerates all coalitions, so its runtime and memory scale as \(\Theta(2^n)\). Use max_players as a guardrail.
  • The resulting game is complete: it explicitly stores values for every coalition.
  • This function implements the restricted game used to define the Myerson value (the Shapley value of \(v_G\)) in communication situations.

Examples:

Restrict a 3-player game with a path graph 0--1--2:

>>> gG = myerson_restriction(g, edges=[(0, 1), (1, 2)])
>>> gG.value(0)  # empty coalition
0.0

If players 0 and 2 cannot communicate directly (only through 1), then coalition {0,2} has two singleton components:

>>> from tucoopy.base.coalition import mask_from_players
>>> S = mask_from_players([0, 2])
>>> gG.value(S) == g.value(mask_from_players([0])) + g.value(mask_from_players([2]))
True