New Constraint Programming Approaches for the Computation of Leximin-Optimal Solutions in Constraint Networks

1 Introduction

Many advances have been done in recent years in modeling and solving combinatorial problems with constraint programming (CP). These advances concern, among others, the ability of this framework to deal with human reasoning schemes, such as, for example, the expression of preferences with soft constraints. However, one aspect of importance has only received a few attention in the constraints community to date: the way to handle fairness requirements in multiagent combinatorial problems.

The seek for fairness stands as a subjective but strong requirement in a wide set of real-world problems implying human agents. It is particularly relevant in crew or worker timetabling and rostering problems, or the optimization of long and short-term planning for firemen and emergency services. Fairness is also ubiquitous in multiagent resource allocation problems, like, among others, bandwidth allocation among network users, fair share of airspace and airport resources among several airlines or Earth observing satellite scheduling and sharing problems [Lemaˆıtre et al., 1999].

In spite of the wide range of problems concerned by fairness issues, it often lacks a theoretical and generic approach. In many Constraint Programming and Operational Research works, fairness is only enforced by specific heuristic local choices guiding the search towards supposed equitable solutions. However, a few works may be cited for their approach of this fairness requirement. [Lemaˆıtre et al., 1999] make use of an Earth observation satellite scheduling and sharing problem to investigate three ways of handling fairness among agents in the context of constraint satisfaction. More recently [Pesant and R´egin, 2005] proposed a new constraint based on statistics, which enforces the relative balance of a given set of variables, and can possibly be used to ensure a kind of equity among a set of agents. Equity is also studied in Operational Research, with for example [Ogryczak and ´Sliwi´nski, 2003], who investigate a way of solving linear programs by aggregating multiple criteria using an Ordered Weighted Average Operator (OWA) [Yager, 1988]. Depending on the weights used in the OWA, this kind of aggregators can provide equitable compromises.

Microeconomy and Social Choice theory provide an important literature on fairness in collective decision making. From this theoretical background we borrow the idea of representing the agents preferences by utility levels, and we adopt the leximin preorder on utility profiles for conveying the fairness and efficiency requirements. Being a refinement of the maximin approach 1 , it has an inclination to fairness, while avoiding the so-called drowning effect of this approach.

Apart from the fact that it conveys and formalizes the concept of equity in multiagent contexts, the leximin preorder is also a subject of interest in other contexts, such as fuzzy CSP [Fargier et al., 1993], and symmetry-breaking in constraint satisfaction problems [Frisch et al., 2003].

This contribution is organized as follows. Section 2 gives a minimal background in social choice theory and justifies the interest of the leximin preorder as a fairness criterion. Section 3 defines the search for leximin-optimality in a constraint programming framework. The main contribution of this paper is Section 4, which presents three algorithms for computing leximin-optimal solutions, the first one being entirely original, and the other ones adapted from existing works. The proposed algorithms have been implemented and tested within a constraint programming system. Section 5 presents an experimental comparison of these algorithms.

2 Background on social choice theory

We first introduce some notations. Calligraphic letters (e.g. X) will stand for sets. Vectors will be written with an arrow (e.g.-→x ), or between brackets (e.g. 〈x1, . . . , xn〉). f(-→x ) will be used as a shortcut for 〈f(x1), . . . , f(xn)〉. Vector -→x ↑ will stand for the vector composed by each element of -→x rearranged in increasing order. We will write x↑i the ith component of vector -→x ↑ . Finally, the interval of integers between k and l will be written llbracketk, lrrbracket.

1 Trying to maximize the utility of the unhappiest agent.

2.1 Collective decision making and welfarism

Let N be a set of n agents, and S be a set of admissible alternatives concerning all of them, among which a benevolent arbitrator has to choose one. The most classical model describing this situation is welfarism (see e.g. [Keeney and Raiffa, 1976; Moulin, 1988]): the choice of the arbitrator is made on the basis of the utility levels enjoyed by the individual agents and on those levels only. Each agent i ∈ N has an individual utility function ui that maps each admissible alternative s ∈ S to a numerical index ui(s). We make here the classical assumption that the individual utilities are comparable between the agents 2 . Therefore each alternative s can be attached to a single utility profile 〈u1(s), . . . , un(s)〉. According to welfarism, comparing two alternatives is performed by comparing their respective utility profiles.

