Abstract
Negotiation is a very common interaction between automated agents. Many common negotiation protocols work with cardinal utilities, even though ordinal preferences, which only rank the outcomes, are easier to elicit from humans. In this work we concentrate on negotiation with ordinal preferences over a finite set of outcomes. We study an intuitive protocol for bilateral negotiation, where the two parties make offers alternately. We analyze the negotiation protocol under different settings. First, we assume that each party has full information about the other party's preference order. We provide elegant strategies that specify a sub-game perfect equilibrium for the agents. We further show how the studied negotiation protocol almost completely implements a known bargaining rule. Finally, we analyze the no information setting. We study several solution concepts that are distribution-free, and analyze both the case where neither party knows the preference order of the other party, and the case where only one party is uninformed.
Introduction
In the field of automated negotiation, the prevailing paradigm has long relied on cardinal utilities—numerical values assigned to outcomes to represent an agent's degree of preference. However, this approach faces significant hurdles in real-world applications. Humans often struggle to provide precise numerical utilities (e.g., "this outcome is worth exactly 0.72 units of utility"), whereas they find it much more natural to provide ordinal preferences (e.g., "I prefer outcome A over outcome B").
Furthermore, many classical models assume a continuum of possible agreements, such as splitting a sum of money. In practice, many negotiations involve a finite, discrete set of options, such as selecting a project lead, choosing a vacation destination, or agreeing on a specific apartment lease. This research addresses these gaps by analyzing bilateral negotiation over a finite set of outcomes using only ordinal rankings.
The VAOV Protocol
The authors focus on the Voting by Alternating Offers and Vetoes (VAOV) protocol. This mechanism is intuitive: two agents take turns proposing outcomes from a shared pool. If the receiving agent accepts the offer, the negotiation concludes. If they reject it, the proposed outcome is permanently removed (vetoed) from the pool, and the rejecting agent must then make a counter-offer.
This process continues until an agreement is reached or only one outcome remains. Given a set of $m$ outcomes, the negotiation is guaranteed to terminate within at most $m$ rounds. This protocol is particularly robust because it does not require agents to disclose their internal utility functions, only to make and respond to discrete offers.
Strategic Equilibrium in Full Information Settings
When both agents have full knowledge of each other's preference rankings, the negotiation can be modeled as a perfect information game. The authors derive a Sub-game Perfect Equilibrium (SPE) for this setting—a strategy where neither player has an incentive to deviate.
A key contribution of this work is the development of an elegant, linear-time algorithm ($O(m)$) to determine the SPE. Previous research into similar protocols often required quadratic time ($O(m^2)$) to compute optimal strategies. By identifying a "Low" set of outcomes—those ranked so poorly by both parties that they are effectively irrelevant to rational agents—the authors simplify the search space. The resulting equilibrium is not only unique but also Pareto optimal, ensuring that no agent can improve their position without harming the other.
Implementing Rational Compromise
One of the paper's most significant theoretical findings is the link between the VAOV protocol and the Rational Compromise (RC) bargaining rule. In cooperative game theory, the RC rule is a centralized method for finding a "fair" outcome that balances the rankings of both parties, typically by minimizing the maximum rank assigned to the chosen outcome by either party.
The authors prove that the decentralized, non-cooperative VAOV protocol naturally implements the Rational Compromise rule. This suggests that simple alternating-offer mechanisms can achieve sophisticated, socially desirable outcomes without the need for a central mediator or complex utility calculations. This bridges a major gap between non-cooperative game theory and cooperative bargaining theory.
Negotiation Under Uncertainty
Recognizing that full information is rare in practice, the paper explores two additional settings:
- No Information: When neither agent knows the other's ranking, they must rely on distribution-free solution concepts. The authors analyze maxmin strategies, where agents attempt to maximize their worst-case outcome. They demonstrate that these strategies form a robust-optimization equilibrium, allowing agents to secure outcomes from the upper portion of their preference lists even in total ignorance of their opponent.
- Asymmetric Information: In cases where one agent is informed and the other is not, the informed agent gains a significant strategic advantage. By anticipating the uninformed agent's maxmin behavior, the informed party can strategically use their knowledge to steer the negotiation toward an outcome that is substantially more favorable to themselves.
Conclusion and Future Directions
This work provides a rigorous foundation for negotiation using ordinal preferences, offering efficient algorithms and proving strong theoretical properties like monotonicity and Pareto optimality. While the current study is limited to bilateral (two-party) interactions with strict preferences, it opens the door for future research into multi-party negotiations and settings where agents may be indifferent between certain outcomes. By bridging the gap between simple protocols and complex bargaining rules, this research moves automated negotiation closer to the way humans naturally interact.
Summary updated