`tucoopy.geometry.weber_set`¶

Weber set (convex hull of marginal vectors).¶

The Weber set of a TU game is defined as the convex hull of all marginal payoff vectors induced by permutations of players.

This module provides:

functions to compute marginal vectors (exact/enumerative, and sampling-based),
:class:WeberSet, a set-valued object exposing a polyhedral representation for small n via :class:tucoopy.geometry.PolyhedralSet.

Notes

The number of permutations is n! and grows quickly. Exact construction is intended for small n only; for larger games, use sampling helpers.

Examples:

Compute marginal vectors and build a Weber set for a small game:

>>> from tucoopy import Game
>>> from tucoopy.geometry.weber_set import marginal_vector, WeberSet
>>> g = Game.from_coalitions(n_players=2, values={0: 0, 1: 0, 2: 0, 3: 1})
>>> marginal_vector(g, [0, 1])
[0.0, 1.0]
>>> ws = WeberSet(g)
>>> len(ws.points())
2

WeberSet `dataclass` ¶

Weber set helper (V-representation generator).

Definition

The Weber set is the convex hull of all marginal contribution vectors:

\[ W(v) = \mathrm{conv}\{ m_\pi : \pi \in \Pi(N) \}. \]

Representation in this library

This object provides access to the generating point set \(\{m_\pi\}\) (V-representation) via :meth:points and :meth:sample_points.

For n_players in {2, 3}, this class also provides a lightweight H-representation via :attr:poly, which is useful for plotting and for reusing :class:~tucoopy.geometry.polyhedron.PolyhedralSet helpers.

Parameters:

Name	Type	Description	Default
`game`	`GameProtocol`	TU game.	required
`max_permutations`	`int`	Safety cap for full enumeration via :meth:`points`.	`720`

Examples:

For n=3, the exact generator set contains at most 3! = 6 points:

>>> from tucoopy import Game
>>> g = Game.from_coalitions(n_players=3, values={
...     0: 0.0,
...     1: 1.0, 2: 1.0, 4: 1.0,
...     3: 2.0, 5: 2.0, 6: 2.0,
...     7: 4.0,
... })
>>> ws = WeberSet(g)
>>> len(ws.points()) <= 6
True

poly `property` ¶

poly

Return an H-representation polyhedron for the Weber set (n=2 or n=3).

For n=2, the Weber set is a line segment on the efficiency line. For n=3, the Weber set is a polygon on the efficiency plane and we return a halfspace representation (inequalities + the efficiency equality).

Notes

Implemented only for n=2 and n=3.
Requires enumerating all marginal vectors via :meth:points, so it is limited by max_permutations.

mean_marginal ¶

mean_marginal()

Return the mean marginal vector under full enumeration (if feasible).

Notes

When all permutations are enumerated, this equals the Shapley value.

mean_marginal_sample ¶

mean_marginal_sample(*, n_samples, seed=None)

Approximate the mean marginal vector by sampling random permutations.

points ¶

points()

Return all marginal vectors if the permutation count is small enough.

Returns

list[list[float]]
    All marginal vectors (one per permutation).

Raises

NotSupportedError If n! > max_permutations.

Examples

>>> from tucoopy import Game
>>> from tucoopy.geometry import WeberSet
>>> g = Game.from_coalitions(n_players=2, values={0:0, 1:0, 2:0, 3:1})
>>> WeberSet(g).points()
[[0.0, 1.0], [1.0, 0.0]]

project ¶

project(dims, *, tol=DEFAULT_GEOMETRY_TOL, max_dim=3)

Project the Weber set polytope onto selected coordinates (n=2 or n=3).

Parameters:

Name	Type	Description	Default
`dims`	`tuple[int, ...] \| list[int]`	Coordinate indices to keep.	required
`tol`	`float`	Numerical tolerance passed to the underlying polyhedron.	`DEFAULT_GEOMETRY_TOL`
`max_dim`	`int`	Safety limit used by the underlying enumeration routine.	`3`

Returns:

Type	Description
`list[list[float]]`	Projected points derived from the vertex set.

sample_points ¶

sample_points(*, n_samples, seed=None)

Sample marginal vectors uniformly by sampling random permutations.

Parameters:

