A lexicographic strategy for approximating dominance in CP-nets

Michael Huelsman, Miroslaw Truszczynski

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

To represent and reason about preferences over elements of a combinatorial domain it is necessary to have a compact preference model. One of the most extensively studied models for that setting is the conditional preference network (CP-net). A major problem with CP-nets is that some tasks that are critical to decision making are computationally hard if the preference ordering is given by a CP-net. To overcome this difficulty we propose to approximate CP-nets with other concise preference models that are equally intuitive but have better computational properties. In this paper, we focus on approximations of CP-nets using modified lexicographic preference models (LPMs). We show an acyclic CP-net's dominance relation can be approximated in polynomial time and present several results on the accuracy of the approximation.

Original languageEnglish
Title of host publicationProceedings of the 33rd International Florida Artificial Intelligence Research Society Conference, FLAIRS 2020
EditorsEric Bell, Roman Bartak
Pages69-72
Number of pages4
ISBN (Electronic)9781577358213
StatePublished - 2020
Event33rd International Florida Artificial Intelligence Research Society Conference, FLAIRS 2020 - North Miami Beach, United States
Duration: May 17 2020May 20 2020

Publication series

NameProceedings of the 33rd International Florida Artificial Intelligence Research Society Conference, FLAIRS 2020

Conference

Conference33rd International Florida Artificial Intelligence Research Society Conference, FLAIRS 2020
Country/TerritoryUnited States
CityNorth Miami Beach
Period5/17/205/20/20

Bibliographical note

Funding Information:
This work was funded by the NSF under the grant number IIS-1618783.

Publisher Copyright:
© FLAIRS 2020.All right reserved.

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software

Fingerprint

Dive into the research topics of 'A lexicographic strategy for approximating dominance in CP-nets'. Together they form a unique fingerprint.

Cite this