A standard way to compare individual utility profiles is to aggregate each of them into a collective utility index, standing for the collective welfare of the agents community. If g is a well-chosen aggregation function, we thus have a collective utility function uc that maps each alternative s to a collective utility level uc(s) = g(u1(s), . . . , un(s)). An optimal alternative is one of those maximizing the collective utility.

2.2 The leximin preorder as a fairness and efficiency criterion

The main difficulty of equitable decision problems is that we have to reconcile the contradictory wishes of the agents. Since generally no solution fully satisfies everyone, the aggregation function g must lead to fair and Pareto-efficient 3 compromises.

The problem of choosing the right aggregation function g is far beyond the scope of this paper. We only describe the two classical ones corresponding to two opposite points of view on social welfare 4 : classical utilitarianism and egalitarianism. The rule advocated by the defenders of classical utilitarianism is that the best decision is the one that maximizes the sum of individual utilities (thus corresponding to g = +). However this kind of aggregation function can lead to huge differences of utility levels among the agents, thus ruling out this aggregator in the context of equitable decisions. From the egalitarian point of view, the best decision is the one that maximizes the happiness of the least satisfied agent (thus corresponding to g = min). Whereas this kind of aggregation function is particularly well-suited for problems in which fairness is essential, it has a major drawback, due to the idempotency of the min operator, and known as "drowning effect" in the community of fuzzy CSP (see e.g.[Dubois and Fortemps, 1999]). Indeed, it leaves many alternatives indistinguishable, such as for example the ones with utility profiles 〈0, . . . , 0〉 and 〈1000, . . . , 1000, 0〉, even if the second one appears to be much better than the first one. In other words, the min aggregation function can lead to non Pareto-optimal decisions, which is not desirable.

2 In other words, they are expressed using a common utility scale.

3 A decision is Pareto-efficient if and only if we cannot strictly increase the satisfaction of an agent unless we strictly decrease the satisfaction of another agent. Pareto-efficiency is generally taken as a basic postulate in collective decision making.

4 Compromises between these two extremes are possible. See e.g. [Moulin, 2003, page 68] or [Yager, 1988] (OWA aggregators).

The leximin preorder is a well-known refinement of the order induced by the min function that overcomes this drawback. It is classically introduced in the social choice literature (see [Moulin, 1988]) as the social welfare ordering that reconcile egalitarianism and Pareto-efficiency, and also in fuzzy CSP [Fargier et al., 1993]. It is defined as follows:

Definition 1 (leximin preorder [Moulin, 1988]) Let -→x and -→y be two vectors of Nn. -→x and -→y are said leximinindifferent (written -→x ∼leximin -→y ) if and only if -→x ↑ = -→y ↑ . The vector -→y is leximin-preferred to -→x (written -→x ≺leximin -→y ) if and only if ∃i ∈ llbracket0, n - 1rrbracket such that ∀j ∈ llbracket1, irrbracket, x↑j = y↑ j and x↑i+1 < y↑ i+1 . We write -→x ⪯leximin -→y for -→x ≺leximin -→y or -→x ∼leximin -→y . The binary relation ⪯leximin is a total preorder.

In other words, the leximin preorder is the lexicographic preorder over ordered utility vectors. For example, we have 〈4, 1, 5, 1〉 ≺leximin 〈2, 2, 1, 2〉.

A known result is that no collective utility function can represent the leximin preorder 5 , unless the set of possible utility profiles is finite. In this latter case, it can be represented by the following non-linear functions: g1 : -→x ↦→ - ∑ni=i n-xi (adapted for leximin from a remark in [Frisch et al., 2003]) and g2 : -→x ↦→ - ∑ni=1 x-q i , where q > 0 is large enough [Moulin, 1988]. Using this kind of functions has however a main drawback: it rapidly becomes unreasonable when the upper bound of the possible values of -→x increases. Moreover, it hides the semantics of the leximin preorder and hinders the computational benefits we can possibly take advantage of.

