Probabilistic Lexicographic Preference Trees

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

Abstract

We introduce probabilistic lexicographic preference trees (or PrLPTs for short). We show that they offer intuitive and often compact representations of non-deterministic qualitative preferences over alternatives in multi-attribute (or, combinatorial) binary domains. We specify how a PrLPT defines the probability that a given outcome has a given rank, and the probability that a given outcome is preferred to another one, and show how to compute these probabilities in polynomial time. We also show that computing outcomes that are optimal with the probability equal to or exceeding a given threshold for some classes of PrLP-trees is in P, but for some other classes the problem is NP-hard.

Original languageEnglish
Title of host publicationAlgorithmic Decision Theory - 7th International Conference, ADT 2021, Proceedings
EditorsDimitris Fotakis, David Ríos Insua
Pages86-100
Number of pages15
DOIs
StatePublished - 2021
Event7th International Conference on Algorithmic Decision Theory, ADT 2021 - Toulouse, France
Duration: Nov 3 2021Nov 5 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13023 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International Conference on Algorithmic Decision Theory, ADT 2021
Country/TerritoryFrance
CityToulouse
Period11/3/2111/5/21

Bibliographical note

Funding Information:
This work was partially supported by the NSF grant IIS-1618783.

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Keywords

  • Lexicographic preference trees
  • Preference representation and reasoning
  • Probabilistic preference models

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'Probabilistic Lexicographic Preference Trees'. Together they form a unique fingerprint.

Cite this