Roberto Lucchetti
email: roberto.lucchetti@polimi.it

Stefano Moretti
email: stefano.moretti@dauphine.fr

Fioravante Patrone
email: patrone@diptem.unige.it

Ranking sets of interacting objects via semivalues

In this paper, we address the problem of how to extend a ranking over single objects to another ranking over all possible collections of objects, taking into account the fact that objects grouped together can have mutual interaction.

An answer to this issue is provided by using game theory and, specifically, the fact that an extension (i.e., a total proorder on the set of all subsets of objects) must be aligned with some probabilistic value, in the sense that the ranking of the objects (according to some probabilistic value computed on a numerical representation of the extension) must also preserve the primitive preorder on the singletons, no matter which utility function is used to represent the extension.

We characterize families of aligned extensions, we focus on their geometric properties and we provide algorithms to verify their alignments. We also show that the framework introduced in this paper may be used to study a new class of extension problems, which integrate some features dealing with risk and complete uncertainty within the class of preference extension problems known in the literature with the name of sets as final outcomes.

Introduction

Many problems, inspired by individual and collective decision making, deal with preferences over collections of objects (e.g., alternatives, opportunities, candidates, etc.). Consider, for instance, the selection of the candidate members for the formation of evaluation committees, the assessments of equity of sets of rights inside a society, the comparison of assets in portfolio analysis, the comparison of the stability of groups in coalition formation theory, and many others. In practice, however, mainly the information about preferences among single objects is available, and then a central question may arise: given a primitive ranking over the single elements of a set N , how to derive a compatible ranking over the set of all subsets of N ?

