Stéphane Gonzalez
email: stephane.gonzalez@univ-paris1.fr

Michel Grabisch
email: michel.grabisch@univ-paris1.fr

Documents de Travail du

Keywords: cooperative game, core, balancedness, c-core, aspiration core, coalition formation, autonomous coalitions JEL Classification: C71

We consider in this paper solutions for TU-games where it is not assumed that the grand coalition is necessarily the final state of cooperation. Partitions of the grand coalition, or balanced collections together with a system of balancing weights interpreted as a time allocation vector are considered as possible states of cooperation. The former case corresponds to the c-core, while the latter corresponds to the aspiration core or d-core, where in both case, the best configuration (called a maximising collection) is sought. We study maximising collections and characterize them with autonomous coalitions, that is, coalitions for which any solution of the d-core yields a payment for that coalition equal to its worth. In particular we show that the collection of autonomous coalitions is balanced, and that one cannot have at the same time a single possible payment (core element) and a single possible configuration. We also introduce the notion of inescapable coalitions, that is, those present in every maximising collection. We characterize the class of games for which the sets of autonomous coalitions, vital coalitions (in the sense of Shellshear and Sudhölter), and inescapable coalitions coincide, and prove that the set of games having a unique maximising coalition is dense in the set of games.

Introduction

The main concern of cooperative game theory is to find a rational way to reward players for their cooperation. The traditional view assumes that eventually the grand coalition will form, so that the problem reduces to a sharing of the worth (benefit) created by the grand coalition among all players. Along this view, one of the most popular solutions of this problem is the core [START_REF] Gillies | Some theorems on n-person games[END_REF][START_REF] Gillies | Solutions to general non-zero-sum games[END_REF]: it is the set of allocations (payoff vectors) such that no coalition receives an amount lower than its own worth (this is called coalitional rationality).

It is well known that the main drawback of the core is that it is empty for a large class of games, namely the nonbalanced games. One way to escape this situation, among the many others which have been studied in the literature, is that we allow for a more general situation of cooperation (the grand coalition may be not the only state of cooperation), or a more general notion of allocation. In the latter case, [START_REF] Grabisch | On the vertices of the k-additive core[END_REF] have proposed to share the worth of the grand coalition not only among individual players, but also among all coalitions, up to a certain size k. This is called the k-additive core, and this notion has been further refined in (Gonzalez and Grabisch, forthcoming), leading to the negotiation set. In the former case, there exists natural generalizations of the core, once it is admitted that players may eventually form either disjoint coalitions, i.e., a partition of the grand coalition, or a collection of coalitions which has the property to be balanced: interpreting the balancing weights as amounts of time and assuming that each player has one unit of time to spend (see for example [START_REF] Peleg | Introduction to the theory of cooperative games[END_REF]), this unit can be split among different coalitions of this collection. The c-core [START_REF] Guesnerie | On economic games which are not necessarily superadditive:solution concept and application to a local public good problem with few a agents[END_REF][START_REF] Sun | Competitive outcomes and endogenous coalition formation in an n-person game[END_REF] corresponds to the case where players form a partition of the grand coalition, while the d-core (a.k.a. aspiration core) [START_REF] Bennett | The aspiration approach to predicting coalition formation and payoff distribution in sidepayment games[END_REF][START_REF] Cross | Some economic characteristics of economic and political coalitions[END_REF][START_REF] Albers | Core-and kernel-variants based on imputations and demand profiles[END_REF], which is never empty, corresponds to the more general case where players share their unit of time into different coalitions. It is important to note that the partition, or the balanced collection, which represents the final state of cooperation, is chosen so as to maximise the total worth obtained by cooperation, and for this reason, we call them maximising collections. In the case of a partition, the total worth is simply the sum of the worth of the coalitions in the partition, while for a balanced collection, one need to take into account the time allocated to each coalition: considering a utility linear in time, one simply compute the weighted sum of the worths, where the weights corresponds to the allotted times: see [START_REF] Cesco | Nonempty core-type solutions over balanced coalitions in tu-games[END_REF] for an axiomatization of such kind of solution, and Bejan and Gómez (2012a), who implements the d-core in strong Nash equilibria.

In a sense, the coalitions which are present in the maximising collection representing the final state of cooperation, have a strong power compared to the other ones. Then the following questions arise: can these coalitions be characterized by some property? Is there some relation with other special families of coalitions, like the vital coalitions introduced by [START_REF] Shellshear | On core stability, vital coalitions, and extendability[END_REF]? The aim of this paper is to study this question in depth. One of the main contribution of this paper is that the "strong" coalitions are the autonomous coalitions, introduced in (Gonzalez and Grabisch, forthcoming). An autonomous coalition of a game is defined as a coalition such that any d-core element yields a payment for that coalition equal to its worth. For a balanced game, the grand coalition is always autonomous, but it is not the only one in general (see, e.g., the glove game). We prove that the existence of a nontrivial autonomous coalition implies the existence of a covering of autonomous coalitions, and that any balanced covering of autonomous coalitions is a maximising collection, and vice versa: this completely characterizes the strong coalitions of the final cooperation state. Moreover, the set of all autonomous coalitions is balanced. A noticeable consequence of our results is that for balanced games, it is not possible to have at the same time a unique possible payment and a unique (or even a finite number of) configuration of coalitions achieving this payment: if the core is reduced to a singleton, then the set of possible configurations (balanced collections with time allocation) is a polyhedron, not reduced to a singleton.

A second natural question arises: suppose that there exists more than one maximising collection (this is the case of the glove game). Then it is not possible to know what will be the final state of cooperation. However, in this case, there exist coalitions with a special property: every maximising collection contains them, and for this reason we call them inescapable. We show that inescapable coalitions are vital, in the sense of [START_REF] Shellshear | On core stability, vital coalitions, and extendability[END_REF]. Games having a unique maximising collection are of particular interest since one can know without ambiguity the final state of cooperation, and for this reason, we call them games with a single state of cooperation (SSC games). We prove that the set of SSC games is dense in the set of games on a given set of players. As a last important result, we give a sufficient and necessary condition for which the sets of autonomous coalitions, vital coalitions, and inescapable coalitions, are all equal.

The paper is organized as follows: Section 2 introduces the necessary background on the c-core, d-core and maximising collections. Section 3 introduces autonomous coalitions and characterizes maximising collections in terms of autonomous coalitions. Section 4 deals with inescapable coalitions and SSC games, and establishes the links between the various types of coalitions introduced (vital, autonomous, inescapable). Section 5 concludes the paper by giving some final remarks, in particular related to the k-additive core.

Maximising systems

We start by fixing the notation and introducing basic definitions. For any nonempty finite set A, we denote by Π(A) the set of partitions over A and |A| the cardinal of A. Let N denote a fixed finite nonempty set with n members, who will be called agents or players. Coalitions of players are nonempty subsets of N, denoted by capital letters S, T , and so on. Whenever possible, we will omit braces for singletons and pairs, denoting {i}, {i, j} by i, ij respectively, in order to avoid a heavy notation A transferable utility (TU) game on N is a pair (N, v) where v is a mapping v : 2 N → R satisfying v(∅) = 0. We denote by G(N) the set of all games over N. For any coalition S, v(S) represents the worth of S, i.e., what coalition S could earn regardless of other players.

A payoff vector is a vector x ∈ R n that assigns to agent i the payoff x i . For any coalition T ⊂ N, we denote by v T the restriction of v to 2 T . Given x ∈ R n , and S ⊆ N, denote by x(S) the sum i∈S x i with the convention that x(∅) = 0.

