Similarity Measures on Preference Structures, Part II: Utility Functions

Vu A. Ha, Peter Haddawy, John MiyamotoUAI 2001

TL;DR

This paper introduces a novel "probabilistic distance" to measure how similar two people's preferences are, especially when those preferences are incomplete or involve uncertainty. They extend this measure to handle complex utility functions, reducing the problem to computing the volume of convex bodies, for which efficient algorithms exist. This work is crucial for building more personalized and intelligent systems that can understand and adapt to individual user preferences.

What Problem Does This Paper Address?

Understanding and quantifying similarity between user preferences is a fundamental challenge in many AI applications, from recommender systems to decision support. In previous work, the authors introduced a "probabilistic distance" for comparing complete preference orders under certainty. However, real-world scenarios often involve incomplete preferences and decision-making under uncertainty, where a person's utility function (representing their preferences) is not fully known. Existing distance measures struggle with these complexities, especially when dealing with partial information. This paper tackles the difficult problem of computing this probabilistic distance for partially specified utility functions in the context of decision-making under uncertainty.

Methods

The core of the paper is the extension of the probabilistic distance to handle uncertainty and partial preferences.

  • Probabilistic Distance: This measure quantifies disagreement between two preference structures by calculating the probability that they rank two randomly chosen decision consequences differently.
  • Utility Functions as Polyhedral Cones: The authors represent sets of consistent utility functions (those that align with a person's partial preferences) as polyhedral cones. This geometric representation is key because it allows them to leverage existing algorithms for computing the volume of convex bodies.
  • Markov Chain Monte Carlo (MCMC) Sampling: To estimate the probabilistic distance for these polyhedral cones, they employ MCMC-based sampling algorithms. These algorithms efficiently sample points (utility functions) from the convex body (the set of consistent utility functions) according to a nearly uniform distribution. This allows for an approximate computation of the probabilistic distance.
  • Reduction to Volume Computation: The paper demonstrates that computing the probabilistic distance on partial utility functions under uncertainty can be reduced to the well-studied problem of computing the volume of polyhedral cones.

Datasets

The paper uses a dataset from a psychology experiment by Miyamoto and Eraker [12] involving 44 undergraduate students. These students provided certainty equivalences (CE) for standard gamble questions related to survival duration. The authors note that this dataset is particularly useful because it involves partially specified utility functions and is not amenable to distance measures that require complete information about decision alternatives.

Key Insights and Ideas

  • Uncertainty and Partial Preferences are Intertwined: The paper highlights that dealing with uncertainty in decision-making significantly complicates the measurement of preference similarity, especially when preferences are not fully known.
  • Geometric Representation is Powerful: Representing sets of utility functions as geometric shapes (polyhedral cones) unlocks powerful computational tools from computational geometry.
  • MCMC as a Bridge: Markov chain-based sampling provides an efficient way to approximate complex integrals and volumes, making the probabilistic distance computable even for infinite sets of utility functions.
  • Probabilistic Distance as a General Metric: The authors argue that the probabilistic distance is a principled way to measure similarity, applicable beyond recommender systems to various domains where understanding preference differences is crucial.

Key Results

The paper presents an algorithm for computing the probabilistic distance on partially specified utility functions under uncertainty. They demonstrate its use with the Miyamoto and Eraker dataset, showing that it can define similarity even when other measures fail. While specific quantitative results like accuracy improvements are not the primary focus, the paper establishes the feasibility and methodology for computing this distance in complex, real-world scenarios. They also note that the probabilistic distance is not a metric on partial orders themselves (it can be positive even for identical partial orders), which they argue is desirable as it reflects potential differences in complete preference orders.

Limitations and Future Work

  • Computational Complexity: While MCMC provides an approximation, computing the volume of convex bodies and thus the probabilistic distance can still be computationally intensive, especially for high-dimensional spaces.
  • Assumption of Linear Constraints: The method relies on the assumption that sets of consistent utility functions can be represented as polyhedral cones, which is a reasonable assumption for many common utility models but might not cover all cases.
  • Inconsistency in Data: The authors acknowledge that real-world data, like the psychology experiment data, often exhibits inconsistencies in responses, which they handle through a sampling approach. They suggest that more robust methods for dealing with such inconsistencies could be explored.
  • Future Work: The authors are actively investigating medical decision problems as potential applications for their case-based preference elicitation approach, highlighting the need for available patient utility databases. They also suggest that the probabilistic distance is a valuable tool for the general study of partial orders, a topic they believe has not received adequate treatment.

Summary updated

BibTeX
@inproceedings{ha2001similarity,
  author = {Vu A. Ha and Peter Haddawy and John Miyamoto},
  title = {{Similarity Measures on Preference Structures, Part II: Utility Functions}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2001},
}

Loading related content...

Figure