Checking Consistency of CP-Theory Preferences in Polynomial Time

Erik Rauer; Samik Basu; Vasant Honavar

doi:10.1609/aaai.v39i14.33659

Checking Consistency of CP-Theory Preferences in Polynomial Time

Erik Rauer, Samik Basu, Vasant Honavar

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

Abstract

We investigate the problem of checking the consistency of qualitative preferences expressed in CP-theory. This problem is PSPACE-Complete even when the preferences are locally consistent or the preference variables have binary domain. We present a new sufficient condition for consistency of preferences and show that the condition can be checked in polynomial time in settings of practical relevance (locally consistent or binary domain preference variables). We further show how the resulting sufficient condition can be used to efficiently identify a subset of outcomes that are non-dominated with respect to a set of qualitative preferences.

Original language	English (US)
Title of host publication	Special Track on AI Alignment
Editors	Toby Walsh, Julie Shah, Zico Kolter
Publisher	Association for the Advancement of Artificial Intelligence
Pages	15126-15133
Number of pages	8
Edition	14
ISBN (Electronic)	157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 157735897X, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978, 9781577358978
DOIs	https://doi.org/10.1609/aaai.v39i14.33659
State	Published - Apr 11 2025
Event	39th Annual AAAI Conference on Artificial Intelligence, AAAI 2025 - Philadelphia, United States Duration: Feb 25 2025 → Mar 4 2025

Publication series

Name	Proceedings of the AAAI Conference on Artificial Intelligence
Number	14
Volume	39
ISSN (Print)	2159-5399
ISSN (Electronic)	2374-3468

Conference

Conference	39th Annual AAAI Conference on Artificial Intelligence, AAAI 2025
Country/Territory	United States
City	Philadelphia
Period	2/25/25 → 3/4/25

All Science Journal Classification (ASJC) codes

Artificial Intelligence

Access to Document

10.1609/aaai.v39i14.33659

Cite this

Rauer, E., Basu, S., & Honavar, V. (2025). Checking Consistency of CP-Theory Preferences in Polynomial Time. In T. Walsh, J. Shah, & Z. Kolter (Eds.), Special Track on AI Alignment (14 ed., pp. 15126-15133). (Proceedings of the AAAI Conference on Artificial Intelligence; Vol. 39, No. 14). Association for the Advancement of Artificial Intelligence. https://doi.org/10.1609/aaai.v39i14.33659

@inproceedings{3862bcaa00d04d2d86c44dba079f9c34,

title = "Checking Consistency of CP-Theory Preferences in Polynomial Time",

abstract = "We investigate the problem of checking the consistency of qualitative preferences expressed in CP-theory. This problem is PSPACE-Complete even when the preferences are locally consistent or the preference variables have binary domain. We present a new sufficient condition for consistency of preferences and show that the condition can be checked in polynomial time in settings of practical relevance (locally consistent or binary domain preference variables). We further show how the resulting sufficient condition can be used to efficiently identify a subset of outcomes that are non-dominated with respect to a set of qualitative preferences.",

author = "Erik Rauer and Samik Basu and Vasant Honavar",

note = "Publisher Copyright: Copyright {\textcopyright} 2025, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 39th Annual AAAI Conference on Artificial Intelligence, AAAI 2025 ; Conference date: 25-02-2025 Through 04-03-2025",

year = "2025",

month = apr,

day = "11",

doi = "10.1609/aaai.v39i14.33659",

language = "English (US)",

series = "Proceedings of the AAAI Conference on Artificial Intelligence",

publisher = "Association for the Advancement of Artificial Intelligence",

number = "14",

pages = "15126--15133",

editor = "Toby Walsh and Julie Shah and Zico Kolter",

booktitle = "Special Track on AI Alignment",

edition = "14",

}

Rauer, E, Basu, S & Honavar, V 2025, Checking Consistency of CP-Theory Preferences in Polynomial Time. in T Walsh, J Shah & Z Kolter (eds), Special Track on AI Alignment. 14 edn, Proceedings of the AAAI Conference on Artificial Intelligence, no. 14, vol. 39, Association for the Advancement of Artificial Intelligence, pp. 15126-15133, 39th Annual AAAI Conference on Artificial Intelligence, AAAI 2025, Philadelphia, United States, 2/25/25. https://doi.org/10.1609/aaai.v39i14.33659

Checking Consistency of CP-Theory Preferences in Polynomial Time. / Rauer, Erik; Basu, Samik; Honavar, Vasant.
Special Track on AI Alignment. ed. / Toby Walsh; Julie Shah; Zico Kolter. 14. ed. Association for the Advancement of Artificial Intelligence, 2025. p. 15126-15133 (Proceedings of the AAAI Conference on Artificial Intelligence; Vol. 39, No. 14).

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

TY - GEN

T1 - Checking Consistency of CP-Theory Preferences in Polynomial Time

AU - Rauer, Erik

AU - Basu, Samik

AU - Honavar, Vasant

PY - 2025/4/11

Y1 - 2025/4/11

N2 - We investigate the problem of checking the consistency of qualitative preferences expressed in CP-theory. This problem is PSPACE-Complete even when the preferences are locally consistent or the preference variables have binary domain. We present a new sufficient condition for consistency of preferences and show that the condition can be checked in polynomial time in settings of practical relevance (locally consistent or binary domain preference variables). We further show how the resulting sufficient condition can be used to efficiently identify a subset of outcomes that are non-dominated with respect to a set of qualitative preferences.

AB - We investigate the problem of checking the consistency of qualitative preferences expressed in CP-theory. This problem is PSPACE-Complete even when the preferences are locally consistent or the preference variables have binary domain. We present a new sufficient condition for consistency of preferences and show that the condition can be checked in polynomial time in settings of practical relevance (locally consistent or binary domain preference variables). We further show how the resulting sufficient condition can be used to efficiently identify a subset of outcomes that are non-dominated with respect to a set of qualitative preferences.

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

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

U2 - 10.1609/aaai.v39i14.33659

DO - 10.1609/aaai.v39i14.33659

M3 - Conference contribution

AN - SCOPUS:105004000988

T3 - Proceedings of the AAAI Conference on Artificial Intelligence

SP - 15126

EP - 15133

BT - Special Track on AI Alignment

A2 - Walsh, Toby

A2 - Shah, Julie

A2 - Kolter, Zico

PB - Association for the Advancement of Artificial Intelligence

T2 - 39th Annual AAAI Conference on Artificial Intelligence, AAAI 2025

Y2 - 25 February 2025 through 4 March 2025

ER -

Checking Consistency of CP-Theory Preferences in Polynomial Time

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this