News Archives

Preferences and Domination

March 3, 2005

  • Date: Thursday, March 3, 2005 
  • Time: 11:00 a.m. 
  • Location: Woodward 149

Judy Goldsmith <goldsmit@cs.uky.e du> 
University of Kentucky

The issue of preferences arises in computer science in the context of e-commerce, decision-theoretic planning, and personalization. The computational questions are: How do you elicit a person’s preferences, and how do you represent those preferences? Given a preference representation, we then need algorithms to determine whether one instance is preferable to another, to find a most-preferred instance, and to determine whether the described preferences even make sense.

Consider the problem of red vs. green (Hatch New Mexico chilis, of course). There are many features to consider: is the green chili fresh? Was it a rainy year? How hot? (Note that answers to the latter two are strongly correlated.)

Computer Scientist X prefers green to red, given that the red sauce was made with beef stock, and otherwise prefers red to green unless the green chili is from freshly-picked chilis.

One representation of preferences is a CP-net, which uses a digraph to represent dependencies of features (“My preference about color depends on the ingredients and freshness”) and conditional preference tables (“If the red is vegetarian and the green is not fresh then I prefer red; If the red is vegetarian and the green is fresh then I prefer the green….”)

We say that one instance (vegetarian, fresh, green) is preferred to another (non-veg, not fresh, red) if there is a sequence of single-feature changes that begins with the less-preferred instance and ends with the more-preferred instance, and where each change increases the preferability. We also say that the preferred instance dominates the less-preferred instance.

We have shown that both the dominance problem and the consistency problem are PSPACE complete for cyclic CP-nets. I will discuss the implications of these results and sketch proofs.

This is joint work with Jerome Lang, Mirek Truszczynski, and Nic Wilson.