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:
- 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.
- 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.
- 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.
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.
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