Compactly representing utility functions using weighted goals and the max aggregator

摘要

Weighted propositional formulas can be used to model preferences over combinatorial domains: each formula represents a goal we would like to see satisfied, the weight of a formula represents the importance of the goal in question, and to assess the desirability of a given alternative we aggregate the weights of the goals satisfied by that alternative. One of several options is to aggregate by using the maximum of the weights of the satisfied goals. This approach gives rise to a family of preference representation languages, one for each of a range of possible restrictions we can impose on either formulas or weights. We analyze the properties of these languages and establish results regarding their expressivity, and absolute and relative succinctness. We also study the computational complexity of the problem of finding the best and the worst alternative for a given set of weighted goals, and of finding an alternative that is optimal for a group of agents, for a range of different notions of collective optimality proposed in social choice theory and welfare economics.