`tucoopy.geometry.bargaining_set`¶

Aumannâ€“Maschler bargaining set (small-$n$ helpers).¶

This module implements a pragmatic, small-$n$ oriented toolkit around the bargaining set for transferable-utility (TU) cooperative games.

The bargaining set is defined via objections and counter-objections and is computationally expensive in general. The implementation here focuses on:

clear data structures (Objection, CounterObjection),
a test function suitable for diagnostics/visualization workflows, and
a sampling-based approach (via :func:tucoopy.geometry.sampling.sample_imputation_set) for exploring candidate points when exhaustive checks are infeasible.

Notes

This module is intended for use with tucoopy.geometry.ImputationSet and other core-family objects. For large games, prefer approximate workflows and explicit limits (number of samples, max attempts, etc.).

Examples:

Create a small game and instantiate the bargaining-set helper:

>>> from tucoopy import Game
>>> from tucoopy.geometry.bargaining_set import BargainingSet
>>> 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,
... })
>>> bs = BargainingSet(g)
>>> isinstance(bs, BargainingSet)
True

BargainingCheckResult `dataclass` ¶

Result of a bargaining-set membership check.

Attributes:

Name	Type	Description
`in_set`	`bool`	True iff the allocation passed the (heuristic) bargaining-set test.
`witness`	`Objection \| None`	If `in_set` is False, an objection (S, y) that has no counterobjection under the heuristic search strategy. If `in_set` is True, this is None.

Notes

This result is intended primarily for debugging/visualization: a non-empty witness helps explain why a point was rejected.

Examples:

>>> from tucoopy.geometry.bargaining_set import BargainingCheckResult
>>> res = BargainingCheckResult(in_set=True)
>>> res.in_set
True

BargainingSet `dataclass` ¶

Aumannâ€“Maschler bargaining set (small-$n$ heuristic membership test).

Definition (informal)

Let $x$ be an imputation (efficient and individually rational). An objection $(S, y)$ by $i$ against $j$ is "justified" if it improves coalition members in $S$ (and strictly improves $i$). The bargaining set contains imputations for which every objection has a counterobjection.

This object provides:

contains(x) / check(x) as a heuristic membership test ($x$ must be an imputation)
sample_points(...) rejection sampling for visualization

Implementation scope

This implementation is intended for very small games (default $n \leq 4$). It searches over coalitions and constructs objections/counterobjections using a closed-form solver for the subproblem:

\[ \text{maximize } z_j \]

subject to

\[ \begin{cases} \sum_{k \in T} z_k = v(T), \\ z_k \geq \text{lower}_k \text{ for } k \in T \end{cases} \]

That subproblem is trivial: assign all players at their lower bounds and give all slack to the maximized player.

Parameters:

Name	Type	Description	Default
`game`	`GameProtocol`	TU game.	required
`tol`	`float`	Numerical tolerance used for comparisons (excess positivity, strict improvements, etc.).	`DEFAULT_BARGAINING_TOL`
`max_objections_per_pair`	`int`	Limit the number of candidate coalitions S tried for each ordered pair (i, j). Candidates are sorted by descending excess and truncated.	`8`
`n_max`	`int`	Safety limit on the number of players. The search is exponential in n.	`DEFAULT_MAX_PLAYERS`

Notes

This is not a complete bargaining-set algorithm for arbitrary $n$. It is meant for pedagogical use and visualization.
The method can return false negatives/positives in principle, because it truncates the search (max_objections_per_pair) and uses simple tie-breaking.

Examples:

Basic construction and type-checking:

>>> 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,
... })
>>> bs = BargainingSet(g, max_objections_per_pair=4)
>>> x = [1.0, 1.0, 2.0]
>>> isinstance(bs.contains(x), bool)
True

Sampling imputations (deterministic with a seed):

>>> pts = bs.sample_points(n_samples=20, seed=0, max_points=5)
>>> len(pts) <= 5
True