In the following, we will use the leximin preorder as a criterion for ensuring fairness and Pareto-efficiency, and we will be seeking the non-dominated solutions in the sense of the leximin preorder. Those solutions will be called leximinoptimal. This problem will be expressed in the next section in a CP framework.

3 Constraint programming and leximin-optimality

The constraint programming framework is an effective and flexible tool for modeling and solving many different combinatorial problems such as planning and scheduling problems, resource allocation problems, or configuration problems. This paradigm is based on the notion of constraint network [Montanari, 1974]. A constraint network consists of a set of variables X = {X1, . . . ,Xp} (in the following, variables will be written with uppercase letters), a set of associated domains D = {DX1 , . . . , DXp }, where DXi is the set of possible values for Xi, and a set of constraints C, where each c ∈ C specifies a set of allowed tuples R(c) over a set of variables X (c). We make the additional assumption that all the domains are in N, and we will use the following notations: X = min(DX) and X = max(DX).

5 In other words there is no g such that -→x ⪯leximin -→y ⇔ g(-→x ) ≤ g(-→y ). See [Moulin, 1988].

An instantiation v of a set S of variables is a function that maps each variable X ∈ S to a value v(X) of its domain DX. If S = X, this instantiation is said to be complete, otherwise it is partial. If S ′ ⊊ S, the projection of an instantiation of S over S ′ is the restriction of this instantiation to S ′ and is written v↓S ′ . An instantiation is said to be consistent if and only if it satisfies all the constraints. A complete consistent instantiation of a constraint network is called a solution. The set of solutions of (X , D, C) is written sol(X , D, C). We will also write v[X ← a] the instantiation v where the value of X is replaced by a.

Given a constraint network, the problem of determining whether it has a solution is called a Constraint Satisfaction Problem (CSP) and is NP-complete. The CSP can be classically adapted to become an optimization problem in the following way. Given a constraint network (X , D, C) and an objective variable O ∈ X, find the value m of DO such that m = max{v(O) | v ∈ sol(X , D, C)}. We will write max(X , D, C,O) for the subset of those solutions that maximize the objective variable O.

Expressing a collective decision making problem with a numerical collective utility criterion as a CSP with objective variable is straightforward: consider the collective utility as the objective variable, and link it to the variables representing individual utilities with a constraint. However this cannot directly encode our problem of computing a leximin-optimal solution, which is a kind of multicriteria optimization problem. We introduce formally the MaxLeximinCSP problem as follows :

Definition 2 (MaxLeximinCSP problem)

Input: a constraint network (X , D, C); a vector of variables -→U = 〈U1, . . . , Un〉 ∈ X n , called an objective vector. Output: "Inconsistent" if sol(X , D, C) = ∅. Otherwise a so-̂

lution ̂v such that ∀v ∈ sol(X , D, C), v(-→U ) ⪯leximin v(-→U ).

We describe in the next section several generic constraint programming algorithms that solve this problem. The first one is entirely original, and the other ones are based on existing works that are adapted to fit with our problem.

4 Proposed algorithms

4.1 Using a cardinality combinator

Our first algorithm is based on an iterative computation of the components of the leximin-optimal vector. It first computes the maximal value y1 such that there is a solution v with ∀i, y1 ≤ v(Ui), or in other words ∑i (y1 ≤ v(Ui)) = n, where by convention the value of (y1 ≤ v(Ui)) is 1 if the inequality is satisfied and 0 otherwise 6 . Then, after having fixed this value for y1, it computes the maximal value y2 such that there is a solution v with ∑i (y2 ≤ v(Ui)) ≥ n - 1, and so on until the maximal value yn such that there is a solution v with ∑i (yn ≤ v(Ui)) ≥ 1.

To enforce the constraint on the yi, we make use of the meta-constraint AtLeast, derived from a cardinality combinator introduced by [Van Hentenryck et al., 1992], and present in most of CP systems:

6 This convention is inspired by the constraint modeling language OPL [Van Hentenryck, 1999].

Definition 3 (Meta-constraint AtLeast) Let Γ be a set of p constraints, and k ∈ llbracket1, prrbracket be an integer. The meta-constraint AtLeast(Γ, k) holds on the union of the scopes of the constraints in Γ, and allows a tuple if and only if at least k constraints from Γ are satisfied.

Due to its genericity, this meta-constraint cannot provide very efficient filtering procedures. In our case where the constraints of Γ are linear, this meta-constraint is simply a counting constraint, and bound-consistency can be achieved in O(n). The specific meta-constraint AtLeast can also be implemented with a set of linear constraints [Garfinkel and Nemhauser, 1972, p.11], by introducing n 0-1 variables {Δ1, . . . ,Δn}, and a set of linear constraints {X1 +Δ1Y ≥ Y, . . . ,Xn +ΔnY ≥ Y, ∑ni=1 Δi ≤ n - k}.

Our first approach for computing a leximin-optimal solution is presented in algorithm 1.

Algorithm 1: Computation of a leximin-optimal solution using a cardinality combinator.

input : A const. network (X , D, C); 〈U1, . . . , Un〉 ∈ X n output: A solution to the MaxLeximinCSP problem if solve(X , D, C) = "Inconsistent" return "Inconsistent"; 1 (X0, D′0, C0) ← (X , D, C); 2 for i ← 1 to n do 3 Xi ← Xi-1 ∪ {Yi}; 4 Di ← D′i-1∪{DYi } with DYi = llbracketminj (Uj ), maxj (Uj )rrbracket; 5 Ci ← Ci-1 ∪ 6 {AtLeast({Yi ≤ U1, . . . , Yi ≤ Un}, n - i + 1)}; b v(i) ← maximize(Xi, Di , Ci, Yi); 7 D′i ← Di with DYi ← {b v(i)(Yi)}; 8

• return b v(n)↓X ; 9

The functions solve and maximize (the detail of which is the concern of solving techniques for constraints satisfaction problems) of lines 1 and 7 respectively return one solution v ∈ sol(X , D, C) (or "Inconsistent" if such a solution does not exist), and an optimal solution ̂ v ∈ max(Xi, Di, Ci, Yi) (or "Inconsistent" if sol(Xi, Di, Ci) = ∅). We assume - contrary to usual constraint solvers - that these two functions do not modify the input constraint network.

The following example illustrates the behavior of the algorithm. It is a simple resource allocation problem, where 3 objects must be allocated to 3 agents, with the following con-

straints: each agent must get one and only one object, and one object cannot be allocated to more than one agent (i.e. a perfect matching agent/objects). A utility is associated with each pair (agent,object) with respect to the array above.

This problem has 6 feasible solutions (one for each permutation of llbracket1, 3rrbracket), producing the 6 utility profiles shown in the columns of the following array:

The algorithm runs in 3 steps: Step 1: After having introduced one variable Y1, we look for the maximal value ̂ y1 of Y1 such that each (at least 3) agent gets at least Y1. We find ̂ y1 = 3. The variable Y1 is fixed to this value, implicitly removing profiles p1 and p3. Step 2: After having introduced one variable Y2, we look for the maximal value ̂ y2 of Y2 such that at least 2 agents get at least Y2. We find ̂ y2 = 7. The variable Y2 is fixed to this value, implicitly removing profile p4. Step 3: After having introduced one variable Y3, we look for the maximal value ̂ y3 of Y3 such that at least 1 agent gets at least Y3. We find ̂ y3 = 9. Only one instantiation maximizes Y3: p6. Finally, the returned leximin-optimal allocation is: a1 ← o3, a2 ← o2 and a3 ← o1.

Proposition 1 If the two functions maximize and solve are both correct and both halt, then algorithm 1 halts and solves the MaxLeximinCSP problem.

In the next proofs, we will write soli and sol′i for respectively sol(Xi, Di, Ci) and sol(Xi, D′i , Ci). We will also write (soli)↓Xj and (sol′i )↓Xj for the same sets of solutions projected on Xj (with j < i). We can notice that sol0 = sol(X , D, C), and that ∀i, sol′i ⊆ soli.

Lemma 1 Let -→x be a vector of size n. At least n - i + 1 components of -→x are greater than or equal to x↑i .

The proof of this useful lemma is obvious, so we omit it.

Lemma 2 If sol0 ̸= ∅ then ̂v(n) is well-defined and not equal to "Inconsistent".