This question has been carried out in the tradition of the literature on extending an order on a set N to its power set (denoted by 2 N ) with the objective to axiomatically characterize families of ordinal preferences over subsets (see, 1 for instance, [START_REF] Barberà | On some axioms for ranking sets of alternatives[END_REF][START_REF] Barberà | Ranking sets of objects. Handbook of Utility Theory[END_REF][START_REF] Bossert | Preference extension rules for ranking sets of alternatives with a fixed cardinality[END_REF][START_REF] Bossert | Ranking opportunity sets: An axiomatic approach[END_REF][START_REF] Fishburn | Signed orders and power set extensions[END_REF][START_REF] Geist | Automated search for impossibility theorems in social choice theory: Ranking sets of objects[END_REF][START_REF] Kannai | A note on the extension of an order on a set to the power set[END_REF][START_REF] Kreps | A representation theorem for "preference for flexibility[END_REF]). In this context, an order on the power set 2 N is required to be an extension of a primitive order R on N . This means that the relative ranking of any two singleton sets according to must be the same as the relative ranking of the corresponding alternatives according to R (i.e., for each a, b ∈ N , {a} {b} ⇔ aRb). According to this definition, in the remaining of the paper we will simply refer to a total preorder on 2 N as an extension on 2 N , with the implicit assumption that such a relation ranks singletons in 2 N in the same way of some equivalent primitive total preorder R on N .

The different axiomatic approaches in the literature are related to the interpretation of the properties used to characterize extensions, that is deeply interconnected to the meaning that is attributed to sets. In fact, according to the survey of [START_REF] Barberà | Ranking sets of objects. Handbook of Utility Theory[END_REF], the main contributions from the literature on ranking sets of objects may be grouped in three main classes of problems: 1) complete uncertainty, where a decision-maker is asked to rank sets which are considered as formed by mutually exclusive objects (i.e., only one object from a set will materialise), and taking into account that he cannot influence the selection of an object from a set (see, for instance, [START_REF] Barberà | On some axioms for ranking sets of alternatives[END_REF][START_REF] Kannai | A note on the extension of an order on a set to the power set[END_REF][START_REF] Nitzan | Median-based extensions of an ordering over a set to the power set: An axiomatic characterization[END_REF]); 2) opportunity sets, where sets contain again mutually exclusive objects but, in this case, a Decision Maker (DM) compares sets taking into account that he will be able to select a single element from a set (see, for example, [START_REF] Bossert | Ranking opportunity sets: An axiomatic approach[END_REF][START_REF] Kreps | A representation theorem for "preference for flexibility[END_REF][START_REF] Puppe | An axiomatic approach to preference for freedom of choice[END_REF]); 3) sets as final outcomes, where each set contains objects that are assumed to materialise simultaneously (if that set is selected; for instance, see [START_REF] Bossert | Preference extension rules for ranking sets of alternatives with a fixed cardinality[END_REF][START_REF] Fishburn | Signed orders and power set extensions[END_REF][START_REF] Roth | The college admissions problem is not equivalent to the marriage problem[END_REF]).

In this paper, we focus on the problem of the third class, where sets of elements materialize simultaneously. A standard application of this kind of problems is the college admissions problem [START_REF] Roth | The college admissions problem is not equivalent to the marriage problem[END_REF][START_REF] Gale | College admissions and the stability of marriage[END_REF], where colleges need to rank sets of students based on their ranking of individual applicants. In this framework, most of the approaches present in the literature do not take into account possible interactions between objects. For instance, a typical assumption is the property of responsiveness (RESP) [START_REF] Roth | The college admissions problem is not equivalent to the marriage problem[END_REF]: an extension on 2 N satisfies RESP if for all i, j ∈ N and all S ∈ 2 N , i, j / ∈ S {i} {j} ⇔ S ∪ {i} S ∪ {j}.

Clearly, this means that if an object i is better than another object j, then it is better to add i rather than j to any other subcollection of objects. Clearly, the RESP property does not take into account the fact that some objects together can present some form of incompatibility or, on the contrary, of mutual enforcement.

For this reason a recent approach has been developed in [START_REF] Moretti | Ranking sets of possibly interacting objects using shapley extensions[END_REF] with the objective to take into account the possible interactions between objects. The model introduced in [START_REF] Moretti | Ranking sets of possibly interacting objects using shapley extensions[END_REF] relies on the fact that an utility function attached to a total preorder on 2 N represents a coalitional game in characteristic function form (provided we set the utility of the empty set to be equal to zero). Since probabilistic values [START_REF] Weber | Probabilistic values for games[END_REF][START_REF] Carreras | Some theoretical reasons for using (regular) semivalues[END_REF][START_REF] Carreras | A note on regular semivalues[END_REF][START_REF] Lucchetti | A new family of regular semivalues and applications[END_REF][START_REF] Owen | Game Theory[END_REF] do provide a natural ranking among the elements of the set N (the players in the game theoretical context, the objects in this approach), we can use them in the following sense. According to [START_REF] Moretti | Ranking sets of possibly interacting objects using shapley extensions[END_REF], given a probabilistic value π, an extension on 2 N will be a π-aligned extension on 2 N , provided that from {i} {j} it follows that π ranks better i than j for every possible choice of the utility function representing . In other terms, an extension on 2 N is such that it never changes the mutual positions in the rankings of the objects, no matter is the numerical representation we give to the preference relation on 2 N . Here we study in details the problem of characterizing these extensions, both for a single probabilistic value and for a whole family of values.

Another interpretation of the framework used in [START_REF] Moretti | Ranking sets of possibly interacting objects using shapley extensions[END_REF], which further motivates the interest for π-aligned extensions and where some aspects related to the framework of uncertainty are merged with considerations about the problem of ranking sets as final outcomes, is illustrated in the following example.

Suppose you receive an invitation for a dinner and, being considered an expert in food and wine parties, you are asked to bring a bottle of wine to accompany the main course. Further, suppose that for some reason you don't know which main course will be served. In general, drinking between meals, you might prefer to have red wine than white wine. However, as accompanying drink of a meal based on fish, you might prefer to have white wine than the red one. Typically, your preferences over meals (which are collection of food items) do not satisfy the RESP property (you prefer the singleton {'red wine'} to the {'white wine'} one as a between meals drink, but the meal {'fish' and 'white whine'} is preferred to {'fish' and 'red wine'}). On the other hand, under certain conditions concerning both the probability distribution and your preferences over all possible meals, you still might decide to bring with you at dinner a bottle of red wine, preserving your original preference on drinks between meals. This example shows the importance of considering the possibility of mutual enforcement among objects in the context where subsets of objects materialize randomly. But it also shows that the criterion used to compare two different single objects takes into account their respective ability to improve the relative ranking of (stochastically generated) collection of objects. In addition, assuming that a fish-based meal is selected, what really matters in the decision making process specifying your preference is the expectation of how much your choice will marginally contribute to the success of the dinner event and to sustain your good reputation as a food and wine expert. Consistently, you might also prefer the event where you bring a white wine bottle to a fish-based dinner where red wine is already served, than the event where you bring a red wine bottle to a fish-based dinner where white wine is already served, even if in both cases you are going to join a dinner where both white and red wine are served.

The above example of "choosing the wine for a dinner" can be seen as a particular instance of the more general problem of modelling the preferences of a consumer facing a future randomly generated endowment of goods, where a DM (e.g., a consumer) must choose a single object from a set N (e.g., a set of goods), knowing that after his choice the DM will receive at a second step and at random, a (possibly empty) collection of the other objects in N . More precisely, for each object a ∈ N , a subset S ⊆ N \ {a} is randomly generated (and all of its elements materialize simultaneously) according to a certain probability distribution p(S) over all subsets S of N \ {a}. Suppose also that the DM is aware of the probability distribution p over 2 N \{a} , for each a ∈ N . So, we can look at this problem as the one where a DM must choose among different lotteries associated to objects in N , where each lottery is composed by a deterministic part, the object selected by the DM at the first step of the process, and a stochastic one, the random collection generated with probability p at the second step. Trying to answer the question of how the DM will compare each pair of object a, b in N in such a situation, we might be interested in understanding under which conditions the relative ranking of lotteries associated to objects a and b preserves the primitive preference over the corresponding singletons {a} and {b}. Clearly, a RESP extension does preserve the primitive preference over the singletons: whatever coalition S will materialize at the second step (according to the random mechanism governed by probability p), having S ∪ {a} is preferred to have S ∪ {b} whenever {a} is preferred to {b}. Consequently, the lottery associated to objects a dominates the one associated to b. But also other extensions on 2 N , that do not necessarily satisfy the RESP property, may guarantee as well the preservation of the original preferences over the singletons. Henceforth, knowing the value function of a DM over the collection of objects of N , we should focus on the marginal contribution of each element a to each subset S ∈ 2 N not containing a, and we would apply the classical framework of expected utility theory for comparing the expected marginal contribution of each object in N to all possible collections of other objects, i.e. π a (u) = S⊆N \{a} p(S)(u(S ∪ {a}) -u(S)) of each element a in N .

Unfortunately, in our context, there is no assumption about the risk attitude of a DM, and this makes it impossible to univocally determine the expected utility of an object, face to the successive random selection of a collection. A natural way to avoid this ambiguity is to focus on those extensions on 2 N preserving the primitive ranking over singletons whatever utility function representing is considered. More precisely, we concentrate our study to extensions such that

a b ⇔ π a (u) ≥ π b (u) (2)
for every value function u : 2 N → R representing (and with u(∅) = 0), which is precisely the definition of "π-aligned extensions" provided in the next section.

Putting up the argument that in some cases a DM could ignore the probabilistic distribution governing the stochastic generation of collections of objects at the second step of the process, we observe that the framework introduced above can be easily adapted to a situation of (complete) uncertainty by simply requiring that relation (2) holds for every probabilistic value [START_REF] Weber | Probabilistic values for games[END_REF]. This is the main reason why in this paper we are also interested in studying families of extensions that are π-aligned to all probabilistic values, or alternatively, to subfamilies of these values. In fact, the most interesting results introduced in this paper deal with the well studied family of semivalues [START_REF] Shapley | A value for n-person games[END_REF][START_REF] Banzhaf | Weighted voting doesn't work: A mathematical analysis[END_REF][START_REF] Dubey | Value theory without efficiency[END_REF][START_REF] Carreras | Some theoretical reasons for using (regular) semivalues[END_REF][START_REF] Carreras | A note on regular semivalues[END_REF][START_REF] Carreras | On ordinal equivalence of power measures given by regular semivalues[END_REF][START_REF] Moretti | Transversality of the shapley value[END_REF][START_REF] Freixas | On ordinal equivalence of the shapley and banzhaf values for cooperative games[END_REF][START_REF] Lucchetti | A new family of regular semivalues and applications[END_REF], where the probability distribution over the subsets S of N not containing i is a function of the cardinality of S, and it is the same for all i in N . Focusing on the family of semivalues allows to capture some interesting geometric properties of π-aligned extensions that will be presented in Section 4. Moreover, since it is, as we shall argue, useful to characterize preorders which are aligned for a large class of values, we shall see that some restriction on the (probabilistic) values must be imposed, since there exists no total preorder aligned with all probabilistic values. And the class of semivalues naturally emerges in this context.

The outline of the paper is as follows. After some preliminaries and basic definitions, in Section 3 we provide a full analysis of all possible π-aligned extensions on the powerset of a set with three objects, together with the conditions to discerning extensions which are π-aligned with some semivalues from others which are not. This analysis for a "simple" case is preliminary to the geometric characterization of π-aligned extensions in the general case of n objects, introduced in Section 4. In Section 5, the infinite system of linear inequalities used for the geometric characterization introduced in Section 4 is reduced to a finite system, that works for all semivalues, by means of a decomposition based on dichotomous total preorders. A faster algorithm to check alignment with semivalues based on rational probabilities is then presented in Section 6, together with a characterization inspired to the one for the "Banzhaf-aligned" extensions [START_REF] Banzhaf | Weighted voting doesn't work: A mathematical analysis[END_REF][START_REF] Moretti | Ranking sets of possibly interacting objects using shapley extensions[END_REF]. Finally, the case of complete uncertainty, where extensions are aligned with all semivalues, is discussed in Section 7. Section 8 draws some conclusions.

Preliminaries

We are given a finite set N , of cardinality n. A TU-game on N is a function v : 2 N → R such that v(∅) = 0. A probabilistic value (or probabilistic power index ) π for the game v is an n-vector π

p (v) = (π p 1 (v), π p 2 (v), . . . , π p n (v)), such that π p i (v) = S∈2 N \{i} p i (S)m i (S) (3)
where m i (S) = v(S ∪ {i}) -v(S) is the marginal contribution of i to S ∪ {i}, for each i ∈ N and S ∈ 2 N \{i} , and p = (p i : 2 N \{i} → R + ) i∈N , is a collection of non negative real-valued functions fulfilling the condition S∈2 N \{i} p i (S) = 1. A probabilistic value π p i is called regular when all the coordinates of p are strictly positive functions. A particular interesting case is when the probabilistic value π p is a semivalue, which means that non negative weights p 0 , . . . , p n-1 are given such that p i (S) = p s , whenever the cardinality of coalition S, denoted by |S|, is equal to s and i ∈ N ; furthermore, it is required that

n-1 k=0 p k n-1 k = 1
, in order to fulfil the condition S∈2 N \{i} p s = 1; thus p = (p 0 , . . . , p n-1 ) represents a probability distribution on the family of the subsets of N not containing i, and it is the same for all i ∈ N . We shall denote by p a vector (p 0 , . . . , p n-1 ) as above, and, by a slight abuse of notation, π p is the semivalue engendered by the vector p. Hence

π p i (v) = S∈2 N \{i} p s m i (S). 1 (4)
The two most famous regular semivalues (i.e., with p s > 0, for each s = 0, . . . , n -1) are the Shapley value, with p s =

1 n( n-1 s )
, and the Banzhaf index, with p s =1 2 n-1 , for each s = 0, . . . , n -1. Other regular semivalues are present in the literature [START_REF] Lucchetti | A new family of regular semivalues and applications[END_REF][START_REF] Owen | Game Theory[END_REF][START_REF] Carreras | On ordinal equivalence of power measures given by regular semivalues[END_REF].

We shall denote by P the set of all probabilistic values and by S (RS, respectively) the set of all semivalues (regular semivalues, respectively), for the given fixed set N . From above, we know that S is a simplex in an n-dimensional space, and RS is its relative interior.

A binary relation on a finite set X is denoted by ⊆ X × X. For each x, y ∈ X, the more familiar notation x y will be used instead of the more formal (x, y) ∈ . The following are some standard properties for a binary relation ⊆ X × X:

• reflexivity: for each x ∈ X, x x;

• transitivity: for each x, y, z ∈ X, x y and y z ⇒ x z;

• total : for each x, y ∈ X, x = y ⇒ x y or x y;

• antisymmetry: for each x, y ∈ X, x y and y x ⇒ x = y.

A total preorder on 2 N is a reflexive, transitive and total binary relation ⊆ 2 N × 2 N . A reflexive, transitive, total and antisymetric binary relation is called total order or linear order. We interpret a total preorder on 2 N as a preference relation on 2 N (that is, for each S, T ∈ 2 N , S T stands for 'S is considered at least as good as T according to '), and we will refer to it with the term extension on 2 N (of a primitive total preorder R on N such that iRj ⇔ {i} {j}).

In this paper, a central property for extensions on 2 N is the responsiveness (RESP) property: Definition 1 (RESP). A total preorder on 2 N satisfies the RESP property on 2 N if for all i, j ∈ N and all S ∈ 2 N , i, j / ∈ S we have that

{i} {j} ⇔ S ∪ {i} S ∪ {j}. (5)
Now, suppose we have an extension on 2 N . This relation naturally induces a TU game for each utility function v representing

(such that v(∅) = 0), i.e. u(S) ≥ u(T ) ⇔ S
T for each S, T ∈ 2 N . We shall denote by V ( ) the set of all v representing the total preorder . Fixed a semivalue, each v ∈ V ( ) provides a ranking on the elements of N . This ranking in general depends on the given utility function selected in V ( ).

In this paper we want to investigate several issues related to the following definition.

Definition 2 (π p -alignement). Given a set N , a total preorder on 2 N and a probabilistic value π p ∈ P, we shall say that is π p -aligned if

{i} {j} ⇔ π p i (v) ≥ π p j (v)
for each v ∈ V ( ).

In the sequel, we shall make use of the following notations. We shall denote by Σ i (Σ ij ) the set of all subsets of N which do not contain i (neither i nor j). Also, denote by Σ s ij the set of the subsets of Σ ij of cardinality s. Given a semivalue π p ∈ S and a TU game with N as set of players, we shall constantly consider the difference π p i (v) -π p j (v). The next two formulas are useful to this aim. The first one is obvious:

π p i (v) -π p j (v) = n-1 s=0 p s [c i (s) -c j (s))] (6)
where

