Abstract
Coalition formation is a problem of great interest in AI, allowing groups of autonomous, individually rational agents to form stable teams. Automating the negotiations underlying coalition formation is, naturally, of special concern. However, research to date in both AI and economics has largely ignored the potential presence of uncertainty in coalitional bargaining. We present a model of discounted coalitional bargaining where agents are uncertain about the types (or capabilities) of potential partners, and hence the value of a coalition. We cast the problem as a Bayesian game in extensive form, and describe its Perfect Bayesian Equilibria as the solutions to a polynomial program. We then present a heuristic algorithm using iterative coalition formation to approximate the optimal solution, and evaluate its performance.
Introduction
In multi-agent systems, coalition formation allows agents to join forces to achieve goals beyond their individual capabilities. While classical models typically assume "full information"—where every agent knows the exact capabilities of others—real-world scenarios are fraught with uncertainty. Whether hiring a contractor or forming a startup, the true skills of potential partners are often unknown, leading to uncertainty regarding the team's eventual success. This research addresses the gap in coalitional bargaining under type uncertainty, exploring how agents should propose deals, accept offers, and update beliefs about their peers through strategic negotiation.
Methodology
The problem is approached through two primary lenses: a theoretical framework and a practical heuristic.
Theoretical Model
The authors formulate coalitional bargaining as a Bayesian extensive game with observable actions. They demonstrate that finding the Perfect Bayesian Equilibrium (PBE)—the optimal strategy for rational play—can be modeled as a polynomial program. While this provides a mathematically rigorous solution, it is computationally intractable for non-trivial problems due to exponential complexity.
The BE Heuristic Algorithm
To overcome computational barriers, the paper proposes a heuristic algorithm (BE) characterized by:
- Limited Lookahead: Agents plan only a few rounds into the future.
- Fixed-Belief Equilibrium: During lookahead, agents assume beliefs remain static to simplify calculations, akin to receding horizon control.
- Bayesian Updating: Agents use Bayes' Rule after each round to update their probability distributions over others' types based on observed bargaining behavior.
- Reinforcement Learning (RL): In repeated interactions, agents carry over learned information across episodes to refine their strategies.
Experimental Setup
The algorithm was evaluated using synthetic simulations designed to test specific strategic challenges:
- Settings A & B: Involved 5 agents with 5 possible types, including "detrimental" agents who reduce coalition value. This tested the algorithm's ability to identify and exclude unproductive partners.
- Setting C: Involved 8 agents with 2 types (Type A vs. Type B) to evaluate performance in larger groups with varying relative power dynamics.
Key Results and Insights
The proposed BE algorithm demonstrated significant improvements over traditional baselines.
Performance and Efficiency
The BE algorithm consistently captured 91% to 95% of the "optimal" reward (the reward achievable with full information). In contrast, the KST baseline—which does not account for evolving beliefs—often captured only 50% to 60% of the optimal reward. The heuristic proved robust even with minimal lookahead depths (e.g., 2 steps) and small sample sizes.
Negotiation as Information
A central insight is that bargaining serves as a signaling mechanism. An agent's willingness to accept or reject specific offers reveals information about their type and their beliefs about others. The BE algorithm successfully learns to exclude detrimental agents, eventually forming coalitions that reflect the true power dynamics of the hidden capabilities.
The "Urgency" Effect
The research found that a lower discount factor (making time more expensive) can accelerate learning. When delay is costly, "weak" types are more likely to accept mediocre deals, making their behavior more predictable and easier to distinguish from "strong" types.
Limitations and Future Work
Despite its success, the model has several limitations:
- Scalability: The number of potential proposals grows rapidly with the number of agents, posing a challenge for larger systems.
- Action Space: The current model uses a discrete set of payoff allocations; future work should explore continuous bargaining spaces.
- Strategic Signaling: The heuristic assumes fixed beliefs during lookahead, ignoring the possibility of agents intentionally acting deceptively to manipulate others' beliefs.
- Theoretical Bounds: While empirically strong, the paper lacks formal theoretical bounds on the heuristic's proximity to the true PBE.
Summary updated