Bruno Escoffier
email: escoffier@lamsade.dauphine.fr

Vangelis Th

Paschos
email: paschos@lamsade.dauphine.fr

Completeness in approximation classes beyond APX

We present a reduction that allows us to establish completeness results for several approximation classes mainly beyond APX. Using it, we extend one of the basic results of S. Khanna, R. Motwani, M. Sudan, and U. Vazirani (On syntactic versus computational views of approximability, SIAM J. Comput., 28:164-191, 1998) by proving the existence of complete problems for the whole Log-APX, the class of problems approximable within ratios that are logarithms of the size of the instance. We also introduce a new approximability class, called Poly-APX(∆), dealing with graph-problems approximable with ratios functions of the maximum degree ∆ of the input graph. For this class also, using the reduction propose, we establish complete problems.

1 An NPO problem is an optimization problem, the decision version of which is in NP.

Introduction and preliminaries

Consider an NPO problem 1 Π = (I Π , Sol Π , m Π , goal Π ), where: I Π denotes the set of instances of Π; for any instance x ∈ I Π , Sol Π (x) is the set of feasible solutions of x; for any x ∈ I Π and any y ∈ Sol(x), m Π (x, y) denotes the value of y; finally, goal Π is max, or min. For any x ∈ I Π , let opt Π (x) be the value of an optimal solution for x. Then, the approximation ratio of an algorithm A computing a feasible solution A(x) = y ∈ Sol(x) is defined by m Π (x, y)/opt Π (x). The objective of the polynomial approximation theory is double: on the one hand it aims at devising polynomial algorithms achieving good approximation ratios for NP-hard problems; on the other hand, it aims at building a hierarchy of these problems, elements of which correspond to strata of problems sharing common approximability properties (they notably are approximable within comparable -in some predefined sense -approximation ratios) and at investigating relations between problems in the same stratum (notably to exhibit problems that are harder from others). This second objective is the scientific are called in short structure in approximability classes.

Study of structure in approximability classes is in the heart of the research in polynomial approximation since the seminal papers of [START_REF] Orponen | On approximation preserving reductions: complete problems and robust measures[END_REF][START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF][START_REF] Crescenzi | Completeness in approximation classes[END_REF]. By using suitable approximation-preserving reductions, the existence of natural complete problems for almost all the known approximation classes has been established. For instance, max wsat for NPO under AP-reduction ( [START_REF] Ausiello | Complexity and approximation[END_REF][START_REF] Crescenzi | Structure in approximation classes[END_REF]), or PTAS-reduction ( [START_REF] Crescenzi | On approximation scheme preserving reducibility and its applications[END_REF]), max wsat-B for APX, the class of the problems approximable within (fixed) constant ratios, under P-reduction ( [START_REF] Crescenzi | Completeness in approximation classes[END_REF]), max 3-sat for APX under AP-reduction ( [START_REF] Ausiello | Complexity and approximation[END_REF][START_REF] Crescenzi | Structure in approximation classes[END_REF]), or PTAS-reduction ( [START_REF] Crescenzi | On approximation scheme preserving reducibility and its applications[END_REF]), max planar independent set for PTAS, the class of the problems solvable by polynomial time approximation schemata, under FT-reduction ( [START_REF] Bazgan | Completeness in standard and differential approximation classes: Poly-(D)APX-and (D)PTAS-completeness[END_REF]), max independent set for Poly-APX under PTAS-reduction ( [START_REF] Bazgan | Completeness in standard and differential approximation classes: Poly-(D)APX-and (D)PTAS-completeness[END_REF]). Also, under E-reduction, completeness in Log-APX-PB, the subclass of Log-APX dealing with polynomially bounded problems (the class of problems whose values are bounded by a polynomial in the size of the instance), has also been established. One problem that, to our knowledge, remains open from this ambitious but so successful research program, is the establishing of completeness for the whole Log-APX.

As one can see by the unravelling of the fascinating history of the approximation-preserving reductions, the one that allows achievement of the most of completeness results is the PTASreduction, originally introduced in [START_REF] Crescenzi | On approximation scheme preserving reducibility and its applications[END_REF]. Let Π and Π ′ be two maximization NPO problems (the case of minimization is completely analogous). We say that Π PTAS-reduces to Π ′ if and only if there exist three functions f , g and c such that:

• for any x ∈ I Π and any ε ∈]0, 1[, f (x, ε) ∈ I Π ′ ; f is computable in time polynomial with |x|;

• for any x ∈ I Π , any ε ∈]0, 1[ and any y ∈ Sol(f (x, ε)), g(x, y, ε) ∈ Sol(x); g is computable in time polynomial with |x| and |y|;

• c :]0, 1[→]0, 1[; • for any x ∈ I Π and any ε ∈]0, 1[, r Π ′ (f (x, ε), y) 1 -c(ε) implies r Π (x, g(x, y, ε)) 1 -ε.
This is the successor of a number of powerful reductions as the L-reduction ( [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF]) or the Ereduction ( [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF]) that, even if they allowed achievement of completeness results in natural approximability sub-classes (e.g., Max-SNP ⊂ APX, for the former, or Log-APX-PB ⊂ Log-APX, for the latter) were not able to extend them to the whole of the classes dealt. In fact, as shown in [START_REF] Crescenzi | On approximation scheme preserving reducibility and its applications[END_REF], these reductions suffered from the fact that they map optimal solutions to optimal solutions and, in this sense, it is very unlikely that they can allow completeness of a polynomially bounded problem in the classes dealt (unless

P sat = P sat[O(log(n))]
, where P sat and P sat[O(log(n))] are the classes of decision problems solvable by using, respectively, a polynomial and a logarithmic number of calls to an oracle solving sat). On the contrary, PTAS-reduction, by allowing functions f and g to depend on ε, does not necessarily map optimal solutions between them and consequently, it allows that general problems are PTAS-reducible to polynomially bounded ones. Indeed, by means of PTAS-reduction it is proved in [START_REF] Crescenzi | On approximation scheme preserving reducibility and its applications[END_REF] that max wsat-B reduces max wsat-B with weights bounded by a polynomial to the size of the instance.

In [START_REF] Bazgan | Completeness in standard and differential approximation classes: Poly-(D)APX-and (D)PTAS-completeness[END_REF] the power of PTAS-reduction has been confirmed since it has allowed the achievement of Poly-APX-complete problems. This was not possible with the E-reduction under which only Poly-APX-PB completeness have been obtained in [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF]. Given a family F of functions, denote by F-APX the subclass of NPO whose problems are approximable in polynomial time within ratio g(n) (in the case of minimization), or 1/g(n) (for maximization), for a g ∈ F. Here we further confirm its scope by generalizing the result of [START_REF] Bazgan | Completeness in standard and differential approximation classes: Poly-(D)APX-and (D)PTAS-completeness[END_REF], providing a way to find complete problems, under PTAS-reducibility, for any approximation class F-APX, where F is a class of polynomially bounded functions. This in particular allows us to establish the Log-APXcompleteness of min set cover. Recall that, in [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF], only the Log-APX-PB completeness of this problem has been established under the E-reduction.

Before continuing, we define some key-notions for what follows, namely, additivity and canonical hardness of a maximization NPO problem. They are introduced in [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF]. A problem Π ∈ NPO is said additive if and only if there exist an operator ⊕ and a function f , both computable in polynomial time, such that:

• ⊕ associates with any pair (x 1 , x 2 ) ∈ I Π × I Π an instance x 1 ⊕ x 2 ∈ I Π with opt(x 1 ⊕ x 2 ) = opt(x 1 ) + opt(x 2 );
• with any solution y ∈ sol Π (x 1 ⊕ x 2 ), f associates two solutions y 1 ∈ sol Π (x 1 ) and

y 2 ∈ sol Π (x 2 ) such that m Π (x 1 ⊕ x 2 , y) = m Π (x 1 , y 1 ) + m Π (x 2 , y 2 ).
A set F of functions from N to N will be called downward close if, for any function g ∈ F and any constant c, if h(n) = O(g(n c )), then h ∈ F. A function g : N → N is hard for F if and only if, for any h ∈ F, there exists a constant c such that h(n) = O(g(n c )); if, in addition, g ∈ F, then g is said complete for F.

A maximization (resp., minimization) problem Π ∈ NPO is canonically hard for F-APX, for a downward close family F of functions, if and only if there exist a polynomially computable function f , two constants n 0 and c and a function F , hard for F, such that:

• for any instance ϕ of 3sat on n n 0 variables and for any N n c , f (ϕ, N ) belongs to I Π ;

• if ϕ is satisfiable, then opt(f (ϕ, N )) = N ; • if x is not satisfiable, then opt(f (ϕ, N )) = N/F (N ) (resp., N F (N )); • for any y ∈ sol Π (f (ϕ, N )) such that m(f (ϕ, N ), y) > N/F (N ) (resp., m(f (ϕ, N ), y) < N F (N ))
, one can polynomially determine a truth assignment satisfying ϕ.

More generally, since 3sat is NP-complete, a maximization (resp., minimization) problem Π is canonically hard for F-APX if and only if, for any decision problem Π ′ ∈ NP, given an instance x ′ of Π ′ , one can construct in polynomial time an instance x of Π such that:

• if x ′ is a positive instance, then opt(x) = N ; • if x ′ is a negative instance, then opt(x) = N/F (N ) (resp. N F (N )); • given a solution y ∈ sol Π (x) such that m(x, y) > N/F (N ) (resp., < N F (N ))
, one can polynomially determine a certificate proving that x ′ is a positive instance.

In [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF], the following major theorem is proved, that constitutes the starting point of the paper at hand.

Theorem 1. ([9]

) Let F be any class of downward close polynomially bounded functions and Ω be an additive maximization problem canonically hard for F. Then, any maximization problem Π ∈ F-APX-PB (the class of problems in F-APX whose values are bounded by a polynomial with the size of the instance) E-reduces to Ω.

In order to extend result of Theorem 1, and since, as we have already mentioned, it seems very unlikely that one could establish completeness for the whole F-APX under E-reducibility (at least for polynomially bounded problems), we introduce a modification of PTAS-reducibility, called MPTAS-reduction, M standing for multivalued, where function f is allowed to be multivalued. Formally, MPTAS-reduction can be defined as follows.

Definition 1. Let Π and Π ′ be two maximization NPO problems (the case of minimization is completely analogous). Then, Π MPTAS-reduces to Π ′ , if and only if there exist three functions f and g, computable in polynomial time, and a function c such that:

• for any x ∈ I Π and any ε ∈]0, 1[, f (x, ε) = (f 1 (x, ε), f 2 (x, ε), . . .
) is a family of instances of Π ′ (this family is necessarily of size polynomial with x);

• for any x ∈ I Π , any ε ∈]0, 1[ and any family of feasible solutions y = (y 1 , y 2 , . . .), where y i is a feasible solution of f i (x, ε), g(x, y, ε) ∈ Sol(x);

• c :]0, 1[→]0, 1[;
• there exists an index j such that, for any x ∈ I Π and any

ε ∈]0, 1[, r Π ′ (f j (x, ε), y j ) 1-c(ε) implies r Π (x, g(x, y, ε)) 1 -ε.
It is easy to see that MPTAS-reduction preserves membership in PTAS.

We show that using MPTAS-reducibility, F-APX-completeness can be extended for any class F of functions even if they are not polynomially bounded. Furthermore, the fact that function f in Definition 1 is allowed to be multivalued, relaxes the restriction to additive problems. As we will see, as a corollary, we have an alternative proof (without explicite use of the Cook-Levin theorem) for the Exp-APX-completeness of min tsp on general graphs, where Exp is the class of exponential functions (note that the NPO-completeness of min tsp immediately derives its Exp-APX-completeness).

The approximation classes beyond APX dealt until now in the literature are defined with respect ratios depending on the size of the instances and not on other parameters even natural. This can be considered as somewhat restrictive given that a lot of approximation (and of inapproximability results) are established with respect to other parameters of the instances. Such parameters can be, for example, the maximum or the average degree of the input-graph, when dealing with graph-problems, the maximum set-cardinality, when dealing with problems on set-systems as the min set cover, or the max set packing, So, the third and last issue of this paper is to consider the class Poly-APX(∆), of maximization (resp., minimization) graph-problems approximable within ratios which are inverse polynomials (resp., polynomials) of the maximum degree ∆ of the input-graph. We prove that max independent set is complete for this class, under MPTAS.

F-APX-completeness for any downward close function

We show in this section that, using MPTAS-reduction (Definition 1), we can apprehend completeness for any class F-APX even containing exponential functions. In a first time we shall deal with maximization problems. Extension to minimization problems will be performed after the proof of Theorem 2 that follows.

Theorem 2. Let F be a class of downward close functions, and Ω ∈ NPO be a maximization problem canonically hard for F-APX. Then, any maximization NPO problem in F-APX MPTAS-reduces to Ω.

Proof. Let Π be a maximization problem of F-APX and let A be an algorithm achieving approximation ratio 1/r(•), r ∈ F. Since Π ∈ NPO, the value of the solutions for any instance x ∈ I Π is bounded above by 2 p(|x|) for some polynomial p. Let Ω be as assumed in theorem's statement. Let F be a function hard for F, and k, n 0 and c ′ be constants such that, for n n 0 r(n) -1 k(F (n c ′ ) -1). Finally, consider x ∈ I Π and ε ∈ (0, 1).

In order to build function f (x, ε), claimed by Definition 1, we first partition interval [1, 2 p(|x|) ] of the possible values for opt(x) into a polynomial number of subintervals

[(1/(1 -ε)) i-1 , (1/(1 - ε)) i ], for i = 1, . . . , M = ⌈p(|x|) ln 2/ ln(1/(1 -ε))⌉ (i.e., (1/(1 -ε)) M 2 p(|x|) ). Consider then, for i = 1, . . . , M , the languages L i = {x ∈ I Π : opt Π (x) (1/(1 -ε)) i-1 }. Set N = |x| c ′ .
Since Ω is canonically hard for F-APX, we can build, for any i = 1, . . . , M , an instance

ω i ∈ I Ω such that, if x ∈ L i , then opt Ω (ω i ) = N , otherwise, opt Ω (ω i ) = N/F (N ). We set f (x, ε) = Υ = (ω i , 1 i M ).
We now show how g(x, y, ε) can be built. Consider a solution y = (y 1 , . . . , y M ) of Υ. Then, for any i ∈ {1, . . . , M }, if m Ω (ω i , y i ) > N/F (N ), one can find a polynomial certificate proving that x ∈ L i , i.e., a solution

y ′ i ∈ Sol(x) such that m Π x, y ′ i 1 1 -ε i-1 (1)
otherwise (i.e., if m Ω (ω i , y i ) N/F (N )), we consider solution A(x). Finally, g(x, y, ε) is the best among the solutions so produced.

Let us now prove that we really deal with an MPTAS-reduction. Let j be an index verifying:

1 1 -ε j-1 opt Π (x) 1 1 -ε j (2) and set c(ε) = ε/(ε + k(1 -ε)).
Assume first that m Ω (ω j , y j ) > N/F (N ). Then, using ( 1) and ( 2), we get:

m Π (x, g(x, y, ε)) opt Π (x) 1 -ε
On the other hand, if m Ω (ω j , y j ) N/F (N ), then ρ(ω j , y j ) 1 -c(ε) implies:

1 F (N ) k(1 -ε) ε + k(1 -ε) (3)
By the assumptions made above, we have:

F (N ) 1 + r(|x|) -1 k (4) ρ (x, g (x, y, ε)) 1 r(|x|) (5)
Using ( 3), ( 4) and ( 5), we get the following implications:

ρ (ω j , y j ) 1 -c(ε) =⇒ 1 + r(|x|) -1 k ε + k(1 -ε) k(1 -ε) =⇒ r(|x|) 1 + k ε k(1 -ε) = 1 1 -ε i.e., ρ(x, g(x, y, ε))
1 -ε. So, the reduction exhibited is indeed a MPTAS-reduction and the proof of the theorem is completed.

In order to extend the result of Theorem 2 to minimization problems, we are based upon an analogous result in [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF]. Let Π be a maximisation problem in F-APX approximable within ratio 1/f (•). One can define a minimization problem Π ′ , identical to Π up to its objective function defined as: m Π ′ (x, y) = ⌊2M 2 (x)/m Π (x, y)⌋, where M (x) is an upper bound for the values in Sol(x). Then, Π E-reduces (hence, MPTAS-reduces also) to Π ′ and, furthermore, Π ′ is approximable within ratio f (•)(1 + 2/M (x)). In completely analogous way, one can MPTASreduce a minimization problem, approximable within ratio f (•), to a maximization problem approximable within ratio 1/(f (•)(1+2/M (x))). This allows the existence of additive canonically hard minimization problems also to be F-APX-complete, since the above transformation derives, from such a problem Π, an additive canonically hard maximization problem Π ′ (notice that f (•) and f (•)(1 + 2/M (x)) have the same hardness status with respect to F). Then, it suffices that one applies Theorem 2 as stated. The remark above applies for any family F. As a consequence, throughout this paper we restrict ourselves to maximization problems. Theorem 3 . Let F be a class of downward close functions, and Ω ∈ NPO be a problem canonically hard for F. Then, any NPO problem in F-APX MPTAS-reduces to Ω.

From the discussion above, two are the main differences between Theorems 1 and 3. The first one is, as it has been already announced, that the latter one applies to the whole of the problems of any class F-APX and not only to the bounded ones. The second difference is that, the use of a multivalued version of PTAS-reduction allows us to relax additivity from the conditions of Theorem 1 enlarging so the scope of the applicability of Theorem 3.

Obviously, the negative result for min tsp of [START_REF] Sahni | P-complete approximation problems[END_REF] (see also [START_REF] Garey | Computers and intractability. A guide to the theory of NP-completeness[END_REF]) can immediately be extended for showing that min tsp is canonically hard for Exp-APX. Consequently, the Exp-APXcompleteness of min tsp can be derived as an immediate corollary of Theorem 3.

Corollary 1. min tsp is Exp-APX-complete under MPTAS-reducibility.

Log-APX-completeness

We deal in this section with Log-APX. For this class, as well as for any class of polynomially bounded downward close functions, we can obviously apply Theorem 3 to get completeness sufficient conditions. However, in what follows, we will use the fact that functions dealt are polynomially bounded in order to prove an equivalent of Theorem 3 but with respect to PTASreducibility. As noticed above, we can restrict ourselves to maximization problems. Theorem 4. Let F be any class of downward close polynomially bounded functions and Ω be an additive maximization problem canonically hard for F-APX. Then, any maximization problem Π ∈ F-APX PTAS-reduces to Ω.

Proof. The proof goes along the lines of the corresponding proof of [START_REF] Bazgan | Completeness in standard and differential approximation classes: Poly-(D)APX-and (D)PTAS-completeness[END_REF] for Poly-APX. Let Π be a maximization problem of F-APX and let A be an achieving approximation ratio 1/r(•), r ∈ F. Let Ω be as assumed in theorem's statement. Let F be a function hard for F, and k, n 0 and c ′ be constants such that, for n n 0 , r(n) k(F (n c ′ )-1). Finally, consider x ∈ I Π , ε ∈ (0, 1) and set |x| = n.

We first construct function f (x, ε). Set m(x, A(x)) = m opt Π (x)/r(n). Partition the interval [0, mr(n)] of the possible values for opt Π (x) into q(n) regular subintervals, where q(n) is bounded by polynomial of n. More precisely, we set q(n) = r(n)/ε. Consider now, for i ∈ {1, . . . , q(n)}, the sets of languages

L i = {x ∈ I Π : opt Π (x) imr(n)/q(n)} and set N = n c ′ .
Since Ω is canonically hard for F-APX, one can build, for any i, an instance

ω i ∈ I Ω such that, if x ∈ L i , then opt Ω (ω i ) = N and if x / ∈ L i , then opt Ω (ω i ) = N/F (N ). We define f (x, ε) = Υ = ⊕ 1 i q(n) ω i . Observing that r(n)/q(n) = ε, we get: opt Ω (Υ) = N |{i q(n) : opt Π (x) imε}| + N F (N ) (q(n) -|{i q(n) : opt Π (x) imε}|) (6)
We now construct function g(x, y, ε). Consider a solution y ∈ Sol(Υ). By the additivity of Ω, one can compute, for any ω i , a solution y i in such a way that m Ω (Υ, y) = i m Ω (ω i , y i ). Let j be the largest among the indices i such that m Ω (ω i , y i ) > N/F (N ) (j = 0, if no i verifies the inequality). Then, one can find a polynomial certificate proving that ∈ L j , i.e., a solution y ′ 1 ∈ Sol(x) verifying: m Π = (x, y ′ 1 ) jmε. Furthermore, m Ω (Υ, y) N j + (q(n) -j)N/F (N ). We then define g(x, y, ε) = y ′ as the best (the largest value one) among y ′ 1 and y ′ 2 = A(x). Obviously, m Π (x, y ′ ) max{m, jmε}.

Let us now prove that the reduction described is indeed a PTAS-reduction. We first notice that, using expressions for m Π and m Ω , the following inequality is derived (after some algebra) for the approximation ratio Ω (Υ, y), using that q(n) = r(n)/ε k(F (N ) -1)/ε:

ρ Ω (Υ, y) j + k ε opt Π (x) εm -1 + k ε
We now consider two cases, namely, j 1/ε and j 1/ε. For the first one, j 1/ε, we get from the expression for ρ Ω (after some algebra and using also that ρ (x, y ′ ) m/opt Π (x)):

ρ Ω (Υ, y) ρ Π (x, y ′ ) (1 + k) 1 + ρ Π (x, y ′ ) (k -ε)
On the other hand, if j 1/ε, noticing that, using expression for m Π , ρ Π (x, y ′ ) jmε/opt Π (x), we also get:

Ω (Υ, y) ρ Π (x, y ′ ) (1 + k) 1 + ρ Π (x, y ′ ) (k -ε) Assume c(ε) = ε 2 /(1 + (1 -ε)(k -ε))
. Then, after some algebra one gets: ρ Π (x, y ′ ) 1 -ε, proving so that the reduction just devised is indeed a PTAS-reduction and completing the proof of the theorem.

Consider now Log-APX, the class of NPO problems approximable with logarithmic (resp., inversely logarithmic when goal = max) ratios, i.e., within ratios O(log(•)) (resp., O(1/ log(•))). Consider also min set cover that is approximable within ratio O(log n) ( [START_REF] Slavík | A tight analysis of the greedy algorithm for set cover[END_REF]), where n is the size of the ground set in the instance, but canonically hard to approximate within ratios O(log n) ( [START_REF] Raz | A sub-constant error probability low-degree test and a sub-constant error probability PCP characterization of NP[END_REF]). Moreover, one can easily see that min set cover is additive. So, immediate application of Theorem 4 definitely settles the status of min set cover with respect to the class Log-APX. Theorem 5. min set cover is Log-APX-complete under PTAS-reducibility.

Completeness in F-APX(∆)

We now deal with a new approximation class, namely, the class of graph-problems approximable with ratio f (∆), where ∆ is the degree of the input-graph, i.e., the maximum degree of its vertices, F a downward class of functions and f ∈ F. Definition 2. Let F be a downward close class of functions and Π ∈ NPO be a maximization (resp., minimization) graph-problem. Then, Π is said canonically hard for F-APX(∆), if there exist three functions f , α and β, computable in polynomial time, a constant ∆ 0 and a function F , hard for F such that:

• for any instance ϕ of 3-sat and any ∆ ∆ 0 , G ϕ = f (ϕ, ∆) is a graph (instance of Π) of maximum degree ∆;

• if ϕ is satisfiable, then opt Π (G ϕ ) α(G ϕ ) (resp., opt Π (G ϕ ) α(G ϕ )); • if ϕ is not satisfiable, then opt Π (G ϕ ) β(G ϕ ) (resp., opt Π (G ϕ ) β(G ϕ )); • α(G ϕ )/β(G ϕ ) f (∆) (resp., β(G ϕ )/α(G ϕ ) f (∆));
• given a solution y ∈ sol(G ϕ ) of value strictly greater (resp., smaller) than β(G ϕ ), one can determine, in polynomial time a truth assignment satisfying ϕ.

For the same reasons as previously, we will restrict ourselves to maximization problems and are going to prove the following theorem. n) ] in same way as in the proof of Theorem 2, and we consider, for any i, the analogous sets L i of languages. We set ∆ = ∆ c ′ (G), we build, for any i an instance