A general payoff vector Gonzalez and Grabisch (forthcoming) is a vector x ∈ R 2 N \∅ that assigns to coalition S ⊆ N the payoff x S .

3 Documents de travail du Centre d'Economie de la Sorbonne -2014.44

A balanced system of N is a vector λ = (λ S ) S⊆N ∈ [0, 1] 2 N such that S⊆N λ S χ S = χ N ,
where χ S is the characteristic vector of S given by χ S i = 1 if i ∈ S and 0 otherwise. We denote by B(N) the set of balanced systems over N. For λ ∈ B(N), we denote by B(λ) the set defined by:

B(λ) = {S ⊆ N, λ S > 0}.
A collection B ⊆ 2 N , is called balanced (over N) if there exits a balanced system λ ∈ B(N) such that B = B(λ). A balanced collection is minimal if no subcollection of it is balanced. It is well-known that a balanced collection B is minimal if and only if there is a unique balanced system λ ∈ B(N) such that B = B(λ).

Definition 1. For a game v ∈ G(N) we define (i) The set of preimputations of v as:

P I(v) := {x ∈ R n | x(N) = v(N)}.
(ii) The set of c-preimputations of v as:

c-P I(v) := {x ∈ R n | x(N) = max π∈Π(N ) S∈π v(S)}.
(iii) The set of d-preimputations of v as:

d-P I(v) := {x ∈ R n | x(N) = max λ∈B(N ) S∈B λ S v(S)}.
(iv) The set of k-preimputation of v, with k ∈ N as:

k-P I(v) := {(x S ) S⊆N ∈ R 2 n , x S = 0 if |S| > k and S⊆N x S = v(N)}
We remark that in the definition of d-preimputations, we need not write sup instead of max, since the maximum is attained for some balanced system. Indeed, it is well known that the set B(N) is a closed convex polytope in R (2 N ) , hence compact, and since the function λ∈B(N ) λ S v(S) is a continuous function on this domain, it reaches its maximum at some point (even more, this point will be an extreme point since the function is linear).

In the classical view of preimputations, it is supposed that the grand coalition will form, and its worth is shared among the players. With a c-preimputation, the best partition of the players is sought, in order to maximise the total worth. Now, d-preimputations generalize c-preimputations since partitions are particular balanced collections. More importantly, d-preimputations have an interesting interpretation if one considers λ S for S ⊆ N as an amount of time1 allocated to S. Assuming that v(S) represents the worth or the production per unit of time, λ S v(S) is the total worth/production achieved by S. Under this viewpoint, a d-preimputation is a sharing among the players of the total worth which can be achieved by the best arrangement of the players in time.

Definition 2. For any game v ∈ G(N) we define (i) The core [START_REF] Gillies | Some theorems on n-person games[END_REF] of v as:

C(v) := {x ∈ P I(v) | x(S) ≥ v(S), ∀S ∈ 2 N }.
(ii) The c-core [START_REF] Guesnerie | On economic games which are not necessarily superadditive:solution concept and application to a local public good problem with few a agents[END_REF]

of v as: c-C(v) := {x ∈ c-P I(v) | x(S) ≥ v(S), ∀S ∈ 2 N }.
(iii) The d-core2 [START_REF] Albers | Core-and kernel-variants based on imputations and demand profiles[END_REF] of v or aspiration core [START_REF] Bennett | The aspiration approach to predicting coalition formation and payoff distribution in sidepayment games[END_REF] of v as:

d-C(v) := {x ∈ d-P I(v) | x(S) ≥ v(S), ∀S ∈ 2 N }.
A game v is totally balanced if, for any ∅ = S ⊆ N, v S is balanced. The totally balanced cover of v denoted by v tb is given by:

v tb (S) = max{ T ⊆S λ T v(T ) | λ ∈ B(S)} It is well known and easy to prove that d-C(v) = C(v tb ).
We say that a game v is balanced if C(v) is nonempty, and c-balanced if c-C(v) is nonempty. The following results, proved independently by [START_REF] Bondareva | Some applications of linear programming methods to the therory of cooperative games[END_REF] and [START_REF] Shapley | On balanced sets and cores[END_REF], are well known.

Theorem 1 (The Bondareva-Shapley Theorem, weak form). A necessary and sufficient condition that the core of a game (N, v) is not empty is that for each balanced system

λ ∈ B(N), v(N) ≥ S⊆N λ S v(S).
Theorem 2 (The Bondareva-Shapley Theorem, sharp form). A necessary and sufficient condition that the core of a game (N, v) is not empty is that for each minimal balanced collection B:

v(N) ≥ S⊆N λ S v(S)
where λ ∈ B(N) is the unique balanced system such that B(λ

) = B.
Observe that the statement is still true if the minimal balanced collection {N} is discarded.

Given a game (N, v) and t ≥ 0, define its t-expansion v t by v t (S) = v(S) for all S ⊂ N, (Bejan and Gómez, 2012b) the minimum amount to be given to the grand coalition in order to ensure balancedness.

and v t (N) = v(N) + t. Now, to any game (N, v) we assign t(v) := min{t ≥ 0 | C(v) = ∅},
The following lemma is central in our analysis.

Lemma 1. For any game (N, v), any balanced system λ ∈ B(N), it holds

v(N) + t(v) ≥ S⊆N λ S v(S)
and there exists at least one minimal balanced system for which equality holds.

Any balanced system for which equality holds is called a maximising system.

Proof. Since v t(v) is balanced and t(v) ≥ 0, it follows by Theorem 1 that for every balanced system λ

v(N) + t(v) ≥ S∈B λ S v t(v) (S) ≥ S∈B λ S v(S).
Now, if v is balanced, then t(v) = 0, and equality holds taking B = {N}. Otherwise, suppose that S⊆N λ S v(S) < v(N) + t(v) for every balanced system, and define

0 < t ′ = max λ∈B(N ) S⊆N λ S v(S) -v(N) < t(v). (1)
(first inequality comes from the fact that v is not balanced and Theorem 1) Then for ev-

ery balanced system λ, S⊆N λ S v(S) ≤ v(N) + t ′ holds. We claim that S⊆N λ S v t ′ (S) ≤ v(N) + t ′
holds for every minimal balanced collection, which by the sharp form of Bondareva-Shapley theorem, implies that v t ′ is balanced, a contradiction with the definition of t(v). Proof of the claim: for the minimal balanced collection {N}, the inequality trivially holds. Now, any other minimal balanced collection cannot contain N.

Therefore S⊆N λ S v t ′ (S) = S⊆N λ S v(S),
which proves the claim by (1).

Finally, consider the following linear program in variables λ S , S ∈ 2 N , maximize

S⊆N λ S v(S) subject to S∋i λ S = 1, i ∈ N λ S ≥ 0, S ∈ 2 N
(note that the feasible domain is the set of balancing weights for all balanced collections)

The above reasoning has proved that this linear program has an optimal solution, and the value of the objective function is v(N)+ t(v). Since there is an optimal solution which is a vertex of the feasible domain, and since it is well known that vertices correspond to minimal balanced collections, the proof is complete.

The following proposition clarifies the position of the different notions introduced so far.

Proposition 1. For any game v in G(N), we have:

C(v) ⊆ c-C(v) ⊆ d-C(v) = C(v t(v) ),
and equality holds everywhere if and only if v is balanced.

We provide a simple proof of this result. The inclusions where shown by, e.g., Bejan and Gómez (2012b), and the last equality by [START_REF] Cross | Some economic characteristics of economic and political coalitions[END_REF] and [START_REF] Bennett | The aspiration approach to predicting coalition formation and payoff distribution in sidepayment games[END_REF].

Proof. By Lemma 1, max λ∈B(N ) S⊆N λ S v(S) = v(N) + t(v), which proves that any element of the d-core is also an element of C(v t(v) ) and vice versa. The last equality is therefore established.

To see the second inclusion, suppose that c-C(v) = ∅, otherwise the result trivially holds. By definition of t(v), any x ∈ R n satisfying x(S) ≥ v(S) for every S ∈ 2 N must satisfy x(N) ≥ v(N) + t(v). If in addition x ∈ c-C(v) and since a partition is a particular balanced collection, it follows by Lemma 1 that x(N) = v(N)+ t(v), hence x is an element of the d-core.

Finally, if the core is empty, the first inclusion trivially holds. Otherwise, t(v) = 0, so that C(v) = C(v t(v) ) and equality holds throughout.

From the last equality, it is clear that the d-core is never empty. We see immediatly that if the core of v is nonempty then t(v) = 0 and λ ∈ B(N) defined by λ N = 1 and λ S = 0 is a maximising system. If the c-core of v is nonempty, then there exists a partition π ∈ Π(N) and a maximising system λ ∈ B(N) such that λ S > 0 ⇔ S ∈ π, and t(v) = S∈π λ S v(S)v(N). Otherwise, there exists a maximising system λ ∈ B(N)

such that t(v) = S⊆N λ S v(S) -v(N).
In his article about the d-core, [START_REF] Cross | Some economic characteristics of economic and political coalitions[END_REF] described his solution as a set of stable coalitions with their associated payoffs. Literature focuses essentially on the set of payoffs without considering the properties of the set of corresponding coalitions. [START_REF] Cesco | Nonempty core-type solutions over balanced coalitions in tu-games[END_REF] gives and axiomatizes a new kind of solution which associates to each game not only an amount of the d-core but also the coalitions which permit to reach this amount, that is, the coalitions S such that there exists a maximising system λ * ∈ B(N) which satisfies λ(S) > 0. Bejan and Gómez (2012a) implements the d-core in strong Nash equilibria, corresponding strategies consist of giving an amount of the d-core and an arrangement of the players in time given by a maximising system which permits to reach this amount.

As we have seen, a maximising system can be interpreted as the best arrangement of the players in time. For balanced games, players can stay in the grand coalition, in the case of c-balanced games, each player can stay in the coalition given by the best partition while other games require that some players change coalitions over time. The quantity t(v) indicates the deviation from balancedness of a game. It may be interesting to study the behavior of v → t(v) and how the configuration of players over time changes when the game slightly changes.

Denote by B * N the mapping which associates to each game v ∈ G(N) the set of maximising systems for v. We can interpret B * N as a correspondence, giving for each game all the possible best configurations of players over time. We will show and characterise in Section 4.3 the games which possess a unique best configuration for players, that is, games such that B * N gives a singleton. 12), that is, all the arrangements of the players in time are equivalent, their final production will be always equal to zero. Let us propose two perturbations of the game v. For ǫ > 0, we define v + and v -by:

Example 1. Let v ∈ G(12) defined by v(1) = v(2) = v(12) = 0. In this case, B * 12 (v) = B(
(i) v + (1) = v + (2) = 0 and v + (12) = ǫ > 0 (ii) v -(1) = v -(2) = 0 and v -(12) = -ǫ < 0
For those two games, as closed as we want to the original game, there exists only one maximising system, that is, a unique way for players to be arranged in time. The configuration given by v + provides an incentive to stay in the grand coalition, while v - encourages all the players to stay alone all the time:

B * N (v + ) = {(λ 1 , λ 2 , λ 12 ), λ 1 = λ 2 = 0, and λ 12 = 1} B * N (v -) = {(λ 1 , λ 2 , λ 12 ), λ 1 = λ 2 = 1
, and λ 12 = 0}. The previous example shows that B * N is not a lower hemicontinuous correspondence. The following Theorem proves in one shot that B * N is upper hemicontinuous and that v → t(v) is continuous.

Theorem 3. The function v → t(v) is continuous and the correspondence v ⇒ B * N (v) is upper hemicontinuous on G(N). Proof. Let f be the function defined on G(N) × [0, 1] 2 N → R by f (v, λ) = S⊆N λ S v(S),
and B N the constant correspondence which associates to each v ∈ G(N) the polytope B(N). f is continuous, B N is a constant correspondence, therefore it is continuous, furthermore since B(N) is a polytope, B N is compact-valued. We can apply immediately the Berge's maximum theorem [START_REF] Berge | Espaces topologiques[END_REF] and conclude that

v → t(v) := max{f (λ, v)|λ ∈ Λ} -v(N)
is continuous, and

v ⇒ B * N (v) := {λ ∈ B(N) | S⊆N λ S v(S) = v(N) + t(v).
is upper hemicontinuous.

3 Autonomous coalitions

Definition and first properties

The study of cooperative games shows that the core gives sometimes very controversial solutions, the more classical example being the glove game defined on N = {1, 2, 3} by

v(i) = 0, ∀i ∈ N, v(12) = v(13) = v(123) = 1 and v(23) = 0.
In this game the core gives the unique payoff: x 1 = 1, x 2 = x 3 = 0. We see that coalition {2, 3} earns the same amount if it stays in the grand coalition (x({2, 3}) = 0) or out of the grand coalition (v({2, 3}) = 0). This coalition has a kind of autonomy regarding to the payoff given by the core, making the game unstable. Therefore, a game may be unstable if there exists a subcoalition S of N such that no payoff vector in the core can ensure a strictly better payoff than what S can achieve by itself, i.e., v(S).

More generally, a coalition is autonomous if it cannot earn more than its own worth with a payoff vector given by the d-core. We give in this section a characterisation of the existence of autonomous subcoalitions in the case of balanced games. We will show that if there exists an autonomous subcoalition, then there necessarily exists a collection of autonomous coalitions covering N. Moreover, the restriction of a game to one of its autonomous coalitions is always balanced, and the covering of autonomous coalitions is always a balanced collection which generates the d-core. We say that a collection A of coalitions is a covering of N if ∪ A∈A A = N. Definition 3. Let (N, v) be a game. A nonempty coalition T ⊆ N is autonomous for (N, v) if for any payoff vector x of C(v t(v) ), it holds x(T ) = v(T ). Similarly, a collection A ⊆ 2 N is an autonomous covering of N for v if it is a covering of N and ∀S ∈ A, S is autonomous.

Note that N is an autonomous coalition if and only if v is balanced. Let us define a maximising collection as a collection B such that there exists a maximising system λ ∈ B(N) with B = B(λ). A first noteworthy result is the following.

Lemma 2. Let v ∈ G(N) be a game. Then any maximising collection is an autonomous covering of N for v.

Proof. Let B be a maximising collection and take x ∈ C(v t(v) ). There exists a maximising system λ ∈ B(N) such that B = B(λ). By positivity of λ S , S ∈ B:

v(N) + t(v) = x(N) = S∈B λ S x(S) ≥ S∈B λ S v(S) = v(N) + t(v).
Hence equality holds throughout, forcing x(S) = v(S) for all S ∈ B. It follows that B is an autonomous covering.

Definition 4 [START_REF] Shellshear | On core stability, vital coalitions, and extendability[END_REF]; [START_REF] Gillies | Some theorems on n-person games[END_REF]). Let S be a coalition of N. S is called vital (w.r.t (S, v)) if there exists x ∈ C(v S ) such that x(T ) > v(T ) for all T ∈ 2 S \ {∅, S}.

Observe that vital coalitions are strongly linked with the notion of autonomous coalition since it is possible to define alternatively a vital coalition as a coalition which is the unique autonomous coalition of the game v S . If S is vital and if there exists a subcoalition T which is autonomous, then for any members x of the core of v S , we have x(T ) = v(T ) that contradicts the Definition 4.

Proposition 2 ( [START_REF] Gillies | Solutions to general non-zero-sum games[END_REF]). S is vital if and only if for any balanced system λ ∈ B(S) such that B(λ) = {S},

T ⊆S λ T v(T ) < v(S).
Since the restriction v S of a game v to a vital coalition is necessarily balanced, the following Theorem contains Proposition 2. Theorem 4. Let v ∈ G(N) be a balanced game. The following propositions are equivalent:

(i) There exists a coalition S ⊂ N which is autonomous in (N, v).

(ii) There exists a collection A = {A 1 , . . . , A k }, with A i = N for i = 1, . . . , k, which is an autonomous covering of N for v.

(iii) ∀ǫ > 0, C(v -ǫ ) = ∅.

(iv) There exists λ * ∈ B(N) such that B(λ * ) = {N} is a minimal collection which is maximising:

v(N) = S⊆N λ * S v(S) (v) N is not vital.
Proof.

-(ii)⇒(i) is obvious.

-(i)⇒(ii): Let S = N be an autonomous coalition. Suppose per contra that there exists i ∈ N such that for any T ⊂ N, T ∋ i, there exists x ∈ C(v) such that x(T ) > v(T ). Since S is autonomous, we have i ∈ S. For each T ⊂ N, T ∋ i, choose x T ∈ C(v) such that x T (T ) > v(T ), and consider x ′ the center of gravity of all these x T . By convexity

x ′ ∈ C(v) and satisfies x ′ (T ) > v(T ) for all T ⊂ N, T ∋ i. Define δ = min T ⊂N,T ∋i (x ′ (T ) -v(T )) > 0,
and consider T * for which the minimum is attained. Take j ∈ S and define the payoff vector x * by

x * i = x ′ i -δ, x * j = x ′ j + δ and x * k = x ′ k for k ∈ N \ {i, j}.
By construction, x * belongs to the core of v, and satisfies x * (S) > v(S), a contradiction with the assumption on S.

-(ii)⇒(iii): Suppose there exists ǫ > 0 such that C(v -ǫ ) = ∅. Take y ∈ C(v -ǫ ) and nonnegative numbers ǫ 1 , . . . , ǫ n such that n i=1 ǫ i = ǫ. Since (y 1 + ǫ 1 , . . . , y n + ǫ n ) ∈ C(v) and A j is an autonomous coalition, we have for every

A j ∈ A v(A j ) = i∈A j (y i + ǫ i ) ≥ y(A j ) ≥ v(A j ),
implying that equality holds throughout, and therefore ǫ i = 0 for all i ∈ A j . Since this holds for every A j ∈ A and A is a covering of N, it follows that ǫ 1 = • • • = ǫ n = 0, which contradicts ǫ > 0.

-(iii)⇒(iv): Let us consider

F := S⊆N λ S v(S) | B(λ) minimal balanced collection , B(λ) = {N} .
Since F is a finite subset of R, there exists λ * ∈ B(N), and B(λ * ) = {N} minimal balanced collection attaining the maximum of F , and we may define the game v by: v(N) = S⊆N λ * S v(S), and v(S) = v(S) for any S ⊂ N. Observe that

v(N) = S⊆N λ * S v(S) ≥ S⊆N λ S v(S) = S⊆N λ S v(S)
for every λ ∈ B(N) such that B(λ) is minimal balanced collection different from {N}, hence by Theorem 2, v is balanced. However v is also balanced, hence by Theorem 2 again, we have v ), and (iv) is proved.

(N) = S⊆N λ * S v(S) ≤ v(N). If v(N) < v(N), we would have C(v -ǫ ) = ∅ with ǫ = v(N) -v(N), a contradiction with (iii). Hence λ * satisfies v(N) = S⊆N λ * S v(S
-(iv)⇒(ii): Take λ * ∈ B(N) such that B(λ * ) is a minimal balanced collection different from {N} such that v(N) = S⊆N λ * S v(S). By Lemma 2, B(λ * ) is an autonomous covering of N, which does not contain N since B(λ * ) is minimal and different from {N}.

-(i)⇔(v): it is a direct consequence of the Definition 4.

The following result, which is a corollary of Theorem 4, states that for balanced games, it is impossible to have an exact information about the configuration of agents over time and an exact information about the payoff vector. The uniqueness of a payoff given by the core can only be achieved through the loss of the uniqueness of the configuration of agents over time while by contraposition, the uniqueness of the configuration of players in time, given by B * N , implies that the core is not reduced to a point.

Corollary 1. Let v be a balanced game. If C(v) is a singleton, then B * N (v) is a polytope not reduced to a point.
Proof. If the polytope C(v) is a singleton, then its dimension is equal to 0, which implies that at least |N| inequality constraints are equality contraints. Hence, v has at least one autonomous coalition different from N, and according to Theorem 4(iv), there exists λ * ∈ B * N (v) such that B(λ * ) = {N} is a minimal collection. However, {N} is also a maximising collection, hence B * N (v) is not reduced to a singleton. The Theorem 4 can be applied to nonbalanced games as well, by applying it to v t (v) . Observe then that (iii) is always satisfied, which proves that a nonbalanced game has always an autonomous coalition different from N. Hence we obtain: Corollary 2. Let v ∈ G(N) be a nonbalanced game. Then there exists an autonomous covering A = {A 1 , . . . , A k } with A i = N, i = 1, . . . , k of N for v, which is a minimal balanced collection with a balanced system λ satisfying

v(N) + t(v) = k i=1 λ A i v(A i ).
Note that this result can be directly deduced from Lemmas 1 and 2. We have seen in the previous subsection that, for balanced games which satisfy one of the assertion of Theorem 4, or for non-balanced games, there exist some autonomous subcoalitions of N such that payoffs given by the d-core are always equal to the worth of those coalitions. Hence, an autonomous coalition has no incentive to stay in the grand coalition or to accept a payoff given by the d-core, and has an equal interest to play alone from the point of view of coalitional rationality: Note that this point of view is enforced by the fact that the restriction of a game to one of these autonomous coalitions has a nonempty core.

Proposition 3. If S is autonomous, then C(v S ) is nonempty. Proof. If S is autonomous for a game v, then a solution x ∈ C(v t(v) ) satisfies x(T ) ≥ v(T ) ∀T ⊆ S and x(S) = v(S). Therefore (x i ) i∈S ∈ C(v S ).
Observe that the Proposition 3 is not an equivalence, otherwise every singleton would be an autonomous coalition.

However, since a player can be in several autonomous coalitions, it is difficult to predict which of them will form. For example, the game v, defined on N = {1, 2, 3} by v(S) = 100 if |S| = 2, and 0 otherwise, has three autonomous coalitions which are the pairs of N. Each pair has a rational interest to leave the grand coalition, but, if one of them leaves, the "alone player" receives nothing. No player, in this case, knows if he will be the "alone player". In this kind of game, each player is in a situation of uncertainty regarding to which autonomous coalition will form. The next result shows that the d-core ensures a payoff as good as one autonomous coalition would receive by leaving the grand coalition, while avoiding the situation of uncertainty described above.

Proposition 4. C(v t(v) ) ⊆ S⊆N S autonomous coalition of v C(v S )
where

C(v S ) := {x ∈ R n | (x i ) i∈S ∈ C(v S )}.
Proof. For any x ∈ C(v t(v) ), we have x(S) = v(S) for any autonomous coalition S. Moreover, every coalition of N satisfies the property:

x(T ) ≥ v(T ), so in particular x(T ) ≥ v(T ) for T ⊆ S.
Remark 1. The reverse inclusion is not true. For example, let v be the game over

N = {1, 2, 3, 4} defined by v(12) = v(34) = 2, v(13) = 1 and v(T ) = 0 for all other T ⊆ N. Then (1, 1, 1, 1) ∈ d-C(v), S 1 = {1, 2}
and S 2 = {3, 4} are the unique autonomous coalitions. Let x = (0, 2, 0, 2), then, for i = 1, 2,

x S i ∈ C(v S i ). However, x ∈ d-C(v).
Lastly, we note a concavity property for the set of autonomous coalitions: If S and T are two autonomous coalitions for (N, v), then we have:

v(S ∪ T ) + v(S ∩ T ) ≤ v(S) + v(T ). Indeed, let x ∈ C(v t(v) ), we have : v(S ∪ T ) ≤ x(S ∪ T ) = x(S) + x(T ) -x(S ∩ T ) ≤ v(S) + v(T ) -v(S ∩ T ).

Links with maximising collections

Given v ∈ G(N), let us study the nature of the set AU(v) of its autonomous coalitions. We prove in this section that AU(v) is balanced, as corollary, we will see the equivalence between being a maximising collection and being a balanced system of autonomous coalitions. First we need the following result: Theorem 5. [START_REF] Zumsteg | Non-Cooperative Aspects of Cooperative Game Theory and Related Computational Problems[END_REF]; [START_REF] Derks | Orderings, excess functions, and the nucleolus[END_REF]] A collection B ∈ 2 N of nonempty sets is balanced if and only if for every vector y ∈ R n such that y(N) = 0, either y(S) = 0 for every S ∈ B or there exist S, T ∈ B such that y(S) > 0 and y(T ) < 0. Theorem 6. For all game v, the collection AU(v) is balanced.

