Choquet Optimization Using GAI Networks for Multiagent/Multicriteria Decision-Making
This paper is devoted to preference-based recommendation or configuration in the context of multiagent (or multicriteria) decision making. More precisely, we study the use of decomposable utility functions in the search for Choquet-optimal solutions on co
- PDF / 315,439 Bytes
- 13 Pages / 430 x 660 pts Page_size
- 57 Downloads / 197 Views
Abstract. This paper is devoted to preference-based recommendation or configuration in the context of multiagent (or multicriteria) decision making. More precisely, we study the use of decomposable utility functions in the search for Choquet-optimal solutions on combinatorial domains. We consider problems where the alternatives (feasible solutions) are represented as elements of a product set of finite domains and evaluated according to different points of view (agents or criteria) leading to different objectives. Assuming that objectives take the form of GAIutility functions over attributes, we investigate the use of GAI networks to determine efficiently an element maximizing an overall utility function defined by a Choquet integral. Keywords: GAI-nets, Choquet Integral, Multiobjective Combinatorial Optimization, Multiagent Decision-Making, Preference-based Configuration.
1
Introduction
The multiplication of preference-based configuration problems has stressed the need for compact preference representation languages and for preference-based optimization algorithms. In this area, graphical models are omnipresent. One can distinguish non-numerical models like CP-nets [1,2] and their extension to the multiagent case mCP-nets [3] on the one hand, and numerical models based on decomposable utility functions like UCP-nets [4] and GAI-nets [5,6,7] on the other hand. In this paper, we investigate the potential of GAI-networks to represent and solve decision making problems where the performance of a solution is evaluated according to different points of view. This type of problem occurs when several criteria, possibly conflicting, must be considered in the decision analysis, or when several agents are involved in the decision process. In both cases, any feasible solution is represented by a vector of utilities. Assuming that each of these utilities is defined by a GAI-decomposable model, we study the use of GAI-nets to determine efficiently a solution having a utility vector maximizing an overall utility function defined by a Choquet integral. The paper is organized as follows: in Section 2 we explain how GAI-networks are used to represent preferences in multiobjective problems. Then, after recalling F. Rossi and A. Tsoukis (Eds.): ADT 2009, LNAI 5783, pp. 377–389, 2009. c Springer-Verlag Berlin Heidelberg 2009
378
J.-P. Dubus, C. Gonzales, and P. Perny
basic notions linked to capacities and Choquet integrals (Section 3), we introduce a vector-passing algorithm for Choquet-optimization (Section 4). Under the assumption of convex capacity, we propose a refinement of the previous algorithm and a second algorithm based on a ranking procedure (Section 5). Both algorithms have been implemented and tested on randomly drawn instances. The solutions times obtained are given for the sake of comparison (Section 6).
2
GAI Models for Individual and Collective Preferences
In configuration problems, alternatives (feasible solutions) are characterized by n variables (or attributes) x1 , . . . , xn taking their values in finite domains X1 , . .
Data Loading...