c i (s) = S∈Σi:|S|=s [v(S ∪ {i}) -v(S)]. (7)
For the second, denote by

d S ij (v) the difference d S ij (v) = v(S∪{i})-v(S∪{j}).
Then the following formula holds:

π p i (v) -π p j (v) = n-2 s=0 (p s + p s+1 )   S∈Σ s ij d S ij (v)   . (8)
For, it is enough to observe that, for every h, k ∈ N ,

π p h (v) = n-2 s=0 S∈Σ s hk p s (v(S ∪ {h}) -v(S)) + S∈Σ s hk p s+1 (v(S ∪ {h} ∪ {k}) -v(S ∪ {k})) .
3 Lessons from the case N = {1, 2, 3}

We consider now the case of three objects, thus N = {1, 2, 3}. The set of all total preorders on the subsets of N is not small, its cardinality being 545835. However the classification of the preorders aligned with some semivalue can be fully characterized with no much difficulty. To perform our analysis, let us make some preliminary consideration. Suppose we are given a preorder , and let us denote by i, j, k the elements of N . Then the basic formula (8) becomes, for i, j:

π p i (v) -π p j (v) = (p 0 + p 1 )(v({i}) -v({j})) + (p 1 + p 2 )(v({i, k}) -v({j, k})). ( 9
)
We have to consider the following cases:

1. suppose {i} {j}. There are three possibilities:

1.i) {i, k} ∼ {j, k}. In this case it is clear that π p i (v) -π p j (v) > 0 if and only if p 2 = 1; 1.ii) {i, k} {j, k}. In this case, π p i (v) -π p j (v) > 0 for each v ∈ V ( ); 1.iii) {j, k} {i, k}.
In this case, one must consider two subcases:

1.iii.a) suppose either {j, k} {i} or {j} {i, k}. In this case the inequality: [START_REF] Fishburn | Signed orders and power set extensions[END_REF] for any fixed (p 0 + p 1 ), (p 1 + p 2 ) cannot be verified by all compatible functions v ∈ V ( ), unless p 0 = 1; 2. suppose now two objects are indifferent, say {i} ∼ {j}. Then, in order to have that ( 9) is null as needed, either p 0 = 1 or, in case p 0 < 1, it is clearly necessary and sufficient that {i, k} ∼ {j, k}.

(p 0 + p 1 )(v({i}) -v({j})) + (p 1 + p 2 )(v({i, k}) -v({j, k})) > 0
Summarizing the above considerations, we can state the following.

Theorem 1. Let N = {1, 2, 3} and let be a total preorder on 2 N . Then, the following alternatives hold: i) is π p -aligned with the whole set of the semivalues π p ∈ S. This happens if and only if for any pair of objects i, j ∈ N we have that either {i} {j} and {i, k} {j, k} or {i} ∼ {j} and {i, k} ∼ {j, k};

ii) is π p -aligned with the set of the semivalues π p ∈ S such that p 0 ≥ p 2 . This happens iff for at least one pair of object i, j ∈ N we have that {i} {j, k} {i, k} {j}, and for the remaining pairs of objects in N the conditions specified at point (i) hold.

iii) is π p -aligned only if p 0 = 1. This happens for all other cases not covered by the previous ones.

Notice that, in order to guarantee that is π p -aligned for p = (0, 0, 1) it is necessary that, for each i, j ∈ N = {1, 2, 3}, i = j, either [{i} {j} and {i, k} {j, k}] or [{i} ∼ {j} and {i, k} ∼ {j, k}], with k ∈ N \ {i, j}, and therefore by Theorem 1.(i), relation is also aligned with all other semivalues in S.

Theorem 1.(i) also shows that, for the case with three objects, the RESP property is a necessary and sufficient condition for an extension to be π p -aligned with all semivalues π p ∈ S. As we will show in Section 7, this results does not hold for larger set of objects, i.e. the extensions that satisfy the RESP property are π p -aligned with all semivalues π p ∈ S (as it is easy to see), but in general the converse is not true (see Example 4), and many extensions that do not satisfy the RESP property are π p -aligned with some semivalues π p ∈ S.

On the other hand, as already mentioned, it is a nonsense to consider the whole class of probabilistic values. For, we claim that no total preorder can be aligned with all of them. To see this, fix a total preorder on 2 N and consider two distinct objects in N = {1, 2, 3}, call them i and j, and suppose {i} {j}. Set p i (S) = 0 unless S = {i}, and p j (S) = 0 unless S = {∅}. Then it is easy to verify that π p i (v) -π p j (v) = v({i, j}) -2v({j}), that can clearly be made negative with a suitable choice of v.

A geometric description of aligned preorders

Now we start the study of the problem of establishing whether a given total preorder on 2 N is aligned for a given semivalue, or also for a specific subfamily of semivalues.

First, let us make a very simple observation. It is quite possible that a given preorder is aligned with only the trivial semivalue (1, 0, . . . , 0): we have already seen this in the case of three objects. Another obvious remark is that when we want to prove that for some i, j ∈ N , it is π p i (v) -π p j (v) ≥ 0, in formula ( 8) we can substitute the coefficients p s + p s+1 , s = 0, . . . , n -2, with coefficients a(p s + p s+1 ) for every a > 0. Thus when the entries p 0 , . . . , p n-1 are rational, we shall assume that the associated p s + p s+1 are actually natural numbers. For instance, in the case of the Banzhaf semivalue, we can assume p s + p s+1 = 1 for all s.

For easy notation, we shall write x s+1 for p s + p s+1 : x s+1 = p s + p s+1 . Now, in order to provide a geometric description of the set of semivalues aligned with a given preorder, we formulate the conditions in Equation ( 8) with a different notation. Set

  S∈Σ s ij d S ij (v)   = a ijv s+1 .
Denote by X the set of solutions of the following semi-infinite system of linear inequalities:

a ijv 1 x 1 + a ijv 2 x 2 + • • • + a ijv n-1 x n-1 ≥ 0, v ∈ V ( ), i j, (11)
x 1 ≥ 0, . . . x n-1 ≥ 0 ( 12
)
Then the set of semivalues aligned with is the set

A = {p = (p 0 , . . . , p n-1 ) : Lp ∈ X} ∩ S,
where L is the (n -1) × n matrix

L =     1 1 0 . . . 0 0 0 1 1 . . . 0 0 . . . . . . . . . . . . . . . . . . 0 0 0 . . . 1 1     .
Clearly A is a closed convex containing the vector (1, 0, . . . , ).

Also the following remark is of some interest. The term a ijv 1 = v({i})-v({j}) is positive if and only if {i} {j} and null if and only if i ∼ j. This implies that if a nonnegative x satisfies the system [START_REF] Freixas | On ordinal equivalence of the shapley and banzhaf values for cooperative games[END_REF], then also x = (x 1 , x2 , xn-1 ) satisfies the same system, for x1 = x 1 + k, xi = x i for 1 < i ≤ n -1. This in turn implies that when x1 < 1, then is aligned with every semivalue p fulfilling p0 + p1 = x1 and ps + ps+1 = αx s+1 for each s = 1, . . . , n -2, and with α such that

n-1 s=0 ps n-1 s = 1.
Finally, it is clear that the system Lp = x has infinite (positive) solutions, for every x, depending on a free parameter.

Summarizing the previous observations we get the following theorem.

Theorem 2. Let be a total preorder on 2 N which is aligned with the elements of a set of semivalues A ⊆ S. We have that A is either reduced to the singleton (1, 0, . . . , 0) or it is at least a two dimensional closed convex subset of the simplex S.

The next Example shows that the set of semivalues for which a total preorder is aligned can be exactly two dimensional even for n > 3.

Example 1. Let N = {1, 2, 3, 4, 5} and consider the preference relation for which 2 N is partitioned in three subsets, respectively V G, G and B, where all elements in the same subset are indifferent and all elements of V G are strictly preferred to all elements of G which in turn are strictly preferred to all elements in B. The sets:

V G = {{1}, {1, 3}, {2}, {2, 3, 4}, {4, 5}, {1, 2, 5}, {1, 2, 3, 4}} G = {{3}, {1, 3, 5}, {4}, {1, 2, 4, 5}, {2, 4}, {3, 5}} and B = {2 N \ {V G ∪ G}}.
Consider the system [START_REF] Freixas | On ordinal equivalence of the shapley and banzhaf values for cooperative games[END_REF]. By comparing the objects 1 and 2 one easily gets x 2 = x 3 and by comparing the objects 3 and 4 it is seen that x 4 = x 3 . A simple calculation shows that no further conditions must be added in order to verify the inequalities. This implies that the preference relation is aligned for every semivalue of the form

p = (p 0 , p 1 , 1 -p 0 -2p 1 2 , p 1 , 1 -p 0 -2p 1 2 )
such that π p ∈ S.

To conclude this section, let us observe that another particular case arises when considering the semivalue (0, . . . , 0, 1). In this case the partial order is aligned with the semivalue if and only if {i} {j} ⇒ N \ {j} N \ {i}. In this case the set of semivalues aligned with contains the edge [(1, 0, . . . , 0), (0, . . . , 0, 1)].

Alignment with a finite number of inequalities