Proof. Let x be the barycentre of d-C(v). Let y ∈ R n . Suppose there exists y ∈ R n such that y(S) ≥ 0 ∀S ∈ AU(v) and y(N) = 0. Since x is the barycentre of d-C(v), we have x(S) = v(S) for all S ∈ AU(v) and x(S) > v(S) for all S ∈ 2 N \ AU(v). Let ǫ be the real number defined by: ǫ := min

S∈2 N \AU (v)
x

(S)v(S)

There exists k ∈ N such that

max S∈2 N |y(S)| k < ǫ. We put ỹ = y k . We have: x(S) + ỹ(S) ≥ v(S), ∀S ∈ 2 N ; and x(N) + ỹ(N) = x(N) + y k (N) = x(N). Hence x + ỹ ∈ d-C(v)
. Therefore, ∀S ∈ AU(v), (x + ỹ)(S) = v(S) and (x + ỹ)(S) = v(S) + ỹ(S). It follows y(S) = 0 for any autonomous coalition S. By application of Theorem 5, we deduce that AU(v) is balanced.

Corollary 3. The set of autonomous coalitions of a game v is a maximising collection of v.

Hence, there is an equivalence between belonging to a maximising collection and being an autonomous covering: Theorem 7. Let v be a game in G(N). The following properties are equivalent:

(i) F is a maximising collection of v (ii) F is a autonomous balanced covering of v Proof.
It is a corollary of Corollary 3 and Lemma 2.

Inescapability

We have seen that our purpose contained two different aspects: the payoff vector, on the one hand, and the configuration of agents in coalition, on the other hand. A natural question for both consists in defining when we have uniqueness. It is fairly simple to know, by the dimension of the d-core, when a game gives a unique payoff vector: Proposition 5. The dimension of the d-core of a game v is

dim(d-C(v)) = n -rank((|S ∩ T |) S,T ∈AU(v) ).
Proof. The d-core is a polytope, then its dimension is equal to nd, where d is the size of the largest collection of linearly independent equality constraints. Since the collection of equality constraints corresponds to the collection {x(S) = v(S)} S∈AU(v) , it comes that the size of the largest linearly independent set of equality constraints is equal to the rank of {χ S } S∈AU (v) . We know that the rank of a family of vector in an inner space is equal to the rank of its corresponding Gram matrix. We can conclude by the observation that χ S , χ T = |S ∩ T |.

We focus now on the conditions of uniqueness of the configuration of agents.

Definition and first properties of inescapability

The glove game, defined for example in N = {1, 2, 3} by v(12) = v(13) = v(123) = 1 and 0 otherwise has four autonomous coalitions: 12, 13, 23, 123. We see that the set of autonomous coalitions, which is by Theorem 7 a maximising collection, contains two disjoint maximising collection: M 1 = {12, 13, 23} and M 2 = {123}, and since B * 123 (v) is a polytope not reduced to a point, there exists infinitely many arrangements of the players in time. Hence, even if 12 is an autonomous coalition, that is a strong coalition, it can be "escapable" for the player 1 or 2 which can prefer to belong to the coalition 123. Hence, among the set of autonomous coalitions, we want to differentiate the ones which are escapable from the ones which are not.

Definition 5. Let v be a game in G(N). A coalition S ⊆ N is said to be inescapable if every maximising collection contains S. Every autonomous coalition which is not inescapable is called escapable. Proposition 6. Let v be a game in G(N). If S is an autonomous coalition for (N, v), then S is inescapable for every game (N, v ǫ ) defined, for any ǫ > 0, by v ǫ (S) = v(S) + ǫ and v ǫ (T ) = v(T ), ∀T = S.

Proof. Let S be an autonomous coalition for the game v. By Theorem 7, there exists λ ∈ B(N) a maximising system such that the maximising collection B(λ) contains S. Let γ be a balanced system of N such that S ∈ B(γ). Then

T ⊆N γ T v ǫ (T ) = T ⊆N γ T v(T ) ≤ T ⊆N λ T v(T ) < T ⊆N λ T v ǫ (T ).
Therefore if γ is a balanced system such that S ∈ B(γ), then γ is not a maximising system for v ǫ . Therefore S is inescapable for v ǫ .

Games with a single state of cooperation.

Note that if every autonomous coalition of a game is inescapable, then the game has a unique maximising collection. Definition 6. A game v ∈ G(N) is said to be with a single state of cooperation (SSC game) if it has a unique maximising collection.

We denote by SG(N) the set of SSC games. Theorem 8. The set of SSC games SG(N) is dense in G(N).

Proof. We know that for any game v ∈ G(N), there always exists a maximising collection B of v. Let O be a smallest subcollection of B which is maximising.Let ǫ > 0 and u ǫ be the game defined by u ǫ (S) = v(S)

+ |S| |N | ǫ if S ∈ O, and u ǫ (S) = v(S) otherwise. Let x ∈ d-C(v). We have x(S) = v(S) if S ∈ O. We put, for all i ∈ N, xi = x i + ǫ |N | .
We have x(S) = x(S)

+ |S| |N | ǫ which is equal to v(S) + |S| |N | ǫ = u ǫ (S) if S ∈ O,
and it is strictly greater otherwise. Hence x belongs to the d-core of u ǫ and, by Theorem 7, O is a maximising collection of u ǫ . Suppose there exists a maximising collection of u ǫ denoted by A such that A = O.

Firstly, if there exists S ∈ A such that S ∈ O then, since S is autonomous for u ǫ , ∀y ∈ d-C(u ǫ ), y(S) = u ǫ (S). It is a contradiction with x ∈ d-C(u ǫ ) and x(S) > u ǫ (S).

