Negotiation Strategies for Agents with Ordinal Preferences

Sefi Erlich, Noam Hazon, Sarit Kraus

Introduction

In the field of automated negotiation, agents traditionally rely on cardinal utilities—numerical values assigned to specific outcomes (e.g., "this outcome is worth 8.5 units"). While mathematically convenient, eliciting precise cardinal values from humans is notoriously difficult and cognitively taxing. In contrast, ordinal preferences—simple rankings such as "I prefer A over B"—are much more intuitive for human users to provide.

This paper addresses the challenge of finding stable, strategic equilibrium behaviors for agents negotiating over a finite set of discrete outcomes using only these ordinal rankings. Moving away from the "continuum" models often found in literature (like splitting infinitely divisible resources), the authors focus on real-world scenarios such as selecting a job candidate or choosing an apartment.

The VAOV Protocol

The researchers analyze the Voting by Alternating Offers and Vetoes (VAOV) protocol. The mechanism operates as follows:

  1. Two parties take turns proposing an outcome from a finite set.
  2. Once an outcome is proposed, it cannot be proposed again, effectively serving as a veto if the offer is rejected.
  3. The negotiation concludes when an offer is accepted or only one outcome remains.

Methodological Contributions

Sub-game Perfect Equilibrium (SPE)

The authors define "Offering" and "Response" strategies that constitute a Sub-game Perfect Equilibrium (SPE). In this state, neither party has an incentive to deviate from their strategy at any point in the game, ensuring a stable and predictable negotiation path.

Linear-Time Efficiency

While previous research by Anbarci (2006) identified SPE results for similar protocols, those methods required quadratic time ($O(m^2)$) relative to the number of outcomes $m$. This paper introduces a more efficient algorithm that computes the optimal strategy in linear time ($O(m)$), significantly improving the scalability of the approach for large outcome sets.

Information Settings

The study examines the protocol under two distinct conditions:

  • Full Information: Both parties are aware of each other's complete preference rankings.
  • No Information: Neither party knows the other's ranking, leading to a "maxmin" approach where agents aim for the best possible "worst-case" outcome.

Key Insights and Theoretical Connections

The Rational Compromise

A significant finding of this research is that the non-cooperative VAOV protocol effectively implements the Rational Compromise (RC) bargaining rule. This discovery bridges a gap between non-cooperative game theory (individual strategic action) and social choice theory (collective fairness).

Robustness and Monotonicity

The authors prove that the negotiation results are monotonic: if an outcome becomes more preferred by one party while remaining the same for the other, the final result will not worsen for that party. Furthermore, in the "No Information" setting, the authors demonstrate that a maxmin strategy specifies a robust-optimization equilibrium. This ensures the strategy remains effective even if the opponent does not play perfectly or possesses unexpected preferences.

Strategic Filtering

The paper introduces the concept of $Low_t$—a set of outcomes ranked so poorly by both parties that they can never be the equilibrium result. By identifying and eliminating these outcomes, agents can focus their strategic efforts on the "Just Good" ($JG_t$) outcomes that are likely to form the basis of a successful compromise.

Results and Conclusion

The proposed framework offers several key advantages:

  • Efficiency: The $O(m)$ algorithm provides a significant computational benchmark improvement.
  • Optimality: The SPE result is unique and Pareto optimal, meaning no other outcome could improve one party's position without harming the other.
  • Information Advantage: In asymmetric settings where only one party is informed, that party can strategically steer the negotiation toward a more favorable result than the standard maxmin outcome.

While this work provides a robust foundation for bilateral ordinal negotiation, future research is needed to extend these strategies to multi-party settings and to conduct user studies to verify the intuitiveness of these strategies for human-agent interaction.

Summary updated

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.
BibTeX
@inproceedings{erlich2018negotiation,
  author = {Sefi Erlich and Noam Hazon and Sarit Kraus},
  title = {{Negotiation Strategies for Agents with Ordinal Preferences}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/29},
}
Figure