Name	Type	Description	Default
`n_samples`	`int`	Number of sampled permutations.	required
`seed`	`int \| None`	Optional RNG seed.	`None`

Returns:

Type	Description
`list[list[float]]`	Sampled marginal vectors.

vertices ¶

vertices(
    *,
    tol=DEFAULT_GEOMETRY_TOL,
    max_players=DEFAULT_GEOMETRY_MAX_PLAYERS,
    max_dim=3,
)

Enumerate vertices of the Weber set polytope (small n).

This is available only when :attr:poly is available (currently n=2 or n=3).

Parameters:

Name	Type	Description	Default
`tol`	`float`	Numerical tolerance passed to the underlying polyhedron.	`DEFAULT_GEOMETRY_TOL`
`max_players`	`int`	Safety cap (API consistency). This helper is intended for small n.	`DEFAULT_GEOMETRY_MAX_PLAYERS`
`max_dim`	`int`	Safety limit for vertex enumeration.	`3`

Returns:

Type	Description
`list[list[float]]`	Vertex list (possibly empty if the construction fails).

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import WeberSet
>>> g = Game.from_coalitions(n_players=2, values={0:0, 1:0, 2:0, 3:1})
>>> WeberSet(g).vertices(max_dim=2)
[[0.0, 1.0], [1.0, 0.0]]

marginal_vector ¶

marginal_vector(game, order)

Marginal contribution vector for a permutation of players.

Given a permutation (order) \(\pi\) of \(N = \{0,\dots,n-1\}\), define the growing chain of coalitions

\[ S_k = \{\pi_1, \dots, \pi_k\}, \qquad k=0,1,\dots,n, \]

with \(S_0 = \varnothing\). The marginal contribution vector \(m_\pi \in \mathbb{R}^n\) is defined by

\[ m_\pi[\pi_k] = v(S_k) - v(S_{k-1}), \qquad k=1,\dots,n. \]

Intuition

Walk through the players in the given order. When player i enters, they "add" \(v(S \cup \{i\}) - v(S)\) to the coalition. Collect these increments into a vector.

Parameters:

Name	Type	Description	Default
`game`	`GameProtocol`	TU game.	required
`order`	`Sequence[int]`	A permutation of players `0..n-1`.	required

Returns:

Type	Description
`list[float]`	Marginal vector (length `n_players`).

Raises:

Type	Description
`InvalidParameterError`	If `order` is not a valid permutation of length `n_players`.

Examples:

Minimal 2-player example:

>>> from tucoopy import Game
>>> from tucoopy.geometry import marginal_vector
>>> g = Game.from_coalitions(n_players=2, values={0:0, 1:0, 2:0, 3:1})
>>> marginal_vector(g, [0, 1])
[0.0, 1.0]
>>> marginal_vector(g, [1, 0])
[1.0, 0.0]

Minimal 3-player "unanimity" game (only grand coalition has value 1):

>>> g = Game.from_coalitions(n_players=3, values={
...     0:0, 1:0, 2:0, 4:0,
...     3:0, 5:0, 6:0,
...     7:1,
... })
>>> marginal_vector(g, [0, 1, 2])
[0.0, 0.0, 1.0]

mean_marginal_sample ¶

mean_marginal_sample(game, *, n_samples, seed=None)

Approximate the mean marginal contribution vector by sampling permutations.

Parameters:

Name	Type	Description	Default
`game`	`GameProtocol`	TU game.	required
`n_samples`	`int`	Number of random permutations to sample.	required
`seed`	`int \| None`	Optional RNG seed.	`None`

Returns:

Type	Description
`list[float]`	Approximate mean marginal vector.

Examples:

>>> from tucoopy import Game
>>> g = Game.from_coalitions(n_players=3, values={
...     0: 0.0,
...     1: 1.0, 2: 1.0, 4: 1.0,
...     3: 2.0, 5: 2.0, 6: 2.0,
...     7: 4.0,
... })
>>> m = mean_marginal_sample(g, n_samples=20, seed=0)
>>> len(m)
3

mean_marginal_vector ¶

mean_marginal_vector(game, *, max_permutations=720)

Mean marginal contribution vector across all permutations.

If all permutations are enumerated, this equals the Shapley value.

Parameters:

Name	Type	Description	Default
`game`	`GameProtocol`	TU game.	required
`max_permutations`	`int`	Safety cap: allow enumeration only if `n! <= max_permutations`.	`720`

Returns:

Type	Description
`list[float]`	Mean marginal vector (length `n_players`).

Examples:

For n=2, the mean marginal vector is easy to compute:

>>> from tucoopy import Game
>>> g = Game.from_coalitions(n_players=2, values={0: 0, 1: 0, 2: 0, 3: 1})
>>> mean_marginal_vector(g)
[0.5, 0.5]

weber_marginal_vectors ¶

weber_marginal_vectors(
    game: GameProtocol,
    *,
    max_permutations: int = 720,
    return_witness: Literal[False] = False,
) -> list[list[float]]

weber_marginal_vectors(
    game: GameProtocol,
    *,
    max_permutations: int = 720,
    return_witness: Literal[True],
) -> tuple[list[list[float]], list[tuple[int, ...]]]

weber_marginal_vectors(
    game, *, max_permutations=720, return_witness=False
)

Enumerate all marginal contribution vectors (all permutations), if feasible.

The Weber set is the convex hull of marginal vectors, one per permutation. This helper returns the generating point set:

\[ \{ m_\pi : \pi \in \Pi(N) \}. \]

Since there are \(n!\) permutations, full enumeration is only practical for small n. This routine raises if \(n!\) exceeds max_permutations.

Parameters:

Name	Type	Description	Default
`game`	`GameProtocol`	TU game.	required
`max_permutations`	`int`	Safety cap: allow enumeration only if `n! <= max_permutations`. Default 720 corresponds to n<=6.	`720`
`return_witness`	`bool`	If True, also return the permutation ("witness") that generated each marginal vector. This is useful for debugging and visualization.	`False`

Returns:

Type	Description
`list[list[float]]`	List of marginal vectors (each of length `n_players`).
`tuple[list[list[float]], list[tuple[int, ...]]]`	If `return_witness=True`: `(points, witnesses)`, where `witnesses[i]` is the permutation that generated `points[i]`.

Raises:

Type	Description
`NotSupportedError`	If `n! > max_permutations`.

Notes

For visualization you often only need the point cloud (V-rep). Converting the convex hull to an H-representation can be significantly heavier and may require additional dependencies.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import weber_marginal_vectors
>>> g = Game.from_coalitions(n_players=2, values={0:0, 1:0, 2:0, 3:1})
>>> weber_marginal_vectors(g)
[[0.0, 1.0], [1.0, 0.0]]
>>> pts, perms = weber_marginal_vectors(g, return_witness=True)
>>> perms
[(0, 1), (1, 0)]

weber_sample ¶

weber_sample(game, *, n_samples, seed=None)

Sample marginal vectors by sampling random permutations.

This is a Monte Carlo approximation to the generating set of the Weber set. It returns a list of marginal vectors \(m_\pi\), where each permutation \(\pi\) is sampled (approximately) uniformly at random.

Parameters:

Name	Type	Description	Default
`game`	`GameProtocol`	TU game.	required
`n_samples`	`int`	Number of random permutations / marginal vectors to generate.	required
`seed`	`int \| None`	Optional RNG seed.	`None`

Returns:

Type	Description
`list[list[float]]`	A list of sampled marginal vectors (each length `n_players`).

Raises:

Type	Description
`InvalidParameterError`	If `n_samples < 1`.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import weber_sample
>>> g = Game.from_coalitions(n_players=3, values={
...     0:0, 1:0, 2:0, 4:0,
...     3:0, 5:0, 6:0,
...     7:1,
... })
>>> pts = weber_sample(g, n_samples=5, seed=0)
>>> len(pts)
5

tucoopy.geometry.weber_set¶

Weber set (convex hull of marginal vectors).¶

WeberSet dataclass ¶

poly property ¶

mean_marginal ¶

mean_marginal_sample ¶

points ¶

project ¶

sample_points ¶

vertices ¶

marginal_vector ¶

mean_marginal_sample ¶

mean_marginal_vector ¶

weber_marginal_vectors ¶

weber_sample ¶

`tucoopy.geometry.weber_set`¶

WeberSet `dataclass` ¶

poly `property` ¶