Secondly, assume A ⊆ O. If there exists S ∈ O such that S ∈ A then, by construction of O, we deduce that A is not balanced, a contradiction.

Links between vitality, autonomy and inescapability

In this section we study the relation between the concepts of autonomous coalitions, vital coalitions, and inescapable coalitions. First, by definition, an inescapable coalition is always autonomous. Hence the set of inescapable coalitions is included in the set of autonomous coalitions, with equality if and only if the game is SSC. [START_REF] Shellshear | On core stability, vital coalitions, and extendability[END_REF] proves that there always exists a maximising collection of vital coalitions3 , then by Theorem 7, the intersection between the set of vital coalitions and the set of autonomous coalitions is always nonempty. Proposition 7. Let v be a game. The set of inescapable coalitions of v is included in the set of vital coalitions of v.

Proof. Let S be an inescapable coalition of (N, v) and α a maximising system. S is autonomous and by Proposition 3, C(v S ) = ∅. Then for any balanced system γ ∈ B(S),

v(S) ≥ T ⊆S γ T v(T ).
If S is not vital, then by Proposition 2, there exists a minimal balanced system λ ∈ B(S), such that B(λ) = {S} and v

(S) = T ⊆S λ T v(T ). Let α ′ ∈ B(N) defined by α ′ = α + α(S) λ -δ S α(S),
where λ ∈ B(N) and δ ∈ {0, 1} 2 N are given by: λ

(T ) = λ(T ), if T ⊆ S 0 otherwise, and
δ S (T ) = 1, if T = S 0 otherwise. The relation T ⊆N α ′ (T )v(T ) = T ⊆N α(T )v(T )
is satisfied, then α ′ is a maximising system. Furthermore, λ ∈ B(S) is a minimal balanced system satisfying B(λ) = {S}, hence λ(S) = 0, which implies α ′ (S) = 0. We conclude that B(α ′ ) is a maximising collection which does not contain S, implying that S is escapable, a contradiction.

Remark 2. Let v be the glove game on N = {1, 2, 3} defined by v(12) = v(13) = v(123) = 1 and v(S) = 0 otherwise. All singletons of this game are vital, but none of them is autonomous. The coalitions 12,13 and 23 are autonomous and vital but not inescapable.

Autonomous coalitions vital coalitions inescapable coalitions

Let us see now a condition on the game v for which these three notions of coalitions become equivalent.

Definition 7. A game v is without imputations if for all coalition S ⊆ N, |S| > 1 i∈S v(i) > v(S).
Proposition 8. A game v is without imputations if and only if the set of autonomous coalitions, the set of inescapable coalitions and the set of vital coalitions of v are equal.

Proof. Claim 1: A game v is without imputations if and only if the singletons are the unique maximising collection. If a game is without imputations, then for any coalition S with at least two players, for any balanced collection B(λ) containing S, the balanced system λ ′ ∈ B(N) defined by λ ′ (T ) = λ(T ) if T = S and λ ′ (i) = λ(i) + λ(S) ∀i ∈ S satisfies:

T ⊆N λ(T )v(T ) ≤ T ⊆N T =S λ(T )v(T )+λ(S)v(S) < T ⊆N T =S λ(T )v(T )+λ(S) i∈S v(i) = T ⊆N λ ′ (T )v(T ).
Conversely, if the singletons are the unique maximising collection, then if there exists a coalition S with at least two players such that i∈S v(i) ≤ v(S) then:

i∈N v(i) < v(S) + i∈N \S v(i), a contradiction.
Suppose v is a game without imputations, by Claim 1, v is SSC, and the singletons are the autonomous coalitions (and also the inescapable coalitions). Furthermore, by Proposition 2 the singletons are the unique vital coalitions. Hence the three types of coalition coincide.

Conversely, if v is a game such that the set of autonomous coalitions, the set of inescapable coalitions and the set of vital coalitions of v are equal, then, since the singletons are always vital, the set of singletons is included into the set of autonomous coalitions. Since the set of singletons is a balanced collection and it is an autonomous covering equal to the set of inescapable coalitions, we deduce that it is the unique maximising collection. Hence, by Claim 1, v is without imputations.

Final remarks

The results of our investigation show that there exist deep links between autonomous coalitions and the concepts of core, c-core, d-core and also the negotiation set: (i) A game v is balanced if and only if N is autonomous, and the set of SSC balanced games is dense over the set of balanced games. In this case, not SSC games corresponds to games which satisfies one of the assertions of Theorem 4;

(ii) A game v is c-balanced if and only if there exists an autonomous covering which is a partition.

We can also define two other concepts of core with the use of k-preimputations, the first one being the k-additive core [START_REF] Grabisch | On the vertices of the k-additive core[END_REF] The negotiation set of a game v can be interpreted as the set of k-preimputations which are as close as possible to the set of preimputations, and such that the sum of amounts given to the subsets of a coalition is larger than its worth. It could be interesting to know what is the "largest" autonomous coalition, that is, how many players an autonomous coalition can contain? The negotiation set gives an answer to this question. The greatest (in the sense of inclusion) autonomous coalitions correspond to coalitions T such that x T = 0 for all x ∈ I n 1 (v), and any superset of T does not satisfy this property. The economic interpretation is the following: The negociation set maximises what we can give to individuals for ensuring coalitional rationality, and shares the debts only to the coalitions of size larger than 2: if x ∈ I n 1 (v), then ∀S ⊆ N such that |S| ≥ 2, we have x S ≤ 0. The following theorem ensures that the autonomous coalitions do not pay the debts, that is, a coalition has to pay some debt if and only if it is not contained in some autonomous coalition.

  defined by:C k (v) := {(x S ) S⊆N S =∅ ∈ k-P I(v), ∀T ⊆ N S⊆T x S ≥ v(T )},and the second one being the negotiation set (Gonzalez and Grabisch, forthcoming) defined by:I n 1 (v) := argmin x∈C k (v) S⊆N |S|≥2 |x S |.

Documents de travail du Centre d'Economie de laSorbonne -2014.44

Although usually it is interpreted as an amount of resources[START_REF] Kannai | The core and balancedness[END_REF].4Documents de travail du Centre d'Economie de laSorbonne -2014.44

See also[START_REF] Albers | Zwei Lösungskonzepte für kooperative Mehrpersonenspiele, die auf Anspruchsnivaus der Spieler basieren[END_REF] and[START_REF] Turbay | On value theories for n-person cooperative games[END_REF].5Documents de travail du Centre d'Economie de laSorbonne -2014.44

More precisely a maximising collection of strongly vital-exact coalitions.

Theorem 9 (Gonzalez and Grabisch (forthcoming)). Let v be a game on N, and S be a coalition of N such that |S| ≥ 2. The following properties are equivalent:

(i) There exists T ⊇ S such that T is autonomous.

(ii) ∀x ∈ I n 1 (v), x S = 0.


Martí Bosch
email: marti.bosch@estudiant.upc.edu

Pierre Genevès
email: pierre.geneves@cnrs.fr

Nabil Layaïda
email: nabil.layaida@inria.fr

Automated Refactoring for Size Reduction of CSS Style Sheets

Keywords: Descriptors 1.7 [Document and Text Processing]: Document preparation; D.2 [Software Engineering]: Testing and Debugging Web development, Style sheets, CSS, Debugging

Cascading Style Sheets (CSS) is a standard language for stylizing and formatting web documents. Its role in web user experience becomes increasingly important. However, CSS files tend to be designed from a result-driven point of view, without much attention devoted to the CSS file structure as long as it produces the desired results. Furthermore, the rendering intended in the browser is often checked and debugged with a document instance. Style sheets normally apply to a set of documents, therefore modifications added while focusing on a particular instance might affect other documents of the set.

