Complex Multi-Issue Negotiation Using Utility Hyper-Graphs

Access this Article

Search this Article

Author(s)

Abstract

<p>We propose to handle the complexity of utility spaces used in multi-issue negotiation by adopting a new representation that allows a modular decomposition of the issues and the constraints. This is based on the idea that a constraint-based utility space is nonlinear with respect to issues, but linear with respect to the constraints. This allows us to rigorously map the utility space into an issue-constraint hyper-graph. Exploring the utility space reduces then to a message passing mechanism along the hyper-edges of the hyper-graph by means of utility propagation. Optimal contracts are found efficiently using a variation of the Max-Sum algorithm. We evaluate the model experimentally using parameterized nonlinear utility spaces, showing that it can handle a large family of complex utility spaces by finding optimal contracts, outperforming previous sampling-based approaches. We also evaluate the model in a negotiation setting. We show that under high complexity, social welfare could be greater than the sum of the individual agents' best utilities.</p>

Journal

  • Journal of Advanced Computational Intelligence and Intelligent Informatics

    Journal of Advanced Computational Intelligence and Intelligent Informatics 19(4), 514-522, 2015

    Fuji Technology Press Ltd.

Codes

  • NII Article ID (NAID)
    130007673251
  • NII NACSIS-CAT ID (NCID)
    AA12042502
  • Text Lang
    ENG
  • ISSN
    1343-0130
  • NDL Article ID
    026675732
  • NDL Call No.
    Z78-A599
  • Data Source
    NDL  J-STAGE 
Page Top