Heuristics for using CP-nets in utility-based negotiation without knowing utilities

Reyhan Aydoğan*, Tim Baarslag, Koen V. Hindriks, Catholijn M. Jonker, Pınar Yolum

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

CP-nets have proven to be an effective representation for capturing preferences. However, their use in automated negotiation is not straightforward because, typically, preferences in CP-nets are partially ordered and negotiating agents are required to compare any two outcomes based on a request and an offer in order to negotiate effectively. If agents know how to generate total orders from their CP-nets, they can make this comparison. This paper proposes heuristics that enable the use of CP-nets in utility-based negotiations by generating total orderings. To validate this approach, the paper compares the performance of CP-nets with our heuristics with the performance of UCP-nets that are equipped with complete preference orderings. Our results show that we can achieve comparable performance in terms of the outcome utility. More importantly, one of our proposed heuristics can achieve this performance with significantly smaller number of interactions compared to UCP-nets.

Original languageEnglish
Pages (from-to)357-388
Number of pages32
JournalKnowledge and Information Systems
Volume45
Issue number2
DOIs
Publication statusPublished - 26 Nov 2015
Externally publishedYes

Keywords

  • Automated negotiation
  • CP-nets
  • Heuristic-based approaches
  • Qualitative preferences

Fingerprint

Dive into the research topics of 'Heuristics for using CP-nets in utility-based negotiation without knowing utilities'. Together they form a unique fingerprint.

Cite this