We present a first prototype of static CSS semantical analyzer and optimizer that is capable of automatically detecting and removing redundant property declarations and rules. We build on earlier work on tree logics to locate redundancies due to the semantics of selectors and properties. Existing purely syntactic CSS optimizers might be used in conjunction with our tool, for performing complementary (and orthogonal) size reduction, toward the common goal of providing smaller and cleaner CSS files.

INTRODUCTION

Cascading style sheets (CSS) is one of the main components of web development, used to describe the aspect and format of a markup document, most of the time an HTML web page. The simplicity of its syntax makes it attractive for designers and amateurs as it only requires assigning values to properties under certain elements of the document.

However CSS language presents a set of combinatorial features that empower its possibilities, while inevitably making it more complex. A single document might use several style sheets, include embedded CSS under the style HTML element, or even use inline styles set directly as attributes of the element concerned. Furthermore, the language used to write selectors is very expressive. The combination of these features might lead to a series of semantical errors and redundancies that make it difficult to spot the origin of problems when one does not get the desired output in the browser. The tool we propose is aimed to help web developers in that matter, as well as reducing the style sheet size.

RELATED WORKS

In sharp contrast with existing debugging tools [START_REF] Liang | SeeSS: Seeing what i brokevisualizing change impact of cascading style sheets (CSS)[END_REF][START_REF] Mesbah | Automated analysis of CSS rules to support style maintenance[END_REF][START_REF]Firebug[END_REF][START_REF]Chrome developer tools[END_REF], we propose a method for automatically analysing and refactoring a CSS file, with the guarantee that the rendering in the browser will not be affected, for any possible document that might use the CSS. A highly novel aspect of our tool is that it is capable of performing CSS refactoring by a semantical analysis of a given CSS file, in the absence of any other information (such as a particular document instance). For this purpose, we build on our previous logical modeling of CSS selectors introduced in [START_REF] Genevès | On the analysis of cascading style sheets[END_REF]. The main difference between the present work and [START_REF] Genevès | On the analysis of cascading style sheets[END_REF] is that [START_REF] Genevès | On the analysis of cascading style sheets[END_REF] focuses on the detection of rendering bugs, whereas the present work seeks to perform automatic CSS size reduction while preserving the rendering semantics.

CSS ANALYSIS AND REFACTORING

In CSS, rules are encapsulated by a selector, that points to the set of elements that will be affected by the rule's declarations. We borrow ideas from the fields of set theory and tree logics to analyze the sets of elements pointed by the different selectors present in a CSS file. Our tool is concerned with the detection of semantical relations between CSS selectors. When some of these relations are detected, our tool might determine that a property declaration is unnecessary and it will thus be deleted, based on the specificity of selectors. In CSS, a selector's specificity is a vector of four integers (a, b, c, d), where a = 1 if the property is declared in a style attribute (a = 0 otherwise), b is the number of id attributes (of the form "# ") in the selector, c is the number of other attributes and pseudo-classes in the selector, and d is the number of element names and pseudo-elements in the selector. Our tool exploits the facts that: (1) if selectors of two different rules have the same specificity, then the last rule in the style sheet gains precedence; (2) when several selectors point to the same set of elements, then the declarations under the one with higher specificity gain precedence.

Containment of selectors

One fundamental relation between two CSS selectors is containment. For example we say that "ul > li" is contained into "li" since any "li" element with an "ul" parent is indeed a "li" element. The existence of containment relations is determined by the analysis of the nested structures of elements and the sets of attributes carried by elements. A selector such as "p.someclass" is contained into "p", since any "p" element with "class" attribute "someclass" is indeed a "p" element. These two kinds of containment can occur simultaneously as it is the case with "table td#someid" ⊂ "td". More generally, containment relates sets of pointed elements that are associated with selectors.

Given two selectors S b and Sp, S b is contained in Sp iff any element pointed by S b is also pointed by Sp. In this section we treat only proper containment, which means S b ⊂ Sp and not S b ⊆ Sp. Under these circumstances, for each property declared under both selectors, there are two different procedures according to the selector's specificity:

¦ ¥

Note that "table.foo" ⊂ "table" and the subset has a higher specificity (0, 0, 1, 1) against (0, 0, 0, 1) from the superset, so we are in the case of optimization 1. Consequently, we have to preserve the "color: #333" declaration as it will override the one from "table" when both rules apply. On the other hand, the "font-size" property statement can be removed from the subset as the same value is already pulled from the superset "table". The following code corresponds to the output of the analysis: Listing 2: containment output.css

¦ ¥

If "table" was more specific than "table.foo", optimization 2 would apply and the "color" property declaration could be erased from the subset too as its value would always be overridden by the dominant "#666" set in the superset.

Equivalence of selectors

Another relation between CSS selectors that can lead to some refactoring is equivalence. Two or more CSS selectors can be equivalent in several ways. Is not uncommon to find a rule Ri with a selector such as "body", and later in the same file another rule Rj with the same selector "body". Another case of equivalence could be a class selector ".classname" and the attribute selector "[class='classname']", or any similar case with the dual syntax for id attributes. These examples could be studied with basic string processing, but the logical and semantical analysis of selectors allows us to detect more complex equivalences too such as the one between selectors "p:nth-child(odd), p:nth-child(even)" and "p", as every paragraph is either odd or even.

Given two selectors Si and Sj, they are equivalent iff any element pointed by Si is also pointed by Sj and vice-versa. In this context there is only one procedure over the bodies: Refactoring 3. For each property declared under both selectors, delete the statements under the less specific selector.

To illustrate the analysis, let's look at the next listing: Listing 3: equivalence input.css

1 d i v#bar { f o n t -s t y l e : i t a l i c ;

¦ ¥

In this case we have two equivalent selectors, "div#bar" and "div[id='bar']" whose specificities are (0, 1, 0, 1) and (0, 0, 1, 1) respectively. For the properties declared under both rules, the values from "div#bar" will dominate, so the ones under "div[id='bar']" will never apply, as selectors point to the same set of elements. This means that for "font-style" and "border", the declarations can be safely erased from "div[id='bar']", resulting in the following output: Listing 4: equivalence output.css

Inheritance of properties

Whenever containment or equivalence relations are detected between selectors, several selectors point to the same elements, and specificity decides which declarations get precedence. In the context of inheritance, an element might be pointed by only one selector and yet be affected by declarations outside the concerning rule. This is because the declaration has been propagated from some ancestor through the inheritance mechanism. Consider a selector using a descendant combinator "Eanc > E desc " with a inheritable property declaration Pa : Va, and another selector "Eanc" with the same declaration. This statement might then be redundant as for E desc the property might inherited from E desc .

However we do not know if some document using this CSS file, presents a structure in which there is a certain element Ex placed in between Eanc and E desc , and the property declarations for Ex alter the property inheritance among Eanc and E desc . For example, a selector concerning only an attribute, such as "[input]", is free to be applied to any element on the document. Only certain CSS properties are inherited by default. Therefore, in our analyses, the amount of refactoring due to inheritance is a priori limited.

IMPLEMENTATION TECHNIQUES

Reasoning over selectors

Given two selectors, we intend to automatically check whether some containment or equivalence relation holds between them. For this purpose, we use the translation of CSS selectors into the tree logic described in [START_REF] Genevès | On the analysis of cascading style sheets[END_REF] and obtain logical formulas. We then formulate containment as logical implication, and test the formula for satisfiability using the logical solver of [START_REF] Genevès | Efficient static analysis of XML paths and types[END_REF]. For two selectors S1 and S2, Table 1 summarizes the tests performed, the four possible scenarios obtained according to the results, and the corresponding actions performed, as explained in section 3.1 and 3.2.

