tucoopy.games.flow¶
Flow games.¶
In a flow game, players own edges of a capacitated directed network. A coalition \(S\) may use exactly the edges owned by its members, and its worth is the maximum \(s\)-\(t\) flow achievable in the induced network.
Notes
This implementation uses the Edmonds–Karp algorithm and is intended for small networks and examples.
See Also
tucoopy.games.mst.mst_game
Examples:
>>> from tucoopy.games.flow import OwnedEdge, flow_game
>>> edges = [OwnedEdge(0, 1, 1.0, owner=0), OwnedEdge(1, 2, 1.0, owner=1)]
>>> g = flow_game(n_players=2, n_nodes=3, edges=edges)
>>> g.value(0b11)
1.0
OwnedEdge dataclass ¶
An owned directed edge in a flow game.
Attributes:
| Name | Type | Description |
|---|---|---|
u, v | Tail and head node indices. | |
capacity | float | Non-negative edge capacity. |
owner | int | Player index that owns the edge. |
Examples:
>>> OwnedEdge(0, 1, 2.0, owner=0)
OwnedEdge(u=0, v=1, capacity=2.0, owner=0)
flow_game ¶
flow_game(
*,
n_players,
n_nodes,
edges,
player_labels=None,
source=0,
sink=None,
)
Construct a flow game (TU) from a directed capacitated network with edge ownership.
Coalition \(S\) can use exactly the edges whose owner is in \(S\), and its worth is the maximum \(s-t\) flow in that induced network.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
n_players | int | Number of players (edge owners). | required |
n_nodes | int | Number of nodes in the network. | required |
edges | list of OwnedEdge | List of owned edges. | required |
player_labels | list of str | Optional labels for players. | None |
source | int | Source node index (default 0). | 0 |
sink | int | Sink node index (default n_nodes-1). | None |
Returns:
| Type | Description |
|---|---|
Game | Cooperative game instance representing the flow game. |
Raises:
| Type | Description |
|---|---|
InvalidParameterError | If n_nodes < 2, source/sink out of range, or edge owner/endpoints out of range. |
Examples:
>>> from tucoopy.games.flow import flow_game, OwnedEdge
>>> edges = [OwnedEdge(0, 1, 5, 0), OwnedEdge(1, 2, 3, 1)]
>>> g = flow_game(n_players=2, n_nodes=3, edges=edges)
>>> g.n_players
2
>>> g.value(3)
3.0