check ¶

check(
    x,
    *,
    search="top_excess",
    seed=None,
    max_objections_per_pair=None,
    max_counterobjections_per_pair=None,
    record_counter_attempts=False,
)

Heuristic bargaining-set membership test (small $n$).

Overview

Verify that $x$ is an imputation.
For each ordered pair $(i, j)$, enumerate candidate coalitions $S$ with: $i \in S$, $j \notin S$, and positive excess $e(S,x) > \text{tol}$.
For each candidate $S$ (up to max_objections_per_pair):
- construct an objection $(S, y)$ by maximizing $y_i$ subject to $y_k \geq x_k$ for $k \in S$ and $\sum_{k \in S} y_k = v(S)$.
- if $y_i > x_i + \text{tol}$, this is a genuine objection candidate.
- if no counterobjection exists for it, return a witness.
If every considered objection is countered, return in_set=True.

Parameters:

Name	Type	Description	Default
`x`	`list[float]`	Candidate allocation (must be an imputation).	required
`search`	`str`	Search policy for objection coalitions S and counterobjection coalitions T. One of: `"top_excess"`, `"random"`, `"all"`.	`'top_excess'`
`seed`	`int \| None`	Optional RNG seed used when `search="random"`.	`None`
`max_objections_per_pair`	`int \| None`	Optional override for the per-pair limit on objection coalitions S.	`None`
`max_counterobjections_per_pair`	`int \| None`	Optional limit for counterobjection coalitions T tested per objection.	`None`
`record_counter_attempts`	`bool`	If True and the check fails, include attempted counterobjections in the witness.	`False`

Returns:

Type	Description
`BargainingCheckResult`	Membership decision plus optional witness objection.

Notes

Candidate coalitions S are sorted by descending excess to find strong objections first.
The search is truncated; passing this test does not formally prove bargaining-set membership for arbitrary games.

contains ¶

contains(x)

Return True iff $x$ passes the bargaining-set heuristic check.

explain ¶

explain(
    x,
    *,
    max_objections_per_pair=None,
    max_counterobjections_per_pair=None,
    search="top_excess",
    seed=None,
    record_counter_attempts=False,
)

Return a short human-readable explanation of bargaining-set membership.

Notes

This is a thin wrapper around check.

sample_point ¶

sample_point(
    *, n_samples=200, seed=None, max_attempts=None
)

Return one bargaining-set point found by sampling, or None.

This is a convenience wrapper around sample_points.

sample_points ¶

sample_points(*, n_samples, seed=None, max_attempts=None)

Sample bargaining-set points for visualization (small $n$) via rejection sampling.

Procedure

Draw candidate points from the imputation set using tucoopy.geometry.sampling.sample_imputation_set.
Keep points that satisfy contains.

Parameters:

Name	Type	Description	Default
`n_samples`	`int`	Target number of accepted points.	required
`seed`	`int \| None`	Optional seed for the underlying imputation sampler.	`None`
`max_attempts`	`int \| None`	Maximum number of candidate points tested. If None, defaults to `200 * n_samples`.	`None`

Returns:

Type	Description
`list[list[float]]`	Accepted bargaining-set points. May contain fewer than `n_samples` points if `max_attempts` is reached.

Notes

Degenerate imputation simplex: If the imputation set is empty, returns []. If it is a singleton, returns either [x0] or [] depending on membership.

scan_imputation_grid ¶

scan_imputation_grid(
    *,
    step,
    max_points=5000,
    search="top_excess",
    seed=None,
    max_objections_per_pair=1,
    max_counterobjections_per_pair=1,
)

Scan a coarse grid over the 3-player imputation simplex (sanity-check helper).

This enumerates points in the imputation set for $n=3$ by discretizing the "slack" coordinates:

$x = l + y$ where $l$ is the imputation lower bound vector, and
$y_i \ge 0$ with $\sum_i y_i = r := v(N) - \sum_i l_i$.