In this section we prove that the infinite system of linear inequalities characterizing alignments, as shown in Section 4, can be reduced to a finite system. It will be also apparent that the system is still very heavy to deal with; for this reason in the following section we shall see a faster system to check alignment. However the characterization we prove here is theoretically important since it applies to all semivalues, while the next one is valid only for a (large) subset of semivalues.

Let be a total preorder on 2 N . For each A ∈ 2 N , we denote by P s ij ( , A) the set of all subsets S containing neither i nor j and with cardinality s, such that S ∪ {i} is weakly preferred to A, i.e. P s ij ( , A) = {S ∈ Σ s ij : S ∪ {i} A}. Moreover, given a set T ∈ 2 N such that there exists B with T B, we shall denote by T σ an element of 2 N such that T T σ and there is no C such that T C T σ . Definition 3. A total preorder on 2 N is called dichotomous if there is a partition of 2 N in two indifference classes, say G and B, such that each element in G is strictly preferred to each element in B.

Given a total preorder on 2 N , for each T ∈ 2 N we denote by T the dichotomous total preorder on 2 N such that G = {S ∈ 2 N : S T }. We shall say that T is a dichotomous total preorder associated to on T fore each T ∈ 2 N .

We prove now a proposition establishing how a total preorder over 2 N may be decomposed in several dichotomous total preorders. Proposition 1. Let be a total preorder on 2 N and let v ∈ V ( ). For each

T ∈ 2 N \ {∅}, consider the game v * T such that for each S ∈ 2 N if T ∅, v * T (S) = v(T ) -v(T σ ) if S T, 0 otherwise (13) if ∅ T, v * T (S) = v(T σ ) -v(T ) if T S, 0 otherwise. ( 14
)
Then, v * T induces the dichotomous total preorder T associated to on T for every T ∈ 2 N and

v = T ∈2 N 1 n T v * T
where n T is the number of elements B indifferent to T in the order .

Proof. The fact that v * T is dichotomous is obvious by definition. So what we need to prove is that for every C ⊆ N the following equality holds:

v(C) = T ∈2 N 1 n T v * T (C).
Let us write the ordering given by in the following fashion:

[S 1 ] [S 2 ] • • • [S i ] • • • [S k ] [∅] [W 1 ] • • • [W j ],
where

v(C) = T ∈2 N 1 n T v * T (C) = T :C T ∅ 1 n T (v(T ) -v(T σ )) = = (v(C) -v(S i+1 )) + (v(S i+1 ) -v(S i+2 )) + • • • + (v(S k ) -v(∅)) = v(C).
The case when ∅ C is handled in the same way.

To clarify the above proposition we now provide a simple example.

Example 2. Let N = {1, 2, 3} and let by the total preorder on 2 N such that

{1, 2, 3} ∼ {2} {3} {1, 3} ∼ {2, 3} ∅ {1} {1, 2}. Consider the following representation v ∈ V ( ): v({1, 2, 3}) = v({2}) = 7, v({3}) = 5, v({1, 3}) = v({2, 3}) = 3, v(∅) = 0, v({1}) = -2, v({1, 2}) = -5.

The functions v *

T are displayed in Table 2. Now, we focus on the class of dichotomous total preorders to show a nice property of π p -aligned extensions in this class.

Proposition 2. Let be a dichotomous preorder and let π p be a semivalue S. Then is π p -aligned if and only if for all i, j ∈ N and all

A ∈ 2 N {i} {j} ⇒ n-2 s=0 x s+1 |P s ij ( , A)| -|P s ji ( , A)| ≥ 0 ( 15
)
where |A| denotes the cardinality of the set A and with the usual notation x s+1 = p s + p s+1 for each s ∈ {0, 1, . . . , n -2}.

Table 1: A decomposition of the game defined in Example 2 by v * T functions. Note that every function v * T ∈ V ( T ), where T is the dichotomous total prorder associated to on

T ∈ 2 N . {1, 2} {1} ∅ {2, 3} {1, 3} {3} {2} {1, 2, 3} v * {1,2} 0 0 0 0 0 0 0 0 v * {1} -3 0 0 0 0 0 0 0 v * ∅ -2 -2 0 0 0 0 0 0 v * {2,3} 0 0 0 3 3 3 3 3 v * {1,3} 0 0 0 3 3 3 3 3 v * {3} 0 0 0 0 0 2 2 2 v * {2} 0 0 0 0 0 0 2 2 v * {1,2,3} 0 0 0 0 0 0 2 2 v = T ∈2 N 1 n T v * T -5 -2 0 3 3 5 7 7
Proof. The if part. Fix A ∈ G and suppose ∅ ∈ B (the proof of the case ∅ ∈ G is analogous). Set α > 0 to be α = v(G) for each G ∈ G.

π p i (v) -π p j (v) = n-2 s=0 x s+1 S∈Σ s ij v(S ∪ {i}) -S∈Σ s ij v(S ∪ {j}) = α n-2 s=0 x s+1 S∈Σ s ij :S∪{i}∈G 1 -S∈Σ s ij :S∪{j}∈G 1 = = α n-2 s=0 x s+1 (|P s ij ( , A)| -|P s ji ( , A)|) . (16)
For the only if part, we need only to consider two cases: either when A ∈ G or when A ∈ B. But in the first case the above calculation holds, while if A ∈ B the inequality is an obvious equality.

In order to put in relation the set P s ji ( , A) for a total preorder on 2 N with the corresponding sets in the associated dichotomous total preorders, we need the following.

Lemma 1. Let be a total preorder on 2 N and let x ∈ R n-1 + . Then, for every i, j ∈ N and every A ∈ 2 N , we have that

n-2 s=0 x s+1 (|P s ij ( T , A)| -|P s ji ( T , A)|) = n-2 s=0 x s+1 (|P s ij ( , A)| -|P s ji ( , A)|) (17
) for every T ∈ 2 N such that A T T (where T is the dichotomous preorder associated to on T ).

Proof. The proof follows immediately from the fact that for every set A ∈ 2 N and for all s = 0, . . . , n -2 the following equality holds

|P s ij ( T , A)| = |P s ij ( , A)| (18)
for every set T ∈ 2 N such that A T T .

Proposition 3. Let be a total preorder on 2 N and let x ∈ R n-1 + . Then, for each i, j ∈ N and every

A, T ∈ 2 N n-2 s=0 x s+1 |P s ij ( , A)| -|P s ji ( , A)| ≥ 0 ⇔ n-2 s=0 x s+1 |P s ij ( T , A)| -|P s ji ( T , A)| ≥ 0. ( 19
)
Proof. (⇒) First, note that for every A ∈ 2 N such that T T A we have that

|P s ij (A)| = |P s ji (A)| = 2 |N |-1
(since all sets of 2 N are weakly preferred to A w.r.t. T ). So,

n-2 s=0 x s+1 |P s ij ( T , A)| -|P s ji ( T , A)| = 0
for every dichotomous preorder T with T T A. Second, for every set A T T , the inequality on the right in relation ( 19) follows by Lemma 1. (⇐) For every A ∈ 2 N , the implication follows immediately by Lemma 1 considering the dichotomous preorder A associated to . Now we can prove the main result of this section.

Theorem 3. Let be a total preorder on 2 N . Then is π p -aligned for a given semivalue π p if and only if for all i, j ∈ N and all

A ∈ 2 N n-2 s=0 x s+1 |P s ij ( , A)| -|P s ji ( , A)| ≥ 0 ⇔ {i} {j}. ( 20
)
Proof. Suppose first that (20) holds. Then by Proposition 3, also every T fulfills [START_REF] Moretti | Ranking sets of possibly interacting objects using shapley extensions[END_REF], and, by Proposition 2, each T is π p -aligned. Now, using Proposition 1 and the additivity of the semivalues, we have that

π p i (v) = T ∈2 N π p i (v * T ) ≥ T ∈2 N π p j (v * T ) = π p j (v), (21)
for every v ∈ V ( ); this proves that is is π p -aligned. Now we prove the opposite implication. Let be π p -aligned and take i, j ∈ N such that {i} {j}. First, we prove that this implies

π p i (v * T ) ≥ π p j (v * T ) ( 22
)
for all v * T ∈ V ( T ). Suppose by contradiction that there exists some T ⊂ N and some

v * T ∈ V ( T ) such that π p j (v * T ) -π p i (v * T ) = 7α, with α > 0. It is easy to construct a function v representing such that ||v * T -v|| ∞ < α.
Since for every semivalue π p the map π p : R 2 n -1 → R N , is 2-Lipschitz (endowing both spaces with || • || ∞ ), then it is easily seen that π p j (v) -π p i (v) > α, which yields a contradiction with the π p -alignment of .

Then, we have proved that relation [START_REF] Owen | Game Theory[END_REF] holds for all v * T and, by Proposition 2, we have that

n-2 s=0 x s+1 |P s ij ( T , A)| -|P s ji ( T , A)| ≥ 0
for every dichotomous total preorder T associated to on T ∈ 2 N . This concludes the proof in view of Proposition 3.

Theorem 3 shows that in order to verify that an extension is π p -aligned with some semivalue π p , one can compare, for each pair of objects i and j and every subset S of N , the respective number of times that i and j are contained in sets which are (weakly) preferred to S according to . Notice that in such a comparison, characteristic functions v ∈ V ( ) do not play any role, and only the probability distribution p is considered.

