EAGER: Preferences in Repeated Choices

Overview: We propose to extend ongoing work on a graphical model of preferences, namely conditional preference networks (CP-nets). First, we focus on the standard definition of CP-nets, and a basic reasoning task: Given a CP-net $N$ and outcomes $o$ and $o'$, does $N$ entail that $o$ is preferred to $o'$? This problem, "dominance testing" (DT), for CP-nets is NP-hard, but there are instances where the proofs of dominance (so-called flipping sequences) are exponentially larger than the input CP-net and the outcomes being compared. We propose to build a portfolio of DT algorithms. There are successful portfolios for other NP-hard problems, e.g., Satisfiability: a portfolio predicts which algorithms are likely to run efficiently on a given instance, then runs them. To support our and others' research on DT, we propose to run a DT programming competition, as a workshop at a near-future AAAI or IJCAI, or as part of an preference handling workshop. Psychologists, marketers, and economists observe that people aren't consistent in their choices. Many explanations have been proposed, including (1) that people cannot easily access their preferences, so they use noisy choice heuristics; (2) that they switch between preference models based on external variables, or randomly; and (3) that there are preference biases such as a preference for novelty or variety, that depend on a history of choices. We have worked on probabilistic CP-nets for (1) and collaborated on a recent lab experiment exploring (2). The second part our proposal is to extend CP-nets to include finite representations of choice history. We call these Temporal Conditional Choice Networks (TCC-nets). We propose to develop algorithms for reasoning with TCC-nets. We propose a study based on an app we'll develop to track a user's choice of routes from work or school to home. Since people usually carry their phones, and that data can be collected with little input from the users after initial installation of the app, we expect to build up a large collection of anonymous choices repeated over time. The data will be labeled with route features rather than GPS coordinates, so should be shareable with other researchers. KEYWORDS: Preference handling, dynamic preference models Intellectual Merit : The IM of this work lies in the development of the extension of the CP-net model to cover known temporal preference phenomena, and the development of reasoning algorithms for TCC-nets. Broader Impacts : CP-nets are being used to reason about communication for ALS patients, and in other technical applications; better DT algorithms means more effective tools. Our broader impact activities include outreach to non-computer scientists (general public, high school students, pre-majors, others) using a recently-developed CP-net visualizer. This allows the PI and her students to talk about knowledge representation, algorithms, and applications of preference handling in a concrete and visual manner during their presentations. The DT competition will build a literature of DT algorithms, making CP-nets a feasible tool for preference reasoning. Finally, the collection of route choices will add to a small, growing data set of preference data, and an even smaller set of non-lab-based repeated choices over time. Thus, the BIs include outreach and a software package, which will be publicly available, for outreach about AI and preference handling, and also contributions to the infrastructure of preference reasoning research.