Probabilistic Lexicographic Preference Trees

Xudong Liu; Miroslaw Truszczynski

doi:10.1007/978-3-030-87756-9_6

Probabilistic Lexicographic Preference Trees

Xudong Liu
, Miroslaw Truszczynski

Computer Science

Producción científica: Conference contribution › revisión exhaustiva

Resumen

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.

Idioma original	English
Título de la publicación alojada	Algorithmic Decision Theory - 7th International Conference, ADT 2021, Proceedings
Editores	Dimitris Fotakis, David Ríos Insua
Páginas	86-100
Número de páginas	15
DOI	https://doi.org/10.1007/978-3-030-87756-9_6
Estado	Published - 2021
Evento	7th International Conference on Algorithmic Decision Theory, ADT 2021 - Toulouse, France Duración: nov 3 2021 → nov 5 2021

Serie de la publicación

Nombre	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen	13023 LNAI
ISSN (versión impresa)	0302-9743
ISSN (versión digital)	1611-3349

Conference

Conference	7th International Conference on Algorithmic Decision Theory, ADT 2021
País/Territorio	France
Ciudad	Toulouse
Período	11/3/21 → 11/5/21

Nota bibliográfica

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Financiación

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

Financiadores	Número del financiador
National Science Foundation (NSF)	IIS-1618783

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Acceder al documento

10.1007/978-3-030-87756-9_6

Otros archivos y enlaces

Citar esto

Liu, X., & Truszczynski, M. (2021). Probabilistic Lexicographic Preference Trees. En D. Fotakis, & D. Ríos Insua (Eds.), Algorithmic Decision Theory - 7th International Conference, ADT 2021, Proceedings (pp. 86-100). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13023 LNAI). https://doi.org/10.1007/978-3-030-87756-9_6

@inproceedings{34ddd7cb04f042eba074e9300a72ee5b,

title = "Probabilistic Lexicographic Preference Trees",

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.",

keywords = "Lexicographic preference trees, Preference representation and reasoning, Probabilistic preference models",

author = "Xudong Liu and Miroslaw Truszczynski",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 7th International Conference on Algorithmic Decision Theory, ADT 2021 ; Conference date: 03-11-2021 Through 05-11-2021",

year = "2021",

doi = "10.1007/978-3-030-87756-9\_6",

language = "English",

isbn = "9783030877552",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "86--100",

editor = "Dimitris Fotakis and \{R{\'i}os Insua\}, David",

booktitle = "Algorithmic Decision Theory - 7th International Conference, ADT 2021, Proceedings",

}

Liu, X & Truszczynski, M 2021, Probabilistic Lexicographic Preference Trees. En D Fotakis & D Ríos Insua (eds.), Algorithmic Decision Theory - 7th International Conference, ADT 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13023 LNAI, pp. 86-100, 7th International Conference on Algorithmic Decision Theory, ADT 2021, Toulouse, France, 11/3/21. https://doi.org/10.1007/978-3-030-87756-9_6

Probabilistic Lexicographic Preference Trees. / Liu, Xudong; Truszczynski, Miroslaw.
Algorithmic Decision Theory - 7th International Conference, ADT 2021, Proceedings. ed. / Dimitris Fotakis; David Ríos Insua. 2021. p. 86-100 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13023 LNAI).

Producción científica: Conference contribution › revisión exhaustiva

TY - GEN

T1 - Probabilistic Lexicographic Preference Trees

AU - Liu, Xudong

AU - Truszczynski, Miroslaw

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Lexicographic preference trees

KW - Preference representation and reasoning

KW - Probabilistic preference models

UR - https://www.scopus.com/pages/publications/85118967419

UR - https://www.scopus.com/pages/publications/85118967419#tab=citedBy

U2 - 10.1007/978-3-030-87756-9_6

DO - 10.1007/978-3-030-87756-9_6

M3 - Conference contribution

AN - SCOPUS:85118967419

SN - 9783030877552

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 86

EP - 100

BT - Algorithmic Decision Theory - 7th International Conference, ADT 2021, Proceedings

A2 - Fotakis, Dimitris

A2 - Ríos Insua, David

T2 - 7th International Conference on Algorithmic Decision Theory, ADT 2021

Y2 - 3 November 2021 through 5 November 2021

ER -

Liu X, Truszczynski M. Probabilistic Lexicographic Preference Trees. En Fotakis D, Ríos Insua D, editores, Algorithmic Decision Theory - 7th International Conference, ADT 2021, Proceedings. 2021. p. 86-100. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-87756-9_6

Probabilistic Lexicographic Preference Trees

Resumen

Serie de la publicación

Conference

Nota bibliográfica

Financiación

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto