Rudolf Berghammer

Agnieszka Rusinowska
email: rusinowska@gate.cnrs.fr

Harrie De Swart

An Interdisciplinary Approach to Coalition Formation

Keywords: JEL Classification: D85, C63, C88, D71, D72 Graph theory, RelView, relational algebra, dominance, stable government

A stable government is by definition not dominated by any other government. However, it may happen that all governments are dominated. In graph-theoretic terms this means that the dominance graph does not possess a source. In this paper we are able to deal with this case by a clever combination of notions from different fields, such as relational algebra, graph theory and social choice theory, and by using the computer support system RelView for computing solutions and visualizing the results. Using relational algorithms, in such a case we break all cycles in each initial strongly connected component by removing the vertices in an appropriate minimum feedback vertex set. In this way we can choose a government that is as close as possible to being un-dominated. To achieve unique solutions, we additionally apply the majority ranking recently introduced by Balinski and Laraki. The main parts of our procedure can be executed using the RelView tool. Its sophisticated implementation of relations allows to deal with graph sizes that are sufficient for practical applications of coalition formation.

Introduction

In Rusinowska et al. [START_REF] Rusinowska | A new model of coalition formation[END_REF] a government is defined as a pair consisting of a coalition (a set of of parties) and a policy. Different governments may have different utilities (values) for the different parties. In Berghammer et al. [START_REF] Berghammer | Applying relational algebra and RelView to coalition formation[END_REF] we have shown how the notion of 'government g dominates government h' can be described in terms of relational algebra. This enabled us to use the Kiel RelView tool for computing and visualizing the dominance relation. The governments that are un-dominated are by definition the stable ones.

Unfortunately, in practical applications stable government may not exist. In this paper we continue the work of Berghammer et al. [START_REF] Berghammer | Applying relational algebra and RelView to coalition formation[END_REF] and deal with the problem what to do when there is no un-dominated government. Using graphtheoretic terms this means that the dominance graph does not possess a source. By a clever combination of well known concepts from different domains (relational algebra, the RelView tool for the manipulation and visualization of relations, graph theory, and the recently introduced majority ranking of [START_REF] Balinski | A Theory of Measuring, Electing and Ranking[END_REF]) we are able to deal with this case and to choose a government which is as close as possible to stable. As in Berghammer et al. [START_REF] Berghammer | Applying relational algebra and RelView to coalition formation[END_REF], the decisive parts of our procedure are formulated as relational expressions and programs, respectively, so that RelView can be used for executing them and for visualizing the results.

The remainder of the paper is organized as follows. In Section 2 we present the model of coalition formation. Section 3 introduces some preliminaries from relational algebra, gives an overview on RelView, and recalls the method of Berghammer et al. [START_REF] Berghammer | Applying relational algebra and RelView to coalition formation[END_REF] for computing the dominance relation with the help of this tool. Section 4 forms the core of the paper. We describe a general procedure for choosing a government in the case that there is no stable one. In the graph theoretical part we compute initial strongly connected components and minimum feedback vertex sets. If our procedure results in more than one government, we apply the recently introduced majority ranking of [START_REF] Balinski | A Theory of Measuring, Electing and Ranking[END_REF] to select one of them.

The Model of Coalition Formation

In this section, we briefly recall some of the main ideas of the model of coalition formation presented in Rusinowska et al. [START_REF] Rusinowska | A new model of coalition formation[END_REF], i.e., the notions essential for the application of relational algebra and RelView to the model. Let N be the finite set of political parties and P be the finite set of all policies. A set of parties, i.e., an element of the powerset 2 N , is called a coalition. We define a government as a pair consisting of a coalition and a policy. Hence,

G := { (S, p) | S ∈ 2 N ∧ p ∈ P }
denotes the set of all governments. Usually, we assume that only a majority coalition (i.e., a coalition with more than half of the total number of seats in Parliament) can form a government. Nevertheless, one may easily imagine a government formed by a minority coalition.

Each party is assumed to have preferences on all policies and on all coalitions. Then a coalition is called feasible if it is acceptable to all its members. A policy is feasible for a given coalition if it is acceptable to all members of that coalition and a government is said to be feasible if it consists of a feasible coalition and a policy feasible for that coalition. By G * we denote the set of all feasible governments:

G * := { g ∈ G | G is feasible } .
For each i ∈ N , we assume a utility function U (i) : G → R, where U (i) (g) denotes the utility (or value) of the government g ∈ G to party i ∈ N . A precise description of the utility of a government to a party has been given in Rusinowska et al. [START_REF] Rusinowska | A new model of coalition formation[END_REF]. In Roubens et al. [START_REF] Roubens | Using MacBeth to determine utilities of governments to parties in coalition formation[END_REF], the MacBeth technique has been applied to determine these utilities.

A feasible government g = (S, p) ∈ G * dominates a feasible government h ∈ G * (denoted as g h) if the property

(∀ i ∈ S : U (i) (g) ≥ U (i) (h)) ∧ (∃ i ∈ S : U (i) (g) > U (i) (h))
holds. We call " " the dominance relation and the directed graph (G * , ) the dominance graph. A feasible government is said to be stable if it is dominated by no feasible government. By

SG * := {g ∈ G * | ¬ ∃ h ∈ G * : h g}
we denote the set of all (feasible) stable governments. Using graph-theoretic terminology, SG * is the set of all sources (or initial vertices) of the dominance graph.

In Rusinowska et al. [START_REF] Rusinowska | A new model of coalition formation[END_REF] necessary and sufficient conditions for the existence and the uniqueness of stable governments are investigated and, in addition, some variants of the notion of stability are discussed. All this shows that the above definition seems to be the most natural one. Therefore, we also use it in the present paper.

Computing the Dominance Relation with RelView

In this section, we first present the basics of relational algebra and indicate how sets can be modeled. For more details, see e.g., Schmidt and Ströhlein [START_REF] Schmidt | Discrete Mathematics for Computer Scientists[END_REF] or Brink et al. [START_REF]Relational Methods in Computer Science[END_REF]. After a short introduction to the RelView tool, we then recall how the dominance relation can be computed and visualized with this tool.

Relational Algebra and RelView

If X and Y are sets, then a subset R of the Cartesian product X × Y is called a (binary) relation with domain X and range Y . We denote the set (in this context also called type) of all relations with domain X and range Y (i.e., the powerset of

X × Y ) by [X ↔ Y ] and write R : X ↔ Y instead of R ∈ [X ↔ Y ]. If X and
Y are finite sets of size m and n respectively, then we may consider a relation R : X ↔ Y as a Boolean matrix with m rows and n columns. The Boolean matrix interpretation of relations is well suited for many purposes and also used as one of the graphical representations of relations within the RelView tool. Therefore, in this paper we often use Boolean matrix terminology and notation. In particular, we write R x,y instead of x, y ∈ R or x R y.

In the present paper we will use the following basic operations on relations: R (complement), R ∪ S (union), R ∩ S (intersection), R T (transposition) and R; S (composition). Complement, union, and intersection are the set-theoretic operations on the complete Boolean lattices [X ↔ Y ]. Hence, for all x ∈ X and y ∈ Y we have R x,y if and only if ¬R x,y , (R ∪ S) x,y if and only if R x,y or S x,y , and (R ∩ S) x,y if and only if R x,y and S x,y . The transposition R T of a relation R : X ↔ Y has type [Y ↔ X] and is defined by the equivalence of R x,y and R T y,x for all x ∈ X and y ∈ Y . A composition R; S is only defined if the range of R coincides with the domain of S. In the case R : X ↔ Y and S : Y ↔ Z we have the typing R; S : X ↔ Z and for all x ∈ X and z ∈ Z that (R; S) x,z if and only if there exists y ∈ Y such that R x,y and S y,z .

Besides the above basic operations we will use the special relations O (empty relation), L (universal relation), and I (identity relation), one for each type. Here we overload the symbols. This means that we avoid the binding of the types to the symbols for these special relations via subscripts (as in O XY ) or superscripts (as in O XY ). This is due to the fact that the types can be re-constructed from the context. The first two constants O and L are the smallest and greatest element of the complete Boolean lattices [X ↔ Y ], respectively, the third one I is the relation-level equivalent of set-theoretic equality. The latter means that each of the equal designated relations I has a type of the form [X ↔ X] and is defined by the equivalence of I x,y and x = y, for all x, y ∈ X.

If R : X ↔ Y is included in S : X ↔ Y we write R ⊆ S and equality of R and S is denoted as R = S. Hence, R ⊆ S if and only if for all x ∈ X and y ∈ Y from R x,y it follows that S x,y and R = S if and only if for all x ∈ X and y ∈ Y both properties even are equivalent.

By R * we denote the reflexive-transitive closure of a relation R : X ↔ X. This closure is introduced via the equation R * = i≥0 R i , where the powers R i of R are inductively defined by R 0 = I and R i+1 = R; R i . Applying graphtheoretic terminology we obtain that R *

x,y if and only if there is a path from the vertex x to the vertex y in the directed graph (X, R).

Relational algebra offers some simple and elegant ways to describe subsets of a given set or, equivalently, predicates on this set. In this paper we will use vectors, membership-relations, and injective embeddings for this task.

A vector v is a relation v with v = v; L. In the Boolean matrix model this condition means that each row either consists of 'true' entries only or consists of 'false' entries only. As for a vector, therefore, the range is irrelevant, we consider in the following mostly vectors v : X ↔ 1 with a specific singleton set 1 := {⊥} as range and omit in such cases the second subscript, i.e., write v x instead of v x,⊥ . Analogously to linear algebra we will use lower-case letters to denote vectors. A vector v : X ↔ 1 can be considered as a Boolean matrix with exactly one column, i.e., as a Boolean column vector, and describes (or is a description of) the subset {x ∈ X | v x } of X. If a vector describes a singleton set, i.e., an element of its domain, it is called a point.

As a second way to model sets we will use the relation-level equivalents of the set-theoretic symbol "∈", i.e., membership-relations M : X ↔ 2 X . These specific relations are defined by M x,Y if and only if x ∈ Y , for all x ∈ X and Y ∈ 2 X . A Boolean matrix representation of M requires exponential space. However, in Berghammer et al. [START_REF] Berghammer | Implementation of relational algebra using binary decision diagrams[END_REF] an implementation of M using ordered binary decision diagrams is presented, the number of vertices of which is linear in the size of X.

If the vector v describes a subset Y of X, then inj (v) : Y ↔ X denotes the injective embedding of Y into X. This means that for all y ∈ Y and x ∈ X we have inj (v) y,x if and only if y = x. A combination of injective embeddings and membership-relations allows a column-wise enumeration of sets of subsets. More specifically, if v describes a subset S of 2 X in the sense defined above, then for all x ∈ X and Y ∈ S we have (M; inj (v)

T ) x,Y if and only if x ∈ Y . Using matrix terminology this means that the elements of S are described precisely by the columns of the relation M; inj (v)

T of type [Y ↔ X]. Relational algebra has a fixed and surprisingly small set of constants and operations which (in the case of finite carrier sets) can be implemented very efficiently. At Kiel University we have developed a computer system for the visualization and manipulation of relations and for relational prototyping and programming, called RelView. The tool is written in the C programming language, uses ordered binary decision diagrams for implementing relations, and makes full use of the X-windows graphical user interface. Details and applications can be found, for instance, in Berghammer et al. [START_REF] Berghammer | Relation-algebraic analysis of Petri nets with RelView[END_REF], Behnke et al. [START_REF] Behnke | RelView -A system for calculation with relations and relational programming[END_REF], Berghammer et al. [START_REF] Berghammer | Implementation of relational algebra using binary decision diagrams[END_REF], and Berghammer et al. [START_REF] Berghammer | RelView and Rath -Two systems for dealing with relations[END_REF].

The main purpose of RelView is the evaluation of relation-algebraic expressions. These are constructed from the relations of its workspace using predefined operations and tests, user-defined relational functions, and user-defined relational programs. A relational program is much like a function procedure in the programming languages Pascal or Modula 2, except that it only uses relations as data type. It starts with a head line containing the program name and the formal parameters. Then the declaration of the local relational domains, functions, and variables follows. Domain declarations can be used to introduce projection relations and pairings of relations in the case of Cartesian products, and injection relations and sums of relations in the case of disjoint unions, respectively. The third part of a program is the body, a while-program over relations. As a program computes a value, finally, its last part consists of a return-clause, which is a relation-algebraic expression whose value after the execution of the body is the result.

Computing and Visualizing Dominance

In Berghammer et al. [START_REF] Berghammer | Applying relational algebra and RelView to coalition formation[END_REF] we have developed a relation-algebraic specification of dominance and stability. To this end, we supposed a relational description of government membership and the parties' utilities to be given. The first means that we have a relation M : N ↔ G * at hand such that for all i ∈ N and g ∈ G * M i,g ⇐⇒ party i is a member of government g; the second means that we have for each party i ∈ N a relation R (i) :

G * ↔ G * at hand such that for all g, h ∈ G * . R (i) g,h ⇐⇒ U (i) (g) ≥ U (i) (h) . Based on the relations R (i) , i ∈ N , we first introduced a global utility (or comparison) relation C : N ↔ G * ×G * by demanding for all i ∈ N and g, h ∈ G * C i, g,h ⇐⇒ R (i) g,h
and transformed this component-based specification into a relation-algebraic (i.e., component-free) one. Then we proved the following fact:

If π : G * ×G * ↔ G * and ρ : G * ×G * ↔ G * are the projection relations of the direct product G * × G * and the vector DomVec(M, C) : G * ×G * ↔ 1 is defined by DomVec(M, C) = (π; M T ∩ C T ); L ∩ (π; M T ∩ E; C T ); L , (1)
where (

E := ρ; π T ∩ π; ρ T : G * ×G * ↔ G * ×G * is the so-called exchange relation 1 , then we have for all g, h ∈ G * ×G * that DomVec(M, C) g,h if and only if g h. Hence, equation (1)
Both equations ( 1) and ( 2) can be used for specifying relation-algebraically the vector description StabVec(M, C) : G * ↔ 1 of the set SG * of all stable governments. We used (1) and arrived after some steps at

StabVec(M, C) = ρ T ; DomVec(M, C) . ( 3
)
We immediately could transform the three relation-algebraic specifications (1), ( 2 Here the first declaration introduces Prod as a name for the direct product G * × G * . Using Prod, the projection relations and the exchange relation are then computed by the three assignments of the body and stored as pi, rho, and E, respectively. The return-clause of the program consists of a direct translation of (1) into RelView-syntax, where ^, -, &, and * denote transposition, complement, intersection, and composition, and, furthermore, the operation dom computes for a relation R : X ↔ Y the vector R; L : X ↔ 1.

Similarly, by straightforward translations we obtained RelView-implementations of the remaining two relation-algebraic specifications.

Here is the RelView-code for specification (

The Case of no Stable Government

Having computed the dominance relation, three cases may occur: there are multiple stable governments, there is exactly one stable government, and a stable government may not exist. Based on the situation in Poland after the 2001 elections, in Berghammer et al. [START_REF] Berghammer | Applying relational algebra and RelView to coalition formation[END_REF] we obtained an example for the first case, viz. a dominance graph with three sources, representing the three different stable governments. In such a situation one might allow negotiations in order to choose a government from among the stable ones; see Rusinowska and de Swart [START_REF] Rusinowska | Negotiating a stable government -an application of bargaining theory to a coalition formation model[END_REF]. An alternative is to select a specific stable government that may be considered as more attractive than the other stable ones via the majority ranking, recently introduced by Balinski and Laraki [START_REF] Balinski | A Theory of Measuring, Electing and Ranking[END_REF], see Sections 4.5 and 4.6.

If there is exactly one stable government (i.e., one source), then obviously this one has to be selected.

In the remainder of this section we continue the work of Berghammer et al. [START_REF] Berghammer | Applying relational algebra and RelView to coalition formation[END_REF] and concentrate on the third case of no stable government. This means that the dominance graph has no source, like in the RelView-picture of Fig. 1. The situation described by this graph appears if we change the utilities of the example of Berghammer et al. [START_REF] Berghammer | Applying relational algebra and RelView to coalition formation[END_REF] a little bit. As in the original case, for reasons of clearness the picture shows a transitive reduction of the dominance graph only, i.e., a minimal subgraph such that the reflexive-transitive closures of the subgraph and of the original graph coincide.

Assuming that a computed dominance graph has no source, in Section 4.1 we first describe our procedure to select a government as close as possible to being stable. After that we go into details and show how to compute initial strongly connected components (Section 4.2) and minimum feedback vertex sets relationalgebraically (Section 4.3). In Section 4.4 we demonstrate the application of our procedure to Fig. 1. If our procedure yields several governments that are as close as possible to being stable, as is the case in our example, we use the majority ranking of [START_REF] Balinski | A Theory of Measuring, Electing and Ranking[END_REF] to select the 'most preferred' one of them. In Section 4.5 we apply the majority ranking of Balinski and Laraki to our example. This will help to understand in Section 4.6 the general description of the majority ranking and some of its nice properties.

The General Approach

If the computed dominance graph has no source, i.e., there exists no stable government, the central question is which government should be chosen. In this section we answer this question by proposing a procedure for choosing a government that can be considered as close as possible to being stable.

As a whole, our proposal is presented below. In it, we apply some well-known concepts from graph theory. First, we use strongly connected components (SCCs), i.e., maximal sets of vertices such that each pair of vertices is mutually reachable. Especially we are interested in SCCs without arcs leading from outside into them. These SCCs are said to be initial . We also use minimum feedback vertex sets, where a feedback vertex set (FVS) is a set of vertices that contains at least one vertex from every cycle of the graph. And here is our procedure: If there is more than one candidate, use the majority ranking of [START_REF] Balinski | A Theory of Measuring, Electing and Ranking[END_REF] to select the 'most preferred' one. 3. If there is more than one set in I, select the final stable government from the results of the second step by applying the majority ranking of [START_REF] Balinski | A Theory of Measuring, Electing and Ranking[END_REF] again.

An outgoing arc of the dominance graph denotes that the government in question dominates another one and an ingoing arc denotes that the government in question is dominated by another one. Hence the governments of an initial SCC can be seen as a cluster which is not dominated from outside.

For each initial strongly connected component, we compute in step 2 the set of all minimum feedback vertex sets, where a minimum feedback vertex set is a minimal set of vertices which breaks all cycles. Next, we choose a specific minimum feedback vertex set according to the following rule. First, we choose the set(s) for which the number of ingoing arcs is maximal. Since an ingoing arc denotes that a government is dominated, such a choice means selecting governments dominated most frequently. Next, if there are at least two such sets, we choose one for which the number of outgoing arcs is minimal, meaning the choice of the governments which dominate other governments least frequently.

Next, we break all cycles by removing the chosen set of governments. This corresponds to a removal of those candidates which are 'least attractive' for two reasons: because they are most frequently dominated and they dominate other governments least frequently. In Section 4.4 we will apply this approach to the example given in Fig. 1.

At this place it should be mentioned that the application of steps 1 and 2 may not lead to a unique solution. In this case we proceed as in the case of multiple stable governments to select the final government from among the 'graph-theoretical' results, see Sections 4.5 and 4.6.

Computing Initial Strongly Connected Components

Given a finite graph (V, R) with relation R : V ↔ V for the arcs, the SCCs of (V, R) are precisely the equivalence classes of the equivalence relation R * ∩(R T ) * . The following RelView-program Classes for column-wisely enumerating the equivalence classes of an equivalence relation S : X ↔ X has been published in Berghammer and Fronk [START_REF] Berghammer | Considering design tasks in OO-software engineering using relations and relation-based tools[END_REF]. In it, the calls Ln1(S) and On1(S) compute the universal vector L : X ↔ 1 and the empty vector O : X ↔ 1, respectively, the call point(v) yields one of the points contained in the non-empty vector v, and the operation + computes the relational sum. In matrix terminology the latter means that it puts the matrices one upon the other, so that the RelView-expression (C^+ c^)^of Classes 'concatenates' the matrix C and the vector c. The RelView-expression incl(R*c,c) of InitSccs tests whether the vector R*c (describing the predecessors of c with respect to R) is contained in c which, in words, exactly means that the SCC described by c is initial.

Computing Minimum Feedback Vertex Sets

The following relation-algebraic computation of minimum FVSs follows the lines of Berghammer and Fronk [START_REF] Berghammer | Exact computation of minimum feedback vertex sets with relational algebra[END_REF]. As in Section 4.2 we assume that (V, R) is a finite graph with relation R :

V ↔ V .
Let M : V ↔ 2 V be the membership-relation on vertices. In a first step we reduce the computation of the FVSs to the computation of simple cordless cycles, i.e., simple cycles c which do not contain a pair x, y of vertices that forms an arc in (V, R) but not an arc in c. Since a set F of vertices is a FVS if and only if it contains a vertex from every simple chordless cycle (Berghammer and Fronk [START_REF] Berghammer | Exact computation of minimum feedback vertex sets with relational algebra[END_REF]), it suffices to enumerate column-wisely the vertex sets of the simple chordless cycles of (X, R) via a relation K : V ↔ C, where C denotes the set of vertex sets of the simple chordless cycles. Assuming K to be at hand, for all F ∈ 2 V we are able to calculate as follows (where c ranges over the simple chordless cycles and S ranges over C):

F is a FVS ⇐⇒ ∀ c : ∃ x : x ∈ F ∧ x vertex of c ⇐⇒ ∀ S : ∃ x : M x,F ∧ K x,S ⇐⇒ ¬∃ S : M T ; K F S ∧ L S ⇐⇒ M T ; K; L F
This calculation yields M T ; K; L : 2 V ↔ 1 as the vector representation of all FVSs of (V, R). Next we apply that the vector v∩Q; v describes the least elements of the set described by the vector v with respect to the preorder Q; see e.g., Schmidt and Ströhlein [START_REF] Schmidt | Discrete Mathematics for Computer Scientists[END_REF]. If we use the above vector as v, the size comparison relation on 2 V as Q, and implement the expressions developed so far in RelView, we obtain the following program for computing the vector description of the minimum FVSs from the relation K:

MfvsVec(K) DECL LeEl(Q,v) = v & -(-Q * v)); DECL M BEG M = epsi(O(K)) RETURN LeEl(cardrel(O(K)),-dom(-(M^*K))) END.
From this program we obtain a program for the column-wise enumeration of the minimum FVSs by applying the technique described in Section 3.1.

We call a set S of vertices of (V, R) progressively infinite if it is non-empty and for each vertex x ∈ S there exists a successor y ∈ S. Fundamental for obtaining a relation-algebraic specification of the relation K : V ↔ C (a task we still have to solve) is the following fact (Berghammer and Fronk [START_REF] Berghammer | Exact computation of minimum feedback vertex sets with relational algebra[END_REF]): S is the vertex set of a simple chordless cycle if and only if it is a minimal progressively infinite set. Thus, our next goal is identified. We have to develop a RelView-program, say MprinfVec, that computes the vector description of the minimal progressively infinite sets. Then the technique of Section 3.1 shows that K is computed by

M * inj(MprinfVec(R))^.
In order to obtain a vector that describes the minimal progressively infinite sets, we first neglect minimality and calculate for a set S of vertices as follows:

S progr. infinite ⇐⇒ (∃ x : x ∈ S) ∧ (∀ x : x ∈ S → ∃ y : y ∈ S ∧ R x,y ) ⇐⇒ (∃ x : M x,S ) ∧ (∀ x : M x,S → ∃ y : M y,S ∧ R x,y ) ⇐⇒ (∃ x : L ⊥,x ∧ M x,S ) ∧ (∀ x : M x,S → (R; M) x,S ) ⇐⇒ (L; M) ⊥,S ∧ (¬∃ x : L ⊥,x ∧ M x,S ∧ R; M x,S ⇐⇒ (L; M) T S ∧ L; (M ∩ R; M) ⊥,S ⇐⇒ ((L; M) T ∩ L; (M ∩ R; M) T ) S Hence, (L; M) T ∩ L; (M ∩ R; M) T : 2 V ↔ 1 is a vector description of the progres-
sively infinite sets of the graph (V, R). Minimalization now is obtained by using two well known results: M T ; M : 2 V ↔ 2 V relation-algebraically specifies set inclusion on 2 V and the vector v ∩ (Q T ∩ I)v describes the minimal elements of the set described by the vector v with respect to the preorder Q; see again Schmidt and Ströhlein [START_REF] Schmidt | Discrete Mathematics for Computer Scientists[END_REF]. If we combine these facts with the vector description of the progressively infinite sets and formulate the result in RelView-syntax, we arrive

MprinfVec(R) DECL Min(Q,v) = v & -((Q^& -I(Q)) * v); M, SI, L BEG M = epsi(O(R)); SI = -(M^* -M); L = L1n(R) RETURN Min(SI, (L*M)^& -(L * (M & -(R*M)))^) END.
The bottleneck of this program is the use of set inclusion since the size of the ordered binary decision diagrams of this relation is exponential in the size of the base set. Using the present RelView-version it can be only applied to graphs with up to approximately 30 vertices. As we apply it, however, only to initial SCCs, this usually suffices for practical applications of coalition formation. It still should be mentioned that Berghammer and Fronk in [START_REF] Berghammer | Considering design tasks in OO-software engineering using relations and relation-based tools[END_REF] develop a refinement of our programs that avoids the use of set inclusion and can be used for graphs consisting of about 100 vertices in general and even more in advantageous cases.

The Example Revisited

In the following, we want to demonstrate an application of the RelViewprograms we have developed so far. As input we assume the dominance relation, the transitive reduction of which graphically is depicted in Fig. 1.

Following the general procedure of Section 4.1, in the first step we have to compute the initial SCCs using the RelView-program InitSccs of Section 4.2. The graph of Fig. 1 possesses exactly one initial SCC. Its RelView-representation as Boolean vector is shown on the right-hand side of Fig. 2. To give an impression how a column-wise enumeration of sets of subsets looks in RelView, on the left-hand side of the figure we additionally show the six SCCs of the input as 17 × 6 matrix. In both cases labels are added to rows and columns by a specific feature of the tool for illustration purposes. In RelView a black square of a Boolean matrix means 'true' and a white square means 'false'. Hence, the That {8, 16} and {8, 12} are indeed the only minimum FVS hopefully becomes clear if we consider Fig. 4. It shows two copies of the input graph of Fig. 1. In both cases we have instructed RelView to draw the vertices of the initial SCC as squares and additionally to indicate a minimum FVS by the colour black. In the graph on the left-hand side we identify the minimum FVS {8, 16} and in the other graph the minimum FVS {8, 12}. From Fig. 4 we also see that five arcs lead from outside into the FVS {8, 12}, but only four arcs lead from outside into {8, 16}. Hence, by Steps b) and c) of the general procedure we have to remove the vertices 8 and 12 from the graph, which leads to 16 and 17 as new sources, i.e., as governments that can be considered as being as close as possible to stable. What government finally is chosen is determined by applying the majority ranking, recently introduced by Balinski and Laraki in [START_REF] Balinski | A Theory of Measuring, Electing and Ranking[END_REF].

Application of the Majority Ranking

According to the procedure described in Section 4.1, if the application of graph theory does not give a unique solution, we select the final government from among the 'graph-theoretical' results by applying the majority ranking, recently introduced by M. Balinski and R. Laraki [START_REF] Balinski | A Theory of Measuring, Electing and Ranking[END_REF].

They blame Arrow's impossibility results on the fact that the social choice or welfare functions take individual orderings of the alternatives as input. But in general the individual agents do not speak the same language: when agent 1 says that he prefers A to B he may mean something quite different than when agent 2 says the same thing; agent 1 may mean that A is slightly better than B, while agent 2 may mean that A is fine but B is repulsive. So, Balinski and Laraki argue that it is no surprise that different election mechanisms yield different outcomes and that there is no social choice or welfare function that satifies all of some well-known properties. By looking at contests in real life, they realized that the agents should speak the same language by sharing a common grading system, for instance the rankings {A, B, C, D, E} in the American school system. And they proved that in this new framework a unique social grading function exists that has very nice properties.

Note that by giving grades to the alternatives in some common grading system much more information is provided by the voters/judges than in the case of giving rankings of the alternatives.

First, we will demonstrate Balinski and Laraki's procedure in our example above and next we will describe their procedure in more general terms.

In the example of Section 4.4 there was no undominated government. By applying 'graph-theoretical' techniques we found two governments g 16 = (AC, p 16 ) and g 17 = (AB, p 17 ) that are as stable as possible in the sense specified in Section 4.1; here {A, C} is the coalition of g 16 and p 16 denotes the policy of g 16 ; similarly for AB and p 17 in g 17 . The dominance graph in our example shows which governments dominate other governments, where domination is defined in terms of the utilities U I (g) of the different governments g for the different parties I. The utilities may have been obtained by the MacBeth software (see [START_REF] Roubens | Using MacBeth to determine utilities of governments to parties in coalition formation[END_REF]), on a fixed grading scale, say from 0 till 100. Let us assume that for party A we have the utilities This gives rise to the following majority ranking: g 16 maj g 17 . So, in our example g 16 is the most preferred, as stable as possible, government to be chosen from the seventeen available non-stable governments.

General Description of the Majority Ranking

As in the traditional framework of Arrow, there is a finite set C of m competitors, governments in our case, a 1 , . . . , a m , and a finite set J of n judges, in our case parties, 1, . . . , n. Furthermore, a common language L is required, in our case the fixed set of possible utilities {0, 1, . . ., 100}. L is a set of strictly ordered grades r n , and may be finite or an interval of the real numbers. We take r i r j to mean that r i is a higher grade than r j or r i = r j . The input for a social grading function (SGF) is then a m by n matrix, called a profile, filled with grades (i.e., elements of L), meaning that every competitor (m rows) is given a grade by every judge (n columns). A method of grading is a function F that assigns to every profile one output, called the final grade, which is an m-tuple of grades (one grade for each competitor, following the order of competitors used in the input matrix).

A function f from n-tuples (the grades given to a competitor by the n judges) to a single grade, the final grade of the competitor, is called an aggregation function if and only if it satisfies the conditions of Anonymity, Unanimity and Monotonicity (see [START_REF] Balinski | A Theory of Measuring, Electing and Ranking[END_REF]).

Balinski and Laraki formulate the following six properties for a Social Grading Function: Neutrality, Anonymity, Unanimity, Monotonicity, IIA and Continuity (see [START_REF] Balinski | A Theory of Measuring, Electing and Ranking[END_REF]) and prove the following Theorem.

Theorem A method of grading F satisfies the six properties just mentioned if and only if there exists an aggregation function f such that the output of F is given by applying f to all the competitors in the input matrix (profile) of F . So, we have the following picture: Balinski and Laraki conclude that these order functions are demonstrably best for aggregating. In particular they are very good at avoiding or minimizing manipulability ( [START_REF] Balinski | A Theory of Measuring, Electing and Ranking[END_REF]).

There are many order-functions. But one in particular is clearly superior to all its competitors, namely the middlemost aggregation function f . Suppose r 1 ≥ r 2 ≥ . . . ≥ r n . A middlemost aggregation function f is defined by:

f (r 1 , . . . , r n ) = r (n+1)/2
when n is odd, and

r n/2 ≥ f (r 1 , . . . , r n ) ≥ r (n+2)/2
when n is even. So, when n is odd the order function f (n+1)/2 is the middlemost aggregation function. When n is even, there are infinitely many. In particular f n/2 is the upper-middlemost and f (n+2)/2 the lower-middlemost aggregation function. Any grade not bounded by the middlemost aggregation functions is condemned by an absolute majority of judges as either too high or too low. And the middlemost aggregation functions have nice properties, see [START_REF] Balinski | A Theory of Measuring, Electing and Ranking[END_REF].

The majority-grade f maj is defined by: f (n+1)/2 when n is odd, and f (n+2)/2 when n is even.

We now have a method to grade. The new model now allows us to use this grading method to construct a ranking method (the traditional framework of Arrow did not offer this option).

The majority-ranking maj is defined as follows:

a i maj a j := f maj (a i ) > f maj (a j ) If f maj (a i ) = f maj (a j ), then the majority-grade is dropped from the grades of both competitors and the procedure is repeated for these alternatives.

Balinski and Laraki prove that the majority-ranking has a number of nice properties, among which the following.

Theorem The majority-ranking always ranks one competitor ahead of another unless the judges have assigned the two competitors identical grades.

In obtaining these results, it is crucial that there is a common language for the judges to use. When there is no common language, the only meaningful input a judge can give is the order of his preferences, which is a serious loss of information and in fact brings us back to the old framework of social choice theory. In this case, the impossibility theorems of social choice theory [START_REF] Arrow | Social Choice and Individual Values[END_REF] also resurface.

Conclusions

The central concepts of the coalition formation model are the notion of (feasible) government and the notion of stable government. The latter is defined as a feasible government dominated by no feasible government. In the present paper, we aim to answer the question which government should be chosen if there is no stable government (that is, if the dominance graph has no source).

The attractiveness and novelty of our approach consists in: 1. the clever combination of notions from partly different domains (relational algebra, graph theory and very recent methods from social choice theory), and 2. the immediate and easy support by the computer system RelView for computing solutions and for visualizing the results.

Starting from a situation in which there is no stable government, the procedure given in Section 4.1 breaks all cycles in each initial strongly connected component by removing the vertices in an appropriate minimum feedback vertex set; this corresponds to a removal of those candidates which are 'least attractive' for two reasons: because they are most frequently dominated and they dominate other governments least frequently. In this way our procedure selects one or more governments that are as close as possible to being stable.

In case that our procedure yields more than one possible outcome, we select the final government (from the results of the procedure described above) by applying the majority ranking, recently introduced by Balinski and Laraki [START_REF] Balinski | A Theory of Measuring, Electing and Ranking[END_REF]. In this way we select, in case there is no stable government, a unique, most preferred, government which is as close as possible to being stable.

Of course, the majority ranking may also be used in case there is more than one stable government in order to select the most preferred of them.

  is a relation-algebraic specification of the dominance relation with the government membership relation M and the global utility relation C as its input. Strictly speaking, according to (1) dominance is specified as a vector of type [G * ×G * ↔ 1]. But what we really wanted is a specification as a relation of type [G * ↔ G * ]. So, we additionally had to apply the technique of Schmidt and Ströhlein [16] for transforming a vector with a direct product as domain into the corresponding relation. Doing so, we obtained a relation-algebraic specification DomRel (M, C) : G * ↔ G * of the dominance relation by DomRel (M, C) = π T ; (ρ ∩ DomVec(M, C); L) .

  ), and (3) into the programming language of RelView. In the first case the result is the following program: DomVec(M,C) DECL Prod = PROD(M^*M,M^*M); pi, rho, E BEG pi = p-1(Prod); rho = p-2(Prod); E = rho*pi^& pi*rhoR ETURN -dom(pi*M^& -C^) & dom(pi*M^& E*-C^) END.

  2): DomRel(M,C) DECL Prod = PROD(M^*M,M^*M); pi, rho BEG pi = p-1(Prod); rho = p-2(Prod) RETURN pi^* (rho & DomVec(M,C) * L1n(C)) END. A translation of specification (3) into the programming language of the tool, finally, led to the following relational program: StabVec(M,C) DECL Prod = PROD(M^*M,M^*M); rho BEG rho = p-2(Prod) RETURN -(rho^* DomVec(M,C)) END. The operation L1n of the RelView-program DomRel computes for a relation R : X ↔ Y the universal relation L of the specific type [1 ↔ Y ], in matrix terminology hence a Boolean universal row vector.

Fig. 1 .

 1 Fig. 1. Dominance without a stable government

1 .

 1 Compute the I of all initial SCCs of the dominance graph. 2. For each SCC C from I do: a) Compute the set F of all minimum FVSs of the subgraph generated by the vertices of C. b) Select from all sets of F with a maximal number of ingoing arcs one with a minimal number of outgoing arcs. We denote this one by F . c) Break all cycles of C by removing the vertices of F from the dominance graph. d) Select an un-dominated government from the remaining graph.

Classes

  (v) DO c = S * point(v); IF isempty(C) THEN C = c ELSE C = (C^+ c^)^FI; v = v & -c OD RETURN C END Using the operation rtc for computing reflexive-transitive closures, from the above remark we obtain that the call Classes(rtc(R) & rtc(R^)) column-wisely enumerates the SCCs of R. In Berghammer and Fronk [8] the authors also refine the program Classes to a RelView-program that computes the initial SCCs of R. Essentially this refinement consists of an additional assignment in front of the hitherto first assignment to compute rtc(R) & rtc(R^) and to store the result as S (which now is a local variable instead of the formal parameter), and it simply checks after the computation of the next equivalence class c via the assignment c = S * point(v) whether c is initial and executing only in that case the conditional of the original while-loop. It leads to the following program: InitSccs(R) DECL S, C, v, c BEG S = rtc(R) & rtc(R^); C = On1(S); v = Ln1(S); WHILE -empty(v) DO c = S * point(v); IF incl(R*c,c) THEN IF isempty(C) THEN C = c ELSE C = (C^+ c^)^FI FI; v = v & -c OD RETURN C END

Fig. 2 .

 2 Fig. 2. SCCs and initial SCC of the former example

Fig. 3 .

 3 Fig. 3. Minimum FVSs of the initial SCC

Fig. 4 .

 4 Fig. 4. The original graph marked with the minimum FVSs

U

  A (g 16 ) = 60, U A (g 17 ) = 70, for party B we have the utilities U B (g 16 ) = 45, U B (g 17 ) = 40 (which means that B dislikes A a lot) and for party C we have the utilities U C (g 16 ) = 50, U C (g 17 ) = 0 (saying that C finds B repulsive). So, we have two alternatives g 16 and g 17 and three judges/parties A, B and C. Balinski and Laraki's matrix of judgements, or profile, consequently looks as follows: Balinski and Laraki's majority-grade f maj to each row (alternative) we find: f maj (60, 45, 50) = 50 and f maj (70, 40, 0) = 40.

  F (f (r 11 , . . . , r 1n ), . . . , f (r m1 , . . . , r mn ))We call F an SGF if and only if F satisfies the six properties given above.The question is if there is a single best aggregation function f , and thus a single best SGF F . Balinski and Laraki consider order functions: the kth order function f k takes as input an n-tuple of grades and gives as output the kth highest grade.

	  	1 . . . n r 11 . . . r 1n . . . . . . . . . r m1 . . . r mn	   →

This name stems from the fact that for all u, v ∈ G * × G * we have E u,v if and only if u1 = v2 and u2 = v1.

Acknowledgement: We want to thank the unknown referees for their valuable remarks.


Lucie Bouvet
email: lucie.bouvet@univ-tlse2.fr

Cynthia Magnen

Clara Bled

Julien Tardieu

Magnen C 1+

Bled. C. . 2+

Keywords: phoneme color synesthesia, speech perception, multisensory representations, veridical mapping, segmental speech processing, dual coding theory

come

1.Introduction

Synesthesia is a subjective phenomenon in which the perception of a specific stimulus automatically triggers an idiosyncratic perception in the same or a different sensory modality (e.g., a letter can trigger the perception of a specific color or a sound can provoke the perception of complex colored photism). Several criteria are used in order to evaluate the genuineness of the synesthesia: the idiosyncratic synesthesic association is generally automatic, involuntary and stable over time [START_REF] Ward | Synesthesia[END_REF]. Among the 60 types of synesthesia that have been described, linguistic synesthesias are the most common form [START_REF] Simner | Synaesthesia : The prevalence of atypical cross-modal experiences[END_REF]. Among them, grapheme-color synesthesia is the most frequent (1 -2% of the general population) and the most widely studied one. Although orality is the primary dimension of language, practically no studies have evidenced phoneme color synesthesia. We previously reported, from a neuropsychological perspective, the case of VA who possesses phoneme color synesthesia. The aim of this paper was to further document VA's phoneme color synesthesia from a psycholinguistic perspective by evaluating the variations of her colored perception as a function of several linguistic levels (acoustic, semantic and graphemic) and its manifestation in a conversational context.

Several studies have explored the implication of the different psycholinguistic levels (i.e., acoustic, phonemic, lexical and graphemic) in speech color synesthesia. At the phonemic level, studies have mainly been carried out on vowels and results generally demonstrated that the acoustic properties of vowel sounds were significant predictors of color choices. In particular, brightness of the synesthesic color is linked to the pitch 1 of vowels: high-pitched vowels (/i/, /e/) are linked to brighter colors and low-pitched vowels (/o/, /u/) are linked to darker colors [START_REF] Lahiri | The mental representation of lexical form : A phonological approach to the recognition lexicon[END_REF]. On similar lines, Fernay et al. (2012) evidenced that voice pitch is linked to the luminance (higher pitch being lighter). Moreover, [START_REF] Moos | Cross-Modal Associations in Synaesthesia : Vowel Colours in the Ear of the Beholder[END_REF] explored the link between acoustic formants 2 and colors. They found that lower values of the first 1 Pitch refers to our perception of the fundamental frequency. Fundamental frequency, often called F0, is the frequency at which the vocal cords vibrate in vowels and voiced consonants. It generates prosodic variations, i.e. of melody and intonation, which contribute to the identification of the sex, the age and the identity of the speaker, as well as to the meaning of the spoken messages. 2 Formants are independent of voice pitch and are more characteristic of the type of vowels. Formant values vary with tongue position in vowel production. F1 values are lower when the tongue is higher in the mouth (i.e., high vowels such as /i/) and higher when the tongue is lower in the mouth (i.e., low vowels such as /a/). F2 values vary according to tongue frontness. formant (F1) (i.e., higher vowels) were greener and yellower, but lower values of the second formant (F2) (i.e., more back vowels) were redder and bluer. In a recent study, [START_REF] Cuskley | Cross-modal associations and synesthesia : Categorical perception and structure in vowel-color mappings in a large online sample[END_REF] replicated these earlier findings. They furthermore evidenced the predominant role of categorical phoneme perception over and above acoustic cues [START_REF] Cuskley | Cross-modal associations and synesthesia : Categorical perception and structure in vowel-color mappings in a large online sample[END_REF]. Their study demonstrates that acoustic and phonemic levels are linked and influence each other during speech perception. At the lexical level, very few studies have been carried out on the question of the underlying processes in this form of synesthesia. Among them, [START_REF] Baron-Cohen | Hearing words and seeing colours : An experimental investigation of a case of synaesthesia[END_REF] reported the case of a chromatic lexical synesthesia, EP, for whom hearing words triggered the perception of color. The authors observed that for words, EP provided a single color whereas for nonwords she provided several colors that could be linked to those triggered by the letters of the alphabet. However, this conclusion concerned only the graphemic level as the association between color and phonemes was not tested. In another study, [START_REF] Baron-Cohen | Coloured speech perception : Is synaesthesia what happens when modularity breaks down?[END_REF] tested whether the synesthetic perception of 9 subjects with colored hearing synesthesia was mediated by a phonemic or rather by a graphemic representation. For all subjects, the synesthesic color was triggered by the initial letter of the word, not by the phoneme. The authors concluded that the participants possessed grapheme-color rather than phoneme-color synesthesia.

These results are emblematic of most studies that have focused on linguistic synesthesia, which have demonstrated that it is mainly induced at the graphemic level [START_REF] Simner | Beyond perception : Synaesthesia as a psycholinguistic phenomenon[END_REF]. However, one can note a recurrent confusion due to the methodological difficulty of working with the oral dimension of language. Indeed, except for vowels, speech sounds are often presented in a syllable, a word or by referring to their graphemic correspondence (i.e. with letters). The problem is that this summons several types of representations which are not directly those that are targeted. Recent studies on synesthesia started to highlight the association between different linguistic representations (acoustic, phonemic and graphemic) and synesthesic mappings [START_REF] Cuskley | Cross-modal associations and synesthesia : Categorical perception and structure in vowel-color mappings in a large online sample[END_REF]. For instance, [START_REF] Kang | Graphemes Sharing Phonetic Features Tend to Induce Similar Synesthetic Colors[END_REF] showed that graphemes sharing a phonetic feature tended to induce similar synesthesic colors across languages among grapheme color synesthetes. Thus, to evaluate as accurately as possible the oral dimension of linguistic synesthesia, it seems necessary to investigate the different linguistic representational levels separately and, at the same time, to consider their mutual influences.

The goal of the present study was to evaluate the influence of the different linguistic variables (acoustic, semantic and graphemic) on a previously reported case (VA) of phoneme color synesthesia (Bouvet et al., 2017). The underlying objective was to evaluate the genuineness of this phoneme color synesthesia, as a "pure" case of this type of synesthesia has not been previously described. We systematically observed whether VA's synesthesia varied with the perception of different types of linguistic stimuli (from phonemes to words) that combined different types of representations and that varied gradually. In the first task, we used isolated vowels and consonant-vowel (CV) syllables. We investigated the influence of acoustic parameters on VA's synesthesic perception. For isolated vowels, we tested two acoustic parameters: vocalic formants and voice pitch (F0). If VA's synesthesia relies on acoustic parameters we could expect, according to the previous literature, that: 1) higher vowels (F1) would be lighter, greener and yellower whereas more back vowels (F2) would be darker, redder and bluer, and 2) higher voice pitch would be associated to brighter colors. For CV syllables, if VA continued to percieve a synesthesic color for each unit, we also investigated the factors that influenced the color attribution for the consonant-color associations. On this point, this work is exploratory as there is currently no study on this type of association. We also assessed whether the constituent elements of the syllable had an influence on the synesthesic colors. In the second task, we used words to investigate the influence of semantic and graphemic factors on VA's synesthesic perception. Lastly, in a third task, we interviewed VA on how her synesthesia manifested itself in a conversational context. The purpose was to determine if the same underlying mechanisms of speech processing evidenced with experimental protocols occurred in her daily life.

Case description

As full details of VA's developmental history were reported in the previous paper (Bouvet et al., 2017), we will give only the main lines here. The acquisition of oral language was atypical, as she started to speak in complete sentences at 16 months but did not pronounce a single word before then. She learnt to read by herself quite early (3 years old). At this age she was also able to perform mental calculations. She showed a particular interest in dinosaurs and space. Despite her intellectual precocity, VA experienced motor and coordination difficulties. She had difficulties developing social relationships, and was socially excluded at school. She experienced difficulties in formal learning during her studies as she struggled to understand ambiguous instructions. She performed poorly in mathematics. She reported seeing spatialized dynamical photisms when hearing sounds and also claimed to have developed an astrophysical theory. She consulted psychiatrists during infancy and as an adult.

None of them mentioned a diagnosis of autism but social phobia and schizophrenia diagnoses were made. The aim of the previous paper was to highlight how neurological and psychiatric conditions can be confused. We evidenced, via a systematic neuropsychological evaluation, that VA possessed higher than average cognitive abilities. We also evidenced in VA the possession of a complex sound-color (speech and non-verbal sounds) synesthesia. For speech, it was found that phonemes in particular triggered the perception of color, while for nonverbal sounds, the perception of a spatialized dynamical colored photism was described. We also observed that VA did indeed possess special abilities in astrophysics. After this first study, she agreed to continue the research with the aim of better understanding her phoneme color synesthesia and her cognitive functioning.

Testing the influence of acoustic parameters on VA's synesthesia

Material and methods

The linguistic material consisted of audio recordings of French vowel and consonant phonemes. The recordings were performed in the sound perception lab of the CCU platform3 in an audiometric booth using a Sennheiser MD46 omnidirectional microphone, a TASCAM DM-3200 mixing console and a MacPro computer equipped with the Reaper software. Four adult native speakers of French were recruited to record speech stimuli: two men and two women with two different high and low pitches. The vowel phonemes [i, e, ɛ, a, u, o, ɔ, y, ø, oe, ɛ , , ɔ ] were pronounced in the carrier sentence « Je dis /V/ comme dans … » [I pronounce /V/ as in …]. The target vowels were written down with their IPA transcription as well as the example word, which appeared at the end of the sentence orthographically. The speakers were checked for their understanding of the symbols before recording. They were asked to read the carrier sentences one by one, twice in a row, for a total of 52 stimuli. Target vowels were then extracted with Audacity® from the audio recordings. The consonant phonemes [p, t, k, b, d, g, m, n, f, s, ʃ, v, z, ʒ, ʁ, l] were produced three times in a CV context where the vowels were [i, a, u], for a total of 192 stimuli. Out of the 244 stimuli created, the phonetician (CM) selected the best exemplar of each phoneme produced by a male and by a female speaker on the basis of its perceptual typicality. In total, there were 122 stimuli: 26 vowels (13 vowels* 2 speakers) and 96 CV syllables (16 consonants* 3 contexts* 2 speakers).

The 122 stimuli were orally presented randomly using the Psychopy software [START_REF] Peirce | PsychoPy-Psychophysics software in Python[END_REF]. After hearing each sound with the headphone (Sennheiser HD 380 pro), VA had to indicate the corresponding color (or colors) closest to her perception with the color chart (MACal 9800 pro© which contains 102 colors). The experimenter noted down the color reference. The sound was played only once. VA was told that she could take as long as she needed to give her answer.

Each color was converted to CIELab space (the correspondence was given directly by MACal ©). It expresses color using three different values. L is the lightness that goes from 0 (darkest black) to 100 (brightest white). The color channels are a and b. The a axis represents the green/red colors with green at negative values and red at positive values. The b axis represents blue/yellow colors with blue at negative values and yellow at positive values.

Analysis and results

Isolated vowels

For 8 of the 13 vowel categories (see Figure 1), VA choose exactly the same color for the same vowel pronounced by the two different speakers [i, e, a, o, ɔ, ø, , ɔ ] (61.5% of the vowels). For the 3 vowel categories y , oe and ɛ /, the colors attributed to the different exemplars were in the same hue. For the two vowel categories /ɛ and u , the colors attributed to the different exemplars were of different hues.

Analysis. Voice pitch (F0) and formants (F1 & F2) were extracted and analyzed using Praat© software (see supplementary data). To evaluate a potential link between the voice pitch, formants and colors, as certain values did not follow the assumption of normality (Shapiro-Wilk p values < .001), Spearman correlations were performed.

Results. Regarding voice pitch, no significant correlation was observed on the different Lab values with F0 [ L : rs(24) = -.27, p = .17 ; a : rs(24) = .36 , p = .07, b : rs(24)= .34, p = .09).

Regarding the influence of formants, we observed a significant negative correlation between F1 and a values, (rs(24) = -.59 , p < .001) which indicates that the lower the F1 values are, the redder the colors. A significant negative correlation between F1 and b values was also observed (rs(24) = -.48, p = .01), indicating that the lower the values on F1, the yellower the colors. A significant correlation between F2 and L values was also observed (rs(18) = .83, p < .001), with vowels with higher F2 values being associated to lighter colors.

CV syllables

For each CV syllable, VA provided two different colors. Thus, consonant and vowels were analysed separately.

Consonants in a CV syllable context. For 12 consonants ([p, k, b, d, g, n, f, s, ʃ, v, ʒ, ʁ], i.e., 75% of the consonants), VA chose exactly the same color for the six exemplars. For the four remaining consonants [m, l, t, z], a few differences in colors were observed especially for the b and the lightness dimensions within the consonant category. As can be seen in Figure 2, these differences in color are minimal.

Analysis. Consonants can be defined by their articulatory mode (either occlusive [p, b, k, g, t, d, m, n] or constrictive [ʃ, f, ʒ, l, ʁ, v, s, z]), and the place of their articulation (bilabial [p, b, m], labiodental [f, v], dental [n, d, t, s, l, z], dorso palatal [ʒ, ʃ] and velar [g, k, ʁ]). The articulatory mode defines how the sound is produced by blocking the airstream. For occlusives, the airstream is momentarily blocked whereas for constrictives, the air passage is narrowed by constriction of the vocal tract. The place of articulation refers to the place along the vocal tract where the articulators (tongue, teeth, lips or glottis) make contact. Analyses were conducted on these articulatory parameters to evaluate their influence on synesthesic color. To test a possible link between the articulatory mode (occlusive vs constrictive) and the chosen colors, as Lab values do not follow the assumption of normality (Shapiro-Wilk p values < .001), we performed a non-parametric test (Mann-Whitney U test). To test if there was a link between the place of articulation of the consonants and the chosen colors, as the place of articulation is an ordinal variable, we performed Spearman's rank correlation. Vowels [i, a, u] in CV syllables. The colors attributed to each vowel within different syllabic contexts are represented in Figure 3. For [a] three different colors were given: luminous cyan4 (20 times), sky blue (11 times), and azur blue (1 times), luminous cyan being the color given for [a] when presented in isolation. For [i], the same color was given for all the 32 exemplars, namely light yellow. It is the same color as for [i] when presented in isolation. For

[u], the same color (eggplant) was given for the majority of 31 exemplars, and the color dark violet was given for one exemplar. These two colors were given for the two exemplars of [u] when presented in isolation. Thus, no variation in color within the syllabic context was observed. Consequently, no further analyses on the influence of acoustic parameters on color were performed.

Figure 3. Representation of the colors chosen by VA for the 32 exemplars of each vowel /a/, /i/, /u/ in different consonant contexts according to the F1 and F2 values. Axis labels indicate vowel quality (vowel height on the F1 axis and front/back vowels on the F2 axis). Note that for [a], the difference between colors is minimal and difficult to discern.

3.3.

Intermediate discussion

In this first task, we used isolated vowels and consonant-vowel (CV) syllables to investigate the influence of acoustic parameters on VA's synesthesic perception. First, we observed that changing the linguistic unit had almost no influence. For CV syllables, VA systematically provided a color for each unit. Interestingly, the phenomenon of coarticulation had no impact on the synesthesic color, as no significant variation in color within a consonant/vowel category was observed, no matter what the association of vowels or consonants. Moreover, the colors associated to vowels in a syllabic context were globally similar to those associated to the same vowels when presented in isolation. Furthermore, we observed that the synesthesic colors were determined by some factors linked to phonemic categories. For isolated vowels, we observed a correlation between formants (F1 & F2) and color values. For VA, higher vowels are redder and yellower, while lower vowels are greener and bluer. Moreover, front vowels are lighter. These results are partially in line with those observed in synesthetes [START_REF] Cuskley | Cross-modal associations and synesthesia : Categorical perception and structure in vowel-color mappings in a large online sample[END_REF][START_REF] Moos | Cross-Modal Associations in Synaesthesia : Vowel Colours in the Ear of the Beholder[END_REF] but also in the general population [START_REF] Cuskley | Cross-modal associations and synesthesia : Categorical perception and structure in vowel-color mappings in a large online sample[END_REF], indicating that VA's synesthesia fits into the framework of general cross-modal mapping to some extent. However, no significant relation between voice pitch and color was observed as previously evidenced (Fernay et al., 2012). For consonants, we observed a correlation between colors and the articulatory mode and the place of articulation. Constrictive consonants were associated to lighter and yellower colors than occlusive consonants and back consonants were associated to a redder color. Taken together, these results indicate that, in the case of VA, synesthesic colors are linked to articulatory and acoustic factors that are correlated with changes in phonemic category. On the other hand, the perceived colors were not influenced by voice pitch, nor by phenomena of intrasyllabic coarticulation, which are acoustic factors that are unrelated to phonemic categories. In the following task, we used words to investigate the influence of semantic and graphemic parameters on VA's synesthesic perception.

Testing the influence of semantic and graphemic parameters on VA's synesthesia

To test the influence of the semantics on VA's synesthesia we used words composed of phonemes associated to different synesthesic colors. Under the assumption that VA's synesthesia was influenced by the meaning, we wanted to be able to evaluate whether the position of phonemes within the words defined the synesthesic color. Furthermore, in the corpus, some phonemes had different graphemic representations. This allowed us to evaluate their possible influence on the synesthesic colors.

Material and methods

We selected 60 monosyllabic words, all nouns, composed of phonemes that elicit different associations of the 6 color categories: green and blue, green and yellow, red and blue, green and orange, orange and blue, and with 3 colors. Each color category comprised 10 words.

The two-color categories comprised 5 bi-phonemic words with the CV form and 5 triphonemic words with the Consonant/Vowel/Consonant (CVC) form in order to balance the length of the words in each group. The three-color categories of words were exclusively composed of 10 CVC words.

The words' frequencies of use were verified in different databases (MANULEX and LEXIQUE). Each word was recorded by a female and a male speaker (for a total of 120 words, 60 monosyllabic words*2 speakers) and was produced with a definite article "le la" (the). The recordings were performed in the same conditions as previously.

The words were presented only once via headphones (Sennheiser HD380 pro) using the PsychoPy® software. The order of presentation was randomized. For each word, VA had to indicate the corresponding color (or colors) closest to her perception with the color chart (MACal 9800 pro® which contains 102 colors). VA was instructed to ignore the definite article for her color choices. The corresponding codes were noted down by the experimenter.

As in the previous task, each color was converted to CIELab space in order to perform analysis.

Analysis and results

Semantic influence. For the bi-phonemic words, VA gave 2 colors and for the tri-phonemic words she gave 3 colors. Despite the different phonemic contexts, the colors of the phonemes did not seem to influence each other since the triggered colors remained identical within 12 out of 28 phoneme categories (42%). When the colors within the same phonemic category were different, the colors selected were in the same hue (see Figure 4). We observed that the meaning of the word has no significant influence on VA's color attribution mechanism. Testing the robustness of VA's phoneme color synesthesia. Since no semantic or graphemic influences on VA's synesthesia were found, we tested the robustness of the phoneme color synesthesia. We compared the colors given for phonemes presented outside a semantic context (isolated vowels and CV syllables of the previous experiment) and the colors given for the phonemes in a semantic context (phonemes that composed the words in the present experiment). To do so, we calculated the Euclidean distance (d) between the mean of the Lab values for each main phoneme category across the two different tasks according to the equation:

The score reflects how far away the two colors are in the color space. The lower the score, the closer the colors are in this color space. According to [START_REF] Rothen | Diagnosing synaesthesia with online colour pickers : Maximising sensitivity and specificity[END_REF], a score below 109 is an indicator of consistency.

For 9 phoneme categories, the d value was 0, indicating that VA chose exactly the same color for the phoneme in the two contexts (outside and within a semantic context). For 18 phoneme categories, the d value was well below 109. For one phoneme category (/ /, d = 153), the color was completely different between the two tasks (see Figure 6).

Intermediate discussion

When testing VA's synesthesia with words, we observed that changing the linguistic unit had, as previously observed with syllables, practically no influence. Contrary to what might have been expected, we did not observe any effect of semantic knowledge on VA's synesthesic perception unlike the study of [START_REF] Baron-Cohen | Coloured speech perception : Is synaesthesia what happens when modularity breaks down?[END_REF]. VA continued to provide one color for each phoneme that composed the word. What is striking is the similarity of the colors triggered for isolated phonemes and CV syllables and the colors triggered for phonemes within the context of a word. These two different tasks were conducted several years apart. This demonstrates the robustness of the synesthesia. Moreover, no significant influence of the graphemic representations was observed, in contrasts to what is found in the majority of linguistic synesthesias [START_REF] Simner | Beyond perception : Synaesthesia as a psycholinguistic phenomenon[END_REF]. Taken together, these results indicate that her synesthesia manifests itself at the level of phoneme categories. Note that these results are based on experimental studies in which VA was asked to provide colors for controlled linguistic units. Words were presented outside their pragmatic context and the result obtained may not reflect the process VA uses in everyday conversation. In order to determine if this process also occurs in a conversational context, we interviewed VA.

Phoneme color synesthesia in the context of conversation

Method

Two semi-directed interviews were conducted with VA by the author CB. The purpose of these interviews was to better understand the functioning of VA's synesthesia and how her synesthesia manifested itself in daily situations (such as conversation). The interviews were conducted at the hospital of Reims in a quiet room. Each interview lasted for approximately 30-45 minutes. The interviews were audio-recorded and the verbatim of the interview was transcribed. From these interviews, we selected the parts that addressed the question of her synesthesia in the context of conversation. In order to perform a thematic analysis, the transcribed interview data were analysed by the author LB. The transcripts were read and reread by LB and an initial set of themes was produced. The themes were reviewed by CB and CM, evaluating how well they captured the coded data. Here, we present a free translation of her statements.

Results

Manifestation of her synesthesia during speech perception

To access the meaning of what is being said in a conversational context, VA described two distinct processes. First of all, the association between sound and color is automatic and these two dimensions are closely linked. For VA, colors are meaningful only in relation with sounds. "Colors only have meaning if they are associated with sounds." "Colors, for me, have no meaning at all, they are not associated with emotions." The automaticity of this association is unidirectional: "I may possibly remember the sound associated with the color but from memory that's all… it's not spontaneous at all! The association only goes one way."

When she has to perceive and to understand speech, a translation process occurs. To access the meaning, she has to translate the perceived colors. Contrary to the automatic correspondence between sound and color, the translation process between color and language is not straightforward: "

Intermediate discussion

Several conclusions can be drawn from this thematic analysis. First of all, for VA, sounds and colors are automatically associated and in the context of conversation the perception of a phoneme automatically triggers the perception of the associated color. What is quite surprising is that the colors are translated and substituted by a multisensory representation of the meaning. These multisensory representations seem to constitute her main way of thinking and cause her difficulties apprehending and evolving in a world that is mostly verbal.

Furthermore, when she has to produce speech, she has to translate her multisensory representations into speech. Paradoxically, these processes of translation (speech/colors to multisensorial representations and multisensorial representations to speech) are not automatic and imply a high cognitive cost. Globally, holding a conversation is a difficult exercise for her.

General discussion

In the present study, we evaluated the consistency of VA's synesthesia with different types of stimuli (isolated phonemes, syllables, and words). The aim was to investigate whether acoustic, semantic or graphemic factors influenced VA's synesthesia. Across these different types of stimuli, we systematically observed that VA provided one specific color for each phoneme. A very stable system emerged from the association between colors and phonemic representations. This observation suggests that VA processes speech segmentally either in experimental conditions when she has to associate colors with different types of linguistic units or in daily conversation. This observation raises several questions that we address in the following.

First of all, her segmental speech perception to access word meaning is atypical and questions current models of the field. During the 80s, the word recognition process via phonemes was the cornerstone of lexicon access models (see for example the TRACE model, [START_REF] Elman | Speech Perception as a Cognitive Process : The Interactive Activation Model[END_REF][START_REF] Mcclelland | The TRACE model of speech perception[END_REF]. More recently, these models have been judged to have too high a cognitive cost (Wauquier-Gravelines, 1999) because they presuppose remembering each phoneme in the time course of the speech in order to access the meaning. They were also deemed to be too close to an orthographic vision of speech perception [START_REF] Grosjean | Prosodic structure and spoken word recognition[END_REF] and not to account for the dynamic nature of speech processing. Nowadays, listeners are considered as linguistic experts who can use differentsized units (phonemes, syllables, words) to match the speech signal to units of meaning in order to understand conversational interactions (for a review see [START_REF] Nguyen | The dynamical approach to speech perception : From fine phonetic detail to abstract phonological categories[END_REF]. The case of VA highlights that access to the meaning uniquely via phonemes is possible but that this rigidity of functioning has a high cognitive cost. We can also wonder why VA developed this atypical speech processing. We can hypothesize that VA used a specific mechanism to represent language with a stable but costly system in order to organize the excess of visual information. This speech process is reminiscent of the learning process of reading when children decipher words grapheme by grapheme, unit by unit. It is interesting to note that VA learnt to read alone and at quite an early age (at 3 years old; see Bouvet et al., 2017). Thus, her early reading skill might have influenced this segmental speech processing and might have helped her to detect regularities between oral linguistic units and visual representations.

A similar atypical mechanism to organize information has been described in the acquisition of some specific abilities (synesthesia, hyperlexia, absolute pitch) via the mechanism of veridical mapping in autism [START_REF] Bouvet | Veridical mapping in savant abilities, absolute pitch, and synesthesia : An autism case study[END_REF][START_REF] Mottron | Veridical mapping in the development of exceptional autistic abilities[END_REF].

Thematic analysis also evidenced a way of thinking dominated by multisensorymainly visualrepresentations in which verbal representations are practically absent. In order to communicate, she described a process of translation from verbal to non-verbal representations. This description raises several questions. Most psycholinguistic models consider that our knowledge about words is stored in a mental lexicon. This mental lexicon contains semantic, syntactic, morphological, phonological and orthographic properties of words. In this view, all information (both verbal and non-verbal) is processed via this mental lexicon [START_REF] Lahiri | The mental representation of lexical form : A phonological approach to the recognition lexicon[END_REF][START_REF] Segui | Évolution du concept de lexique mental[END_REF]. However, the dual coding theory [START_REF] Paivio | Dual coding theory and the mental lexicon[END_REF] stipulates that verbal and non-verbal information are processed via two distinct but interrelated systems. The latter view accounts better for VA's difficulties in translating verbal into non-verbal information and vice versa. The cognitive cost of shifting between the two types of representation seems to underline her communication difficulties. We can wonder to what extent communication difficulties observed in certain psychopathological disorders such as autism may be related to this difficulty of translation between verbal and non-verbal representations, as autistic individuals are often described as sensory/visual thinkers [START_REF] Bled | Thinking in pictures in everyday life situations among autistic adults[END_REF][START_REF] Kunda | Thinking in Pictures as a cognitive account of autism[END_REF].

Finally, the question arises as to how this atypical speech processing and non-verbal thinking style are related. It was recently pointed out that synesthesia is one manifestation of a particular neurodiverse phenotype [START_REF] Ward | Synaesthesia as a model system for understanding variation in the human mind and brain[END_REF]. In the case of VA we can hypothesize that her segmental speech processing (of which the phoneme color synesthesia is a manifestation) can be related to her particular way of thinking. As discussed earlier, using a segmental way to process speech would be a costly and inefficient process for most people. For VA, however, the use of phonemes might be the most efficient way to process speech as she does not use linguistic representations to think. Phonemes are the smallest unit of sound and meaning in speech and make it possible to decipher speech without access to the mental lexicon.

There are several limitations to this study. First of all, as a case study, results cannot be generalised to other groups in the population. However, case studies have the power to shed light on a particular (mainly compensatory) mechanism and can contribute to an understanding of the general functioning [START_REF] Shallice | Case study approach in neuropsychological research[END_REF]. The uniqueness of VA's synesthesia is related to her atypical/segmental way of processing speech and her case could contribute to reflection on theories of speech perception. Moreover, her non-verbal way of thinking and the cognitive cost of translation into verbal representations might also contribute to a better understanding of the organization of our mental representations. Another limitation is that there is no control group included in this study. This methodological decision was motivated by the goal of the study which was to demonstrate the genuineness of the phoneme color synesthesia. All the tasks were designed around VA's synesthesia; the participation of a control group was therefore not relevant. Lastly, the use of interviews to explore VA's functioning can also be questioned as it provides subjective data. Thus, They may not reflect reality. However, this methodology allowed us to have access to some cognitive processes that would otherwise have remained inaccessible.

To conclude on this case study, using different methodologies we have evidenced a case of genuine phoneme color synesthesia. This synesthesia might be unique as it reflects a particular way (i.e., segmental) of processing speech and might emerge from a sensory/visual way of processing information. Further research could consider the interest of combining different types of methodologies intra-individually in order to better apprehend some complex forms of perception.

Figure 1 .

 1 Figure 1. Representation of colors chosen by VA for vowels (2 trials) in the Lab color system. Axis labels indicate the color dimension (a green/red colors and b blue/yellow). On the right panel, the colors of the vowels are represented along the lightness dimension (L). f indicates vowels pronounced by a female speaker and m indicates vowels pronounced by a male speaker.

Figure 2 .

 2 Figure 2. Representation of colors chosen by VA for consonants (6 trials) in the Lab color system. Axis labels indicate the color dimension (a green/red colors and b blue/yellow). On the right panel, the colors of the consonants are represented along the lightness dimension (L). Numbers indicate the two different colors chosen for the consonant.

Figure 4 .

 4 Figure 4. Representation of colors chosen by VA for phonemes in a semantic context in the Lab color system. Axis labels indicate the color dimension (a green/red colors and b

Figure 6 .

 6 Figure 6. Mean colors for phonemes when presented outside (experiment 1) or within a (experiment 2) semantic context. The d value indicates the Euclidean distance between the mean Lab values between the two tasks. The lower the value, the closer the two colors are.

  The meaning of words is a work of translation in my head and this translation work requires a much greater effort than being able to look at the colors. I have to translate the colors." "If I want to be able to understand what people are saying when they speak, I also have to focus on synesthesia because otherwise I don't understand the words." She also feels overwhelmed by all the information and that causes her to lose track of the conversation, especially when the interaction lasts a long time and the speech flow is fast. "For example, when[someone] explained to me how to fill out my papers, and then she went from one subject to another, and she made a long long speech and then I couldn't hold on to the end, because there were too many colors." "After a while, I

	she has to translate this multisensory way of thinking into words. "[when I think] all the senses are suddenly activated. So, I have to translate them back into words when I speak". VA explained that since she processes information in a sensory/visual way, she has difficulties apprehending and evolving in a world that she described as mostly verbal: "For most people, the world is partly verbal, for me it's a foreign language." "Teaching methods are extremely verbal and I am not. It requires a huge verbal memory and I would like to learn more visually." "I don't have the same perception of things as most people so that suddenly in terms of studies and work, it doesn't work." Sensory overwhelm and communication difficulties Because of her particular way of processing speech (processes of translation, hypersensitivity), holding a conversation requires a great deal of effort. The processes of translation make it difficult for VA to interact with others: "It's hard to understand what I of words." "I have a lot of trouble holding a conversation for a long time, if it lasts it's a terrible effort." "When the perceptions are really strong, for example [...], when there is someone who speaks quickly and then for a very long time, it is completely exhausting." These double processes of translation made it difficult for VA to interact with others: "It's hard to hear and to express myself." switch off because I end up focusing on colors and voice rather than focusing on the meaning understand what I hear and to express myself."

A multisensory predominantly visual cognitive style

This process of translation gives her access to a multisensory representation of the meaning: "I do not remember the words, I see the meaning of what I hear: it is more than an image because there are all five senses." These multisensory representations seem to constitute her main way of thinking which is mostly dominated by the visual modality: "If I think of a cake, I won't think of the word cake: I will think of all the sensations I have when I see, touch and eat the cake. All the senses are suddenly activated." "I think in video constantly, in pictures." "I don't think in words." Consequently, when she has to produce speech, i.e. when she speaks,

3 https://mshs.univ-toulouse.fr/plateformes/les-plateformes-technologiques/ccu-cognitioncomportements-et-usages/petra/

The names of the colors are given by the MACal color chart.

Acknowledgements

We are greatly indebted to VA who taught us so much by participating in this research.

Funding

This work was supported by the MSHS-T (Maison des sciences de l'homme et de la société de Toulouse) and by the French National Research Agency (VISUAL ANR-19-CE28-0012)

blue/yellow). Numbers indicate the different colors chosen for the different versions of the phonemes.

Graphemic influence. Among the selected words, there were different graphemic representations for 5 vowel phonemes and for 3 consonant phonemes (see Table 1). It can be seen in Figure 5 that for phonemes for which there are some graphemic representations made of two or three letters, VA provided a single color. Moreover, for each phoneme, there were very slight color variations which cannot be linked to the graphemic variations.


PharmD, PhD Guillaume Monneret

PharmD Fabienne Venet

MD Pei-Ra Ling

Keywords: immunosuppression, lymphocyte, nosocomial infections, sepsis, trauma adipose tissue, critical illness, obesity

Critical Care Medicine www.ccmjournal.org 367 N osocomial infections (NIs) remain a serious and frequent complication of (ICUs) hospitalization and represent an important economic burden by significantly increasing hospitalization cost [START_REF] Safdar | Clinical and economic consequences of ventilator-associated pneumonia: A systematic review[END_REF]. Predicting which patients are at increased risk for developing NI is most likely one of the major challenges in the forthcoming evolution of ICU patients' care [START_REF] Kethireddy | Mortality due to septic shock following early, appropriate antibiotic therapy: Can we do better?[END_REF].

Although plainly obvious, the necessity of a robust immune response to battle against germs has been largely under recognized over years in the assessment of risk factors for NI. Meanwhile, increasing evidences indicate that a delayed immune failure occurs after any systemic inflammatory response syndrome. This is illustrated in ICU patients by infections normally solely pathogenic in an immunocompromised host [START_REF] Hotchkiss | The sepsis seesaw: Tilting toward immunosuppression[END_REF][START_REF] Pugin | Immunostimulation is a rational therapeutic strategy in sepsis[END_REF][START_REF] Monneret | ICU-acquired immunosuppression and the risk for secondary fungal infections[END_REF].

Importantly, this immune suppression has been shown to be induced after a variety of severe injuries leading patients to the ICU: sepsis, trauma, burn, pancreatitis, surgery, and stroke [START_REF] Monneret | Monitoring immune dysfunctions in the septic patient: A new skin for the old ceremony[END_REF]. It is thus of major interest to delineate the mechanisms sustaining this immunosuppression in ICU patients. To this purpose, in this issue of Critical Care Medicine (7), Deknuydt et al present an elegant work on the orchestration of immune response in patients with brain injury (BI). These patients present with similar features of immunosuppression and are characterized by high rates of NI [START_REF] Meisel | Suppressing immunosuppression after stroke[END_REF]. Here, the authors investigated BI patient's immune response within the model of granuloma formation in response to Bacillus Calmette-Guerin. This very interesting model provides in vitro a nice reflection of the coordination of both innate and adaptive immune cells to mount a protective response against a pathogen [START_REF] Puissegur | An in vitro dual model of mycobacterial granulomas to investigate the molecular interactions between mycobacteria and human host cells[END_REF].

The most important result of this study is the observation that BI patients developed a significantly lower number of granulomatous structures and that this decrease was even more pronounced in patients who were to develop NI. Another interesting aspect was to show that, in BI patients, granulomatous structures were characterized by poorly differentiated multinucleated cells (indicating a low level of maturity) and by low numbers of natural killers and γδ T cells. These parameters tended to be exemplified in patients with delayed infections. With that said and as duly acknowledged by the authors, the understanding of intimate mechanisms responsible for such results would deserve further investigations (e.g., role of regulatory T cells, decreased monocyte human leukocyte antigen-DR expression). Despite these limitations, this study provides the first observation of a global defect of immune functions in BI patients as illustrated by impaired granuloma formation in response to Bacillus Calmette-Guerin.

Beyond these results, the work of Deknuydt et al [START_REF] Deknuydt | An In Vitro Model of Mycobacterial Granuloma to Investigate the Immune Response in Brain-Injured Patients[END_REF] underlines the interest of functional testing to evaluate the immune response in ICU patients. Indeed, as there is no clinical sign for immune failure, prevention of NI by identification of patients at risk may rely on the use biomarkers. Of them, functional testing remains the gold standard because it directly measures ex vivo the capacity of a cell population to respond to an immune challenge. Here, although the low number of patients precludes any definitive conclusions, these preliminary results tend to indicate that functional testing may be indicative/predictive of deleterious outcomes in clinic. Similarly, two hallmarks of ICU-acquired immunosuppression are usually reported: the decreased monocyte capacity to release proinflammatory cytokines in response to endotoxin challenge and the lowered lymphocyte proliferation. Overall, these protocols provided excellent insights regarding pathophysiology but remain barely usable on a routine clinical monitoring basis (long incubation time, lengthy cell purification procedures, low standardization, etc.). Thus, one major challenge in the forthcoming years is to abolish the gap between comprehensive and compelling studies like that from Deknuydt et al [START_REF] Deknuydt | An In Vitro Model of Mycobacterial Granuloma to Investigate the Immune Response in Brain-Injured Patients[END_REF] and functional testing usable on routine daily practice.

One solution could be the development of surrogate markers of leukocyte functionality. The best example is the decreased expression of the major histocompatibility complex class II molecule human leukocyte antigen-DR on circulating monocytes. This decreased expression has been observed to correlate with monocyte functional response (tumor necrosis factor production after stimulation and antigen presentation capacity) and to be predictive of deleterious outcomes (mortality, nosocomial infections) in various clinical contexts [START_REF] Monneret | Monitoring immune dysfunctions in the septic patient: A new skin for the old ceremony[END_REF]. In contrast, no such marker is available regarding lymphocyte functionality. To date, the best available test for assessment of lymphocyte functional response remains the measure of proliferation in response to specific antigens (tuberculin, tetanus toxin) or nonspecific stimulations (phytohemagglutinin, anti-CD3, anti-CD28 antibodies) with all the limitations inherent to such measurement (tritiated thymidine uptake, several day-incubation time).

As lymphocyte alterations are associated with increased mortality/NI rates and as recent works suggest that impaired lymphocytes can be rejuvenated after stress/injury [START_REF] Boomer | A prospective analysis of lymphocyte phenotype and function over the course of acute sepsis[END_REF][START_REF] Unsinger | Interleukin-7 ameliorates immune dysfunction and improves survival in a 2-hit model of fungal sepsis[END_REF], novel therapeutic strategies reversing ICU-acquired immunosuppression in ICU patients are proposed [START_REF] Hotchkiss | Immunotherapy for sepsis-a new approach against an ancient foe[END_REF]. Knowing the pivotal role of lymphocytes (mainly CD4+ T cells) in orchestrating immune responses, one may expect that, by restoring their function, one can generate a global positive effect on the overall immune response, both mediated by lymphocytes and innate immune cells. In such indications, therapies like recombinant human interleukin-7 or anti-PD1 antibodies, already used in other clinical contexts, could represent interesting candidates. However, before such treatments can be administered to patients, robust and rapidly available markers measuring lymphocyte functions in the clinic on a routine basis are urgently needed. These tests will enable the clinicians not only to identify the patients that will benefit from such therapy but also to follow response to treatment. O besity makes nearly every aspect of care of critical ill patients more difficult. In general, a relative risk of death is 1.19 for those with a body mass index (BMI) from 30-35 and increases to 2 for those with a BMI >40 [START_REF] Safdar | Clinical and economic consequences of ventilator-associated pneumonia: A systematic review[END_REF]. The clinical impression is that BMI is a very important predictor of outcome for ICU patients. However, recent published outcome studies have paradoxically demonstrated a survival benefit for obese patients in the ICU [START_REF] Kethireddy | Mortality due to septic shock following early, appropriate antibiotic therapy: Can we do better?[END_REF][START_REF] Hotchkiss | The sepsis seesaw: Tilting toward immunosuppression[END_REF]. This discrepancy leads us to ask, Why? As the prevalence of obesity continues to rise among the ICU population, it is important for medical teams to understand the underlying mechanisms and the relationship between obesity and critical illness, thereby improving the care of critically ill patients.

In this issue of Critical Care Medicine, Marques and Langouche (4) challenge the "obesity paradox" and provide a detailed summa ry of the differences in adipose tissue between healthy subjects and critically ill patients, focusing on morphology, gene expressions of leptine, adiponectin, and cytokines and key components in glucose and lipid metabolism pathways. The evidence strongly suggests that during critical illness, the adipose tissue is a metabolically active organ. The functions of adipose tissue Marques and Langouche (4) elaborate initially seem to be quite obvious: new and small fat cells are created in the adipose tissue for increasing insulin sensitivity, more glucose and triglycerides are stored in adipose tissue as a nutrition and energy reservoir to protect against hypercatabolism, and changes in gene expression on all measured parameters in the fat tissue favor the alteration of inflammatory responses for a better outcome. It seems that adipose tissue acts as a buffer for a possible adaptive and protective role in optimizing changes of

Immune

  Functional Testing in Clinics: Feasibility and Prediction of Deleterious Outcomes* www.ccmjournal.org January 2013 • Volume 41 • Number 1