Reasoning with preference trees over combinatorial domains

Xudong Liu; Miroslaw Truszczynski

doi:10.1007/978-3-319-23114-3_2

Reasoning with preference trees over combinatorial domains

Xudong Liu, Miroslaw Truszczynski

Computer Science

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

4 Scopus citations

Abstract

Preference trees, or P-trees for short, offer an intuitive and often concise way of representing preferences over combinatorial domains. In this paper, we propose an alternative definition of P-trees, and formally introduce their compact representation that exploits occurrences of identical subtrees. We show that P-trees generalize lexicographic preference trees and are strictly more expressive. We relate P-trees to answerset optimization programs and possibilistic logic theories. Finally, we study reasoning with P-trees and establish computational complexity results for the key reasoning tasks of comparing outcomes with respect to orders defined by P-trees, and of finding optimal outcomes.

Original language	English
Title of host publication	Algorithmic Decision Theory - 4th International Conference, ADT 2015, Proceedings
Editors	Toby Walsh
Pages	19-34
Number of pages	16
DOIs	https://doi.org/10.1007/978-3-319-23114-3_2
State	Published - 2015
Event	4th International Conference on Algorithmic Decision Theory, ADT 2015 - Lexington, United States Duration: Sep 27 2015 → Sep 30 2015

Publication series

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

Conference

Conference	4th International Conference on Algorithmic Decision Theory, ADT 2015
Country/Territory	United States
City	Lexington
Period	9/27/15 → 9/30/15

Bibliographical note

Publisher Copyright:
© Springer International Publishing Switzerland 2015.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-23114-3_2

Cite this

Liu, X., & Truszczynski, M. (2015). Reasoning with preference trees over combinatorial domains. In T. Walsh (Ed.), Algorithmic Decision Theory - 4th International Conference, ADT 2015, Proceedings (pp. 19-34). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9346). https://doi.org/10.1007/978-3-319-23114-3_2

@inproceedings{fcbe2ce553254a6a962ec44431be1aab,

title = "Reasoning with preference trees over combinatorial domains",

abstract = "Preference trees, or P-trees for short, offer an intuitive and often concise way of representing preferences over combinatorial domains. In this paper, we propose an alternative definition of P-trees, and formally introduce their compact representation that exploits occurrences of identical subtrees. We show that P-trees generalize lexicographic preference trees and are strictly more expressive. We relate P-trees to answerset optimization programs and possibilistic logic theories. Finally, we study reasoning with P-trees and establish computational complexity results for the key reasoning tasks of comparing outcomes with respect to orders defined by P-trees, and of finding optimal outcomes.",

author = "Xudong Liu and Miroslaw Truszczynski",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 4th International Conference on Algorithmic Decision Theory, ADT 2015 ; Conference date: 27-09-2015 Through 30-09-2015",

year = "2015",

doi = "10.1007/978-3-319-23114-3_2",

language = "English",

isbn = "9783319231136",

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

pages = "19--34",

editor = "Toby Walsh",

booktitle = "Algorithmic Decision Theory - 4th International Conference, ADT 2015, Proceedings",

}

Liu, X & Truszczynski, M 2015, Reasoning with preference trees over combinatorial domains. in T Walsh (ed.), Algorithmic Decision Theory - 4th International Conference, ADT 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9346, pp. 19-34, 4th International Conference on Algorithmic Decision Theory, ADT 2015, Lexington, United States, 9/27/15. https://doi.org/10.1007/978-3-319-23114-3_2

Reasoning with preference trees over combinatorial domains. / Liu, Xudong; Truszczynski, Miroslaw.
Algorithmic Decision Theory - 4th International Conference, ADT 2015, Proceedings. ed. / Toby Walsh. 2015. p. 19-34 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9346).

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

TY - GEN

T1 - Reasoning with preference trees over combinatorial domains

AU - Liu, Xudong

AU - Truszczynski, Miroslaw

PY - 2015

Y1 - 2015

N2 - Preference trees, or P-trees for short, offer an intuitive and often concise way of representing preferences over combinatorial domains. In this paper, we propose an alternative definition of P-trees, and formally introduce their compact representation that exploits occurrences of identical subtrees. We show that P-trees generalize lexicographic preference trees and are strictly more expressive. We relate P-trees to answerset optimization programs and possibilistic logic theories. Finally, we study reasoning with P-trees and establish computational complexity results for the key reasoning tasks of comparing outcomes with respect to orders defined by P-trees, and of finding optimal outcomes.

AB - Preference trees, or P-trees for short, offer an intuitive and often concise way of representing preferences over combinatorial domains. In this paper, we propose an alternative definition of P-trees, and formally introduce their compact representation that exploits occurrences of identical subtrees. We show that P-trees generalize lexicographic preference trees and are strictly more expressive. We relate P-trees to answerset optimization programs and possibilistic logic theories. Finally, we study reasoning with P-trees and establish computational complexity results for the key reasoning tasks of comparing outcomes with respect to orders defined by P-trees, and of finding optimal outcomes.

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

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

U2 - 10.1007/978-3-319-23114-3_2

DO - 10.1007/978-3-319-23114-3_2

M3 - Conference contribution

AN - SCOPUS:84945932591

SN - 9783319231136

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

SP - 19

EP - 34

BT - Algorithmic Decision Theory - 4th International Conference, ADT 2015, Proceedings

A2 - Walsh, Toby

T2 - 4th International Conference on Algorithmic Decision Theory, ADT 2015

Y2 - 27 September 2015 through 30 September 2015

ER -

Liu X, Truszczynski M. Reasoning with preference trees over combinatorial domains. In Walsh T, editor, Algorithmic Decision Theory - 4th International Conference, ADT 2015, Proceedings. 2015. p. 19-34. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-23114-3_2

Reasoning with preference trees over combinatorial domains

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this