A faster algorithm to check π p -alignment

In this section we want to produce another condition equivalent to π p -alignment, for a fixed semivalue π p . Differently from that one given in the previous section, it does not apply to all semivalues, but to the large class of semivalues such that the quantities x s+1 = p s + p s+1 are rational. This clearly suffices for practical purposes. On the other hand, the condition provided here is much more easily handleable w.r.t. the one provided in Theorem 3. We remind that it is possible to substitute, in all inequalities, the quantity x s+1 , for s = 1, . . . , n -1, with ax s+1 , for any a > 0. Thus, to simplify notations, we shall always assume, in this section, that the quantities x s+1 are actually natural numbers. In order to introduce our condition, we need a bit more of notation.

Let us then fix a preference relation on 2 N , suppose π p is a given semivalue and fix the associated natural number x 1 , . . . , x n-1 . For a given i ∈ N and a subfamily F of 2 N , we write θ p (F, i) for the vector constructed in the following way. Order in decreasing order of preference the sets S ∪ {i}, where S ∈ F:

S 1 ∪ {i} S 2 ∪ {i} • • • S l ∪ {i} . . . , then replicate each coalition S k x s k times, if |S k | = s k ,

and form the vector

θ p (F, i) = (S 1 ∪ {i}, . . . , S 1 ∪ {i} xs 1 times , S 2 ∪ {i}, . . . , S 2 ∪ {i} xs 2 times , . . . ). Example 3. Let N = {1, 2, 3}, let N {1} {2, 3} {1, 3} {2} {1, 2} {3} ∅.
Let F = Σ 12 = {∅, {3}}. Let p be the semivalue with x = (1, 1, 2). Then θ p (Σ 12 , 1) = ({1}, {1}, {1, 3}, {1, 3}, {1, 3}) and

θ p (Σ 12 , 2) = ({2, 3}, {2, 3}, {2, 3}, {2}, {2}).
With a little abuse of notation, we shall write

θ p (Σ ij , i) θ p (Σ ij , j) if (θ p (Σ ij , i)) k (θ p (Σ ij , j)) k , ∀k ∈ {1, . . . , n-2 s=0 n -2 s x s+1 }
and we define a relation p over N such that {i} p {j} :⇔ θ p (Σ ij , i) θ p (Σ ij , j). It is clear that p induces a partial order on the set of singletons in N .

Definition 4 (p-WPR). We say that the total preorder on 2 N satisfies the p-weighted permutational responsiveness (p-WPR) property if for each i, j ∈ N we have that {i} {j} ⇔ i p j.

In other words, a total preorder on 2 N has the p-WPR property provided the partial order defined by actually coincides with the original total preorder on N . The easiest case is when

x i = 1 for i = 1, • • • = n -1,
which corresponds to the case where the Banzhaf semivalue is considered.

It is easy to check that the p-WPR property directly implies condition (20): if a total preorder on 2 N satisfies the p-WPR property, and i p j, then the number of coalitions S in θ p (Σ ij , i) with S A is not smaller than the number of coalitions T in θ p (Σ ij , j) with T A, for each coalition A ∈ 2 N . The converse follows from Theorem 3 and the following Theorem 4, whose proof requires Lemma 2.

Lemma 2. Let x 1 ≥ x 2 ≥ • • • ≥ x l and y 1 ≥ y 2 ≥ • • • ≥ y l be real numbers such that l r=1 f (x r ) -f (y r ) ≥ 0
for every strictly increasing function f : R → R. Then x r ≥ y r for all r ∈ {1, . . . , l}.

Proof. Suppose not. Take the first index h such that y h -x h > 0, and suppose, w.l.o.g. y h -x h = 1. Consider any strictly increasing continuous function f : R → R such that:

f (m) = 0, f (x h ) = 1 2l , f (t) = t + 1 2l -x h , t ∈ [x h , y h ],
where m = min{x l , y l } and

lim t→∞ f (t) = y h -x h + 1 l .
Notice that, for every r = 1, . . . , l, with r = h, such that x r ≥ y r , we have that f (x r ) -f (y r ) < 1 l (precisely, if r ≤ h, then we always have that x r ≥ y r ). Then, we have the following contradiction

l r=1 (f (x r ) -f (y r )) = h-1 r=1 (f (x r ) -f (y r )) + (f (x h ) -f (y h )) + l r=h+1 (f (x r ) -f (y r )) ≤ h-1 r=1 (f (x r ) -f (y r )) + (x h -y h ) + l≥r≥h:yr≤xr (f (x r ) -f (y r )) ≤ (h -1) 1 l -1 + (l -h) 1 l = l-1 l -1 < 0.
We are ready to state and prove the main result of the section.

Theorem 4. Let be a total preorder on 2 N and let π p be a semivalue with rational probabilities. The following two statements are equivalent:

1)
is π p -aligned;

2) satisfies the p-WPR property.

Proof. Take two elements i, j ∈ N . For a function v ∈ V ( ) representing the order , we have that

π p i (v) -π p j (v) = n-2 s=0 x s+1 S∈Σ s ij v(S ∪ {i}) -S∈Σ s ij v(S ∪ {j}) = l k=1 v(θ p (Σ s ij , i) k ) -v(θ p (Σ s ij , j) k ), (24)
where the second equality is obtained by rearranging terms in the sum, and l = n-2 s=0 x s+1 n-2 s . Now suppose {i} {j}. Equation [START_REF] Roth | The college admissions problem is not equivalent to the marriage problem[END_REF] shows that the p-WPR property implies π p i (v)-π p j (v) ≥ 0 for all v representing V ( ), i.e. the p-WPR property implies that is π p -aligned.

To see that the p-WPR property is also necessary to have is π p -aligned, it is enough to fix a v ∈ V ( ) and to notice that every transformation of v by a strictly increasing function f : R → R is still an element of V ( ). Then, if is π p -aligned, by equation [START_REF] Roth | The college admissions problem is not equivalent to the marriage problem[END_REF] we have that

l k=1 f (v(θ p (Σ s ij , i) k )) -f (v(θ p (Σ s ij , j) k )) ≥ 0, (25)
for every strictly increasing real-valued function f . The proof is concluded by relation [START_REF] Shapley | A value for n-person games[END_REF] and using Lemma 2 with v(θ p (Σ s ij , i) k ) and v(θ p (Σ s ij , j) k ) in the role of x r and y r , respectively. Remark 1. Given a total preorder on 2 N that satisfies the p-WPR property, an alternative way to prove Theorem 4 is by noticing that relation [START_REF] Roth | The college admissions problem is not equivalent to the marriage problem[END_REF] implies that, for each v ∈ V ( ) and for each i, j ∈ N such that {i} {j}, the gamble I = (v(S ∪ {i}); x |S|+1 ) S∈Σij first-order stochastically dominates (FSD) ( [START_REF] Hadar | Rules for ordering uncertain prospects[END_REF]; see also the book [START_REF] Mas-Colell | Microeconomic theory[END_REF]) the gamble J = (v(S∪{j}); x |S|+1 ) S∈Σij , which means that the cumulative distribution function (cdf ) F I (w) = S∈Σij :v(S∪{i})≤w x |S|+1 is smaller or equal to the cdf F J (w) = S∈Σij :v(S∪{j})≤w x |S|+1 , for each w ∈ R.

It is a well known fact the a gamble I first-order stochastically dominates J if and only if the expected value E I (u(v)) of gamble I is larger or equal than the expected value E J (u(v)) of gamble J for all increasing functions u. Since u(v) is still an element of V ( ) and, obviously,

E I (u(v)) = π p i (u(v)) and E J (u(v)) = π p j (u(v)
), the statement of Theorem 4 follows.

π p -alignment with all semivalues

In this section we want to characterize those total preorders on 2 N that are π p -aligned for all semivalues π p ∈ S. In the literature it is possible to find some sufficient condition, no one of them being necessary. For example, the RESP property, introduced in Section 2 and further discussed in Section 3, is a sufficient condition for a total preorder to be π p -aligned with all regular semivalues [START_REF] Moretti | Ranking sets of possibly interacting objects using shapley extensions[END_REF]. Another condition, known in literature as permutational responsiveness (PR) [START_REF] Moretti | Ranking sets of possibly interacting objects using shapley extensions[END_REF], generalizes the notion of RESP property and also guarantees the alignment of a total preorder with any semivalue. To define it, for a given subfamily F of 2 N , we use the notation of the previous section, denoting by θ(F, i) the vector θ p (F, i) when p = (1, . . . , 1), that is each coalition S ∈ F is replicated in θ(F, i) precisely once. Definition 5 (PR). We say that a total preorder on 2 N satisfies the permutational responsiveness (PR) property if for each i, j ∈ N we have that

{i} {j} ⇔ θ(Σ s ij , i) k θ(Σ s ij , j) k ( 26
)
for every k = 1, . . . , |Σ s ij | and every s = 0, . . . , n -2.

One more time we see that the condition θ(Σ s ij , i) k θ(Σ s ij , j) k for every k = 1, . . . , |Σ s ij | and every s = 0, . . . , n -2, induces a partial order on the elements of N , and the PR condition, analogously to the p-WPR given in the previous section, requires that this partial order actually coincides with the total preorder on the singletons.

In other terms, for each i, j ∈ N such that {i} {j} and for each s = 0, . . . , n -2, the PR property admits the possibility of relative rankings which violate the conditions imposed by the RESP property (i.e., S ∪ {j} is preferred to S ∪ {i}) due to the effect of mutual interaction within the objects in S. Nevertheless, such an interaction should be compatible with the requirement that, between sets of the same cardinality, the original relative ranking between {i} and {j} should be preserved with respect to the position of subsets in Σ s ij and Σ s ji , when they are arranged in descending order of preference (i.e., the most preferred subsets in Σ s ij should be preferred to the most preferred subsets in Σ s ji , the second most preferred subsets in Σ k ij should be preferred to the second most preferred subsets in Σ k ji , etc.).

In the context of the introductory example of "choosing the wine for a dinner", the PR property says that comparing meals of the same size (cardinality), and assuming they have the same probability to realize (like we do assume, using semivalues), even if the meal 'fish and white wine' is the top meal among the ones served with white wine, and it is preferred to 'fish and red wine', then the choice to bring at dinner 'red wine' instead of 'white wine' should be a consequence of the fact that the top meal among the one served with 'red wine' (e.g., 'beef and red wine') is in turn preferred to 'fish and white wine'.

In [START_REF] Moretti | Ranking sets of possibly interacting objects using shapley extensions[END_REF] it is shown that the PR condition is sufficient to guarantee that a total preorder is aligned with all semivalues. The following example, instead, displays a total preorder on 2 {1,2,3,4} which is π p -aligned for all π p ∈ S and that does not satisfy the PR property.

Example 4. Let X = {1, 2, 3, 4} and let be a total preorder such that

{1, 2, 3, 4} {2, 3, 4} {3, 4} {4} {3} {2} {2, 4} {1, 4} {1, 3} {2, 3} {1, 3, 4} {1, 2, 4} {1, 2, 3} {1, 2} {1} ∅.
Note that does not satisfy PR because {2} {1}, {2, 4} is strictly preferred to {1, 4} and {1, 3} is strictly preferred to {2, 3}. However, is π p -aligned for all semivalues π p ∈ S (see the Appendix for the details of the proof ).

We are ready to introduce the property that we shall show to be necessary and sufficient for the alignment of the preorder to all semivalues. One more time we introduce a partial order on N , and the condition will require that it coincides with the initial total preorder.

For every i, j ∈ N , we set D s ij to be the set D s ij = Σ s ij ∪ Σ s+1 ij for s = 0, . . . , n -3. With a little abuse of notation, set D n-2 ij = Σ n-1 ij . Definition 6 (DPR). We say that a total preorder on 2 N satisfies the double permutational responsiveness (DPR) property if for each i, j ∈ N we have that

{i} {j} ⇔ θ(D s ij , i) k θ(D s ij , j) k (27)
for every l = 1, . . . , |D s ij | and every s = 0, . . . , n -2. We are ready to prove the main theorem of this section.

Theorem 5. Let be a total preorder on 2 N and let π p be a semivalue. The following statements are equivalent: 1) fulfills the DPR property;

2) is π p -aligned for all semivalues.

Proof. It is clear that 2) can be equivalently expressed by saying that is π paligned when p ranges on the extreme points of the simplex of the semivalues. Now observe that for the extreme semivalue (0, . . . , 1, . . . , 0), where 1 is at the s-th place, it can be set x i = 0 for i = s, i = s + 1, while x s = x s+1 = 1.

Observing that to be aligned with (0, . . . , 1) is equivalent to

{i} {j} ⇒ θ(D n-1 ij , i) θ(D n-1 ij , j) the thesis is a consequence of Theorem 4.
We conclude with the following observation. In [START_REF] Freixas | On ordinal equivalence of the shapley and banzhaf values for cooperative games[END_REF], a game v is defined weakly complete provided the relation i ≥ j ⇒ c i (s) ≥ c j (s) (28)

for every s = 0, . . . , n -1 provides a total preorder on the set N (c i (s), c j (s) were defined in Equation ( 7)). Then one important result of [START_REF] Freixas | On ordinal equivalence of the shapley and banzhaf values for cooperative games[END_REF] is that for a game to be weakly complete is equivalent to the fact that all semivalues provide the same ranking on the elements of N . Our result shows in particular that for a total preorder fulfilling DPR every numerical representation by a utility function (with v(∅) = 0) generates a weakly complete game. However it is possible that a given game is weakly complete without the underlying preorder fulfilling DPR. In such a case another utility function representing the same preorder will not be weakly complete. A simple example is the following game with N = {1, 2, 3, 4}. It is easy to see that the game v is weakly complete but the total preorder on 2 N such that S T ⇔ v(S) ≥ v(T ), for each S, T ∈ 2 N , does not satisfy the DPR property (to check this, it is sufficient to make the comparison between objects 1 and 2).

Conclusions

In this paper, the idea of alignment with a semivalue was developed in order to have meaningful extensions of a total preorder on a finite set N , to the set of its subsets, and keeping into account the possibility that objects within each subset may interact. Specifically, the fact that an extension must be aligned with a semivalue means that the ranking of the objects according to the semivalue must be the same and must preserve the primitive total preorder on the singletons, no matter which utility function is used to describe the preorder. In the most favourable situation it remains the same for the whole simplex of the semivalues (if and only if the total preorder on 2 N fulfills the DPR property).

We want also to stress the fact that one can think of the possibility to do a kind a inverse process: from a ranking on the power set of a given set of objects how to derive a ranking on the objects, that will take into account the interactions, and thus not necessarily preserving the ranking restricted to the singletons. Again, this makes sense in the setting of considering interactions between objects: as a striking example we can think that any reasonable ranking of top soccer players will never give a good team just by taking the first 11 of the list! In this case one can consider as nice the total preorders that are aligned (according to a semivalue), in the sense that the final ranking on the objects will not depend from the utility function used to represent the preorder . However the analysis of ordinality, which presents analogies but also some meaningful differences, will be pursued on a subsequent paper.

where the inequality follows from the fact that v(2, 4) -v(1, 4) > 0 for every semivalue π p and every v ∈ V ( ). Note that, due to the relative ranking of coalitions, we have that

where the strict inequality follows from relations (30) and (31). By relation (29), it immediately follows that π p 2 (v) -π p 1 (v) > 0 for every semivalue π p and every v ∈ V ( ).

In a similar way, for every semivalue π p and every v ∈ V ( ), we have immediately that Of course one can verify as well that the preorder fulfills the DPR property.

π p 3 (v) -π p 2 (v) = (p 0 + p 1 ) v(3) -v(2) + (p 1 + p 2 ) v(1,

  [O] represents the indifference class containing the set O. Now suppose C ∅, and C ∈ [S i ]. Then

  v({1, 4}) = 100, v({1}) = 4, v({2, 3}) = 3, v({2, 4}) = 2, v({2}) = 1, v({4}) = -1, v({A}) = 0 otherwise.

v( 2 )

 2 -v(1) > v(1, 3) -v(2, 3), (30) and v(2, 3, 4) -v(1, 3, 4) > v(1, 3) -v(2, 3). (31)Moreover, we have that(p 0 + p 1 ) v(2) -v(1) + (p 2 + p 3 ) v(2, 3, 4) -v(1, 3, 4) ≥ (p 0 + p 1 + p 2 + p 3 ) min{[v(2) -v(1)], [v(2, 3, 4) -v(1, 3, 4)]} ≥ (p 1 + p 2 ) min{[v(2) -v(1)], [v(2, 3, 4) -v(1, 3, 4)]} > (p 1 + p 2 ) v(1, 3) -v(2, 3) ,

3 )

 3 -v(1, 2) + (p 1 + p 2 ) v(3, 4) -v(2, 4) + (p 2 + p 3 ) v(1, 3, 4) -v(1, 2, 4) > 0. ) -π p 3 (v) = (p 0 + p 1 ) v(4) -v(3) + (p 1 + p 2 ) v(1, 4) -v(1, 3) + (p 1 + p 2 ) v(2, 4) -v(2, 3) + (p 2 + p 3 ) v(1, 2, 4) -v(1, 2, 3) = (p 0 + p 1 ) v(4) -v(3) + (p 1 + p 2 ) v(2, 4) -v(2, 3) + (p 2 + p 3 ) v(1, 2, 4) -v(1, 2, 3) > 0.(34)

We shall use the notation π q i (v) also for any 0 ≤ q = (q 0 , . . . , q n-1 ).

Appendix

We provide the details of the calculations proving that the relation of Example 4 is π p -aligned with all semivalues π p ∈ S.

Take a semivalue π p ∈ S, for some collection of probability distribution p, and consider a numerical representation v ∈ V ( ). We have that


Miguel Mujica Mota

Catya Zuniga
email: catya.zuniga@recherche.enac.fr

A Simulation-Evolutionary Approach for the allocation of Check-In Desks in Airport Terminals

Keywords: Simulation, Heuristics, Terminal, Check-In, Evolutionary Algorithms

The aeronautical industry is still under expansion in spite of the problems it is facing due to the increase in oil prices, limited capacity, and novel regulations. The expansion trends translate into problems at different locations within an airport system and are more evident when the resources to cope with the demand are limited or are reaching to theirs limits. In the check-in areas they are appreciated as excessive waiting times which in turn are appreciated by the customers as bad service levels. The article presents a methodology that combines evolutionary algorithms and simulation in order to give the best results taking into account not only the mandatory hard and soft rules determined by the internal policies of a terminal but also the quality indicators which are very difficult to include using an abstract representation. The methodology uses an evolutionary algorithm to satisfy the different mandatory restrictions such as minimum and maximum number of check-in desks per flight, load balance in the check-in islands, opening times of check-in desks and other restrictions imposed by the level of service agreement. Once the solutions are obtained, they are evaluated using a simulation model of the terminal that takes into account other aspects of the problem such as arriving profiles of the passengers, the opening times and the physical configurations of the facility under study with the objective to determine which allocation is the most efficient in real situations in order to maintain the quality indicators at the desired level

Introduction

The aeronautical industry is still under expansion in spite of the problems it is facing due to the increase in oil prices, limited capacity, and novel regulations. The expansion trends translate into problems at different locations within an airport system and are more evident when the resources to cope with the demand become scarce. In the airfield these problems appear as queues in the runways with the corresponding delays; inside the terminals they are appreciated as huge queues in the security filters and in the check-in counters as excessive waiting times which in turn are appreciated by the customers as bad service levels. The planning departments of the airports are concerned about these problems and they are currently looking for better ways to manage the scarce resources while the traffic and number of passengers are also increasing. The traditional way of facing such problems has been just the expansion of the terminal facilities and the increase of resources at hand (i.e. addition of more counters, security filters or even runways). In the particular case of the Terminals, the decision makers that manage these systems need to allocate the increasing traffic using the current resources taking into account not only the limitations such as budget, limited areas for expansion, availability of resources but also the ones imposed by the internal policies which take into account metrics that are associated to the satisfaction of the customers. These metrics which are commonly called as Level of Service indicators (LOS) measure some characteristics associated with the comfort inside the terminal such as available area per passenger or the speed at which the passenger can travel inside the terminal. Table 1 illustrates some of the typical values used by airports to evaluate their level of comfort inside terminal areas [START_REF] Neufville | Airport systems -planning, design and management[END_REF].

Table 1.Typical Values for Level of Service Indicators

Due to the current situation, the operations research techniques appear as the ones that are able to tackle the aeronautical problems in the most efficient way taking into account all the different restrictions of a problem. Furthermore when these techniques are applied using a proper cost function they can generate solutions that not only satisfy the current restrictions but also give solutions with high potential of improving the current performances.

The use of optimization techniques are able to give optimal or close-to-theoptimal solutions to problems that are deterministic in nature; on the other hand simulation approaches have the advantages that they are able to describe the studied systems under different abstraction levels and can also consider the stochastic nature of the processes that participate in the system under study. Unfortunately when simulation is used as a decision support tool it presents the disadvantage that it only explores a small subset of the whole possible scenarios that can be reached by the system under study thus reducing its optimization potential.

The article presents a methodology that combines the two approaches in order to give the best results for a common in an abstract representation. The methodology uses in the first phase of the approach an evolutionary algorithm in order to satisfy the measurable restrictions such as minimum and maximum number of check-in desks per flight, load balance in the check-in islands, opening times of check-in desks and other restrictions imposed by the LOS. The solutions are then encoded as chromosomes and then the typical operations of an evolutionary algorithm are performed in order to obtain the best promising solutions using a particular cost function. Once the solutions are obtained, they are tested using a simulation model of the terminal that takes into account not only the arriving profiles of the passengers but also the opening times, physical configurations of the facility under study and the interactions between passengers when they flow inside the terminal. These elements are used to determine which allocation is the most quality-efficient in a close-to-real scenario in order to maintain the LOS indicators in the desired level. The proposed implementation has been developed using information of a real terminal but it can be easily adapted to another one with different restrictions imposed by the correspondent LOS agreements.

1.

A combined Approach: Evolutionary algorithms and simulation

Evolutionary Approach

The evolutionary approach is a method inspired by common evolutionary processes found in nature [START_REF] Goldberg | Genetic Algorithms in Search, Optimization, and Machine learning[END_REF].

The general idea behind an evolutionary algorithm is the representation of a solution in the form of a vector of decision variables.

Let us assume that we have a discrete search space and a function

The general problem is to find: min Here x is a vector of decision variables, and is the objective function. Such a problem is commonly called discrete or combinatorial optimization problems [START_REF] Reeves | Genetic Algorithms[END_REF].

The idea of an evolutionary algorithm is to represent the actual decision variables of the original problem into a different form which has correspondence with the original ones. In line with biological usage of the terms, it has become customary to distinguish the 'genotype'-the encoded representation of the variables, from the 'phenotype'-the set of variables themselves.

In the general evolutionary problem the representation is one of the main challenging procedures of the approach. Since most of the representations are not bijections of the original problem some of the obtained solutions are not feasible when they are implemented using the original variables.

Simulation

Simulation is the imitation of the operation of a real system or process over time. Simulation is used to generate artificial history and data of a system, and the observation of that artificial history to draw inferences concerning the operating characteristics of the real system [START_REF] Banks | Discrete Event System Simulation[END_REF].

The behaviour of a system as it evolves over time is studied by developing a simulation model. This model usually takes the form of a set of assumptions concerning the operation of the system. These assumptions are expressed in mathematical, logical, and symbolic relationships between the entities, or objects of interest, of the system. Once developed and validated, a model can be used to investigate a wide variety of "what-if" questions about the real-world system. Potential changes to the system can be simulated in order to predict their impact on system performance. Simulation can also be used to study systems in the design stage, before such systems are built. Thus, simulation modelling can be used both as an analysis tool for predicting the effect of changes to existing systems, and as a design tool to predict the performance of new systems under varying sets of circumstances. Nowadays and with the evolution of computer capacities, computer simulation is also able to develop very accurate models and graphically appealing that can represent a system under different abstraction levels depending on the objective of the study. In order to analyse the performance of systems is necessary to execute several experiments with the simulation model in order to have insight about the behaviour of the system under study.

Unfortunately the main limitation of this approach is that when it is used as a decision support tool it cannot ensure the best outcome since the experiments only explore a subset of the whole different configurations of the system under study. Thus the decision making supported in the simulation experiments always has a certain level of uncertainty which can be minimized when the simulation methodology is applied correctly.

The Check-In Allocation Problem

The inefficient management of resources at hand (ground services, personnel, desks, filters, etc.) are appreciated as congestions in terminals. The congestion can be appreciated in several points throughout the passenger-boarding process; for example in the check-in desks, the security filters, passport control and sometimes on the boarding gate. These problems have been traditionally faced by the aviation industry through the increase of physical resources (e.g. increase in the check-in desks, increase in the number of security filters etc.). Furthermore the increase in competition between airlines has forced them to optimize their resources at hand in order to reduce their costs and keep competitive.

The general check-in allocation problem consists in allocating the available desks of a terminal in such a way that the allocation satisfies a series of restrictions imposed by the airport and the companies through a service contract. These restrictions may change depending on the airport, the airlines, the region it serves and the type of terminal [START_REF] Kasda | Airport Design and Operation[END_REF].

The check-in allocation problem is a very-well known problem in airport terminals and has been studied by some authors using also evolutionary approaches or mathematical formulations [START_REF] Bruno | A Mathematical Model for the Optimization of the Airport Check-In Service Problem[END_REF][9] [START_REF] Hsu | Dynamic allocation of check-in facilities and dynamic assignment of passengers at air terminals[END_REF]. These approaches have the drawbacks that do not take into account all the different elements present in the check-in area of the terminal or the interactions between passengers inside the terminal or with other elements of the facility. On the other hand the increase of passenger traffic in airports makes necessary the developing of novel decision support tools that take into consideration all the different elements that are part of the area under study and not only an abstract representation of it.

Furthermore the traffic increase caused mainly by the competition between airlines to market liberalization and the increasing number of low-cost airlines will force the need of an efficient allocation of check-in desks inside terminals if the LOS are to be maintained.

The study presented in this paper deals with the problem of performing the checkin allocation desks in a terminal taking into account not only the internal policies and quality indicators but also the interactions between passengers and the physical facilities of a terminal. The different rules and information data have been provided by a terminal in the Middle East under a confidentiality agreement. We shall refer to this airport, when applicable, as "the airport".

Description of the Problem

The problem consists of performing the check-in desks allocation satisfying a series of hard and soft rules. The hard rules are the ones that must be satisfied by the approach and the soft rules are the ones that are desirable to be satisfied but can be violated when there is no other available option. a) Hard Rules Overlap Verification: The current allocation will be aligned always with the allocation of the previous month in order to avoid having allocated the same check-in desks or near-by for the last flights of the previous month and for the first flights of the current month.

Balanced Loads: Allocating flights to check-in counters will consider an aspirational usage of 20% for each of areas A, B, C, D and E. The acceptable deviance is 1% on daily basis and 5% on each 2-hours window. Fig. 1 illustrates the different zones of the terminal.

Number of Desks: Allocating flights to check-in counters will consider a minimum standard of one check-in counter per 45 passengers. Optimized Queuing / Circulation Areas for any flights: The allocation will avoid placing 2 flights on consecutive counters at any given one-hour window. The recommended practice is to leave at least one counter free between two flightsfor redundancy and flexibility purposes.

Airline Preferences: Airline preferences for allocation of their flights to specific rows or fixed desks will be collected officially during meetings and the solution will consider their requests, only after complying with all the allocation rules.

Methodology

The methodology proposed to give solution to this problem is a combination of an evolutionary algorithm and simulation in order to include as much as possible the constraints imposed by the airport and the requirements of the airlines. The simulation environment allows to evaluate the interaction between elements that otherwise could not been included in the model such as passenger-passenger interactions, pax speeds etc.

Fig. 3 presents the diagram that illustrates the different steps in the methodology.

The first approach of the methodology takes into account only some of the aforementioned hard and soft rules, namely:

-Overlap of Flights -Counters are opened 3 hours in advance -It calculates the number of counters needed in a base of 45 pax/counter -It leaves a check-in desk in between flights -The flights are allocated in the correspondent sections of the check-in area so that the luggage does not end in a different luggage hall -It allocates the check-in desks in a random way trying to distribute the flights uniformly (load balance) Taking into account these constraints an initial set of solutions is generated following a set of allocation rules.

The initial solutions are obtained through an allocation algorithm approach providing only feasible solutions which do not take into account any cost function.

The restrictions are satisfied using the following rules:

-An empty check-in desk is left between flights -The number of check-in desks needed are calculated dividing the number of pax by 45 and limiting up to 5 check-in desks per flight -There is no overlapping between flights -The check-in desks are opened 3 hours-prior to departure Once the initial solutions are generated the next challenging task is the transformation of the solutions into vectors with the information that will be used by the evolutionary algorithm.

1) Chromosome Encoding

The following information composes the chromosomes of the evolutionary algorithm:

2) Crossover

Since the opening time and closing time cannot be changed, the numbers of desks are the ones that can be used by the algorithm to provide new solutions.

In this approach the crossover will be performed in two points of the solutions. The initial and final Check-In desks will be used as the crossover points for generating new potential solutions.

3) Feasibility Testing

There will be a couple of tests performed by the algorithm in order to evaluate the feasibility of the solutions. The first feasibility test will be performed once the crossover has been performed; this test is performed in the following way. It will evaluate if the allocation does not violate the hard rules (field #7). If the new solution does not violate the hard rules it will be kept as a feasible check-in desk allocation.

The crossover is performed in a random way varying the number of crossovers of the new solution.

4) Cost Function Evaluation

Once several feasible solutions are obtained the cost function F(v1,v2,v3,v4) is evaluated where, v1: number of flights that do not respect the 1 check-in desk in between flights v2: balance loads for the solution in accordance with the policies imposed by the airport v3: number of heavy flights in the same island during 1-hour window v4: distribution of flights in the islands

The exact values of the function have been kept confidential due to the aforementioned non-disclosure agreement with the airport.

The whole evolutionary process is performed using the values of the function to calculate the goodness-of-fit of the different allocations and the selection process is carried out based on those values.

The most promising solutions are then selected and the process starts all over again until certain number of iterations is reached (stop criteria).

5) Final Evaluation

The best solution is selected for the final evaluation in the simulated environment of the check-in area of the correspondent terminal. This evaluation will provide a better estimation of the quality levels that can be achieved in the real system.

It is important to mention that certain requirements are needed for the simulator in order to have the best evaluation of the quality indicators, that is:

-agent-based -high-description level -It must allow interaction agent-agent, agent-objects -Independent behaviour for each of the simulated entities There are some simulators in the market that satisfy these requirements [START_REF] Swain | Software survey: Simulation-Back to the future[END_REF] thus the methodology can be implemented making use of the one that suits best the objective of the study. The use of the simulated scenario allows testing the potential best solutions in a close-to-real environment. Sometimes occur that solutions do not perform well in the real system once they are implemented. The latter could be caused by some obstacles present in the facilities (e.g. big columns, trolley stations, etc.) that cause that a potential good solution is not because congestion has been generated due to the interaction pax-pax or pax-object.

Case Study

The methodology has been used to develop an initial solver for the check-in desk allocation for the airport. The initial approach will be used to evaluate the feasibility of the approach and once it has been validated as a decision support tool it will be extended to an operational one.

An initial flight plan has been used for testing the approach, and its implementation in the simulated environment. Table 2 presents the flight plan used for the example presented here. The titles of the columns are self-explanatory; Table 2 was constructed from real information provided by the airport for a particular area of the terminal. This information will be used for the initial development.

1) Initial solution

The initial solution (the satisfaction problem) can be represented in a matrix where the horizontal axis represents time and the vertical one represents the check-in desks. Fig. 4 exemplifies the representation of the initial solutions. As the main outcome from the initial phase some initial solutions are generated and used as the initial population of the evolutionary algorithm. The feasible solutions are encoded as explained in the previous section and then the evolutionary algorithm generates new solutions.

Table 3 presents the evolution of values for the cost function when 50,000 iterations have been performed. It can be appreciated that the solution converges rapidly to a more stable value demonstrating its potential for a decision support tool.

The model of the terminal area has been developed using a general purpose simulation software called SIMIO [START_REF] Simio Homepage | [END_REF] . The simulator has been selected for the study since it possesses most of the characteristics mentioned in previous sections. Fig. 6 presents a snap-shot of the simulation model. In the general case the arrival profiles of the passengers are taken as homogeneous for every passenger in the terminal since the objective of the article is to present only the methodology as an approach for supporting decisions in planning.

In order to appreciate the potential of the methodology the initial allocation and the optimized one have been tested in the simulated environment. The LOS indicators have been evaluated using the simulation model for the simulated area. Table 4 presents the indicators obtained for the two scenarios.

5.

Conclusions And Future Work

The article presents the key elements to develop an approach that combines an evolutionary approach and simulation that performs the check-in desk allocation for optimizing the LOS indicators in a terminal. The algorithm provides different feasible configurations which were selected using a cost function that penalizes the violation of the soft rules imposed by the internal policy of the airport. Once the solutions are obtained, they are evaluated using a simulated environment that takes into account other elements of the problem such as physical locations, queue policies, arriving profiles for the passengers etc. The results show that the methodology is able to provide good solutions with few iterations and the reliability of the solutions is increased with the simulated model. The constraints that cannot be included in the evolutionary algorithm can be added to the simulation model in order to evaluate which solution is the one that gives best results for the objectives of the airport. The presented methodology can be easily extrapolated to other terminals but the simulation model of the correspondent terminal must be developed.

As a future work it will be tested the approach using the complete flight plan of the terminal and it will be compared to a real one in order to determine the level of improvement that can be achieved. Also in future implementations a meta-model can be integrated in the evolutionary algorithm in order to develop a stand-alone tool for decision making.

Figure 1 .

 1 Figure 1. The check-in areas in the terminal

  Figure 2 illustrates a diagram with the two luggage conveyors systems.

Figure 2 .

 2 Figure 2. The luggage-halls diagram b) Soft Rules Optimized Queuing / Circulation Areas for heavy flights: The allocation will avoid placing more than 3 heavy flights on the same row / island at any given one-hour window.Optimized Queuing / Circulation Areas for any flights: The allocation will avoid placing 2 flights on consecutive counters at any given one-hour window. The recommended practice is to leave at least one counter free between two flightsfor redundancy and flexibility purposes.Airline Preferences: Airline preferences for allocation of their flights to specific rows or fixed desks will be collected officially during meetings and the solution will consider their requests, only after complying with all the allocation rules.

Figure 3 .

 3 Figure 3. The evolutionary-simulation methodology

1 .

 1 Flight ID (string) 2. Check-In Desk Opening time (min.) 3. Check-In Desk Closing time (min.) 4. Initial Check-In Counter (integer) 5. Final Check-In Counter (integer) 6. Check-In Allocation Soft Rules (Integer) 7. Check-In Allocation Hard Rules (Integer) The first field of information holds the ID of the correspondent flight. The second and third fields refer to the time the Check-In counters are open. The next two fields provide the information related to which check-in counters were initially allocated for of LOS of the selected solutions under a simulated Environment Selection of the Best Solution the flight. Finally the last two fields are related to the number of check-in desks needed to satisfy the hard and soft rules.

Figure 4 .

 4 Figure 4. Example of allocation

Fig. 5

 5 Fig. 5 illustrates the evolution of the cost function versus the number of iterations.

Figure 5 .

 5 Figure 5. Convergence of the cost function

Figure 6 .

 6 Figure 6. The simulated environment

Table 2 .

 2 Departure Flight Schedule

Table 3 .

 3 Values of the cost function

	ITERATIONS AVG. COST VALUE % Improvement
	1	1.36
	10	1.012	25.58823529
	20	0.6714	50.63235294
	30	0.468	65.58823529
	40	0.4228	68.91176471
	45	0.3542	73.95588235
	60	0.15068	88.92058824
	624	0.145276	89.31794118
	891	0.13397	90.14926471
	3858	0.126434	90.70338235
	6605	0.125325	90.78492647
	6914	0.112363	91.73801471
	31600	0.11074	91.85735294

Table 4 .

 4 Level of Service Indicators

						AVG. COST VALUE
	1.6
	1.4
	1.2
	1
	0.8										AVG. COST VALUE
	0.6
	0.4
	0.2
	0
	0	100	200	300	400	500	600	700	800	900	1000

Acknowledgments

The authors would like to thank the Mexican Council for Science and Research (CONACYT) for its support for this work.