Addressing Complexity in Multi-Issue Negotiation via Utility Hypergraphs

Rafik Hadfi, Takayuki ItoAAAI 2014 · DOI

Introduction

Negotiating multi-issue contracts—where parties must agree on variables like price, delivery date, and warranty—is a fundamental challenge in automated negotiation. While simple models assume these issues are independent, real-world scenarios are characterized by complex interdependencies. These dependencies create "rugged," nonlinear utility landscapes where finding an optimal agreement is computationally intensive.

A 3D visualization of a rugged utility landscape, illustrating the complexity of finding optimal contracts in multi-issue negotiation.

Traditional search methods, such as Simulated Annealing (SA), often struggle to scale as the number of issues and constraints grows. This paper proposes a structural approach to this problem by decomposing utility functions into modular components using utility hypergraphs.

Methodology: Utility Hypergraphs and Message Passing

The core innovation lies in representing the negotiation space as a graphical model. Instead of treating utility as a single "black-box" function, the authors introduce utility hypergraphs. In this model:

  • Nodes represent individual negotiation issues.
  • Hyperedges (Factors) represent specific constraints or dependencies between issues.

While the global utility function remains nonlinear, it is decomposed into a sum of local, modular constraints. This decomposition allows for the application of AsynchMP (Asynchronous Message Passing). Inspired by belief propagation algorithms, AsynchMP finds optimal issue values by passing and aggregating utility messages across the hypergraph.

To further optimize performance, the authors developed AsynchMPi. This variant utilizes a "Power-Law" propagation strategy, prioritizing messages through "hub" nodes—constraints that involve a high number of issues—to accelerate convergence in complex topologies.

Complexity Assessment via Entropy

A significant contribution of this work is the quantitative assessment of negotiation complexity. The authors demonstrate that the difficulty of a scenario is not merely a function of the number of issues ($n$) or constraints ($m$), but rather the connectivity topology ($\pi$). By applying information entropy to the hypergraph's structure, they can predict the computational duration required to reach an optimal solution.

Experimental Results

The proposed methods were evaluated using synthetic negotiation scenarios generated as parametrized random hypergraphs. Key findings include:

  1. Performance over Baseline: AsynchMP consistently outperformed Simulated Annealing in identifying optimal contracts, particularly as the density of constraints increased.
  2. Algorithmic Efficiency: The optimized AsynchMPi demonstrated significant scalability. As shown in the performance analysis, while standard message passing durations can spike exponentially with topological complexity, the prioritized propagation strategy maintains high efficiency.
Comparison of search durations between AsynchMP and the optimized AsynchMPi across different topology complexities.

Conclusion

By shifting from global search to local message passing on utility hypergraphs, this research provides a scalable framework for complex multi-issue negotiations. The use of entropy as a complexity metric offers a principled way to evaluate negotiation scenarios. Future work will extend this single-agent optimization framework to multi-agent protocols where parties must reach agreements while keeping their underlying utility structures private.

Summary updated

BibTeX
@inproceedings{hadfi2014addressing,
  author = {Rafik Hadfi and Takayuki Ito},
  title = {{Addressing Complexity in Multi-Issue Negotiation via Utility Hypergraphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.9101},
}

Loading related content...

Figure