tucoopy.geometry.imputation_set¶

Compute the individual-rationality lower bounds for the imputation set.

In a TU cooperative game with characteristic function \(v\), the imputation set requires individual rationality:

Define the lower bounds

This function returns the vector \(l = (l_1,\dots,l_n)\).

Parameters:

Returns:

Examples:

Minimal runnable example using a tiny dummy game (3 players)::

>>> class _G:
...     n_players = 3
...     grand_coalition = (1 << 3) - 1
...     def value(self, S: int) -> float:
...         # singleton values: v({0})=1, v({1})=2, v({2})=0.5
...         return {1: 1.0, 2: 2.0, 4: 0.5}.get(S, 0.0)
...
>>> imputation_lower_bounds(_G())
[1.0, 2.0, 0.5]

Return the imputation set as a polyhedral set (H-representation).

The imputation set is the intersection of the efficiency hyperplane with the individual-rationality halfspaces:

Parameters:

Returns:

Examples:

A 2-player game with v(N)=5 and singleton values (1,2)::

>>> class _G:
...     n_players = 2
...     grand_coalition = 3
...     def value(self, S: int) -> float:
...         return {1: 1.0, 2: 2.0, 3: 5.0}.get(S, 0.0)
...
>>> poly = imputation_polyhedron(_G())
>>> poly.contains([1.0, 4.0])
True
>>> poly.contains([0.5, 4.5])  # violates x0 >= 1
False

Test whether an allocation belongs to the imputation set.

The imputation set for a TU game \(v\) is the set of allocations that are:

• Efficient (feasible for the grand coalition):

• Individually rational:

Parameters:

Returns:

Examples:

A 2-player dummy game where \(v(\{0\})=1\), \(v(\{1\})=2\), \(v(N)=5\)::

>>> class _G:
...     n_players = 2
...     grand_coalition = 3
...     def value(self, S: int) -> float:
...         return {1: 1.0, 2: 2.0, 3: 5.0}.get(S, 0.0)
...
>>> is_in_imputation_set(_G(), [1.0, 4.0])
True
>>> is_in_imputation_set(_G(), [0.9, 4.1])  # violates x0 >= 1
False
>>> is_in_imputation_set(_G(), [1.0, 3.9])  # not efficient (sum != 5)
False

Return the pre-imputation set as a polyhedral (affine) set.

The pre-imputation set consists of allocations that satisfy only efficiency:

with no lower bounds \(x_i \ge v(\{i\})\).

Parameters:

Returns:

Examples:

For a 3-player game with v(N)=10 , the set is the plane x0+x1+x_2=10::

>>> class _G:
...     n_players = 3
...     grand_coalition = 7
...     def value(self, S: int) -> float:
...         return 10.0 if S == 7 else 0.0
...
>>> poly = preimputation_polyhedron(_G())
>>> poly.contains([3.0, 3.0, 4.0])
True
>>> poly.contains([3.0, 3.0, 3.9])
False

Compute the Euclidean projection onto the imputation set.

The imputation set is

This routine returns the closest point (in Euclidean norm) in $\mathcal{I}(v)to a given vector $\hat{x} \in \mathbb{R}^n.

Parameters:

Returns:

Examples:

2 players, singleton bounds (1,2) and v(N)=5 => imputation is segment between (3,2) and (1,4). Projecting [10, -10] lands at the nearest endpoint::

>>> class _G:
...     n_players = 2
...     grand_coalition = 3
...     def value(self, S: int) -> float:
...         return {1: 1.0, 2: 2.0, 3: 5.0}.get(S, 0.0)
...
>>> proj = project_to_imputation(_G(), [10.0, -10.0])
>>> proj.feasible
True
>>> round(sum(proj.x), 10)
5.0
>>> proj.x[0] >= 1.0 and proj.x[1] >= 2.0
True

Empty imputation set example (sum singletons > v(N))::

>>> class _Bad:
...     n_players = 2
...     grand_coalition = 3
...     def value(self, S: int) -> float:
...         return {1: 5.0, 2: 5.0, 3: 3.0}.get(S, 0.0)
...
>>> proj = project_to_imputation(_Bad(), [0.0, 0.0])
>>> proj.feasible
False