Proof: Let i ∈ llbracket1, nrrbracket, suppose that sol′i-1 ̸= ∅, and let v(i) ∈ sol′i-1. Then extending v(i) by instantiating Yi to minj(Uj) leads to a solution of (Xi, Di, Ci) (only one constraint has been added and it is satisfied by the latter instantiation). Therefore soli ̸= ∅ and, if maximize is correct, b v(i) ̸= "Inconsistent" and b v(i) ∈ sol′i. So, sol′i ̸= ∅. It proves lemma 2 by induction. ■

Proof: We have sol′i ⊆ soli, and (soli+1)↓Xi ⊆ sol′i (since from (Xi, D′i, Ci) to (Xi+1, Di+1, Ci+1) we just add a constraint). More generally, (sol′i)↓Xj ⊆ (soli)↓Xj , and (soli+1)↓Xj ⊆ (sol′i)↓Xj , as soon as j ≤ i. Hence, (b v(n))↓Xi ∈ (sol′n)↓Xi ⊆ (soln)↓Xi ⊆ · · · ⊆ (soli+1)↓Xi ⊆ sol′i ⊆ soli. ■

Proof: For all i ∈ llbracket1, nrrbracket, (b v(n))↓Xi is a solution of soli by lemma 3. By lemma 1, (b v(n))↓Xi [Yi ← b v(n)(-→U )↑i ] satisfies the cardinality constraint of iteration i, and is then a solution of soli. By definition of function maximize, we thus have b v(i)(Yi) ≥ b v(n)(-→U )↑i . Since b v(i)(Yi) = b v(n)(Yi), we have b v(n)(Yi) ≥ b v(n)(-→U )↑i .

Since b v(n) is a solution of soln, at least n - i + 1 numbers from vector b v(n)(-→U ) are greater than or equal to b v(n)(Yi). At least the n - i + 1 greatest numbers from b v(n)(-→U ) must then be greater than or equal to b v(n)(Yi). These components include bv(n)(-→U )↑i , which leads to b v(n)(Yi) ≤ b v(n)(-→U )↑i , proving the lemma. ■

We can now put things together and prove proposition 1.

Proof of proposition 1: If sol(X , D, C) = ∅, and if solve is correct, then algorithm 1 obviously returns "Inconsistent". Otherwise, following lemma 2, it outputs an instantiation (b v(n))↓X which is, according to lemma 3, a solution of (X0, D0, C0) = (X , D, C). Suppose that there is a v ∈ sol(X , D, C) such that v(-→U ) ≻leximin b v(n)(-→U ). Then following definition 1, ∃i ∈ llbracket1, nrrbracket such that ∀j < i, v(-→U )↑j = b v(n)(-→U )↑j and v(-→U )↑i > b v(n)(-→U )↑i . Let v+ (i) be the extension of v respectively instantiating Y1, . . . Yi-1 to b v(n)(Y1), . . . b v(n)(Yi-1) and Yi to v(-→U )↑i . Following lemma 4, ∀j, b v(n)(Yj) = b v(n)(-→U )↑j . By gathering all the previous equalities, we have ∀j < i v+ (i) (Yj) = bv(n)(Yj) = v(-→U )↑j = (v+ (i) (-→U ))↑j . We also have v+ (i) (Yi) = v(-→U )↑i = (v+ (i) (-→U ))↑i . By lemma 1, ∀j ≤ i at least n - j + 1 numbers from (v+ (i) (-→U )) are greater than or equal to v+ (i) (Yj), proving that v+ (i) satisfies all the cardinality constraints at iteration i. Since it also satisfies each constraint in C and maps each variable of Xi to one of its possible values, it is a solution of soli, and v+ (i) (Yi) = v(-→U )↑i > b v(n)(-→U )↑i = b v(i)(Yi). It contradicts the definition of maximize, proving the proposition 1. ■

4.2 Using a sorting constraint

Our second algorithm is directly based on the definition 1 of the leximin preorder, which involves the sorted version of the objective vector. This can be naturally expressed in the CP paradigm by introducing a vector of variables -→Y and enforcing the constraint Sort(-→U , -→Y ) which is defined as follows:

Definition 4 (Constraint Sort) Let -→X and -→X ′ be two vectors of variables of the same length, and v be an instantiation. The constraint Sort(-→X, -→X ′ ) holds on the set of variables being either in -→X or in -→X ′ , and is satisfied by v if and only if v(-→X ′ ) is the sorted version of v(-→X) in increasing order.

This constraint has been particularly studied in two works, which both introduce a filtering algorithm for enforcing bound consistency on this constraint. The first algorithm comes from [Bleuzen-Guernalec and Colmerauer, 1997] and runs in O(n logn) (n being the size of -→X). [Mehlhorn and Thiel, 2000] designed a simpler algorithm that runs in O(n) plus the time required to sort the interval endpoints of -→X , which can asymptotically be faster than O(n log n).

Algorithm 2: Computation of a leximin-optimal solution using a sorting constraint.

input : A const. network (X , D, C); 〈U1, . . . , Un〉 ∈ X n output: A solution to the MaxLeximinCSP problem

• if solve(X , D, C) = "Inconsistent" return "Inconsistent"; 1 X ′ ← X ∪ {Y1, . . . , Yn}; 2 D′ ← D ∪ {DY1 , . . . , DYn }, DYi = llbracketminj (Uj ), maxj (Uj )rrbracket; 3 C ′ ← C ∪ {Sort(-→U , -→Y )}; 4 for i ← 1 to n do 5 b v(i) ← maximize(X ′ , D′ , C ′ , Yi); 6 DYi ← {b v(i)(Yi)}; 7 return b v(n)↓X ; 8

Proposition 2 If the two functions maximize and solve are both correct and both halt, then algorithm 2 halts and solves the MaxLeximinCSP problem.

Proof: If sol(X , D, C) = ∅ and if solve is correct, then algorithm 2 obviously returns "Inconsistent". We will suppose in the following that sol(X , D, C) ̸= ∅ and we will use the following notations: soli and sol′i are the sets of solutions of (X ′ , D′ , C ′ ) respectively at the beginning and at the end of iteration i.

We have obviously ∀i ∈ llbracket1, n - 1rrbracket soli+1 = sol′i, which proves that if soli ̸= ∅, then the call to maximize at line 6 does not return "Inconsistent", and soli+1 ̸= ∅. Thus b v(n) is well-defined, and obviously (b v(n))↓X is a solution of (X , D, C).

We note bv = b v(n) the instantiation computed by the last maximize in algorithm 2. Suppose that there is an instantiation v ∈ sol(X , D, C) such that b v(-→U ) ≺leximin v(-→U ). We define v+ the extension of v that instantiates each yi to v(-→U )↑i . Then, due to constraint Sort, bv(-→Y ) and v+(Y ) are the respective sorted version of b v(-→U ) and v+(U). Following definition 1, there is an i ∈ llbracket0, n - 1rrbracket such that ∀j ∈ llbracket1, irrbracket, b v(Yj) = v+(Yj) and b v(Yi+1) < v+(Yi+1). Due to line 7, we have b v(Yi+1) = b v(n)(Yi+1) = b v(i+1)(Yi+1). Thus v+ is a solution in max(X ′ , D′ , C ′ , Yi+1) with objective value v+ (i+1) (Yi+1) strictly greater than b v(i+1) (Yi+1), which contradicts the hypothesis about maximize. ■

4.3 Using a multiset ordering constraint

Our third algorithm computing a leximin-optimal solution is perhaps the most intuitive one. It proceeds in a pseudo branch and bound manner: it computes a first solution, then tries to improve it by specifying that the next solution has to be better (in the sense of the leximin preorder) than the current one, and so on until the constraint network becomes inconsistent. This approach is based on the following constraint:

Definition 5 (Constraint Leximin) Let -→X be a vector of variables, -→λ be a vector of integers, and v be an instantiation. The constraint Leximin(-→λ , -→X) holds on the set of variables belonging to -→X, and is satisfied by v if and only if -→λ ≺leximin ---→ v(X).

Although this constraint does not exist in the literature, the work of [Frisch et al., 2003] introduces an algorithm for enforcing generalized arc-consistency on a quite similar constraint: the multiset ordering constraint, which is, in the context of multisets, the equivalent of a leximax 7 constraint on vectors of variables. At the price of some slight modifications, the algorithm they introduce can easily be used to enforce the latter constraint Leximin.

Proposition 3 If the function solve is correct and halts, then algorithm 3 halts and solves the MaxLeximinCSP problem.

The proof is rather straightforward, so we omit it.

4.4 Other approaches

In the context of fuzzy constraints, two algorithms dedicated to the computation of leximin-optimal solutions have been published by [Dubois and Fortemps, 1999]. These algorithms Algorithm 3: Computation of a leximin-optimal solution in a branch and bound manner.

7 The leximax is based on an increasing reordering of the values, instead of a decreasing one for leximin.

input : A const. network (X , D, C); 〈U1, . . . , Un〉 ∈ X n output: A solution to the MaxLeximinCSP problem b v ← null; v ← solve(X , D, C); 1 while v ̸= "Inconsistent" do 2 b v ← v; 3 C ← C ∪ {Leximin(b v(-→U ), -→U )}; 4 v ← solve(X , D, C); 5 if b v ̸= null then return bv else return "Inconsistent"; 6

work by enumerating, at each step, all the subsets of fuzzy constraints (corresponding to our agents) having a property connected to the notion of consistency degree.

[Ehrgott, 2000, p. 162] describes two very simple algorithms for solving the closely related "Lexicographic MaxOrdering" problem (that could be called "leximax-optimal" in our terms). However, they do not seem realistic in the context of combinatorial problems, since they are based on an enumeration of all utility profiles.

5 Experimental results

The algorithms 1, 2, 3 and the first algorithm proposed in [Dubois and Fortemps, 1999] have been implemented and tested using the constraint programming tool CHOCO [Laburthe, 2000]. So as to test them on realistic instances, we have extracted, from a real-world problem, a simplified multiagent resource allocation problem. In this problem, the resource is a set of objects O, that must be allocated to some agents under volume and consumption constraints. The individual utility functions are specified by a set of weights wa,o (one per pair (agent, object)): given an allocation of the objects, the individual utility of an agent i is the sum of the weights wi,o of the objects o that she receives. The weights can be generated uniformly or can be concentrated around some powers of 10, so as to simulate some kind of priorities 8 .

We have developed a customizable generator of random instances, available online 9 . We tested our algorithms on several instances, with very different characteristics, leading to very different kind of problems. Here is a brief description of each kind of instances appearing in table 1 (by default, the weights are non-uniformly distributed, and the constraints are of medium tightness):

(1) 10 agents, 100 objects. (2) 4 agents, 100 objects. (3) 20 agents, 40 objects. (4) 10 agents, 100 objects, low-tightness constraints. (5) 10 agents, 100 objects, hard-tightness constraints. (6) 10 agents, 30 objects, uniformweights (with low values), hard-tightness constraints. (7) 4 agents, 150 objects.

The results from table 1 show that algorithm 1 has the best running times with most of the instances, followed by algorithm 2 which is almost as fast, but is less efficient when the number of agents increases (instances of kind 3), whereas algorithm 3 is better on this kind of instances. As expected, the algorithm from [Dubois and Fortemps, 1999] explodes when the number of equal components in the leximin-optimal vector increases (kinds (3) and (6)).

8 Approximating the conditions of our real-world application.

9 http://www.cert.fr/dcsd/THESES/sbouveret/benchmark/

These results must however be considered with care, since they are subject to our implementation of the filtering algorithms. In particular, not every optimizations given in [Mehlhorn and Thiel, 2000] for the constraint Sort have been implemented yet. Moreover, the running times are highly affected by the variable choice heuristics. In our tests, we used the following particular heuristics, that are specially efficient: choose as the next variable to instantiate the one that will the most increase the lowest objective value (in our application problem we first allocate the objects that have the highest weight for the currently least satisfied agent).

6 Conclusion

The leximin preorder cannot be ignored when dealing with optimization problems in which some kind of fairness must be enforced between utilities of agents or equally important criteria. This paper brings a contribution to the computation of leximin-optimal solutions of combinatorial problems. It describes, in a constraint programming framework, three generic algorithms solving this problem. The first one, based on a cardinality combinator, is entirely new, and gives slightly better results than two algorithms based on the sort and leximin constraints.