Pular para conteúdo

tucoopy.diagnostics.blocking_regions

Blocking regions diagnostics (n=3).

This module computes max-excess blocking regions inside the imputation simplex. It is intended for visualization and explanation: regions can be rendered as polygons in barycentric coordinates.

Notes

The polygon clipping routine is implemented for n=3 only (triangle simplex). For other n this module returns an empty set of regions.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.diagnostics.blocking_regions import blocking_regions
>>> g = Game.from_coalitions(n_players=3, values={0: 0, 7: 1})
>>> br = blocking_regions(g)
>>> br.coordinate_system
'barycentric_imputation'

BlockingRegion dataclass

A single blocking region in barycentric coordinates.

Attributes:

Name Type Description
coalition_mask int

Coalition mask S that is the (one of the) max-excess blockers in this region. For n=2, the only proper non-empty coalitions are {0} and {1} (masks {1,2}). For n=3, proper non-empty coalitions are masks in {1,2,3,4,5,6}.
vertices list[list[float]]

Region vertices in barycentric coordinates b of the imputation simplex. Each vertex is a length-n vector b with: - b_i >= 0 - sum_i b_i = 1

Examples:

>>> r = BlockingRegion(coalition_mask=3, vertices=[[1.0, 0.0, 0.0]])
>>> r.coalition_mask
3

BlockingRegions dataclass

Blocking regions in the imputation simplex (implemented for \(n=3\)).

Concept

For an allocation \(x\), the excess of a coalition \(S\) is:

\[ e(S, x) = v(S) - x(S). \]

A coalition \(S\) is said to be a (max-excess) blocker at \(x\). In our sign convention, blocking corresponds to positive excess (the coalition can improve upon \(x\)):

  1. It can block: \(e(S, x) > 0\)
  2. It attains the maximum excess among proper non-empty coalitions: \(e(S, x) \geq e(T, x)\) for all proper non-empty \(T \neq N\).

This routine partitions (parts of) the imputation simplex into regions where the identity of the max-excess blocker is constant.

Coordinate system

The computation is performed in barycentric coordinates \(b\) over the imputation simplex. Let:

  • \(l_i = v(\{i\})\) (individual rationality lower bounds)
  • \(r = v(N) - \sum_{i=1}^n l_i\) (simplex "radius")

Any imputation can be written as:

\[ x = l + r b, \]

where \(b\) is barycentric:

\[ b_i \geq 0, \; \sum_i b_i = 1. \]

Internally, we represent \(b\) in 2D using \((b_0, b_1)\), with:

\[ b_2 = 1 - b_0 - b_1, \]

and the simplex is the triangle with vertices \((b_0, b_1)\) in:

\[ (1,0), (0,1), (0,0). \]
Notes
  • This is currently implemented only for \(n=3\) because it uses planar polygon clipping (half-plane intersection).
  • If the imputation set is empty or degenerates to a point (\(r \leq tol\)), the result is empty.
  • Regions are computed by intersecting the simplex triangle with linear half-planes derived from comparisons:
\[e (S, x) \geq e(T, x) \]

and the blocking condition:

\[ e(S, x) >= 0. \]

Attributes:

Name Type Description
coordinate_system str

Always "barycentric_imputation".
regions list[BlockingRegion]

List of BlockingRegion polygons.
See also

tucoopy.geometry.imputation.ImputationSet The imputation simplex representation used here.

Examples:

>>> br = BlockingRegions(coordinate_system="barycentric_imputation", regions=[])
>>> br.regions
[]

blocking_regions 

blocking_regions(game, *, tol=DEFAULT_GEOMETRY_TOL)

Compute max-excess blocking regions in the imputation simplex (\(n=3\)).

Definition

For an allocation \(x\), define the coalition excess:

\[ e(S, x) = v(S) - x(S),\\ x(S) = \sum_{i \in S} x_i. \]

A coalition S is a max-excess blocker at x if:

  1. \(e(S, x) \geq 0\)
  2. \(e(S, x) \geq e(T, x)\) for all proper non-empty coalitions \(T \neq S\).

This routine returns polygonal regions in the imputation simplex where a fixed coalition S satisfies the two conditions above.

Coordinate system

For \(n=3\), every imputation can be written as:

\[ x = l + r b, \]

where:

  • \(l_i = v(\{i\})\)
  • \(r = v(N) - \sum_i l_i\)
  • \(b\) is barycentric: \(b_i \geq 0\) and \(\sum_i b_i = 1\)

The returned polygons use \(b\) as coordinates (stored explicitly as length-3 vectors), but internally the clipping is done in the 2D chart \((b_0, b_1)\), with \(b_2 = 1 - b_0 - b_1\).

Parameters:

Name Type Description Default
game GameProtocol

TU game.

 required
tol float

Numerical tolerance used to: - detect degenerate imputation simplex (r <= tol), - soften half-plane comparisons, - de-duplicate nearly-identical polygon vertices.

 DEFAULT_GEOMETRY_TOL

Returns:

Type Description
BlockingRegions

A container with regions, each giving a coalition mask S and a polygon (list of barycentric vertices) describing where S is the max-excess blocker.
Notes
  • Implemented for n=3. For n != 3 this returns no regions.
  • If the imputation set is empty or a singleton (r <= tol), returns no regions.
  • Ties between coalitions (multiple maximizers) are not explicitly merged; you may see overlapping/adjacent regions due to numerical tolerances.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.diagnostics.blocking_regions import blocking_regions
>>> g = Game.from_value_function(3, lambda S: float(len(S)))  # additive
>>> br = blocking_regions(g)
>>> br.regions
[]