Bargaining Set

The core is a more restrictive solution concept. A payoff is in the core if no coalition can improve upon it for all its members. The bargaining set is generally a superset of the core.

• Core → Bargaining Set: Any payoff in the core is automatically in the bargaining set, as no coalition has any improving objection.
• Bargaining Set \ Core: Payoffs can be in the bargaining set but not the core. This happens when an objection exists, but a valid counter-objection also exists, creating a balanced tension. The bargaining set often exists (is non-empty) even when the core is empty, providing a more widely applicable stability concept for multi-agent systems.

In multi-agent system orchestration, the bargaining set provides a formal framework for stable resource and task allocation.

• Coalition Stability: Determines if a proposed division of rewards (e.g., revenue, compute resources) among collaborating agents is resilient to internal disputes.
• Negotiation Protocol Design: Informs the design of protocols where agents can formally raise and counter objections during automated negotiation, moving toward a bargaining set allocation.
• Conflict Resolution: Serves as a criterion for an orchestrator or mediator agent to evaluate and propose payoff distributions that minimize the risk of sub-coalitions defecting. It is particularly relevant for long-lived agent coalitions in domains like autonomous supply chains or federated learning consortia.

Consider three AI firms (A, B, C) forming a consortium to train a model. The value (profit) each coalition can generate is:

• Any single firm: $0
• Any pair (A,B): $90, (A,C): $80, (B,C): $70
• The grand coalition (A,B,C): $120

A proposed payoff: A=$50, B=$40, C=$30 (Total=$120).

• Objection: Coalition {A,B} could object against C. They can generate $90 on their own and propose a new split: A=$55, B=$35 (both better than $50/$40).
• Counter-Objection: Coalition {A,C} could counter-object. They can generate $80. They offer A=$50 (same as original), C=$30 (same as original). This protects A and matches C's original payoff, invalidating the {A,B} objection. Since a counter-objection exists, the original ($50,$40,$30) distribution is in the bargaining set, even though the core of this game is empty.

Determining if a given payoff vector is in the bargaining set is computationally challenging, which impacts its use in real-time agent systems.

• The problem is generally in the co-NP complexity class, as disproving membership requires finding a justified objection with no counter-objection.
• For practical agent orchestration, this necessitates:
  • Heuristic search for objections/counter-objections within bounded time.
  • Approximate stability concepts that are easier to compute.
  • Restricted domains (e.g., few agents, specific utility functions) where the problem becomes tractable. This complexity underscores the role of the bargaining set as a theoretical benchmark for stability, with simplified derivatives used in implemented negotiation protocols.

The set of payoff distributions for a coalition where no sub-group (sub-coalition) can guarantee all its members a higher payoff by breaking away. It represents a stronger stability condition than the bargaining set.

• Relationship to Bargaining Set: The core is often a subset of the bargaining set. If a payoff is in the core, it has no objections at all. A payoff in the bargaining set may have objections, but each objection has a counter-objection.
• Empty Core Problem: Many cooperative games have an empty core, meaning no distribution satisfies this strict 'no-blocking' condition. The bargaining set is often non-empty, providing a more practical solution concept.

The 'inverse engineering' of game theory, involving the design of negotiation protocols or rules (mechanisms) so that the strategic interactions of self-interested agents produce a desired social outcome, like efficiency or truth-telling.

• Goal Alignment: Designs protocols where agents' dominant strategies lead to a globally optimal result (e.g., the Vickrey auction).
• Revelation Principle: A key theorem stating any equilibrium outcome of any complex mechanism can be replicated by a simpler direct revelation mechanism where agents truthfully report their private types.
• Application to MAS: Used to design auction-based task allocation, fair division protocols, and voting systems for agent collectives.

A state of resource allocation or agreement where it is impossible to make any one agent better off without making at least one other agent worse off. It defines an efficiency frontier for negotiations.

• Negotiation Goal: Rational agents seek Pareto improvements—moves that benefit at least one agent without harming others—until a Pareto optimal outcome is reached.
• Connection to Bargaining: Both the Nash Bargaining Solution and payoff vectors in the bargaining set are required to be Pareto optimal within their respective coalitions. An inefficient distribution would invite objections.

A framework for modeling multi-agent coordination problems where variables, domains, and constraints are distributed among agents, who must collaboratively find a solution optimizing a global objective function.

• Negotiation as Search: Agents negotiate to find variable assignments that satisfy local and global constraints while maximizing utility, analogous to finding a stable payoff in a coalition.
• Algorithms: Solved using algorithms like ADOPT (Asynchronous Distributed OPTimization) or DPOP (Distributed Pseudotree Optimization Procedure).
• Use Case: Directly applicable to task scheduling, resource allocation, and sensor network problems where agents must reason about dependencies.