Efficient Utility Functions for Ceteris Paribus Preferences

Ceteris paribus (other things being equal) preference provides a convenient means for stating constraints on numeric utility functions, but direct constructions of numerical utility representations from such statements have exponential worst-case cost. This paper describes more efficient constructions that combine analysis of utility independence with constraint-based search.