Structured Preference Representation and Multiattribute Auctions

Abstract

Handling preferences over multiple objectives (or attributes) poses serious challenges to the development of automated solutions to complex decision problems. The number of decision outcomes grows exponentially with the number of attributes, and that makes elicitation, maintenance, and reasoning with preferences particularly complex. This problem can potentially be alleviated by using a factored representation of preferences based on independencies among the attributes. This work has two main components. The first component focuses on development of graphical models for multiattribute preferences and utility functions. Graphical models take advantage of factored utility, and yield a compact representation for preferences. Specifically, I introduce CUI networks, a compact graphical representation of utility functions over multiple attributes. CUI networks model multiattribute utility functions using the well studied utility independence concept. I show how conditional utility independence leads to an effective functional decomposition that can be exhibited graphically, and how local conditional utility functions, depending on each node and its parents, can be used to calculate joint utility. The second main component deals with the integration of preference structures and graphical models in trading mechanisms, and in particular in multiattribute auctions. I first develop multiattribute auctions that accommodate generalized additive independent (GAI) preferences. Previous multiattribute mechanisms generally either remain agnostic about traders’ preference structures, or presume highly restrictive forms, such as full additivity. I present an approximately efficient iterative auction mechanism that maintains prices on potentially overlapping GAI clusters of attributes, thus decreasing elicitation and computation burden while allowing for expressive preference representation. Further, I apply preference structures and preference-based constraints to simplify the particularly complex, but practically useful domain of multi-unit multiattribute auctions and exchanges. I generalize the iterative multiattribute mechanism to a subset of this domain, and investigate the problem of finding an optimal set of trades in multiattribute call markets, given restrictions on preference expression. Finally, I apply preference structures to simplify the modeling of user utility in sponsored-search auctions, in order to facilitate ranking mechanisms that account for the user experience from advertisements. I provide short-term and long-term simulations showing the effect on search-engine revenues.