S1 ⊆ S2 S1 ⊇ S2 Relation Action 0 0 None None 0 1 S1 ⊃ S2 Refactoring 1, 2 1 0 S1 ⊂ S2 Refactoring 1, 2 1 1 S1 ⇔ S2 Rafactor 3
Table 1: Actions associated with detected relations.

Processing on declaration blocks

Once a relation between selectors S1 and S2 has been found, for each of the properties declared under both rules, we determine whether it is necessary or not, depending on three aspects: the relation between selectors, the selector's specificity, and whether the properties share the same value; as illustrated on examples in sections 3.1 and 3.2.

In some cases, the deletion of unnecessary property statements results in an empty rule. In this case, the whole rule is (safely) erased from the style sheet.

Optimization of elapsed time

In a style sheet with n rules, each rule can be tested against all rules but itself, adding up to a total of n × (n -1) possible tests. Given the diversity of elements in a HTML tree, tests concerning selector pairs such as "body" and "p" will not be uncommon. Only by adding a few basic pre checks, we will be able to determine the result of logical tests before actually processing it. We take advantage of two main observations for drastically reducing the number of pairwise tests:

1. If two selectors point to elements with syntactically different names, they will never be contained in each other, in any of the two possible containment directions.

2. If a selector S1 refers to one or more attributes that S2 does not, S1 will never contain S2.

Statistics tracking

The tool tracks some statistics about the analysis. First, while parsing it detects the total number of rules, the number of ignored ones, the number of possible tests, and the tests that were actually carried out. After all reasoning is done, the tool counts the number of relations between selectors, the modified rules, the number of deleted properties as well as the deleted bits. Finally, the time spent on each one of the analysis parts is also shown.

Room for improvements

Our prototype implements the aforementioned procedures for a significant CSS subset, sufficient for performing practical experiments with real-world style sheets. Our prototype can be improved in many respects, though. In particular, the library css-validator1 , that is used for parsing the CSS file and traversing the properties of the rules, could be improved. Some methods concerning comparisons of properties are not implemented, and thus some potential property deletions cannot be automatically carried out. It does not support browser specific properties yet. Some CSS selectors' features are not supported yet, such as grouping, pseudo-classes, pseudo-elements, multiple class and id selectors and media queries. Consequently, the concerning selectors are ignored. With their implementation, additional refactoring might be performed.

EXPERIMENTAL RESULTS

In order to get a representative collection of results, three different groups have been defined. The first group involves CSS code provided by frameworks and CMS, and is represented by Bootstrap, Joomla and JQuery. The second group consists in style sheets from complex web applications, and features Instagram, Twitter and The Times. Finally, we have extracted CSS files from some random web sites of medium complexity, which are ACM DL, DocEng, and Inovallée.

CSS Size Reduction in Practice

After processing the aforementioned files, the tool has spotted on average 4.95%2 of unnecessary properties, modifying 4.56% of the total rules. Of the relations found, 83.38% were containment ones, and the remaining 16.62% correspond to equivalence between selectors. It is clear that the style sheets from the first and second group present a low percentage of deleted properties (1.16% and 1.73% respectively). The same holds for the percentage of modified rules (1.59% for the first group and 2.19% for the second one). However, in the third group these numbers rise dramatically, reaching 11.05% of deleted properties and 16.95% of modified rules. Although these latter sites might not have involved as much testing as the first ones, they are not amateur web sites either.

Performance of the tool

The time taken to analyze each file is shown in Figure 2. A 34.30% of the rules have been ignored due to unsupported selectors commented in Section 4.5, and an average of 99.88%3 of the them has been discarded by the optimization mechanism described in Section 4.3. Each test between selectors requires a median of 156.71 ms, so without the optimization mechanism, each file analysis would have taken a median of 16.60 hours, in contraposition to the 78.16 seconds that were actually required, still guaranteeing the same results.

CONCLUSION

This paper presents a tool that automatically detects and removes unnecessary property declarations in CSS files, based on the analysis of semantical relations between selectors. We provide a first prototype implementation, with many perspectives for further development. Our method can constitute the core mechanism in several applications aimed to help developers code higher quality style sheets. A basic example could be a file processor where the user inputs a CSS file and gets as output an equivalent lighter file. The tool could also be integrated into more powerful components such as context features for web IDEs. In any scenario, the benefit of our tool is to conduct precise semantical analyses, that go far beyond the capabilities of purely syntactic analyses done by current CSS optimizers. Generating equivalent but simpler CSS files not only improves the time spent in loading and formatting a web page, but also facilitates the debugging process of style sheets. Despite the large number of unsupported features, the results obtained in section 5 already validate our approach: we have been able to detect large numbers of unnecessary property declarations in non-amateur web pages; and we have also found mistakes in the style sheets of some of the most popular web sites. The number of safe modifications can easily grow as more components of CSS are supported and more features are implemented, such as property inheritance, translation of pseudo-classes into query languages, analysis of media queries, merging of equivalent selectors or containment involving grouped selectors.

A perspective for further work consists in extending the number and the precision of our analyses by supporting constraints on the document structure when they are available (as a DTD/Schema, or via another formalism such as [START_REF] Benson | Cascading tree sheets and recombinant HTML: better encapsulation and retargeting of web content[END_REF]).

Refactoring 1 .Refactoring 2 . 5 t

 125 Subset more specific: delete the property declaration from S b only if it has the same value set under both S b and Sp. Subset less specific: delete the property declaration from S b , since the value set under Sp will always override the one under S b . For example, consider the following code snippet: Listing 1: containment input.css 1 t a b l e . f o o { c o l o r : #333; 2 f o n t -s i z e : 12 px ; 3 f o n t -w e i g h t : b o l d } 4 a b l e { c o l o r : #666; 6 f o n t -s i z e : 12 px }

1 t 4 t

 14 a b l e . f o o { c o l o r : #333; 2 f o n t -w e i g h t : b o l d } 3 a b l e { c o l o r : #666; 5 f o n t -s i z e : 12 px }

2 b 4 d

 24 o r d e r : none } 3 i v [ i d =' bar ' ] { c o l o r : #666; 5 f o n t -s t y l e : normal ; 6 b o r d e r : none }

1 d 4 d

 14 i v#bar { f o n t -s t y l e : i t a l i c ; 2 b o r d e r : none } 3 i v [ i d =' bar ' ] { c o l o r : #666 } ¦ ¥

Figure 1 :

 1 Figure 1: Refactoring performed.

Figure 2 :

 2 Figure 2: elapsed time (s)

Table 2 :

 2 Table 2 provides detailed information about the corresponding CSS file sizes and complexity. Dataset for the experiments.

	Name	# bytes # rules
	Bootstrap (Framework's CSS )	127343	805
	Joomla (Template Beez20's CSS)	30158	325
	JQuery (Framework's CSS)	32891	349
	Instagram (www.instagram.com)	123815	791
	The Times (www.thetimes.co.uk)	89362	469
	Twitter (www.twitter.com)	245473	2402
	ACM DL (dl.acm.org)	11151	97
	DocEng (www.doceng2014.org)	204970	1571
	Inovallée (www.inovallee.com)	29930	189

see http://jigsaw.w3.org/css-validator/

calculated over the properties that the tool supports.

calculated over considered tests, discarding ignored ones.

Work partly supported by ANR project Typex (ANR-11-BS02-007).