Preference Aggregation with Graphical Utility Models

Christophe Gonzales, Patrice Perny, Sergio QueirozAAAI 2008

Abstract

Collective decision-making over complex, multi-attribute options often faces the challenge of exponential search spaces and interacting individual preferences. This paper proposes an efficient framework for finding fair, Pareto-optimal compromises by representing preferences through Generalized Additive Independent (GAI) models. By leveraging a graphical utility structure and a specialized ranking algorithm with a provable stopping condition, the approach identifies optimal solutions in combinatorial spaces as large as $10^{20}$ within seconds.

Introduction

In group decision-making scenarios—such as selecting a vacation package or configuring a vehicle—options are typically defined by numerous attributes. The resulting combinatorial explosion makes exhaustive search infeasible. Furthermore, individual preferences are rarely simple; they often involve interactions between attributes (e.g., a preference for specific wine-food pairings). While Generalized Additive Independent (GAI) models can capture these nuances, aggregating them to find a fair compromise is computationally NP-hard. This work bridges the gap between expressive preference modeling and efficient collective optimization.

Methodology

The proposed framework identifies the best compromise by minimizing the weighted Tchebycheff norm, which aims to maximize the satisfaction of the least satisfied group member. The process involves three primary stages:

  1. Scalarization: The complex fairness function is approximated using a simpler weighted sum of agents' GAI utilities. This sum retains a GAI structure, facilitating easier optimization.
  2. Ranking: A specialized ranking algorithm for GAI networks employs a message-passing approach on a "GAI tree" to enumerate the top-$k$ solutions according to the weighted sum.
  3. Stopping Condition: The authors prove a "cut" condition (Proposition 1). By tracking the best compromise found during ranking, the algorithm can mathematically guarantee optimality once the weighted sum falls below a specific threshold, pruning the remaining search space.
A GAI tree representation used for local computations, decomposing global optimization into manageable sub-problems.

The core efficiency stems from decomposing global optimization into local computations on the graphical model, as illustrated in the GAI tree structure.

Experimental Evaluation

The approach was evaluated using synthetic datasets featuring 20 attributes and 10 overlapping sub-utility functions. The experiments varied the number of agents ($m = 3, 5, 7$) and attribute domain sizes (2, 5, 10), creating search spaces of up to $10^{20}$ configurations.

Performance results showing computation time $t(s)$ and the number of generated solutions (#gen) across different group sizes $m$ and domain sizes.

The results demonstrate high efficiency for small to medium groups. For groups of 3 and 5, the average computation time remained under one second. While scaling to 7 agents with a domain size of 10 increased the time to approximately 44 seconds, the algorithm remained practical for semi-interactive systems. Notably, the stopping condition allowed the algorithm to find the optimal compromise by examining only a tiny fraction (e.g., 1.5 million out of $10^{20}$) of the total possible solutions.

Conclusion

By utilizing cardinal utility and graphical models, this framework bypasses traditional social choice impossibility results and provides a scalable solution for group preference aggregation. While performance is sensitive to the structural similarity of agent preferences and the total number of agents, the use of heuristic bounding and GAI trees offers a robust path forward for complex multi-attribute decision support.

Summary updated

BibTeX
@inproceedings{gonzales2008preference,
  author = {Christophe Gonzales and Patrice Perny and Sergio Queiroz},
  title = {{Preference Aggregation with Graphical Utility Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure