Multi−Objective Variable Elimination for Collaborative Graphical Games

Abstract

In cooperative multi-agent systems, the number of possible joint actions grows exponentially in the number of agents. Consequently, exploiting loose couplings, as expressed in graphical models, are key to computationally efficient decision making in such settings. However, existing methods such as variable elimination for solving such models assume there is a only a single objective. In contrast, many real-world problems are characterized by the presence of multiple objectives to which the solution is not a single action but the set of actions optimal for all trade-offs between the objectives. In this paper, we propose a new method for multi-objective multi-agent graphical games called multi-objective variable elimination, which replaces the maximization performed by variable elimination with an operator that prunes away dominated solutions. We prove the correctness of the proposed method and analyze its complexity. We also present an empirical study that shows that this method can tackle multi-objective problems much faster than those that do not exploit loose couplings, and analyzes its scalability with respect to multiple factors such as the number of objectives, the number of agents, the induced width of the graphical model, and the size of the solution set.