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 o and o', of a minimal proof that o is preferred to o'. 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.

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.

Conditional preference networks (CP-nets) are a commonly studied compact formalism for modeling preferences. To study the properties of CP-nets or the performance of CP-net algorithms on average, one needs to generate CP-nets in an equiprobable manner. We discuss common problems with naive generation, including sampling bias, which invalidates the base assumptions of many statistical tests and can undermine the results of an experimental study. We provide a novel algorithm for provably generating acyclic CP-nets uniformly at random. Our method is computationally efficient and allows for multi-valued domains and arbitrary bounds on the indegree in the dependency graph.

The Model AI Assignments session seeks to gather and disseminate the best assignment designs of the Artificial Intelligence (AI) Education community. Recognizing that assignments form the core of student learning experience, we here present abstracts of six AI assignments from the 2016 session that are easily adoptable, playfully engaging, and flexible for a variety of instructor needs.

In this challenge paper, we consider the importance of preferences in smart homes and assistive environments and discuss the potential application of models and algorithms developed within the computational preferences community. We suggest the value of future research collaborations.

Conditional preference networks (CP-nets) exploit the power of conditional ceteris paribus rules to enable a compact representation of human preferences. CP-nets have much appeal. However, the study of CP-nets has not advanced sufficiently for their widespread use in complex, real-world applications. Most studies limit their attention to strict, complete, consistent preferences over binary domains. In my research, I attempt to address these limitations to make CP-nets more useful. I discuss recent research in which we presented a novel algorithm for learning CP-nets from user queries, as well as work showing how to adapt existing algorithms to learn and reason with multivalued CP-nets that can model indifference as well as strict preference. I outline anticipated research to extend our elicitation algorithm to a richer class of CP-nets, develop a formal model of expected flipping sequence length, and learn CP-nets in which a subject prefers to coordinate certain features, leading to a cycle in the dependency graph.