An Analysis of the Linear Bilateral ANAC Domains Using the MiCRO Benchmark Strategy

Dave de JongeIJCAI 2022 · DOI

TL;DR

This paper argues that the standard linear negotiation domains used in the Automated Negotiating Agents Competition (ANAC) are too simplistic and can be easily solved by a novel, non-learning strategy called MiCRO. MiCRO consistently outperforms top ANAC agents, suggesting that these benchmark domains may not accurately reflect the complexity of real-world negotiation and that future research should focus on more challenging scenarios or at least include MiCRO as a baseline.

What Problem Does This Paper Address?

Automated negotiation research often relies on benchmark domains to evaluate new algorithms. The Automated Negotiating Agents Competition (ANAC) has historically used linear bilateral negotiation domains as a primary benchmark. While these domains have been useful for developing and comparing complex strategies, particularly those involving opponent modeling and machine learning, this paper questions their continued relevance. The authors contend that these domains have become too simple, allowing even basic strategies to achieve high performance, thus potentially masking the true capabilities and limitations of more sophisticated algorithms. They aim to demonstrate this by introducing a simple strategy that outperforms established agents and by providing a theoretical analysis of why these domains are so easily solvable.

Methods

The core of the paper introduces a new negotiation strategy called MiCRO (Minimal Concession in Reply to new Offers). Unlike most ANAC agents, MiCRO does not employ any form of opponent modeling or machine learning. Its strategy is straightforward:

  • On the opponent's turn: MiCRO tracks the number of unique offers it has received from the opponent ($n$) and the number of unique offers it has made ($m$).
  • When it's MiCRO's turn:
    • If $m \le n$, MiCRO proposes the next offer on its pre-sorted list of preferred offers (sorted by its own utility).
  • If $m > n$, MiCRO randomly picks a previous offer it has made.
  • Crucially, MiCRO never proposes an offer below its reservation value.

The paper also details two evaluation methods:

  • Tournament Evaluation: Calculating the average utility obtained by each agent across all negotiation sessions.
  • Game-Theoretical Evaluation: Constructing a payoff matrix to identify Nash equilibria, which provides a more robust assessment of strategy performance.

Datasets

The paper uses existing datasets from the ANAC competitions, specifically:

  • ANAC 2013 domains: Used for experiments with ANAC 2018 and ANAC 2019 agents, as well as for ANAC 2013 agents.
  • ANAC 2012 domains: Used for experiments with ANAC 2012 agents.
  • ANAC 2019 domains: Mentioned as being more complex (partial preferences), but the paper adapted them for their experiments by providing full preference orderings.

The authors note that for ANAC 2019 experiments, discount factors were set to 1 and reservation values to 0 to align with the competition's focus and to ensure MiCRO could operate. For other experiments, original reservation values and discount factors were used.

Key Insights and Ideas

  • Simplicity Trumps Complexity (in these domains): The most striking insight is that a strategy as simple as MiCRO, which eschews complex learning and modeling, can outperform sophisticated agents that have been developed over years of competition. This strongly suggests the benchmark domains themselves are the limiting factor.
  • Linear Domains are Too Predictable: The theoretical analysis points to a "symmetry" in many linear ANAC domains, particularly concerning the Nash Bargaining Solution (NBS). This symmetry makes it easier to predict outcomes and find near-optimal strategies, rendering complex opponent modeling less critical.
  • MiCRO as a New Baseline: The paper proposes MiCRO not just as a successful strategy but as a crucial new baseline for evaluating future negotiation algorithms, especially those tested on linear domains.
  • Rethinking Opponent Modeling's Importance: The success of MiCRO challenges the assumption that advanced opponent modeling is always necessary for high performance in automated negotiation, at least within the context of these specific benchmark domains.

Key Results

  • Outperformance in ANAC Competitions: MiCRO consistently achieved the highest tournament scores when tested against top agents from ANAC 2012, 2013, 2018, and 2019.
  • In ANAC 2018 (using ANAC 2013 domains), MiCRO scored an average of 0.745 against itself, outperforming other agents.
  • In ANAC 2019 (adapted domains), MiCRO tied for first place with AgentGG.
  • In ANAC 2012 and 2013 experiments, MiCRO also secured top positions.
  • Pure Nash Equilibria: In most experimental setups, the "MiCRO vs. MiCRO" pairing formed a pure Nash equilibrium, indicating its robustness and stability within these domains.
  • Speed: Despite its minimal concessions, MiCRO sessions, especially MiCRO vs. MiCRO, often finished much faster than sessions involving other agents, even in large domains, due to the absence of computational overhead from opponent modeling.

Limitations and Future Work

  • Domain Specificity: The authors acknowledge that their conclusions are primarily based on linear ANAC domains. They emphasize that MiCRO's success does not diminish the importance of opponent modeling in more complex, non-linear, or partially observable negotiation scenarios (like the ANAC 2014 or Diplomacy domains).
  • Theoretical Analysis Scope: The theoretical analysis of balance values and their relation to the NBS is presented for a specific class of domains and relies on assumptions of agent consistency.
  • Future Work:
    • Design more challenging negotiation domains that are less susceptible to simple strategies like MiCRO.
  • Test new negotiation algorithms on these more complex domains or, at minimum, compare them against MiCRO when using linear ANAC domains.
  • Reassess the importance of opponent modeling algorithms if they have only been tested on linear ANAC domains.
  • The authors explicitly state MiCRO is intended as a benchmark strategy, not for practical applications or human negotiation.

Summary updated

BibTeX
@inproceedings{jonge2022analysis,
  author = {Dave de Jonge},
  title = {{An Analysis of the Linear Bilateral ANAC Domains Using the MiCRO Benchmark Strategy}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/32},
}

Loading related content...

Figure