Introduction
Negotiation is a fundamental process in multi-agent systems, yet a gap persists between the symbolic logic used in AI and the numerical utility functions of game theory. Traditional bargaining models, pioneered by John Nash, often rely on numerical utilities and randomized "lotteries" to resolve ties. This paper proposes a computational model that bridges this gap by grounding negotiation in belief revision and logical "entrenchment," providing a deterministic bargaining solution justified by game-theoretic principles.
The Limits of Numerical Utility
Traditional bargaining theory treats negotiation as a numerical optimization problem. However, assigning numbers to complex preferences can obscure the underlying meaning of the items being negotiated. For instance, if two agents have conflicting goals—such as Bob wanting a child and Mary wanting to travel, while both acknowledge they cannot afford both—a numerical model might suggest a 50/50 lottery. Such a "mixed deal" fails to provide a logically consistent agreement that respects the agents' internal reasoning.
The Logic-Based Framework
The authors build their model on Nebel’s syntax-based belief revision. In this framework, each agent possesses a Demand Set—a collection of logical formulas representing their goals. Rather than numerical scores, these demands are organized into a Preference Hierarchy based on "entrenchment," where critical demands are prioritized over negotiable ones.
The central concept is the "Deal": a maximal subset of demands from both agents that remains mutually consistent. The "core" of the agreement is the intersection of all best possible deals, serving as a fair starting point for negotiation.
As shown in Table 1, different configurations of preferences lead to distinct sets of deals. The model uses a two-stage procedure:
- Core Acceptance: Agents agree to accept each other's core demands.
- Prioritized Revision: Agents use belief revision to adjust their remaining demands to ensure consistency with the established core.
Game-Theoretic Stability
To ensure the model is more than just a heuristic, the authors provide a game-theoretic justification. They prove that every "deal" defined in their logical framework corresponds to a Nash equilibrium. Furthermore, by introducing a simultaneous-offers procedure—where players repeatedly reduce demands until compatibility is reached—they demonstrate that their bargaining solution is the unique Subgame Perfect Equilibrium (SPE). This result suggests that the logical model represents the rational outcome for agents following these rules.
Computational Complexity
While the model provides a robust theoretical framework, it introduces significant computational challenges. The authors map the complexity of various tasks within the model:
- Deal Membership: Determining if a pair of demand subsets constitutes a "deal" is DP-complete.
- The Core: Identifying the core of an agreement is both NP-hard and coNP-hard.
- Agreement Inference: Deciding if a specific formula will be part of the final agreement is $\Pi^P_2$-hard.
These findings indicate that logic-based negotiation is inherently more complex than standard belief revision, reflecting the difficulty of reaching mutual agreement between competing rational agents.
Conclusion and Future Work
The proposed model offers a deterministic, logic-based alternative to traditional bargaining theory. While it provides a unique SPE, it faces limitations such as syntax dependency and high computational costs for large demand sets. Future research may explore expanding the model to multi-agent scenarios and integrating numerical preferences with logical structures to create more practical AI negotiation systems.
Summary updated