AAAI 2016 CP-net Tutorial Syllabus

Thomas E. Allen, Judy Goldsmith, Francesca Rossi

SLIDES COMING VERY SOON!

  1. Intro to CP-nets
    1. Definition
    2. Building a CP-net, using GUI tool
    3. Applications
    4. Computations: k best, comparison (a.k.a. dominance)
  2. Dominance Testing
    1. Flipping sequences
    2. Preference graph
    3. Complexity results, briefly
    4. Survey of algorithms
    5. Special (easy) cases
    6. Proposal for dominance-testing competition
  3. Learning CP-nets
    1. Elicitation
    2. Learning from choice data
    3. Human subjects tests
  4. Generating
    1. Motivation for generating CP-nets at random
    2. What was done in the past, and the biases thereof
    3. Uniform generation of DAGs, CPTs, and CP-nets
    4. Special cases: bounded indegree, trees, etc.
  5. Uncertainty and multi-agent preferences
    1. PCP nets
      1. definition
      2. optimal outcome
      3. dominance
    2. Multi-agent preference aggregation
      1. CP-nets plus voting
      2. PCP-nets

Description

Introduction

Combinatorial preference domains abound, and CP-nets have a wide range of interesting and important applications, including automated negotiation Aydogan et al., interest-matching in social networks, Wicker and Doyle, cybersecurity Bistarelli, Fioravanti, and Peretti, and as aggregation primitives for making group decisions Lang and Xia, Mattei et al. and Xia, Conitzer, and Lang, and in communicating with people with cognitive impairments such as traumatic brain injury or amyotriphic lateral sclerosis Dorr et al.

It is known that certain reasoning tasks, in particular that of dominance (e.g., given a CP-net N and two outcomes or items, which if either is preferred according to N?), are computationally complex — NP-hard or worse. However, there is a growing base of heuristic algorithms for dominance testing. This bolsters the case for more widespread use of CP-nets in practice.

In this tutorial we hope to introduce participants to CP-nets and methods for using them. Those familiar with preference representations will be interested in our demonstration of a new GUI for visualizing CP-nets, recent approaches to dominance testing, an algorithm to generate CP-nets uniformly at random, and results of extensive human-subjects experiments. We expect participants to complete the session with an increased appreciation for the usefulness and usability of CP-nets.

Expanded Outline

We will begin by introducing CP-nets and their applications. We will elicit a CP-net from an attendee and then use our CP-net GUI interface to introduce notions of dependence (contextual or conditional preferences), binary or multi-valued variables, conditional preference tables (CPTs), degenerate CPTs, and incomplete CPTs.

We will then look at common preference reasoning tasks: finding the optimal outcome, finding the k-best outcomes, aggregating multiple preferences, and comparing two outcomes. We will introduce simple algorithms for the first two, and then introduce the notion of a flipping sequence, first graphically and then formally. Flipping sequences provide the underlying semantics for comparisons; the existence question, given N and outcomes o and o', of a flipping sequence from o' to o is called the dominance testing problem.

We will describe some of the available dominance testing algorithms, including Boutilier, et al.'s initial heuristics and more recent approaches based on planning and Santhanam et al.'s work on model-checking. We will propose a dominance-testing competition, which we hope to organize in conjunction with an AI conference in 2017. We expect that the competition will also allow for remote entries to encourage broader participation.

Next, we will present some of the CP-net learning algorithms and discuss their applicability and why they are needed. We will describe the human-subjects test recently run by our colleagues in the related fields of quantitative psychology and behavioral economics, and the data that is (or will be) available from those tests. We will also discuss the challenges inherent in such experiments.

There are many notions of preference aggregation. We will present work on voting with CP-nets and on probabilistic CP-nets (PCP-nets) as preference aggregation representations.

Finally, we will discuss the use of "randomly generated" CP-nets, and the statistical biases introduced by most work up to now. We will introduce an algorithm for uniformly generating CP-nets at random and discuss the sort of questions that can be explored using such generation.