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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-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 language	English
Title of host publication	Algorithmic Decision Theory - 7th International Conference, ADT 2021, Proceedings
Editors	Dimitris Fotakis, David Ríos Insua
Pages	86-100
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-030-87756-9_6
State	Published - 2021
Event	7th International Conference on Algorithmic Decision Theory, ADT 2021 - Toulouse, France Duration: Nov 3 2021 → Nov 5 2021

Publication series

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

Conference

Conference	7th International Conference on Algorithmic Decision Theory, ADT 2021
Country/Territory	France
City	Toulouse
Period	11/3/21 → 11/5/21

Bibliographical note

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
General Computer Science

Access to Document

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

Cite this

Liu, X., & Truszczynski, M. (2021). Probabilistic Lexicographic Preference Trees. In 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. in 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).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 - http://www.scopus.com/inward/record.url?scp=85118967419&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85118967419&partnerID=8YFLogxK

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. In Fotakis D, Ríos Insua D, editors, 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

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this