An official website of the United States government
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.
more »
« less
Representing and Reasoning with Multi-Stakeholder Qualitative Preference Queries
Many decision-making scenarios, e.g., public policy, healthcare, business, and disaster response, require accommodating the preferences of multiple stakeholders. We offer the first formal treatment of reasoning with multi-stakeholder qualitative preferences in a setting where stakeholders express their preferences in a qualitative preference language, e.g., CP-net, CI-net, TCP-net, CP-Theory. We introduce a query language for expressing queries against such preferences over sets of outcomes that satisfy specified criteria, e.g., ψ1PAψ2 (read loosely as the set of outcomes satisfying ψ1 that are preferred over outcomes satisfying ψ2 by a set of stakeholders A). Motivated by practical application scenarios, we introduce and analyze several alternative semantics for such queries, and examine their interrelationships. We provide a provably correct algorithm for answering multi-stakeholder qualitative preference queries using model checking in alternation-free μ-calculus. We present experimental results that demonstrate the feasibility of our approach.
more »
« less
- PAR ID:
- 10471259
- Publisher / Repository:
- IOS Press
- Date Published:
- Journal Name:
- Frontiers in Artificial Intelligence and Applications, Proceedings of ECAI
- ISBN:
- 978-1-64368-436-9
- Page Range / eLocation ID:
- 206-213
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Conditional preference networks (CP-nets) are an intuitive and expressive representation for qualitative preferences. Such models must somehow be acquired. Psychologists argue that direct elicitation is suspect. On the other hand, learning general CP-nets from pairwise comparisons is NP-hard, and --- for some notions of learning --- this extends even to the simplest forms of CP-nets. We introduce a novel, concise encoding of binary-valued, tree-structured CP-nets that supports the first local-search-based CP-net learning algorithms. While exact learning of binary-valued, tree-structured CP-nets --- for a strict, entailment-based notion of learning --- is already in P, our algorithm is the first space-efficient learning algorithm that gracefully handles noisy (i.e., realistic) comparison sets.more » « less
-
Companies use personalization to tailor user experiences. Personalization appears in search engines and online stores, which include salutations and statistically learned correlations over search-, browsing- and purchase-histories. However, users have a wider variety of substantive, domain-specific preferences that affect their choices when they use directory services, and these have largely been overlooked or ignored. The contributions of this paper include: (1) a grounded theory describing how stakeholder preferences are expressed in text scenarios; (2) an app feature survey to assess whether elicited preferences represent missing requirements in existing systems; (3) an evaluation of three classifiers to label preference words in scenarios; and (4) a linker to build preference phrases by linking labeled preference words to each other based on word position. In this study, the authors analyzed 217 elicited directory service scenarios across 12 domain categories to yield a total of 7,661 stakeholder preferences labels. The app survey yielded 43 stakeholder preferences that were missed on average 49.7% by 15 directory service websites studied. The BERT-based transformer showed the best average overall 81.1% precision, 84.4% recall and 82.6% F1-score when tested on unseen domains. Finally, the preference linker correctly links preference phrases with 90.1% accuracy. Given these results, we believe directory service developers can use this approach to automatically identify user preferences to improve service designs.more » « less
-
The generation of preferences represented as CP-nets for experiments and empirical testing has typically been done in an ad hoc manner that may have introduced a large statistical bias in previous experimental work. We present novel polynomial-time algorithms for generating CP-nets with n nodes and maximum in-degree c uniformly at random. We extend this result to several statistical cultures commonly used in the social choice and preference reasoning literature. A CP-net is composed of both a graph and underlying cp-statements; our algorithm is the first to provably generate both the graph structure and cp-statements, and hence the underlying preference orders themselves, uniformly at random. We have released this code as a free and open source project. We use the uniform generation algorithm to investigate the maximum and expected flipping lengths, i.e., the maximum length over all outcomes o1 and o2, of a minimal proof that o1 is preferred to o2. Using our new statistical evidence, we conjecture that, for CP-nets with binary variables and complete conditional preference tables, the expected flipping length is polynomial in the number of preference variables. This has positive implications for the usability of CP-nets as compact preference models.more » « less
-
In this paper, we study planning in stochastic systems, modeled as Markov decision processes (MDPs), with preferences over temporally extended goals. Prior work on temporal planning with preferences assumes that the user preferences form a total order, meaning that every pair of outcomes are comparable with each other. In this work, we consider the case where the preferences over possible outcomes are a partial order rather than a total order. We first introduce a variant of deterministic finite automaton, referred to as a preference DFA, for specifying the user's preferences over temporally extended goals. Based on the order theory, we translate the preference DFA to a preference relation over policies for probabilistic planning in a labeled MDP. In this treatment, a most preferred policy induces a weak-stochastic nondominated probability distribution over the finite paths in the MDP. The proposed planning algorithm hinges on the construction of a multi-objective MDP. We prove that a weak-stochastic nondominated policy given the preference specification is Pareto-optimal in the constructed multi-objective MDP, and vice versa. Throughout the paper, we employ a running example to demonstrate the proposed preference specification and solution approaches. We show the efficacy of our algorithm using the example with detailed analysis, and then discuss possible future directions.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.3233/FAIA230272