H i of Ω, of maximum degree ∆ such that if G ∈ L i , then opt Ω (H i ) α(H i ), otherwise opt Ω (H i ) β(H i ), with α(H i )/β(H i ) F (∆) and, finally we specify f (G, ε) = H = (H i , 1 i M ).
Function g(G, y, ε) is defined as in the proof of Theorem 2, setting β(H i ) instead of N/F (N ). The proof for the transfer of the approximation ratios is also done in the same way as there (always with β(H i ) instead of N/F (N )).

Denote by Poly-APX(∆) the subclass of the graph-problems in NPO which are approximable within polynomials of ∆ -1 (of ∆ when dealing with minimization problems). We are going now to establish an interesting completeness result for this class by showing that one of the most paradigmatic problems for the polynomial approximation theory and the combinatorial optimization, the max independent set, is complete for Poly-APX(∆). For this we will use the following theorem ( [START_REF] Alon | Derandomized graph products[END_REF]).

Theorem 7. ([1]) Let (a, b) ∈ [0, 1] 2 , a > b.
There exists ε 0 > 0 that, for any ∆ 3, there exists a function f that transforms an instance G of max independent set into an instance of max independent set-∆, i.e., into a graph with degree bounded by ∆, and two positive quantities α and β such that:

• if opt(G) an, then opt(f (G)) α(f (G)); • if opt(G) bn, then opt(f (G)) β(f (G)); • α(f (G))/β(f (G)) ∆ ε 0 .
Thanks to the PCP theorem, stating that there exist a and b that it is NP-complete to distinguish graphs with maximum independent set with size at least a times their order, from graphs having maximum independent set at most b times their order, the following corollary can be derived ( [START_REF] Alon | Derandomized graph products[END_REF]).

Corollary 2. ([1]

) There exists an ε 0 such that, for any ∆ 3, max independent set-∆ is not approximable within ratio ∆ -ε 0 .

We will also use the following proposition, derived from an immediate application of the PCP theorem.

Proposition 1. There exists (a, b) ∈ [0, 1] 2 , a > b, such that, for any Π ∈ NP there exists a function f which transforms an instance x of Π into a graph G = f (x), instance of max independent set, that verifies:

1. if x is positive, then opt(G) an;

2. if x is negative, then opt(G) bn;

3. given an independent set S in G with size |S| > bn, one can determine, in polynomial time, a witness proving that x is positive.

Indeed, Proposition 1, is an approximation preserving transfer, by say an L-reduction ( [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF]), of an analogous result dealing with max 3-sat (appearing in [START_REF] Arora | Proof verification and intractability of approximation problems[END_REF]) to max independent set. Theorem 8. There exists an ε 0 > 0 such that, for any ∆ 3, given Π ∈ NP, there exists a function f computable in polynomial time, that transforms an instance x of Π into a graph G = f (x), instance of max independent set, and two positive quantities α and β verifying:

1. if x is positive, then opt(G) α(G); 2. if x is negative, then opt(G) β(G);

the maximum degree of G is ∆;

4. α(G)/β(G) ∆ ε 0 ; 5. given an independent set S of G such that |S| > β, one can build, in polynomial time, a certificate proving that x is positive.

Proof. Items 1 to 4 are direct applications of Theorem 7 and Proposition 1. Item 5 is derived by the proof of Theorem 7 in [START_REF] Alon | Derandomized graph products[END_REF]. Indeed, following the relations between the independent sets in G and those in its derandomized product f (G), from an independent set of f (G) of size strictly greater than β, one can easily derive an independent set of G of size b times the order of G. Then, using item 3 of Proposition 1, one can specify a polynomial certificate proving that x is positive.

Consider now Poly-APX(∆) and max independent set-∆. In order to apply Theorem 6, one has just to show that the complexity of the function f stated in Theorem 8 is polynomial in ∆. This is derived after a careful reading of the proof of Theorem 7 ( [START_REF] Alon | Derandomized graph products[END_REF]). So, the following theorem concludes the paper. Theorem 9. max independent set-∆ is Poly-APX(∆)-complete under MPTAS-reducibility.

Theorem 6 .

 6 If F is a downward close family of functions and Ω is a maximization problem canonically hard for F-APX(∆), then any problem in F-APX(∆) MPTAS-reduces to Ω. Proof. Consider a maximization problem Π ∈ F-APX(∆) a graph G ∈ I Π of order n and an algorithm A for Π achieving approximation ratio 1/r(∆(G)), where r ∈ F. The proof goes along the same line as the one of Theorem 2. For constructing function f (G, ε) claimed by Definition 1 we partition the interval [1, 2 p(


Vincent Mousseau
email: mousseau@lamsade.dauphine.fri

A general framework for constructive learning preference elicitation in multiple criteria decision aid

Keywords: Preference Elicitation, Multiple Criteria Decision Aiding, Constructive Learning iii

Multiple Criteria Decision Aid (MCDA) aims at providing support to a decision maker (DM) involved in a decision process. This requires a decision aiding process in which the DM and an analyst interact to build a model grounded on several criteria. This decision aiding process is usually composed of various phases among which the identification of the stakeholders, the definition of set of alternatives, construction of evaluation criteria, the elicitation of the DM's preferences. The later task require to organize a preference elicitation process.

In this paper, we aims at studying the nature of such elicitation process. We show that preference elicitation can be conceived so that the DM to elaborate his/her convictions along the elicitation process: constructive learning preference elicitation. We investigate the specificities of tools supporting such elicitation processes. We also provide a general framework to describe a large class of preference elicitation procedures.

Introduction

In order to provide support to a decision maker (DM) involved in a decision process, it is necessary to structure a decision aiding process in which the DM and an analyst interact to build a model which should provide insights on the decision problem. Multiple Criteria Decision Aid (MCDA) models the decision behavior as not necessarily driven by a single criterion but rather as a result of the aggregation of several conflicting criteria. Within this framework, the MCDA models and tools are based on the construction of an explicit family of criteria representing the relevant aspects of the decision problem.

The decision aiding process is usually composed of various phases among which the identification of the stakeholders, the definition of set of alternatives, the construction of evaluation criteria and the elicitation of the DM's preferences. The latter requires organizing a preference elicitation process and this paper aims at studying the nature of such a process.

The paper is organized as follows. In a first section, we define a preference elicitation process. We distinguish, in a second section, the descriptivist and constructivist approaches to preference elicitation and we show how preference elicitation can be conceived in a constructive learning perspective. The third part investigates the nature of the tools that support preference elicitation through constructive learning. Section 4 proposes a general framework to describe constructive learning preference elicitation procedures. Finally, concluding remarks provide insights into future research.

Preference elicitation process

A classical way to model the DM preferences on a set of alternatives A consists in using binary relations to represent how any two alternatives compare. Comparing two alternatives may result in various preference situations. Classical decision theory (see [START_REF] Fishburn | Utility Theory for Decision Making[END_REF]) distinguishes only two distinct preference relations: indifference and preference which are both considered as transitive.

The European school of multiple criteria decision aid (see [START_REF] Roy | An overview on 'the European School of MCDA: Emergence, basic features and current works[END_REF]) enriched this dichotomy by the introduction of an incomparability relation which represents the impossibility for the DM to choose one of the two above mentioned preference situations. Moreover, the European school does not hypothesize the transitivity of any of these relations. We will denote I the indifference relation on A (reflexive and symmetric), P the preference relation (irreflexive and asymmetric) and R the incomparability relation (symmetric et irreflexive).

Definition 1. A Relational Preference Structure is a set of binary relations (I,P,R) such that any pair of alternatives is contained in one and only one of these relations.

Multiple criteria preference modelling consists in building a family of n criterion functions g 1 , g 2 , . . . , g n , (n ≥ 2), each of these functions expressing preferences related to a specific aspect of alternatives. Building such criterion functions has proved to be difficult (see [START_REF] Bouyssou | Building criteria: A prerequisite for MCDA[END_REF]). To be useful the family of criteria should fulfill some properties to be consistent (see [START_REF] Roy | Méthodologie multicritère d'aide à la décision[END_REF] et [START_REF] Roy | Aide Multicritère à la Décision : Méthodes et Cas[END_REF]). Once the criteria g 1 , g 2 , . . . , g n defined (F = {1, 2, . . . , n}), the comparison of alternatives is grounded on the comparison of evaluation vectors (g 1 (a), g 2 (a), . . . , g n (a)). However, the evaluation vector provides very little information on how alternatives compare. Without any additional information, the only pairs of alternatives for which the comparison is relevant are those linked by the dominance relation ∆.

Definition 2. The dominance relation on A denoted ∆ is defined by:

a∆b ⇔ ∀j ∈ F, g j (a) ≥ g j (b) ∃j ∈ F, g j (a) > g j (b)
When the aim of the decision aiding activity is to enrich the dominance relation, it is necessary to obtain additional information on the DM's preferences. Definition 3. We call Preference Information denoted I any piece of information that makes it possible to discriminate among alternatives that are not linked with the dominance relation ∆.

An illustration of the necessity to introduce preference information is the following argument: the proportion of evaluation vectors that are in the dominance relation quickly becomes very low as the number of criteria increases (see [START_REF] Rosinger | Beyond preference information based multiple criteria decision making[END_REF]).

Within the framework of a decision aiding study, only the DM (or one of his/her representative) is able to express preference information. For instance, he/she can specify:

• how two evaluation vectors that are not in the dominance relation compare,

• a pre-order (possibly partial) on a subset of alternatives A * ⊂ A or a statement of the type "alternatives whose evaluation on criterion g j is less than x are not very likely to be placed at the top of the ranking", when the problem statement involves ranking alternatives

• a desired assignment to a category when the problem statement involves assigning alternatives to categories.

The above mentioned examples illustrate cases in which preference information is expressed in reference to the expected results of the decision aiding model. In such case we shall talk about output oriented preference information which we will denote I out .

Another way for the DM to specify preference information consists in evaluating the values for the preference parameters used in the aggregation model. In such case we shall talk about input oriented preference information which we will denote I in . The DM can express such an information by specifying, for instance:

• an evaluation difference that is not significant on a specific criterion,

• a comparison of criteria (or coalitions of criteria) in terms of relative importance,

• a tradeoff between two criteria.

Let us note that the expression by the DM of input oriented preference information is contingent to the nature of the preference parameters of the model used. This requires that the DM understands the semantics attached to these parameters. Decision aid often aims at devising des recommendations from which the DM will derive a plan for action. In a multicriteria context, devising recommendations requires a multiple criteria aggregation procedure (see [START_REF] Roy | Aide Multicritère à la Décision : Méthodes et Cas[END_REF]) that makes it possible to synthesize preferences on each criterion and contribute to the la definition of a result. Definition 4. A multiple criteria aggregation procedure (MCAP) is a rule, a process that allows to elaborate from the evaluation table and a set of values for the preference parameters, one (or several) relational preference structure(s) on the set of alternatives A. Using an exploitation procedure, this (these) relational preference structure(s) alow(s) to define, a result whose nature depends on the problem statement.

During a decision aiding study, the analyst can have access to a preference information I through an interaction with the DM or one of his/her representative. If the decision process involves multiple decision makers, the interaction should involve all these DMs. The information obtained during the interaction is highly dependent on the way the analyst proceeds during the interaction. This information allows the analyst to assign values to preference parameters.

Notations

Let us consider an MCAP P to which is attached a vector of k preferences parameters υ = (υ 1 , υ 2 , ...υ k ). Let Ω be the space for the values of υ, i.e., consistent values for the preference parameters (in the absence of information concerning the DM's preferences).

In this framework, the knowledge concerning the preference parameters is defined by a subset Ω ′ ⊆ Ω. Usually Ω ′ is defined by a list of constraints on the values of preference parameters. An interesting special case occurs when Ω ′ is reduced to a single point in Ω (Ω ′ = {ω}). In such case, the value of each preference parameter is fully determined. In all other cases, the value of at least one preference parameter is not accurately known.

Applying an MCAP P to a subset of alternatives A ′ ⊆ A with a set of parameters ω ∈ Ω leads to a result denoted R P (A ′ , ω). Such result consists of:

• the subset selected alternatives A * ⊆ A ′ in the case of a choice problem statement,

• the assignment of each alternative of A ′ to one of the predefined categories in the case of a sorting problem statement,

• a (partial) pre-order on A ′ in the case of a ranking problem statement,

Definition

Definition 5. Considering an MCAP P selected to model the DM's preferences, we will call preference elicitation process any process that goes through an interaction between the DM and the analyst (or a software) and leads the DM to express preference information within the framework of the selected MCAP. It takes the form of a set Ω ′ ⊆ Ω of plausible values for the preference parameters of the MCAP. At the end of this process, applying Ω ′ to the MCAP should lead to a result compatibles with the views of the DM.

The above definition views the preference elicitation process as an element of the decision aiding process. Specifically, this definition does not include identifying of the stakeholders, modelling the set of alternatives and building the set of criteria.

It should also be noted that this definition takes the choice of the MCAP intended to model the DM's preferences as a prerequisite. This implies that this choice should not be questioned during the process, unless a new process is started on the basis of a new MCAP.

Moreover various authors (see [START_REF] Mousseau | Problèmes liés à l'évaluation de l'importance relative des critères en aide multicritère à la décision : Réflexions théoriques, expérimentations et implémentations informatiques[END_REF], [START_REF] Podinovski | Criteria importance theory[END_REF], [START_REF] Ph | L'Aide Multicritère à la Décision[END_REF]) have shown that the values attached to preference parameters (in particular the importance parameters or weights) do not convey any clear meaning as long as they are not related to the MCAP in which they are to be used. Note that this statement is implicitly included in definition 5.

It is also important to note that the notion of interaction between the DM and the analyst gives the preference elicitation process a concrete form, a sequence of question-answer enabling the DM to express preference information progressively. This sequence gives the DM the opportunity to test hypothesis, proceed by trial and error, backtrack... This preference elicitation process allows to define a set of combinations of plausible values for preference parameters. This set Ω ′ ⊆ Ω is defined progressively during the procedure; the set of plausible combinations being reduces as the DM provides answers to questions. Each answer usually induces a constraint on the value of some preference parameters. Hence the set Ω ′ is reduced as the questioning process progresses.

Lastly it is important to note that the set Ω ′ ⊆ Ω obtained at the end of the process should lead, when using the MCAP, to a result consistent with the views of the DM. If not, the process can go on so as to revise Ω ′ accordingly.

To end this section, it should be stressed that a relatively limited part of the research conducted in the field of MCDA is devoted to the development of implementation tools which contributes to the definition of a doctrine of intervention for real world applications. In order to progress in this direction, more work should be focussing on the development of tools to organize the interaction between the DM and the analyst within the framework of a specific aggregation model, study the DM's behavior so as to build tools compatible with the effective practice of DMs when investigating decision problems, and test the operational validity of proposed tools, ...

Nature of the preference elicitation activity

The preference elicitation activity aims at making the DM's value system explicit through a model selected to model his/her preferences. The choice of the preference model is usually done by the analyst who checks the compatibility of the model hypothesis with the reasoning of the DM. The nature of what is at stake during this process can be viewed in different manners. The way by which the analyst gives meaning to the preference elicitation process differs whether he/she comprehends this process in a descriptivist or constructivist approach. We describe hereafter these two "extreme visions"; however, it seems that the philosophy of intervention adopted by analysts in real world case studies mostly corresponds to a median position.

Descriptivist approach for preference elicitation

The descriptivist approach hypothesizes that the way by which two alternatives compare is clearly defined in the mind of the DM before the preference elicitation process begins. Moreover, process does not alter the structure of these comparisons. Preference information is considered stable and refers to an objective reality. The model chosen to model DM's preferences aims at accounting for his/her preferences as "reliably" as possible. The role of the preference elicitation process is then to "match" a clearly defined existing situation. Some authors use the term "estimation" of the numerical value of preference parameters such as criteria importance coefficients or weights w j . Such a formulation is meaningless unless a "correct" numerical value for these parameters is hypothesized. In such case, the goal of the activity of preference elicitation is to approach these true values as closely as possible.

In such an approach, the lability of observed preferences (cf. [START_REF] Fischhoff | Knowing what you want: Measuring labile values[END_REF], [START_REF] Weber | Behavioral influences on weight judgments in multiattribute decision making[END_REF]) is explained by the biases induced by the preference elicitation phase. [START_REF] Beattie | Investingating the effect of stimulus range on attribute weight[END_REF] support the idea according to which there exists a "distinction between true and estimated weights and it is possible that subjects' true weights remain constant at all times, but become distorted in the elicitation process".

Constructivist approach for preference elicitation

The seminal works of Herbert Simon did inspire a trend of research interested in empirical analysis of decision behavior which tends to show that observed decision behaviors do not result from a simple algorithm (such as utility maximization) from data coming from the DM's memory. On the contrary, the limitations in terms of information processing can explain that preferences concerning objects are often constructed and not simply revealed when the DM makes a judgment or a choice. The concept of constructed preference is grounded on the observation that DMs do not have predefined values on most alternatives, but on the contrary, they construct their preferences on the spot when necessary, i.e., when they have to evaluate/compare alternatives.

The constructivist approach considers preferences as not completely pre-established in the mind of the DM and that the role of the preference elicitation activity (and a fortiori of the decision aiding activity) is to specify and even sometimes modify pre-existing elements. The MCAP that underlies the preference model is considered as appropriate to construct preferences. Therefore, the numerical values assigned to the preference parameters reflect a reasonable working hypothesis that is useful to elaborate recommendations. The "true" numerical values for preference parameters that are required to refer to the estimation paradigm do not necessarily exist. Nevertheless, the values assigned to preference parameters are useful means for reasoning, testing scenarios and communicating with the various stakeholders of the decision aiding process. The values (of intervals of variations) usually express, within the MCAP chosen to model the DM's preferences, a number of assertions stated by the DM during the elicitation process (see [START_REF] Roy | Decision science or decision-aid science[END_REF], [START_REF] Mousseau | Problèmes liés à l'évaluation de l'importance relative des critères en aide multicritère à la décision : Réflexions théoriques, expérimentations et implémentations informatiques[END_REF] and [START_REF] Payne | Behavioral decision research: a constructive processing perspective[END_REF]).

Preference elicitation through constructive learning

Designing a preference elicitation process in a constructive learning perspective consists in choosing a constructivist approach and considering that beyond the model definition, one of the prominent role of the elicitation process is to make some convictions on how alternatives compare concrete in the mind of the DM. Elaborating such conviction is grounded on:

• preexisting elements such as the DM's value system, past experiences related to the decision problem, on one hand,

• the preference elicitation process itself, on the other hand.

In order to be more specific about the nature of constructive learning preference elicitation, it is important to explain what is being learned and by whom. On one hand, the preference information provided by the DM contributes to the definition of the preference model. On the other hand, the elaboration/use of the preference model can shape the DM's preference (or at least make his/her convictions evolve), see Figure 1. Firstly, learning concerns the decision aiding model: it makes it possible to integrate into the model (and therefore to learn) the DM's preferences through the expressed preference information I he/she provides. Let us recall that this information can take the form of constraints on preference parameters: input oriented information; or elements of results expected from the model (see figure 1, link 1). The most tangible result of such a process is a set of values (or intervals of variation) for the preference parameters associated to the considered MCAP. The way the preference information provided by the DM is taken into account should obviously be compatible with the semantic the MCAP confers to the preference parameters.

But constructive learning also concerns the DM himself/herself. A less tangible result is characterized by the fact that the DM gains insights, during the course of the preference elicitation process, on his/her preferences and how his/her value system interacts with the decision problem (see Figure 1, link 2). Even more, such a process forces the DM to confront his/her value system to the result of the MCAP chosen to represent his/her preferences. This confrontation can lead the DM to have a better understanding of his/her preferences but also to understand the intrinsic logic of the used MCAP (underlying assumptions of the aggregation, semantic attached to the preference parameters, ...). This second type of learning plays an important role in the elaboration of the DM's preferences. Moreover, it distinguishes constructive learning preference elicitation from a standard approach in artificial intelligence: machine learning/learning classifiers (see [START_REF] Michalski | A theory and methodology of inductive learning[END_REF], [START_REF] Quinlan | Induction of decision trees[END_REF]). This literature proposes "descriptive learning" oriented methods, i.e., they aim at reproducing observed input/output phenomena: an explicative model is inferred trough a certain form of optimization that aims at best matching the observations. The validity of a model is then related to its ability to reproduce input/output links. Models that reproduce the phenomenon in the same way are judged equivalent.

On the contrary, in a constructive learning approach, two models that have the same ability to restitute the preference information provided by the DM are judged as equivalent only if the DM considers them so, which is only rarely the case. Very often, considering the models specificities (e.g., values of preference parameters), a DM is able to judge one of the models as more pertinent than the other one; such judgment usually generates further interaction that allows to refine the model.

Components of a preference elicitation process through constructive learning

As a preliminary remark to this section, it is important to underline that a preference elicitation tool is not "constructive" in itself but the way it is used during a decision aid process orients the preference elicitation process towards a constructive or descriptive path (see [START_REF] Stewart | Towards reconciling outranking and value measurement practice[END_REF], [START_REF] Dias | On the constructive and other approaches in decision aiding[END_REF]). However, there exists in the literature some tools that were specifically conceived to be used within a constructive preference elicitation perspective: UTA [START_REF] Jacquet-Lagrèze | Binary preference indices: A new look on multicriteria aggregation procedures[END_REF], Macbeth (see [START_REF] Bana E Costa | Macbeth -an interactive path towards the construction of cardinal value fonctions[END_REF]), Electre Tri (see [START_REF] Mousseau | ELECTRE TRI 2.0a : Methodological guide and user's documentation[END_REF], [START_REF] Mousseau | A user-oriented implementation of the ELECTRE TRI method integrating preference elicitation support[END_REF]), Iris (see [START_REF] Dias | Iris-interactive robustness analysis and parameters'inference for multicriteria sorting problems (2.0). user manual[END_REF])... Some others (AHP [START_REF] Saaty | A scaling method for priorities in hierarchical structures[END_REF], Eleccalc [KMN94], SRF [START_REF] Roy | Determining the weights of criteria in the ELECTRE type methods with a revised Simos' procedure[END_REF]) although not specifically designed for constructive learning purposes, can be used in a constructive perspective.

Designing tools that aim at supporting a constructive learning preference elicitation process is not an easy task. However, several "ingredients" can induce, between the DM and the analyst, an interaction similar to the one described in the previous section. This section tries to investigate these "ingredients".

Aggregation/Disaggregation approach

As in §1.2, we consider an MCAP P to which is attached a vector of k preferences parameters υ = (υ 1 , υ 2 , ...υ k ). Let Ω be the space for the values of υ, i.e., consistent values for the preference parameters (in absence of information concerning the DM's preferences).

In this framework, the knowledge concerning the preference parameters is defined by a subset Ω ′ ⊆ Ω. Usually Ω ′ is defined by a list of constraints on the values of preference parameters. An interesting special case occurs when Ω ′ is reduced to a single point in Ω (Ω ′ = {ω}). In such case, the value of each preference parameter is fully determined. In all other cases, the value of at least one preference parameter is not precisely known.

Applying an MCAP P to a subset of alternatives A ′ ⊆ A with a set of parameters ω ∈ Ω leads to a result denoted R P (A ′ , ω). During a preference elicitation process, the DM can provide a result concerning a subset of alternatives A * ⊆ A that he/she would like to obtain as part of the output of the decision aid model; we denote R DM (A * ) such a result provided by the DM. We shall also denote Ω(R DM (A * )) = {ω ∈ Ω : R P (ω, A * ) = R DM (A * )} the set of combinations of preference parameter values for which applying P to A * leads to R DM (A * ). Let us remark that, in some situations, the set Ω(R DM (A * )) can be empty. Such a situation occurs when it is impossible to represent R DM (A * ) in the MCAP P chosen to model DM's preferences; this requires a specific analysis that we will study in section §3.5.

Following an aggregation approach in the implementation of a decision aid study is the most common practice. This approach is sequential in its nature (although implementations prove returns to earlier phases and iterations to be possible and useful) and consists in :

• defining the set of alternatives A,

• designing a set of criteria g 1 , g 2 , ..., g n ,

• choosing a multiple criteria aggregation procedure P,

• assigning values (or intervals of variation) to preference parameters used in P,

• aggregating the data on criteria to determine overall preferences,

• Carrying out a sensitivity/robustness analysis to lead to recommendations.

The Disaggregation approach refers to a process that, for a given MCAP P, is organized in the following way:

• define the set of alternatives A,

• design a set of criteria g 1 , g 2 , ..., g n ,

• interact with the DM to obtain information (corresponding to his/her intuitive preferences) on the result R DM (A * ) (concerning a subset of alternatives A * ⊆ A), that he/she would like the aggregation procedure to reproduce. According to the problem formulation, R DM (A * ) can be a partial pre-order on A * , pairwise comparisons of alternatives in A * , assignment of alternatives from A * to categories...

• using a disaggregation (or inference) procedure, compute the values ω * (R DM (A * )) for preference parameters that "best match" R DM (A * ). The MCAP P with ω * (R DM (A * )) then constitutes a preference model.

• apply the model obtained to the set of all alternatives A, i.e., compute R P (A, ω * (R DM (A * ))).

In the process described above, a disaggregation () or inference procedure is an algorithm which identifies, from preference information I provided by the DM (corresponding to his/her intuitive preferences), a set of values ω * (I) ∈ Ω for preference parameters that "best restitute" I through the application of the aggregation procedure. I may concern the result of the MCAP (output oriented preference information) or take the form of constraints on the preference parameter values (input oriented preference information). Formally these two types of information are of the same nature as imposing constraints on the result expected from a MCAP leads to set constraints on the value of the preference parameters. The role of these inference procedures is studied in section §3.4.

The disaggregation approach aims at avoiding asking the DM to express his/her preference in terms of numerical values for preference parameters, but to requires him/her to provide parts of results he/she would like to obtain as an output of the preference model from which recommendations inferred through the MCAP given the provided information.

Adopting an aggregation/disaggregation approach consists in elaborating a preference elicitation process alternating aggregation and disaggregation phases; the output of each phase being the information used for the next phase. For instance, a DM willing to conceive a ranking on a set of alternatives can state "I prefer a 3 to a 6 " and compute (through disaggregation) a set of parameters ω * (I) that best restore his/her statement. Let us suppose that applying the MCAP P using ω * (I) leads to a ranking in which a 1 has a better rank than a 2 ; the DM might react stating that "I prefer a 2 to a 1 "; this second statement is then added to the preceding one to start a new disaggregation phase... The aggregation/disaggregation approach shares commonalities with so called interactive methods (e.g. [START_REF] Benayoun | Linear programming with multiple objective functions: Step method (STEM)[END_REF], [START_REF] Geoffrion | An interactive approach for multicriteria optimization with an application to the operation of an accademic department[END_REF], [START_REF] Zionts | An interactive multiple objective linear programming method for a class of underlying nonlinear utility functions[END_REF], [START_REF] Vanderpooten | L'approche interactive dans l'aide multicritère à la décision : Aspects conceptuels, méthodologiques et informatiques[END_REF]). These methods (mostly devoted to the choice problem statement) alternate dialog phases in which one or several alternatives are presented to the DM (in order to induce a reaction from him/her) and computation phases in which the new information is used to generate new propositions. The sequence -computation phase/dialog phase-are close to the aggregation/disaggregation approach; it should however be noted that these interactive methods have a very different aim: their purpose is not to model the preferences of the DM but only to explore the set of alternative (even if some of these methods include "learning" features).

Aggregation/Disaggregation approach and invariance w.r.t. third alternative

Invariance with respect to a third alternative (ITA) is a property which states that the comparison of two alternatives a and b is not affected by the presence/absence of a third alternative c in the set of alternatives A. The structure of some MCAP is such that they respect the ITA property (e.g. MAUT [START_REF] Keeney | Decisions with multiple objectives: Preferences and value tradeoffs[END_REF] or the lexicographic aggregation [START_REF] Fishburn | Lexicographic orders, utilities and decision rules: a survey[END_REF]). Some other MCAP take into account, in order to define how two alternative a and b compare, the way a and b compare to all other alternatives in A and hence do not respect ITA (it is the case for instance for Electre III [START_REF] Roy | ELECTRE III : Un algorithme de classements fondé sur une représentation floue des préférences en présence de critères multiples[END_REF] et AHP [START_REF] Dyer | Remarks on the analytic hierarchy process[END_REF], [START_REF] Perez | Some comments on Saaty's AHP[END_REF]).

The fact that an MCAP satisfies or not the ITA property is not positive or negative in itself; it depends on the way this MCAP defines how two alternatives compare. On the other hand, the fact that a specific MCAP does not satisfy ITA has important consequences when this MCAP is to be implemented in a decision aiding process using an aggregation/disaggregation approach.

The following considerations concern MCAPs designed for comparative problem statements (choice and ranking). In fact, the very nature of the sorting problem statement (assigning alternatives to pre-defined categories) is absolute evaluation and implies that the assignment of an alternative is defined independently from others. Hence, any MCAP designed for sorting problems implicitly satisfies ITA.

Let us consider an MCAP P that we intend to use within an aggregation/disaggregation approach. Let R DM (A * ) denote a result provided by the DM on a subset of alternatives A * ⊆ A.

Consider Ω(R DM (A * )) = {ω ∈ Ω : R P (ω, A * ) = R DM (A * )} the set of combinations of values for preference parameters for which the computation of P when considering the set of alternatives A * leads to R DM (A * ). The aggregation/disaggregation approach aims at identifying a specific set of preference parameters ω * (R DM (A * )) ∈ Ω(R DM (A * )) and to compute R P (ω * (R DM (A * )), A). Consider now R P (ω * (R DM (A * )), A * ) the restriction to A * of the result R P (ω, A). In the case of a ranking problem statement, R P (ω * (R DM (A * )), A * ) can be defined as the subgraph of the partial pre-order R P (ω, A) restricted to the alternatives in A * . Suppose that the MCAP satisfies ITA; then it holds: R DM (A * ) = R P (ω * (R DM (A * )), A * ), i.e., the result provided by the DM on the subset A * "is contained" in the result of the MCAP P when considering all alternatives and using the parameter values inferred through disaggregation. In the case of a ranking problem, it means that if the DM gives the ranking a ≻ b ≻ c, then the ranking obtained applying P to A with the inferred set of parameters will always rank a better than b better than c.

Let us now suppose that the MCAP P does not satisfy ITA. In such case, nothing ensures that R DM (A * ) = R P (ω * (R DM (A * )), A * ) : the result provided by the DM concerning the subset A * may be contradicted by the result of the MCAP P when considering all alternatives and using the parameter values inferred through disaggregation. In the case of the ranking problem statement, if the DM provides the ranking a ≻ b ≻ c, then ranking on A obtained with the inferred parameters, may in some cases not containt that a ≻ b ≻ c. Hence, not respecting the ITA property implies that the DM can ,in an aggregation/disaggregation approach, be confronted to an inferred result which partly "contradicts" the information he/she provided. Hence it appears that the ITA property should be satisfied in order to implement an MCAP within an aggregation/disaggregation approach in a satisfactory way.

Following the preceding argument, we may conclude that any multiple criteria sorting model can be elicited with a DM using an aggregation/disaggregation approach; indeed any sorting procedure structurally satisfies ITA. On the other hand, a choice or a ranking procedure is not necessarily adapted to an aggregation/disaggregation implementation. Specifically, procedures that proceed by pairwise comparisons (construction and exploitation of an outranking relation) are not really suitable to aggregation/disaggregation as described above. However, it is still possible for these procedures, to implement an aggregation/disaggregation approach in which the outranking relation itself (and not the result, i.e., choice or ranking) is to be inferred.

Interaction modes with the DM

An important issue in the design of constructive learning preference elicitation procedure concerns what will be the vehicle of the interaction between the analyst and the DM. Roughly, it is possible to ground the interaction on:

• the result (or a part of the result) of the MCAP, • the value (or interval of variation) of some preference parameters.

Moreover, it is important to distinguish in the interaction:

• the mode by which the DM will express preference information, on one hand, • the type of information presented to the DM in order to foster interaction, on the other hand.

In the course of a preference elicitation process, the DM can provide information in the form of a partial result (output oriented preference information I out , see §1.1) or by specifying constraints on the values of preference parameters (input oriented preference information I in , see §1.1).

• The first type of information, I out , often corresponds to an expression mode close to the spontaneous statements made by DMs ("alternative a j should be assigned to category C k ", or "alternative a j cannot have a better rank than alternative a j ′ "). Such statements can correspond to past decisions, judgments concerning fictitious alternatives, ...

• The second type of information refers to the aggregation model and therefore is relatively distant from the DM's language. Nevertheless, the DM can sometimes express information related to the value of some preference parameters ("a difference of 5 between the evaluation of two alternatives on criterion g 2 is not significant", or "criterion g 1 is more important than criterion g 2 "). Expressing such information requires from the DM a minimal understanding of the semantic that the MCAP confers to the preference parameters.

Firstly, the information to be presented to the DM may refer to the result. If I = I in ∪ I out is the preference information provided by the DM, and consequently Ω(I) ⊂ Ω the compatible parameter values. If Ω(I) = ∅, the result of the MCAP ω ∈ Ω(I) constitutes for the DM interesting information which might foster a reaction. Moreover, the DM should have the possibility to "question" this robust result (for instance, "why is alternative a j ranked after alternative a j ′ ? or "why is it not possible to assign alternative a j to category C k ? ").

Second, it is possible to present to the DM information related to the value of the preference parameters, i.e., expressed in terms of the model. For instance, the set of parameter values ω * (I) computed by an inference procedure (see §3.4) that best match the information I can make the DM react. If, for example, ω * (I) is such that the "most important criterion" (we suppose here that the MCAP makes it possible to define such an assertion), the DM may disagree and react. Moreover, presenting such information during the process will increase the DM's understanding of the semantic attached to the preference parameters.

Lastly, it is possible to present to the DM input-output mixed information. Such information aims at making explicit the relation between a stated preference information and its impact on the preference model. Let us consider, for an illustrative purpose, a multiple criteria sorting procedure. A preference information ι ∈ I can be an assignment example stating that "alternative a j should be assigned to category C k ". What is the impact of ι within I ? This impact can be analyzed in the result of the sorting procedure (does ι have an important impact on the assignment of alternatives from A), but also in terms of the space of acceptable values for preference parameters (comparing Ω(I) the space of acceptable values considering I with Ω(I \ {ι}) may be informative; this comparison can be made in terms of relative volume).

Finally, it should be stressed that the information to be presented to the DM should be contextualized according to the nature of the preference parameters and according to the problem statement.

Infer a preference model

One of the essential components of a constructive learning preference elicitation process concerns the ability to infer a preference model from a preference information I provided by the DM. This is materialized by an inference procedure, i.e., an algorithm which, starting from the information I provided by the DM (and corresponding to his/her intuitive preferences) identifies an element ω * (I) ∈ Ω that "best matches" I when used in P (see Figure 2). The information I may concern the result (output oriented preference information, see §1.1) or take the form of constraints on the value of preference parameters (input oriented preference information, see §1.1).

Most often, such an inference procedure is grounded on the resolution of a mathematical program in which:

• decision variables are the preference parameters whose value is to be determined,

• the objective function aims at minimizing an error function that captures to which extent the preference information is taken into account in the inferred model,

• the constraints express how the information I is integrated in the MCAP in terms of the parameter values.

At the optimum, the values of preference parameters correspond to the best way (in the sense of the error function) to account for I in the MCAP. However, a post-optimal analysis may be useful to identify alternative values for the preference parameters leading to solutions "close" to the optimum. Indeed, the sets of parameters that restore I in an equivalent way might not be considered as equivalent by the DM. He/she may have an intuitive appreciation of the values of some preference parameters and wish to differentiate among these sets of parameters that restore I equally. According to the chosen MCAP, the computational complexity for solving the program varies: in some cases (UTA for instance [START_REF] Jacquet-Lagrèze | Assessing a set of additive utility functions for multicriteria decision making: the UTA method[END_REF]) it is a linear program, but sometimes (inference of an outranking relation, [START_REF] Mousseau | Inferring an ELECTRE TRI model from assignment examples[END_REF] [DM02] for instance) obtaining a global optimum is harder. Two approaches are possible to overcome this difficulty: first, it is possible to specify a method based on a meta-heuristic; second, if the value of some preference parameters can be considered as known, "partial" inference procedures can be designed.

Preference

A partial inference is useful in situations in which the value of some parameters can reasonably be set. If not, it is possible to partition the parameters in sets, and proceed through a sequence of partial inference in which the value of some parameters is fixed.

Inferring a certain form of knowledge (a preference model) from decision examples is typical in artificial intelligence. Inducing rules or decision trees from examples through machine learning ( [START_REF] Michalski | A theory and methodology of inductive learning[END_REF], [START_REF] Quinlan | Induction of decision trees[END_REF]), knowledge acquisition based on rough sets ([GB92], [START_REF] Pawlak | Rough set approach to multi-attribute decision analysis[END_REF], [START_REF] Slowinski | Intelligent decision support -Handbook of applications and advances of the Rough Sets theory[END_REF]), case based reasoning ([GS95], [START_REF] Gilboa | Case-based knowledge and induction[END_REF]) supervised learning on neural networks ([Gal93], [START_REF] Weiss | Computer Systems That Learn[END_REF]) are typical examples of this approach. The appeal of this type of methods comes from the fact that DMs have more difficulties explaining decisions than making decisions. However, inference procedures presented in this paper differ from these methods which consider two models having the same ability to restore the data as equivalent (which is not necessarily the case in a preference elicitation process).

Detect and solve "inconsistencies"

One of the difficulties of the constructive learning preference elicitation approach lies in the fact that the DM sometimes provides information that cannot be fully represented in the MCAP chosen to model his/her preferences. Such type of information can be called "inconsistent" although no negative connotation should be attached to it: it does not necessarily corresponds to an error that the DM should correct, but only to a list of statements provided by the DM for which no combination of values for preference parameters exist in order to restore all DM's assertions.

During the elicitation process, such "inconsistencies" may occur because:

• the constraints specified by the DM on parameters values are not compatible with the partial results,

• the DM's point of view is evolving during the elicitation process,

• there are multiple DMs,

• the DM's reasoning is incompatible with the logic underlying the MCAP.

When such a situation occurs, it is necessary to inform the DM, but also to provide him/her with elements that will make it possible for him/her to understand what caused the inconsistency and how to solve it, i.e., how to modify the set of his/her initial statements so that this set becomes representable in the chosen MCAP. Note, however, that removing the inconsistency is not absolutely necessary; keeping consistency along the elicitation process usually increases clarity, but the process may also be pursued keeping preference information which is not fully representable in the chosen MCAP.

During a preference elicitation process, the fact that an inconsistency appears (and its analysis) can help the DM to learn/gain insights on his/her preferences. Indeed, the search for preference information that underlies the inconsistency leads the DM to note that some of his/her assertions are conflicting in the context of the chosen MCAP. For instance, if the statements "I prefer a 1 to a 2 " et "criterion g 7 is more important than criterion g 5 " are in conflict, this shows the DM that the way by which the MCAP exploits his/her second assertion is incompatible with his/her first assertion.

When dealing with an inconsistent preference information I, there is no unique way to modify I so as to restore a preference information compatible with the MCAP. Whatever the MCAP, the identification of all these solutions is a hard combinatorial problem. Nevertheless, it is not reasonable to leave the DM without any support when an inconsistency appears. It is then necessary to help him/her in the management of such a situation. This can be done by proposing several (not all) alternative ways to solve inconsistencies (modification in I that yields a preference information compatible with the MCAP). To do so, one must choose the solutions to be presented to the DM and define the presentation order. This can be done by giving priority to solutions yielding minimal modifications in I, those leading to modifying the "oldest" piece of information in I, those modifying elements in I for which the DM is the least confident (if the DM can associate confidence levels to his/her statements) ... [MDF + 03] proposed some algorithms but this issue is still to be explored.

Preference elicitation and robustness analysis

When the precise value for preference parameters ω ∈ Ω is "known", applying an MCAP P leads to a result denoted R P (A, ω). Even when the knowledge about the preference parameters is incomplete, one can try to determine a result. Applying an MCAP P considering the knowledge on preference parameters Ω ′ ⊆ Ω leads to a result denoted R P (A, Ω ′ ). R P (A, Ω ′ ) represents a result "valid" considering a value for parameters varying in Ω ′ .

A nave method to identify R P (A, Ω ′ ) could be to apply the procedure P for each ω ∈ Ω ′ and compute a "synthesis" of these results R P (A, ω), ∀ω ∈ Ω ′ . The output obtained, denoted R P (A, Ω ′ ), corresponds to a result that refers to an imperfect knowledge about the value of preference parameters. The nature of the "synthesis" to be performed may vary according to the problem statement.

• In the sorting problem statement, the synthesis may be expressed by the set of categories to which an alternative can be assigned for at least one ω ∈ Ω ′ .

• In the ranking problem statement, the synthesis can be performed by computing the intersection of partial pre-orders obtained for each ω ∈ Ω ′ .

• In the choice problem statement, R P (A, Ω ′ ) can be defined by the set of alternatives which are present in R P (A, ω), ∀ω ∈ Ω ′ .

Defining R P (A, Ω ′ ) as a "synthesis" of the results R P (A, ω), ∀ω ∈ Ω ′ is closely related to the concept of robust conclusion (see [START_REF] Roy | A missing link in OR-DA, Robustness analysis[END_REF]). The computation of R P (A, Ω ′ ) is usually performed analytically and not through an enumeration of results for each ω ∈ Ω ′ . Generally, computing R P (A, Ω ′ ) requires the development of specific algorithms adapted to the MCAP P. For instance, [DC00] developed an algorithm identifying assignment of alternatives compatible with partial information about the DM's preferences. [START_REF] Greco | L'approche agrégation/désagrégation pour les méthodes de surclassement[END_REF] proposed UTA GMS , a variant of the UTA method, which identifies the partial pre-order induced by a set of pairwise comparisons of alternatives.

If Ω ′ does not restrict in a strong way the value of preference parameters, R P (A, Ω ′ ) will be poor and uninformative for the DM. Showing the DM such a result will usually induce a reaction of the DM so that the result will be "enriched", hence providing a new preference information. If Ω ′ does strongly constrain the parameters values, R P (A, Ω ′ ) will be richer and more informative for the DM. In this case, the DM may disagree with part of the result ("no, a 4 is not better than a 9 " or "a 4 cannot be assigned to category C 2 ". In this case, the introduction of the new preference information will necessarily produce an inconsistency whose resolution will explain what grounds the part of the result R P (A, Ω ′ ) the DM disagrees with. In both cases, the nature of the interaction will help the DM to form his/her opinion.

Preference Information

I Ω ′ (I) ⊂ Ω Result R P (A, Ω ′ (I))
Robustness Inference Thus it appears that preference elicitation and robustness analysis should not be seen as two disjoint steps of a decision aiding process but on the contrary as two phases which necessarily interact in order to give the DM the opportunity to construct his/her preferences as follows (see Figure 3):

• the DM provides preference information I, Let Ω ′ (I) ⊂ Ω be the space of parameters values compatible with I,

• it leads to a result R P (A, Ω ′ (I)),

• The DM reacts modifying R P (A, Ω ′ (I)) according to his/her preferences,

• the inference procedure indicates the impact of the DM's statements on the parameters values, which may trigger another reaction from the DM.

Link with decision aid in the context of incomplete information

A way to conceive a preference elicitation process consists in considering that the DM starts the process without any specifications concerning his/her preferences; the process aims at specifying these preferences within the context of the chosen MCAP. In this context, a given stage of the process corresponds to a state of incompleteness of the DM's preferences.

A large literature deals with decision making in the context of incomplete information. Most of these articles focuss on defining the "best alternative" or a ranking of the alternatives when imprecise information is available on the values of the model parameter ( [START_REF] Hazen | Partial information, dominance, and potential optimality in multiattribute utility theory[END_REF], [START_REF] Weber | Decision making with incomplete information[END_REF], [START_REF] Athanassopoulos | Dominance and potential optimality in multiple criteria decision analysis[END_REF], [START_REF] Carrizosa | Multi-criteria analysis with partial information about the weighting coefficients[END_REF], [START_REF] Salo | Preference assessment by imprecise ratio statements[END_REF], [START_REF] Malakooti | Ranking and screeningmultiple criteria alternativeswith partial information and use of ordinal and cardinal strength of preferences[END_REF], [START_REF] Barron | Selecting a best multiattribute alternative with partial information about attribute weights[END_REF], [START_REF] Salo | Preference ratio in multiattribute evaluation (PRIME) -elicitation and decision procedures under incomplete information[END_REF], [START_REF] Weber | A method of multiattribute decsision making with incomplete information[END_REF], [START_REF] Moskowitz | Multiple-criteria robust interactive decision analysis (MCRID) for optimizing public policies[END_REF], [START_REF] Kirkwood | The effectiveness of partial information about weights for ranking alternatives in multiattribute decision making[END_REF]). This literature mainly deals with multiple attribute utility theory.

A general framework to describe constructive learning preference elicitation procedures

In this section, we present the scheme of a general algorithm that can be used as a framework to the description of a large class of procedures whose role is to support a constructive learning preference elicitation process. To be fully specified, the algorithm 1 should be adapted to a specific MCAP. This requires to define namely:

• a procedure to compute R P (Ω ′ (I (k) ), A),

• an inference procedure identifying a set of preference parameters ω * (I (k) ),

• an algorithm identifying, when Ω ′ (I (k) ) = ∅, modifications of I (k) that make the information compatible with the MCAP P In addition, this general algorithm does not define how the preference information is managed during the elicitation process, i.e., the way the DM makes the preference information evolve from an iteration to the following one.

A first strategy consists in starting the elicitation process without any preference information and to add, at each iteration, an"elementary" piece of information. The advantage of this strategy is that the DM can control precisely the impact of the introduction of each piece of information on the model and on the result, hence favoring learning.

Another strategy starts with the introduction of a large quantity of preference information at the beginning of the process. This information is often not representable in the MCAP and the analysis of "inconsistencies" leads to construct a model on the basis of a part of the initial information only. Such a strategy is useful when the decision is recurrent, namely when historical data is available. Various other hybrid strategies can be designed.

Lastly, the test "Until the DM is satisfied with the obtained model " is only grounded on the DM views, and is not specified in a formal way. Although it may be difficult to define a specific test, elements that could assess the progress of an elicitation process should help the analyst and DM to appreciate when the process reach the end:

• the robust result R P (Ω ′ (I (k) ), A) is acceptable by the DM as a whole to elaborate recommendations,

• the set of preference parameters ω * (I (k) ) is viewed by the DM as a good synthesis of his/her value system and the associated result R P (ω ′ (I (k) ), A) is satisfying.

Conclusion

Preference elicitation is a crucial phase of any decision aiding process. In this paper, we define the preference elicitation activity and show that such activity can be conceived in a way that allows the DM to elaborate his/her convictions within a preference model along the elicitation process: constructive learning preference elicitation.

We have identified several features of preference elicitation tools that are useful to implement constructive learning preference elicitation processes. We also have provided a general framework that makes it possible to describe a large class of preference elicitation procedures.

Figure 1 :

 1 Figure 1: Constructive Learning Preference Elicitation

  Figure 2: Inference procedure

Figure 3 :

 3 Figure 3: Integration Robustness/Elicitation

Algorithme 1 .

 1 Constructive learning preference elicitation algorithmBeginchoose an MCAP P k ← 0I (0) = ∅ Ω ′ (I (0) ) ← Ω Repeat -compute Ω ′ (I (k)) the space of values for ω compatible withI (k) -compute R P (Ω ′ (I (k) ), A) -infer the parameters ω * (I (k) ) that best match I (k) -apply the MCAP P with ω * (I (k) ) → R P (ω * (I (k) ), A) -present R P (Ω ′ (I (k) ), A), ω * (k) (I) and R P (ω * (k) , A) -If Ω ′ (I (k) ) = ∅then -propose modifications of I (k) making the information compatible with P to the DM End If -ask the DM to revise I (k) → we obtain I (k+1) k ← k+1 Until the DM is satisfied with the obtained model End

  Introduction 1 Preference elicitation process 1.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Nature of the preference elicitation activity 2.1 Descriptivist approach for preference elicitation . . . . . . . . . . . . . . . . . . . . . 2.2 Constructivist approach for preference elicitation . . . . . . . . . . . . . . . . . . . . 2.3 Preference elicitation through constructive learning . . . . . . . . . . . . . . . . . . .

3 Components of a preference elicitation process through constructive learning 3.1 Aggregation/Disaggregation approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Aggregation/Disaggregation approach and invariance w.r.t. third alternative . . . . . 3.3 Interaction modes with the DM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Infer a preference model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Detect and solve "inconsistencies" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Preference elicitation and robustness analysis . . . . . . . . . . . . . . . . . . . . . . . 3.7 Link with decision aid in the context of incomplete information . . . . . . . . . . . . 4 A general framework to describe constructive learning preference elicitation procedures 5 Conclusion