The scan uses a simple grid spacing step in the payoff units of the game, then tests each point with contains.

Parameters:

Name	Type	Description	Default
`step`	`float`	Grid spacing in payoff units. Larger values mean fewer points.	required
`max_points`	`int`	Hard limit on returned points.	`5000`
`search`	`str`	Passed to `check`.	`'top_excess'`
`seed`	`str`	Passed to `check`.	`'top_excess'`
`max_objections_per_pair`	`str`	Passed to `check`.	`'top_excess'`
`max_counterobjections_per_pair`	`str`	Passed to `check`.	`'top_excess'`

Returns:

Type	Description
`list[tuple[list[float], bool]]`	List of (x, in_set) pairs. Points are returned in a deterministic order.

Notes

Implemented only for $n=3$.
This is a debugging/visualization helper; it does not provide guarantees about bargaining-set membership for arbitrary games.
The membership test requires an LP backend when non-trivial objections are present.

Examples:

>>> from tucoopy import Game
>>> from tucoopy.geometry import BargainingSet
>>> g = Game.from_coalitions(
...     n_players=3,
...     values={
...         (): 0.0,
...         (0,): 1.0, (1,): 1.2, (2,): 0.8,
...         (0, 1): 2.8, (0, 2): 2.2, (1, 2): 2.0,
...         (0, 1, 2): 4.0,
...     },
... )
>>> bs = BargainingSet(g)
>>> pts = bs.scan_imputation_grid(step=0.5)
>>> len(pts) > 0
True

CounterobjectionAttempt `dataclass` ¶

Attempt to find a counterobjection on a coalition $T$.

This is optional diagnostic information returned when a bargaining-set check fails and the caller requests counter-search details.

Examples:

>>> from tucoopy.geometry.bargaining_set import CounterobjectionAttempt
>>> att = CounterobjectionAttempt(coalition=0b101, feasible=True, achieved_maximized_value=1.0, required_value=0.5)
>>> att.feasible
True

Objection `dataclass` ¶

Objection $(S, y)$ by player $i$ against player $j$.

Background

In the Aumannâ€“Maschler bargaining set, an objection is a pair $(S, y)$ where:

$S$ is a coalition such that $i \in S$ and $j \notin S$
$y$ is an allocation for coalition $S$ (extended to $N$ by leaving non-members as $0$), satisfying feasibility on $S$ and improving all members of $S$ relative to $x$

In this implementation we follow the common imputation-based notion:

$y$ is feasible for $S$: $$\sum_{k in S} y_k = v(S)$$
each $k \in S$ is at least as well off as in $x: y_k \geq x_k$
player $i$ strictly improves: $y_i > x_i$

The pair $(i, j)$ identifies "who objects against whom".

Attributes:

Name	Type	Description
`i, j`		Player indices (0-based).
`coalition`	`Coalition`	Coalition mask S.
`y`	`list[float]`	Full length-n vector representing the objection allocation (entries outside S are typically unused / 0 in this implementation).

Examples:

>>> from tucoopy.geometry.bargaining_set import Objection
>>> obj = Objection(i=0, j=2, coalition=0b011, y=[1.5, 0.5, 0.0])
>>> (obj.i, obj.j, obj.coalition)
(0, 2, 3)

tucoopy.geometry.bargaining_set¶

Aumannâ€“Maschler bargaining set (small-\(n\) helpers).¶

BargainingCheckResult dataclass ¶

BargainingSet dataclass ¶

check ¶

contains ¶

explain ¶

sample_point ¶

sample_points ¶

scan_imputation_grid ¶

CounterobjectionAttempt dataclass ¶

Objection dataclass ¶

`tucoopy.geometry.bargaining_set`¶

BargainingCheckResult `dataclass` ¶

BargainingSet `dataclass` ¶

CounterobjectionAttempt `dataclass` ¶

Objection `dataclass` ¶