Elise Bonzon
email: bonzon@irit.fr

Marie-Christine Lagasquie-Schiex

Jérôme Lang
email: lang@irit.fr

Efficient coalitions in Boolean games

Boolean games are a logical setting for representing strategic games in a succinct way, taking advantage of the expressive power and conciseness of propositional logic. A Boolean game consists of a set of players, each of whom controls a set of propositional variables and has a specific goal expressed by a propositional formula. We show here that Boolean games are a very simple setting, yet sophisticated enough, for studying coalitions. Due to the fact that players have dichotomous preferences, the following notion emerges naturally: a coalition in a Boolean game is efficient if it guarantees that the goal of each member of the coalition is satisfied. We study the properties of efficient coalitions, and we give a characterization of efficient coalitions.

Introduction

Boolean games [START_REF] Harrenstein | Boolean games[END_REF][START_REF] Harrenstein | Logic in Conflict[END_REF][START_REF] Dunne | Representation and complexity in boolean games[END_REF][START_REF] Bonzon | Boolean games revisited[END_REF] are a logical setting for representing strategic games in a succinct way, taking advantage of the expressive power and conciseness of propositional logic. Informally, a Boolean game consists of a set of players, each of whom controls a set of propositional variables and has a specific goal expressed by a propositional formula 1 . Thus, a player in a Boolean game has a dichotomous preference relation: either her goal is satisfied or it is not. This restriction may appear at first glance unreasonable. However, many concrete situations can be modelled as games where agents have dichotomous preferences (we give such an example in the paper). Moreover, due to the fact that players have dichotomous preferences, the following simple (yet sophisticated enough) notion emerges naturally: a coalition in a Boolean game is efficient if it guarantees that all goals of the members of the coalition are satisfied. Our aim in the following is to define and characterize efficient coalitions, and see how they are related to the well-known concept of core. After recalling some background of Boolean games in Section 2, we study in Section 3 the properties of effectivity functions associated with Boolean games. In Section 4 we study in detail the notion of efficient coalitions. We give an exact characterization of sets of coalitions that can be obtained as the set of efficient coalitions associated with a Boolean game, and we relate coalition efficiency to the notion of core. Related work and further issues are discussed in Section 5.

n-player Boolean games

For any finite set V = {a, b, . . .} of propositional variables, L V denotes the propositional language built up from V , the Boolean constants and ⊥, and the usual connectives. Formulas of L V are denoted by ϕ, ψ etc. A literal is a variable x of V or the negation of a literal. A term is a consistent conjunction of literals. A clause is a disjunction of literals. If ϕ ∈ L V , then Var(ϕ) (resp. Lit(α)) denotes the set of propositional variables (resp. literals) appearing in ϕ. 2 V is the set of the interpretations for V , with the usual convention that for M ∈ 2 V and x ∈ V , M gives the value true to x if x ∈ M and false otherwise. |= denotes the consequence relation of classical propositional logic. Let V ⊆ V . A Vinterpretation is a truth assignement to each variable of V , that is, an element of 2 V . V -interpretations are denoted by listing all variables of V , with a ¯symbol when the variable is set to false: for instance, let V = {a, b, d}, then the V -interpretation M = {a, d} assigning a and d to true and b to false is denoted by abd. If Var(ϕ) ⊆ X, then Mod X (ϕ) represents the set of X-interpretations satisfying ϕ. If {V 1 , . . . ,V p } is a partition of V and {M 1 , . . . , M p } are partial interpretations, where

M i ∈ 2 V i , (M 1 , . . . , M p ) denotes the interpretation M 1 ∪ . . . ∪ M p .
Given a set of propositional variables V , a Boolean game on V is an n-player game 2 , where the actions available to each player consist in assigning a truth value to each variable in a given subset of V . The preferences of each player i are represented by a propositional formula ϕ i formed using the variables in V .

Definition 1.

An n-player Boolean game is a 5-tuple (N,V, π, Γ, Φ), where

• N = {1, 2, . . . , n} is a set of players (also called agents);

• V is a set of propositional variables;

• π : V → N is a control assignment function; • Γ = {γ 1 , . . . , γ n } is a set of constraints, where each γ i is a satisfiable proposi- tional formula of L π(i) ; • Φ = {ϕ 1 , . . . , ϕ n } is a set of goals, where each ϕ i is a satisfiable formula of L V .
A 4-tuple (N,V, π, Γ), with N,V, π, Γ defined as above, is called a pre-Boolean game.

The control assignment function π maps each variable to the player who controls it. For ease of notation, the set of all the variables controlled by a player i is written

π i such as π i = {x ∈ V |π(x) = i}.
Each variable is controlled by one and only one agent, that is, {π 1 , . . . , π n } forms a partition of V . For each i, γ i is a constraint restricting the possible strategy profiles for player i. Definition 2. Let G = (N,V, π, Γ, Φ) be a Boolean game. A strategy 3 for player i in G is a π i -interpretation satisfying γ i . The set of strategies for player i in G is

S i = {s i ∈ 2 π i | s i |= γ i }. A strategy profile s for G is a n-tuple s = (s 1 , s 2 , . . . , s n )
where for all i, s i ∈ S i . S = S 1 × . . . × S n is the set of all strategy profiles. Note that since {π 1 , . . . , π n } forms a partition of V , a strategy profile s is an interpretation for V , i.e., s ∈ 2 V . The following notations are usual in game theory. Let s = (s 1 , . . . , s n ) be a strategy profile. For any nonempty set of players I ⊆ N, the projection of s on I is defined by s I = (s i ) i∈I and s -I = s N\I . If I = {i}, we denote the projection of s on {i} by s i instead of s {i} ; similarly, we note s -i instead of s -{i} . π I denotes the set of the variables controlled by I, and π -I = π N\I . The set of strategies for I ⊆ N is S I = × i∈I S i , and the set of goals for

I ⊆ N is Φ I = V i∈I ϕ i .
can easily be generalized to n players and non necessarily zero-sum games [START_REF] Bonzon | Boolean games revisited[END_REF]. 3 In this paper, only pure strategies are considered. Note that this choice of binary utilites clearly implies a loss of generality. However, some interesting problems, as in Example 2, have preferences that are naturally dichotomous, and Boolean games allow to represent these problems in a compact way. Furthermore, Boolean games can easily be extended so as to allow for nondichotomous preferences, represented in some compact language for preference representation (see [START_REF] Bonzon | Compact preference representation for boolean games[END_REF]).

Coalitions and effectivity functions in Boolean games

Effectivity functions have been developed in social choice to model the ability of coalitions [11,[START_REF] Abdou | Effectivity functions in social choice[END_REF][START_REF] Pauly | Logic for Social Software[END_REF]. As usual, a coalition C is any subset of N. N is called the grand coalition. Given a set of alternatives S from which a set of agents N have to choose, an effectivity function Eff : 2 N → 2 2 S associates a set of subsets of S with each coalition. X ∈ Eff(C) is interpreted as "coalition C is effective for X".

Definition 3. A coalitional effectivity function is a function Eff: 2 N → 2 2 S which is monotonic: for every coalition C ⊆ N, X ∈ Eff(C) implies Y ∈ Eff(C) whenever X ⊆ Y ⊆ S.
The function Eff associates to every group of players the set of outcomes for which the group is effective. We usually interpret X ∈ Eff(C) as "the players in C have a joint strategy for bringing about an outcome in X".

In [START_REF] Pauly | Logic for Social Software[END_REF], the meaning of "effective" is precised in the framework of strategic games by defining "α-effectivity": a coalition C ⊆ N is α-effective for X ⊆ S if and only if players in C have a joint strategy to achieve an outcome in X no matter what strategies the other players choose.

As Boolean games are a specific case of strategic games, we would like to define α-effectivity functions in this framework. One of the features of Boolean games is the definition of individual strategies as truth assignments of a given set of propositional variables. We might wonder how restrictive this specificity is. In this section we study Boolean games from the point of view of effectivity functions. Clearly, the definition of S i as Mod π i (γ i ) induces some constraints on the power of players. Our aim is to give an exact characterization of α-effectivity functions induced by Boolean games. Since in Boolean games the power of an agent i is her goal ϕ i , it suffices to consider pre-Boolean games only when dealing with effectivity functions. A pre-Boolean game G induces an α-effectivity function Eff G as follows:

Definition 4. Let G = (N,V, π, Γ) be a pre-Boolean game. The coalitional α-effectivity function induced by G is the function Eff G : 2 N → 2 2 S defined by: for any X ⊆ S and any

C ⊆ N, X ∈ Eff G (C) if there exists s C ∈ S C such that for any s -C ∈ S -C , (s C , s -C ) ∈ X. 4
This definition is a particular case of the α-effectivity function induced by a strategic game (see [START_REF] Pauly | Logic for Social Software[END_REF], chapter 2). Therefore, these functions satisfy the following properties (cf. [START_REF] Pauly | Logic for Social Software[END_REF], Theorem 2.27)

: (i) ∀C ⊆ N, ∅ ∈ Eff(C); (ii) ∀C ⊆ N, S ∈ Eff(C); (iii) for all X ⊆ S, if X ∈ Eff(∅) then X ∈ Eff(N); (iv) Eff is superadditive, that is, if for all C,C ⊆ N and X,Y ⊆ S, X ∈ Eff(C) and Y ∈ Eff(C ), then X ∩Y ∈ Eff(C ∪C ).
An effectivity function satisfying these four properties is called strongly playable. Note that strong playability implies regularity and coalition-monotonicity ([14], Lemma 2.26).

However, pre-Boolean games are a specific case of strategic game forms, therefore we would like to have an exact characterization of those effectivity functions that correspond to a pre-Boolean game. We first have to define two additional properties. Define At(C) as the minimal sets in Eff(C), that is,

At(C) = {X ∈ Eff(C)| there is no Y ∈ Eff(C) such that Y ⊆ X}.
Atomicity: Eff satisfies atomicity if for every C ⊆ N, At(C) forms a partition of S.

Decomposability: Eff satisfies decomposability if for every I, J ⊆ N and for every X ⊆ S, X ∈ Eff(I ∪ J) if and only if there exist Y ∈ Eff(I) and Z ∈ Eff(J) such that X = Y ∩ Z. Note that decomposability is a strong property that implies superadditivity. Proposition 1. A coalitional effectivity function Eff satisfies (1) strong playability, (2) atomicity, (3) decomposability and ( 4) Eff(N) = 2 S \ ∅ if and only if there exists a pre-Boolean game G = (N,V, π, Γ) and an injective function

µ : S → 2 V such that for every C ⊆ N: Eff G (C) = {µ(X)|X ∈ Eff(C)}.
Sketch of proof: 5 The (⇐) direction does not present any difficulty: we can easily prove than Eff G satisfies strong playability (from Theorem 2.27 in [START_REF] Pauly | Logic for Social Software[END_REF]), atomicity, decomposability and Eff G (N) = 2 S \ ∅. As µ is a bijection between S and µ(S), these properties transfer to Eff. For the (⇒) direction, we first show than for every s ∈ S, there exists a unique (Z 1 , . . . , Z n ) such that for every i, Z i ∈ At(i) and Z 1 ∩ . . . ∩ Z n = {s}. Then, we build G from Eff as follows:

• for every i, number At(i): let r i be a bijective mapping from At(i) to {0, 1, . . . ,

|At(i)| -1}. Then create p i = log 2 |At(i)| propositional variables x 1 i , . . . , x p i i . Finally, let V = {x j i |i ∈ N, 1 ≤ j ≤ p i };
• for each i: π i = {x 1 i , . . . , x p i i }; • for each i and each j ≤ p i , let ε i, j be the jth digit in the binary representation of p i . Note that ε i,p i = 1 by definition of p i . If x is a propositional variable then we use the following notation: 0.x = ¬x and 1.x = x. Then define

γ i = V j∈{2,...,p i },ε i, j =0 V 1≤k≤ j-1 ε i, j .x k i → ¬x j i
• finally, for each s ∈ S, let µ(s) ∈ 2 V defined by: x j i ∈ µ(s) if and only if the jth digit of the binary representation of r i (Z i (s)) is 1.

For every i ∈ N and every Z ∈ At(i), let k = r i (Z) and s i (Z) the strategy of player in i in G corresponding to the binary representation of k using {x i 1, . . . , x p i i }, x i 1 being the most significant bit. For instance, if

p i = 3 and r i (Z i ) = 6 then s i (Z) = (x i 1, x i 2, ¬x i 3).
Note: To follow the proof, it may be helpful to see how this construction works on an example. Let N = {1, 2, 3}, S = {1, 2, 3, 4, 5, 6, 7, 8, 9, A, B,C}, At(1) = {1234, 5678, 9ABC}, At(2) = {13579B, 2468AC}, At(3) = {12569C, 3478AB} (parentheses for subsets of S are omitted -1234 means {1, 2, 3, 4} and so on). By decomposability,we have At(12) = {13, 24, 57, 68, 9B, AC}, At(13) = {12, 34, 56, 78, 9C, AB}, and

At(23) = {159, 37B, 26C, 48A}. |At(1)| = 3, therefore p 1 = 2. |At(2)| = |At(3)| = 2, therefore p 2 = p 3 = 1. Thus, V = {x 1 1, x 1 2, x 2 1, x 3 1}. Let At(1) = {Z 0 , Z 1 , Z 2 }, that is, r 1 (1234) = 0, r 1 (5678) = 1 and r 1 (9ABC) = 2. Likewise, r 2 (13579B) = 0, r 2 (2468AC) = 1, r 3 (12569C) = 0 and r 3 (3478AB) = 1. Consider s = 6. We have s = 5678∩2468AC ∩12569C, therefore s G = µ(s) = (¬x 1 1, x 1 2, x 2 1, ¬x 3 1). The con- straints are γ 1 = (x 1 1 → ¬x 1 2), γ 2 = γ 3 = .
Then, we show that for every C, Eff G (C) = µ(Eff(C)). The proof, though rather long, does not present any particular difficulty. See [START_REF] Bonzon | Efficient coalitions in boolean games[END_REF].

Efficient coalitions

Definitions and characterization

We now consider full Boolean games and define efficient coalitions. Informally, a coalition is efficient in a Boolean game if and only if it has the ability to jointly satisfy the goals of all members of the coalition: Observe first that ϕ 1 ∧ ϕ 3 is inconsistent, therefore no coalition containing {1, 3} can be efficient. {1} is not efficient, because ϕ 1 cannot be made true only by fixing the value of a; similarly, {2} and {3} are not efficient either. {1, 2} is efficient, because the joint strategy

s {1,2} = ab is such that s {1,2} |= ϕ 1 ∧ ϕ 2 . {2, 3} is efficient, because s {2,3} = bc |= ϕ 2 ∧ ϕ 3 . Obviously, ∅ is efficient 6 , because ϕ ∅ = V i∈∅ ϕ i ≡ is always satisfied. Therefore, EC(G) = {∅, {1, 2}, {2, 3}}.
From this simple example we see already that EC is neither downward closed nor upward closed, that is, if C is efficient, then a subset or a superset of C may not be efficient. We also see that EC is not closed under union or intersection: {1, 2} and {2, 3} are efficient, but neither {1, 2} ∩ {2, 3} nor {1, 2} ∪ {2, 3} is.

Example 2 (kidney exchange, after [START_REF] Abraham | Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchange[END_REF]). Consider n pairs of individuals, each consisting of a recipient R i in urgent need of a kidney transplant, and a donor D i who is ready to give one of her kidneys to save R i . As D i 's donor kidney is not necessarily compatible with R i , a strategy for saving more people consists in considering the graph {1, . . . , n}, E containing a node i ∈ 1, . . . , n for each pair (D i , R i ) and containing the edge (i, j) whenever D i 's kidney is compatible with R j . A solution is any set of nodes that can be partitioned into disjoint cycles in the graph: in a solution, a donor D i gives a kidney if and only if R i is given one. An optimal solution (saving a maximum number of lifes) is a solution with a maximum number of nodes. The problem can be seen as the following Boolean game G:

• N = {1, . . . , n};

• V = {g i j |i, j ∈ {1, . . . , n}}; g i j being true means that D i gives a kidney to R j .

• π i = {g i j ; 1 ≤ j ≤ n};
• for every i, γ i = V j =k ¬(g i j ∧ g ik ) expresses that a donor cannot give more than one kidney.

• for every i, ϕ i = W ( j,i)∈E g ji expresses that the goal of i is to be given a kidney that is compatible with R i .

For example, take n = 5 and E = {(1, 1), (1, 2), (2, 3), (2, 4), (2, 5), (3, 1), (4, 2), (5, 4)}. Then G = (N,V, Γ, π, Φ), with

• N = {1, 2, 3, 4, 5} • V = {g i j | 1 ≤ i, j ≤ 5}; • ∀i, γ i = V j =k ¬(g i j ∧ g ik )
• π 1 = {g 11 , g 12 , g 13 , g 14 , g 15 }, and similarly for π 2 , etc. nition of an efficient coalition could be changed so as to exclude ∅, further notions and results would be unchanged.

• ϕ 1 = g 11 ∨ g 31 ; ϕ 2 = g 12 ∨ g 42 ; ϕ 3 = g 23 ; ϕ 4 = g 24 ∨ g 54 ; ϕ 5 = g 25 .

The corresponding graph is depicted below. We have seen that the set of efficient coalitions associated with a Boolean game may not be downward closed nor upward closed, nor closed under union or non-empty intersection. We find that it is possible to characterize the efficient coalitions of a Boolean game.

Proposition 2. Let N = {1, . . . , n} be a set of agents and SC ∈ 2 2 N a set of coalitions.

There exists a Boolean game G over N such that the set of efficient coalitions for G is SC (i.e. EC(G) = SC ) if and only if SC satisfies these two properties:

(1) ∅ ∈ SC .

(2) for all I, J ∈ SC such that I ∩ J = ∅, I ∪ J ∈ SC .

Thus, a set of coalitions corresponds to the set of efficient coalitions for some Boolean game if and only if (a) it contains the empty set and (b) it is closed by union of disjoint coalitions. Sketch of proof: 7 The (⇒) direction is proven easily; intuitively, when two disjoint coalitions I and J are efficient, each one has a strategy guaranteeing its goals to be satisfied, and the joint strategies of I and J guarantee that the goals of all agents in I ∪ J are satisfied. As seen in Example 1, this is no longer true when I and J intersect. The (⇐) direction of the proof is more involved and needs the following Boolean game G to be constructed for each set of coalitions SC satisfying ( 1) and

(2):

• V = {connect(i, j)|i, j ∈ N} (all possible connections between players);

• ∀i, γ i = ;

• π i = {connect(i, j)| j ∈ N} (all connections from player i);

• ϕ i = W I∈S C ,i∈I F I , where F I = V j,k∈I connect( j, k) V V
j∈I,k ∈I ¬connect( j, k) (player i wants all the players of her coalition to be connected with each other and disconnected from the players outside the coalition).

We want to show that EC G = SC (where EC G is the set of efficient coalitions for G). We first show that SC ⊆ EC G . Let I ∈ SC . If every agent i ∈ I plays

V j∈I connect(i, j) V V k ∈I ¬connect(i, k)
, then ϕ i is satisfied for every i ∈ I. Hence, I is an efficient coalition for G and SC is included in EC(G).

In order to prove that EC G ⊆ SC, we define a covering of a coalition I by disjoint subsets of SC as a tuple C = C i |i ∈ I of coalitions such that: (a) for every k ∈ I,

C k ∈ SC ; (b) for all C j ,C k ∈ C, either C j = C k or C j ∩ C k = ∅; (c) for every i ∈ I, i ∈ C i . Let Cov(S C , I) be the set of all covering of I by disjoint subsets of SC . For instance, if SC = {∅, 1, 24, 123, 124} then Cov(S C,12) = { 1, 24 , 123, 123 , 124, 124 } 8 , Cov(S C , 124) = { 1, 1, 24 , 1, 24, 24 , 124, 124, 124 }, Cov(S C,123) = { 123, 123, 123 } and Cov(S C,234) = Cov(S C , 1234) = ∅.
The proof goes along the following steps:

L1 For any collection Col = {C i , i = 1, . . . , q} ⊆ 2 2 N , V 1≤i≤q F C i is satisfiable if and only if for any i, j ∈ {1, . . . , q}, either C i = C j or C i ∩C j = ∅.
L2 From L1, we deduce that ∀I = ∅, Φ I is equivalent to

W C∈Cov(S C ,I) V i∈I F C i .
L3 From property (2) (assumption of Proposition 2) and L2, we can prove that if I ⊆ 2 N , then Φ I is satisfiable if and only if there exists J ∈ SC such that I ⊆ J.

Let I be an efficient coalition such that I ∈ SC (which implies I = ∅, because by assumption ∅ ∈ SC ).

• If I = N then there is no J ∈ SC such that I ⊆ J (because I ∈ SC ), and then L3 implies that Φ I is unsatisfiable, therefore I cannot be efficient for G.

• Assume now that I = N and define the following Ī-strategy S Ī ( Ī = N \ I):

for every i ∈ Ī, s i = {¬connect(i, j)| j ∈ I} (plus whatever on the variables

connect(i, j) such that j ∈ I). Let C = C i , i ∈ I ∈ Cov(S C,I).
We first claim that there is a i * ∈ I such that C i * is not contained in I. Indeed, suppose that for every i ∈ I, C i ⊆ I. Then, because i ∈ C i holds for every i, we have S i∈I C i = I. Now, C i ∈ SC for all i, and any two distinct C i ,C j are disjoint, therefore, by property (2) we get I ∈ SC , which by assumption is false.

Now, let k ∈ C i * \ I (such a k exists because C i * is not contained in I). Now, the satisfaction of F C i requires connect(k, i * ) to be true, because both i and k are in C i . Therefore s k |= ¬F C i , and a fortiori s Ī |= ¬F C i , which entails s Ī |= ¬ V i∈I F C i .
This being true for any C ∈ Cov(S C , I), we have

s Ī |= V C∈Cov(S C ,I) ¬ V i∈I F C i . that is, sĪ |= ¬ W C∈Cov(S C ,I) V i∈I F C i .
Together with L2, this entails s Ī |= ¬Φ I . Hence, I does not control Φ I and I cannot be efficient for G.

The notion of efficient coalition is the same as the notion of successful coalition in qualitative coalitional games (QCG) introduced in [START_REF] Wooldridge | On the computational complexity of qualitative coalitional games[END_REF], even if, as we discuss in Section 5, QCG and Boolean games are quite different.

Efficient coalitions and the core

We now relate the notion of efficient coalition to the usual notion of core of a coalitional game. In coalitional games with ordinal preferences, the core is usually defined as follows (see e.g. [START_REF] Aumann | A survey of cooperative games without side payments[END_REF][START_REF] Owen | Game Theory[END_REF][START_REF] Myerson | Game Theory: Analysis of Conflict[END_REF]): a strategy profile s is in the core of a coalitional game if and only if there exists no coalition C with a joint strategy s C that guarantees that all members of C are better off than with s. Here we consider also a stronger notion of core: a strategy profile s is in the strong core of a coalitional game if and only if there exists no coalition C with a joint strategy s C that guarantees that all members of C are at least as satisfied as with s, and at least one member of C is strictly better off than with s. Definition 6. Let G be a Boolean game. The (weak) core of G, denoted by WCore(G), is the set of strategy profiles s = (s 1 , . . . , s n ) such that there exists no C ⊂ N and no s C ∈ S C such that for every i ∈ C and every s -C ∈ S -C , (s C , s -C ) i s.

The strong core of a Boolean game G, denoted by SCore(G), is the set of strategy profiles s = (s 1 , . . . , s n ) such that there exists no C ⊂ N and no s C ∈ S C such that for every i ∈ C and every s -C ∈ S -C , (s C , s -C ) i s and there is an i ∈ C such that for every s -C ∈ S -C , (s C , s -C ) i s.

This concept of weak core is equivalent 9 to the notion of strong Nash equilibrium introduced by [START_REF] Aumann | Acceptable points in general n-person games[END_REF], where coalitions form in order to correlate the strategies of their members. This notion involves, at least implicitly, the assumption that cooperation necessarily requires that players be able to sign "binding agreements": players have to follow the strategies they have agreed upon, even if some of them, in turn, might profit by deviating. However, if players of a coalition C agreed for a strategy s C , at least one player i ∈ C is satisfied by this strategy: we have ∃i ∈ C such that s |= ϕ i .

The relationship between the (weak) core of a Boolean game and its set of efficient coalitions is expressed by the following simple result. The proofs of following results can be found in [START_REF] Bonzon | Efficient coalitions in boolean games[END_REF]: Proposition 3. Let G = (N,V, Γ, π, Φ) be a Boolean game. s ∈ WCore(G) if and only if s satisfies at least one member of every efficient coalition, that is, for every

C ∈ EC(G), s |= W i∈C ϕ i .
In particular, when no coalition of a Boolean game G is efficient, then all strategy profiles are in WCore(G). Moreover, the weak core of a Boolean game cannot be empty: Proposition 4. For any Boolean game G, WCore(G) = ∅.

The strong core of a Boolean game is harder to characterize in terms of efficient coalitions. We only have the following implication. Proposition 5. Let G = (N,V, Γ, π, Φ) be a Boolean game, and s be a strategy profile. If s ∈ SCore(G) then for every C ∈ EC(G) and every i ∈ C, s |= ϕ i . Thus, a strategy in the strong core of G satisfies the goal of every member of every efficient coalition. The following counterexample shows that the converse does not hold.

Example 3. Let G = (N,V, Γ, π, Φ) be a Boolean game. We have: V = {a, b, c, d, e, f }, N = {1, 2, 3, 4, 5, 6}, γ i = for every i,

π 1 = {a}, π 2 = {b}, π 3 = {c}, π 4 = {d}, π 5 = {e}, π 6 = { f }, ϕ 1 = b ∨ d, ϕ 2 = a ∨ c, ϕ 3 = ¬b ∨ d, ϕ 4 = e, ϕ 5 = ¬a ∧ ¬b ∧ ¬c
and ϕ 6 = ¬a ∧ ¬c ∧ ¬d. This game has two efficient coalitions: {1, 2} and {2, 3}. Let s = abcde f . We have

s |= ϕ 1 ∧ ϕ 2 ∧ ϕ 3 ∧ ¬ϕ 4 ∧ ¬ϕ 5 ∧ ¬ϕ 6 . So, ∀C ∈ EC(G), ∀i ∈ C, s |= ϕ i . However, s ∈ SCore(G): ∃C = {1, 2, 3, 4, 5} ⊂ N such that ∃s C = abcde |= ϕ 1 ∧ ϕ 2 ∧ ϕ 3 ∧ϕ 4 ∧¬ϕ 5 . So, ∀s -C , (s C , s -C ) 1 s, (s C , s -C ) 2 s, (s C , s -C ) 3 s, (s C , s -C ) 5 s, and (s C , s -C ) 4 s. s ∈ SCore(G).
Note that the strong core of a Boolean game can be empty: in Example 1, the set of efficient coalitions is {∅, {1, 2}, {2, 3}}, therefore there is no s ∈ S such that for all C ∈ EC(G), for all i ∈ C, s |= ϕ i , therefore, SCore(G) = ∅. However, we can show than the non-emptyness of the strong core is equivalent to the following simple condition on efficient coalitions. Proposition 6. Let G = (N,V, Γ, π, Φ) be a Boolean game. We have the following: Score(G) = / 0 if and only if S {C ⊆ N|C ∈ EC(G)} ∈ EC(G), that is, if and only if the union of all efficient coalitions is efficient.

Conclusion

We have shown that Boolean games can be used as a compact representation setting for coalitional games where players have dichotomous preferences. This specificity lead us to define an interesting notion of efficient coalitions. We have given an exact characterization of sets of coalitions that correspond to the set of efficient coalitions for a Boolean game, and we have given several results concerning the computation of efficient coalitions. Note that some of our notions and results do not explicitly rely on the use of propositional logic. For instance, efficient coalitions can be defined in a more general setting where goals are simply expressed as nonempty sets of states. However, many notions (in particular, the control assignment function π) become much less clear when abstracting from the propositional representation.

Clearly, a limitation of our results is that they apply to dichotomous preferences only. However, as illustrated on Example 2, some problems are naturally expressed with dichotomous goals. Moreover, it is always worth starting by studying simple cases, especially when they already raise complex notions 10 .

As Boolean games, qualitative coalitional games (QCG), introduced in [START_REF] Wooldridge | On the computational complexity of qualitative coalitional games[END_REF], are games in which agents are not assigned utility values over outcomes, but are satisfied if their goals are achieved. A first difference between QCG and Boolean games is that there is no control assignment function in QCG. A second one is that each agent in QCG can have a set of goals, and is satisfied if at least one of her goals is satisfied, whereas each agent in Boolean games has a unique goal. However, QCG's characteristic function, which associates to each coalition C the sets of goals that members of C can achieve, corresponds in Boolean games to the set W (C) = {X ⊆ {ϕ 1 , . . . , ϕ n } such that ∃s C ∈ S C : s C |= ϕ i } 11 .

Coalition logic [START_REF] Pauly | Logic for Social Software[END_REF] allows to express, for any coalition C and any formula ϕ, the ability of C to ensure that ϕ hold (which is written [C]ϕ). In Boolean games, the power of agents, expressed by the control assignment function π, is still in the metalanguage. Expressing π within coalition logic would however be possible, probably using ideas from [START_REF] Van Der Hoek | On the logic of cooperation and propositional control[END_REF]. The next step would then consist in introducing goals into coalition logic. This is something we plan to do in the near future.

Definition 5 .Example 1 .

 51 Let G = (N,V, π, Γ, Φ) be a Boolean game. A coalition C ⊆ N is efficient if and only if ∃s C ∈ S C such that ∀s -C , s C |= V i∈C ϕ i . The set of all efficient coalitions of a game G is denoted by EC(G). Let G = (N,V, Γ, π, Φ) where V = {a, b, c}, N = {1, 2, 3}, γ i = for every i, π 1 = {a}, π 2 = {b}, π 3 = {c}, ϕ 1 = (¬a ∧ b), ϕ 2 = (¬a ∨ ¬c) and ϕ 3 = (¬b ∧ ¬c).

  efficient coalitions correspond to solutions. In our example, the efficient coalitions are ∅, {1}, {2, 4}, {1, 2, 4}, {1, 2, 3}, {2, 4, 5} and {1, 2, 4, 5}.

  If s and s are two strategy profiles, (s -I , s I ) denotes the strategy profile obtained from s by replacing s i with s i for all i ∈ I. |= ¬ϕ i and u i (s) = 1 if s |= ϕ i . s is at least as good as s for i, denoted by s i s , if u i (s) ≥ u i (s ), or equivalently, if s |= ¬ϕ i implies s |= ¬ϕ i ; s is strictly better than s for i, denoted by s i s , if u i (s) > u i (s ), or, equivalently, s |= ϕ i and s |= ¬ϕ i .

	The goal ϕ i of player i is a compact representation of a dichotomous preference
	relation, or equivalently, of a binary utility function u i : S → {0, 1} defined by u i (s) =
	0 if s

We refer here to the version of Boolean games defined in[START_REF] Bonzon | Boolean games revisited[END_REF], that generalizes the initial proposal[START_REF] Harrenstein | Boolean games[END_REF].

In the original proposal[START_REF] Harrenstein | Boolean games[END_REF], Boolean games are two-players zero-sum games. However the model

Note that effectivity functions induced by pre-Boolean games may be equivalently expressed as mappings Eff : 2 N → 2 L V from coalitions to sets of logical formulas: ϕ ∈ Eff(I) if Mod π I (ϕ) ∈ Eff(I). This definition obviously implies syntax-independence, that is, if ϕ ≡ ψ then ϕ ∈ Eff(I) iff ψ ∈ Eff(I).

A complete version of this proof can be found in[START_REF] Bonzon | Efficient coalitions in boolean games[END_REF].

One may argue this makes little sense to say that the empty coalition is efficient. Anyway, the defi-

A complete version of this proof can be found in[START_REF] Bonzon | Efficient coalitions in boolean games[END_REF].

There are two players in I = {1, 2}, therefore each C in Cov(S C , 12) contains 2 coalitions, one for each player, satisfying (a), (b) and (c).

This equivalence is easily shown: it is just a rewriting of the definition given in[START_REF] Aumann | Acceptable points in general n-person games[END_REF].


Cédric Gil-Jardiné

Gabrielle Chenais

Catherine Pradeau

Eric Tentillier

Philipe Revel

Xavier Combes

Michel Galinski

Eric Tellier

Emmanuel Lagarde

Gil-Jardiné Cédric

Chenais Gabrielle

Pradeau Catherine

Tentillier Eric

Revel Philipe

Combes Xavier

Galinski Michel

Tellier Eric

Lagarde Emmanuel

* Affiliations

Trends in reasons for emergency calls during the COVID-19 crisis in the department of Gironde, France using automatic classification

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Coronavirus 2019 Disease (COVID-19) caused by Severe Acute Respiratory Syndrome Coronavirus 2 (SARS-CoV-2) was detected for the first time in December 2019 in China [START_REF] Zhu | A novel coronavirus from patients with pneumonia in China[END_REF] . Since then, as of first November 2020, more than 40 million cases and more than 1,100,000 deaths have been reported worldwide [START_REF] Who | Coronavirus (COVID-19) events as they happen[END_REF] .

Health-related surveillance data are indispensable for the adjustment of public health policies aimed at curbing the spread of the virus and protecting vulnerable populations, for adapting the means of caring for the most seriously ill, and for assessing the indirect consequences of the pandemic and of the measures implemented to control it: lockdown, movement restriction, social distancing and quarantine for some countries.

Many countries have relied on an extrapolation of classic infection-control and public-health measures to contain the COVID-19 pandemic, similar to those used for SARS in 2003 and H1N1 in 2009. These range from extreme quarantine measures in China to painstaking detailed contact tracing with hundreds of contact tracers (e.g., Singapore, Hong Kong, South Korea). However, these measures may not be effective in 2020 for tackling the scale of COVID-19 [START_REF] Ting | Digital technology and COVID-19[END_REF] . Monitoring, surveillance, detection and prevention of COVID-19 have launched a new challenge on a global scale and digital technologies have so far failed to be the driving force behind it with a few notable exceptions [START_REF] Park | Information Technology-Based Tracing Strategy in Response to COVID-19 in South Korea-Privacy Controversies[END_REF] .

The number of people who test positives by PCR or chest CT images with characteristic lung damage is the most reliable indicator of the number of people with the virus. It is, however, heavily dependent on the screening strategy, which varies greatly from one country to another. The number of people entering an ER with symptoms suggesting SARS-CoV-2 infection was implemented nationally in France on March 16, 2020, with specific coding of the main diagnosis in ER summary reports centralized by Santé Publique France in the OSCOUR® Emergency Department Surveillance Network [START_REF] Josseran | Assessment a syndromic surveillance system based on morbidity data: results from the Oscour network during a heat wave[END_REF] set up in 2004. The French health authorities are also monitoring the number of COVID-19 patients hospitalized, admitted to intensive care units, and the number of deaths in hospital and in nursing homes (EHPAD).

All these tools, completed by a large set of ad-hoc surveys and specific surveillance systems have been mobilized to monitor the course of the epidemics and its consequences. For example, analysis of the registry of the Paris-Sudden Death Expertise Center observed a transient increase in cardiac arrest incidence [START_REF] Marijon | Out-of-hospital cardiac arrest during the COVID-19 pandemic in Paris, France: a population-based, observational study[END_REF] . A similar observation was reported in Lombardy, Italy, a region heavily impacted by the COVID-19 pandemic [START_REF] Baldi | Out-of-hospital cardiac arrest during the Covid-19 outbreak in Italy[END_REF] .

Reports of call content to emergency medical communication centers (EMCC) is a source of information that needs to be considered for health surveillance during such a pandemic. By dialing 15, French citizens can get medical advice and, if necessary, a medical mobile care unit can be sent to the scene. In addition, the health authorities had instructed the population to call 15 in the case of symptoms or concerns, and to avoid spontaneous uninvited visits to the emergency room (ER) [START_REF] Adnet | International EMS systems: France[END_REF] .

We used an automatic classification tool based on an artificial neural network language model we recently adapted for free-text clinical notes [START_REF] Xu | Pre-Training a Neural Language Model Improves the Sample Efficiency of an Emergency Room Classification Model[END_REF] to identify the main reasons for calls to the Gironde EMCC, in order to monitor trends in the nature of these calls before, during and after the national lockdown established in France on March 17, 2020 and eased on May, 11, 2020.

Method

Setting

The Gironde department (1.6 million inhabitants) is served by a medicalized EMCC known as SAMU 33 (Service d'Aide Médicale Urgente de la Gironde) which answers calls to the French toll-free number dedicated to medical emergencies (the "15"). A call is first received by a medical assistant, and then an emergency physician or a general practitioner (depending on the severity of the case) decides on the appropriate response, from medical advice to the dispatch of an ambulance or a mobile intensive care unit [START_REF] Josseran | Assessment a syndromic surveillance system based on morbidity data: results from the Oscour network during a heat wave[END_REF] .

Clinical reports

For all cases handled, a clinical report is created in the form of a computerized free-text note and updated by a medical assistant and a physician through the various telephone interactions with the patient, family, witnesses, and then with the paramedics if applicable. These clinical notes contain all the elements that make it possible to know the circumstances of the event at the origin of the call and the clinical observations made by the protagonists, whether they are witnesses, the patients themselves, or the medical personnel involved on site or responding to the call.

Classification of clinical reports using the GPT-2 neural language model

Over the past 10 years, neural language models have progressively taken the largest share in the field of natural language, with applications like machine translation, document classification, text summarization and speech recognition.

New levels of performance have only recently been achieved with the use of models based on the concept of attention, which consists in learning dependencies between words in a sentence without regard to their distances. This mechanism has been implemented in a sequence to sequence neural network model, the Transformer architecture, proposed in 2017 [START_REF] Vaswani | Attention Is All You Need[END_REF] . One of the latest examples is the GPT-2, published in February 2019 by OpenAI. GPT-2 is a large transformer-based language model trained on a dataset of 8 million web pages [START_REF] Radford | Language models are unsupervised multitask learners[END_REF] . Beyond the capability to generate coherent texts, Transformer models have the potential to perform other tasks such as question answering and document classification with a limited number of training examples. The training of the model is performed in two distinct phases [START_REF] Radford | Improving language understanding by generative pretraining[END_REF] : the first pre-training unsupervised phase (i.e. not needing a human classification), consists in exploitation of a text corpus. In our application, this consisted in the 312,367 clinical reports of the year 2018. This leads to the ability of automatic text generation (see Supplementary material 1). The relevance of these synthetic sentences suggests that the networks learn contextual semantic representations. The second training phase, this time a supervised one (i.e. using examples classified by humans), creates a system able to perform the specific classification tasks.

The 117-million parameters version of the GPT-2 model was trained on a workstation with one Nvidia GeForce RTX Titan Graphic Processing Unit with 24GB of VRAM. The computation time for the pre-training phase was 26 hours per epoch. On average, 12 samples were processed per second in the training phase.

Extraction of free-text digital calls reports from the EMCC of the Gironde department, France

We retrieved call reports from the digital medical record system of the EMCC of the Gironde department, France. Five EMCC datasets were extracted corresponding to the years 2016, 2017,2018, 2019 and 2020. The three 2016, 2017, 2018 datasets consisted of 888,469 calls with a free-text clinical report and were used both for the unsupervised pre-training of the GPT-2 model and for the building of the training sample based, when available, on standardized diagnosis coded during the calls. The 2019 dataset corresponded to the 302,925 free-text clinical call reports of the year 2019. A random sample of this dataset was manually coded by a trained pool of emergency nurses for validation. The trained and validated models were applied to the 2020 dataset which corresponded to the COVID-19 period, with 255,556 handled calls with a free-text report from January 1, 2020 to September 30, 2020. This provided a classification of reasons for calls before (January 1-March 16), during (March 17-May 10) and after (May 11-September 30) COVID-19 lockdown.

Selected groups of reasons for calls

A first model was built by grouping calls according to the main reasons into 12 broad categories (chest pain, gastroenteritis and abdominal pain, flu-like symptoms and breathing difficulties, focal neurologic deficit and stroke, road traffic crash, violence, suicide and self-harm, injury other than violence, self-harm and road crash, pregnancy and delivery problems, malaise with loss of consciousness, stress and anxiety). Many symptoms or situations did not fall into these broad categories and were grouped into a thirteenth "other" category.

Another distinct model was built to count calls for which an acute alcohol intoxication was involved.

Classification procedure

Classification models were built and validated using a five-phase procedure: (iii) These two models were validated using the manual coding of a 39,907 random sample from the 2019 dataset.

(v) All 254,633 call reports of 2020 (January to September) were classified using the two models built in the previous steps;

Emergency room admissions with suspected COVID-19 and SARS-CoV2-2 PCR tests result

We retrieved daily aggregated data of ER admission with suspected COVID-19 and the daily number of SARS-Cov-2 PCR positive tests in the department of Gironde from the national public health agency "Santé Publique France". All data are available on the Geodes website (https://geodes.santepubliquefrance.fr/).

Analysis

For all call reasons, a probability cutpoint was determined in order to optimize the accuracy of the number of calls estimated by the model. This was done by selecting the cutpoint for which precision and recall are equal in the validation sample (i.e. when the number of false positive predictions equals the number of false negative predictions). The confidence of the method was assessed using a bootstrap procedure with 10,000 1:1 random partitions of the validation sample. For each partition (and each reasons), the cutpoint is selected using the first half of this partition sample and is the one for which precision equals recall. The difference between the manually determined prevalence of the given reasons and the predicted prevalence (using the selected cutpoint) is then computed in the second half of the sample. Median bias and 95% confidence interval were derived from the distribution of these 10,000 bias measures. Estimated daily counts of calls to EMCC were plotted against time with a 7-days moving average window to smooth the one-week periodicity in calls, which were systematically 25% more frequent on Saturday and Sunday.

Results

Model training, parametrization and validation

The unsupervised training phase led to a model capable of generating artificial texts with the same structure as the learning texts, containing essentially the same clinical notions, but whose coherence is often inconsistent (see examples in the appendix). The content of these synthetic reports however suggests that the model has learned contextual semantic representations.

The training sample included from 1,829 (road traffic crash) to 412,218 (other reasons) samples per group (see Table 1). Performance statistics computed using the 39,907 manually-coded samples are shown in Table 1. Area under the ROC curve ranged from 0.785 to 0.990.

The optimal cutpoints to minimize bias in prevalence estimates were chosen using the same manually-coded sample of 39,907 call reports. Bootstrap 95% confidence interval assessment showed that the method provided narrow confidence intervals (Table1).

Reasons for calls during the Covid-19 crisis

In 2020, the median daily number of calls to the EMCC with a report was 892 with a total number of 254,633 and a peak of 1,926 on March 14. The distribution of the estimated number of calls per group of reasons and according to the lockdown period is shown in Table 2.

Three groups exhibited a peak at the onset of the lockdown period. Figure 1 shows that calls for flu-like symptoms and breathing difficulties began to rise on February 21, 20 days before the rise in ER admission for COVID-19, and peaked on March 14 with 928 calls out of a total of 1,926 calls that day. By the 16th day after February 21, the number of calls in this group had reached 403 calls per day, which is higher than all levels over the past 5 years. Starting from March, 1, 2020, the correlation between daily calls for flu-like symptoms and daily ER admissions with a delay of 14 days was 0.80 (p <10 -15 ; Pearson's test). Two other reasons, chest pain and stress and anxiety, were found to peak 12 days after March 14, with a curve of the same shape as the number of ER visits for COVID-19.

Figure 2 shows that calls for alcohol intoxication, road traffic crash and malaise with loss of consciousness experienced a sharp decline around the onset of lockdown and that these trends started several days before the first day of lockdown. In a lesser extent, the latter curves were parallel with those for violence and injuries other than violence and road crash. Finally, no noticeable trends in relation to lockdown was found for other groups of reasons including gastroenteritis and abdominal pain, stroke, suicide and self-harm, pregnancy and delivery problems.

Discussion

The number of calls to EMCC showed a significant spike centered on the March 14, the day before the closure of all nonessential public places in France, three days before lockdown. The main reasons were related to flu-like symptoms (cough and/or fever), followed 14 days later by a peak in ER admissions, in calls for chest pain and calls for stress and anxiety. Calls for road traffic crashes, malaises with loss of consciousness, non-voluntary injuries and alcohol intoxication fell by 59%, 38%, 24% and 23% respectively during lockdown.

Probably the most interesting finding of our study is the delay we observed between the rise in calls for flu-like symptoms (mainly cough and fever) and the rise in ER visits for suspected COVID-19. Thus, the curve began to rise 20 days before the increase in ER visits. By the 16th day after the start of this rise, the levels reached a level higher than any levels in the past 5 years. One could hypothesize that the peak of calls recorded around March 14 was due by the concern, if not anxiety, caused by the announcement on television of the closure of public places by the French President on that day. However, in a more affected part of the country, the Ile-de-France region, the peak was reached much earlier (10 days earlier) [START_REF] Riou | Emergency calls are early indicators of ICU bed requirement during the COVID-19 epidemic[END_REF] , suggesting that most of the calls we recorded were more motivated by symptoms than by concerns raised by communication by the authorities. Further, a spike in calls for stress and anxiety was measure 14 days later. EMCC call content is therefore probably the most predictive early indicator of the start of the epidemic, as recently shown by Riou and colleagues who found in the Ile-de-France region a strong correlation between calls regarding suspected COVID-19 and the number of patients in intensive care, with a delay of 23 days [START_REF] Riou | Emergency calls are early indicators of ICU bed requirement during the COVID-19 epidemic[END_REF] . This is why this is considered for the monitoring of a potential relapses in the epidemic [START_REF] Salje | Estimation of the burden of SARS-CoV2 in France[END_REF] . Finally, while the number of calls for flu-like symptoms proved to be an early and relevant signal, its intensity was probably increased by the request of the authorities not to go directly to the ER and to contact instead the EMCC.

An important difference between the work of Riou and colleagues and this study is that our process was clearly agnostic to the COVID-19 epidemic or to lockdown, as the automatic classification used models trained using reports from previous years. This results in a procedure that remains independent of the COVID-19 epidemic and lockdown, which would have influenced human codification. The signal thus obtained depends less on the context and is more likely to be an indicator of the actual public health situation. More generally, the added value of using an automatic classification procedure based on a natural language processing model is that it frees us from the context in which the reported events are coded. For this reason, we did not use the coded diagnoses at the time of the call to observe trends. In addition, these diagnoses were absent from one-third of the reports.

In the context of the COVID-19 epidemic, several research teams have used a similar approach, attempting to investigate the internet or social media to build early indicators of the epidemic [START_REF] Li | Retrospective analysis of the possibility of predicting the COVID-19 outbreak from Internet searches and social media data, China[END_REF][START_REF] Ayyoubzadeh | Predicting COVID-19 incidence through analysis of Google trends data in Iran: Data mining and deep learning pilot study[END_REF] . However, no such signal could be found from a Google keyword search 18 , as the peak for cough, fever, coronavirus or COVID-19 was not reached until the week of 15-21 March.

Contrary to what was observed in Paris [START_REF] Lapostolle | Collateral consequences of COVID-19 epidemic in Greater Paris[END_REF] , no increase in calls related to cardiac arrest was observed in our study. This observation supports the hypothesis that the transient twofold increase in out-of-hospital cardiac arrests observed in Paris and its suburbs could be due to COVID-19 infections and to pandemic-related health system issues in heavily impacted regions. This was clearly not the case in the Gironde department where EMCC and intensive care units have never been overwhelmed.

A very significant decrease in calls for malaise with loss of consciousness, and to a lesser extent for strokes, was observed, starting one week before lockdown. This paralleled the sudden drop in ER visits that was observed in many countries that issued a statewide stay-at-home order [START_REF] Wong | Where are all the patients ? Addressing COVID-19 fear to encourage sick patients to seek emergency care[END_REF] , raising concerns that patients who needed medical care were not presenting to the hospitals and, for example, that stroke patients arrived too late to receive tissue plasminogen activator. The actual overall public health impact of this phenomenon will have to be carefully assessed when we have enough hindsight to appreciate its medium-term health consequences.

The decrease in calls associated with interpersonal violence and alcohol intoxication is less surprising as it is probably due to the reduction in social interactions. Interestingly, the figures returned to normal levels by the end of the lockdown period. Early on, concerns were raised about the risk of domestic violence as a result of lockdown [START_REF] Mazza | Danger in danger: Interpersonal violence during COVID-19 quarantine[END_REF] . This was not confirmed here by calls to EMCC. Although, unfortunately, not all domestic violence is reported to EMCC, this is an interesting result because most statistics used during lockdown to estimate the incidence of intimate partner violence were derived from Police reports and not all violent events reported to EMCC are reported to the police.

In order to produce results in a time frame compatible with the health emergency related to the recent lifting of lockdown measures, we used the samples from 2016-2018 for which a diagnosis was coded during the call by the medical assistant in charge of handling it. The ideal procedure would have been to perform a manual coding of this training sample, which was done for a sample of 39,907 reports from 2019, but retained in this work as a validation sample. Our previous work has shown that it takes about a thousand different examples to maximize the performance of the model [START_REF] Xu | Pre-Training a Neural Language Model Improves the Sample Efficiency of an Emergency Room Classification Model[END_REF] . This would have meant manually coding more than 100,000 notes, a task that was out of reach in a short period of time. The performances of the GPT-2 model measured with the manually coded validation samples were, however, very high and allowed us to derive a reason for call for all reports including the 22% of them with a missing value for the diagnosis. Some limitations need to be acknowledged. First, although we have shown that an AI-based natural language model shows high performance in classifying free-text clinical reports, a small proportion of reports remains misclassified. Because our exercise here was to provide prevalence estimates, we adjusted the decision cutpoints so that precision equals recall. The bootstrap analysis showed that this was a very reliable strategy. Second, not all calls are handled by the EMCC, a proportion of them remains unanswered and this proportion increases during peak periods. It is therefore likely that around March 14 the number of attempted calls was higher than those handled. Finally, the study was done in Gironde, a department with a reportedly low rate of SARS-Cov-2 infection if compared to the Ile de France and the north-east regions of France. However, lockdown and fear of the epidemic affected all French people and the Gironde EMCC are the third largest in terms of the number of calls received in France, which has made it possible to build up a sufficiently large database.

Conclusion

Given the fast spread and severity of COVID-19, the availability of reliable surveillance platforms is crucial for timely monitoring and for responding with adequate control measures to the COVID-19 epidemic and others to come, together with other major events with public health consequences. The results of this study, carried out in the context of a period of lockdown related to the COVID-19 epidemic, illustrate the extent to which automated classification of the reasons for calling EMCC is a powerful epidemiological surveillance tool, provides insights into the societal upheavals induced by a health crisis and would be instrumental to better anticipate the needs of the health care system.

Tables and Figures

  (i) A total of 888,469 records with call reports of 2016, 2017 and 2018 were used to pre-train the GPT-2 model in an unsupervised manner with 1 epochs. (ii) A dataset of training examples for supervised training was built extracting the 690,103 (out of 888,469) call reports from the same 2016, 2017, 2018 years with a diagnosis code manually coded in real time by the people handling calls (medical regulation assistants, emergency physicians and general practitioners); The pre-trained model was then finetuned using these training labelled examples to build the model used to classified main reasons for call in 12 categories and a distinct model to identify calls for which an acute alcohol intoxication was involved.

Figure 1 .

 1 Figure 1. Number of calls to the Gironde to emergency medical communication center in 2020 by reasons from GPT-2 classification with a significant increase around the onset of the lockdown period.

Figure 2 .

 2 Figure 2. Number of calls to the Gironde to emergency medical communication center in 2020 by reasons for calls from GPT-2 classification with a significant decline around the onset of the lockdown period.

Table 1 .

 1 Training sample size (from 2016-8 datasets) and validation from manually coded samples from 2019 dataset

		Training	Max F1	AUC	Accuracy Proportion in	95% confidence interval
		sample				2020	using bias estimated by
	Reasons	size					bootstrap*
	Main reasons for EMS calls
	Chest pain	29,310 0.800	0.987	0.978	0.057	0.0542 -0.0598
	Gastroenteritis and abdominal pain	63,446 0.710	0.958	0.946	0.082	0.0777 -0.0863
	Flu-like symptoms and breathing difficulties	72,323 0.683	0.958	0.929	0.151	0.1461 -0.1559
	Focal neurologic deficit, stroke	5,951 0.698	0.978	0.991	0.0135	0.0118 -0.0152
	Road traffic crash (RTC)	1,829 0.799	0.980	0.988	0.0233	0.0214 -0.0252
	Violence	3,158 0.636	0.984	0.991	0.011	0.0092 -0.0128
	Suicide and self-harm	5,904 0.654	0.969	0.988	0.015	0.0131 -0.0169
	Injury other than violence, self-harm and RTC 120,007 0.694	0.938	0.887	0.166	0.1596 -0.1724
	Pregnancy and delivery problems	6,222 0.804	0.990	0.994	0.013	0.0116 -0.0144
	Malaise with loss of consciousness	41,468 0.492	0.935	0.958	0.035	0.0313 -0.0387
	Stress and anxiety	12,198 0.479	0.877	0.956	0.046	0.042 -0.05
	Other reasons	412,218 0.673	0.785	0.746	0.385	0.3754 -0.3946
	Alcohol intoxication	8,934 0.712	0.982	0.979	0.033	0.0303 -0.0357
	* As estimated by bootstrapping (N=10,000) the validation sample

Table 2 .

 2 Reasons for calls to EMS in 2020 as determined by the GPT-2 model. Calls per day and per motive

		Before lockdown	During lockdown	After lockdown
		(calls per day)	(calls per day))	(calls per day)
	Motives
	Total	N=79,672	N=49,743	N=125,218
	Main reasons for EMS calls
	Chest pain	5.1	7.2	5.5
	Gastroenteritis and abdominal pain	8.9	7.3	8.2
	Flu-like symptoms and breathing difficulties	20.7	22.7	8.7
	Focal neurologic deficit, stroke	1.3	1.3	1.4
	Road traffic crash (RTC)	2.2	0.9	3.0
	Violence	0.10	0.08	0.13
	Suicide and self-harm	1.3	1.4	1.6
	Injury other than violence, self-harm and RTC	15.0	11.4	19.7
	Pregnancy and delivery problems	1.2	1.3	1.4
	Malaise with loss of consciousness	3.4	2.1	4.0
	Stress and anxiety	3.8	5.5	4.8
	Other reasons	35.4	36.6	41.3
	Alcohol intoxication	3.0	2.3	3.9

  Example of real and synthetic EMS clinical reports.

	ta 98/62 bd f 50
	Real EMS reports homme de 68 ans douleurs abdominales dernière selle ce matin pas de gaz vomissement il y a une heure atcd subocclusions sur brides(2) atcd dnid/irénale ap pour pole santé pas d'ambulance de garde sur le secteur tel ne repond pas sp carence h 68 a pas de pci cst fv 16 sat 94 aa puls 83 ta 146/66 bd vomissements a raccroche avant conf gene respi je fais contre appel messagerie je rappelle a nouveau je reussi a avoir la patiente depuis vendredi grippe et gastro vomissements ne s alimente pas a fait malaise pas de gene respi vendredi médecin ttt / grippe et gastro vomissement ne s'alimente pas et ne boit pas non plus vertige douluer épigastrique >>>>sp en urgence f76a dl ventre et estomac depuis 3 jrs vu med vendredi gastro dl 8/10 sat 95 cste ta g 124/65 pas de gene respi a pas manger depuis 3 jrs a bu et elle vomit consciente alcoolisée + toxique consciente >> ap pour hsa dit qu'elle ne peut pas se deplacer puls70 elle dit qu'elle est triste alcolisee + drogue sage femme du bras f 16 a F Resp : 22 sp carence Sat : 100 pas d'ap de garde sur secteur 8 TA : 132/67 ta 127/87 PLS : 72 sat 100 aa ATCD : puls 82 conscient : oui cst Bilan SP : h 90, dl epaule dit avoir etait droguer adresser les sp f 34 a douleur épaule mis en pls / insct respi / a glissé lieu de travail pense fatigue malaise pci ne reagit pas chute fv26 sat 100 aa ne mange pas / etourdi / diarrhée / s'urine dessus / ne veut pas aller a l'hopital diarrhée vertiges toux courbatures atcds : 0 ttt : 0 >> sos sos rappelle por demande de smur cyanose marbrures pas d'atcd appel pour asthénie / vertiges 8 de tension cyanosé marbré apyrétique point appel pulmonaire mis sous 02 ==> mieux. on va envoyer sp h 69 sos med place conscient orienté sos sur ll pupilles sym fv 26 diff sensation ettouff parole poss sat 84 cyanose marbrures chute / dl epaule dte / pas de pc / antcd prothese hanche dte regul r evrard hsa mdg ok demande exclusivement pellegrin pas d autres signes de gravite refus des 4 pav et de libourne toux rauque sat a 93 maman sur LL 02 9l sat pas de gene respi pas d'allergie lavage de nez pas de tt toux rauque pas d'hospi rhino mhta virose selon la mere ta g 80/50 souhaite mdg dans un premier temps fc115 reg cste Synthetic EMS reports bien oriente dl bras dt depuis dimanche / pas de fourmillement pas de pc F 41a d apres sa femme de la dame a eu rale et fatigue Douleur thoracique d'apparition brutale en se frottant les bras cette nuit sans faux mouvement antcd pbl respi + stents en 2017 Bouge bien sa jambe ni l'estomac p 64 Fumeuse sat 100 ATCD : néant ta 142/67 Douleur de novembre 2017 : RAS refuse evac Pas de dyspnée rappel sp : ne va pas bien dans cet etat pas de position antalgique pas de plainte >> SPazl, doliprane 1000 est ok pour aller a l hopital f 41 chute, plaie du front / assis par terre, assis sur le canapé, désorienté f 41 chute dl bras dt relevé par sa fille dl cou a du mal a marcher cervicales conscient pas de céphalées ****pompiers pour pellegrin a deja eu ca mais pas consulté : peut etre pire Bilan VSAV fc 57 H 96 ans ta 118/87 conscient sat 99 chute de sa hauteur toux fievre chariotale en bas toux de nouveau pas de douleur febrile 39 a du mal a parler toux seche bien oriente pas de gene respi ni malaise FC 85 ATCD: neant SAT 98 pas dautre symptome TA G 143/89 vomissements x 1 pas de trauma >> conseils pas de saignement >> rappel si besoin sous anticoagulant rappel de la mere toux pas de d'anticoagulant

Supplementary material 1.

Acknowledgement

We thank the university hospital of Bordeaux for providing the logistical support that allowed us to access and analyse the data needed for the manuscript in such a short period. We are also grateful to Julien Anjoubault, Clarisse Marguinaud, Virginie Cocuelle, Delphine Vauthier, Alexandra Barbe, François Garreau, Quentin Bana, Claire Riou, Pauline Soubelet and Elisabeth Verbitskaya for their expertise, which allowed proper manual coding for validation and to Benjamin Contrand, Loïck Bourdois and Marie-Odile Coste for data management and administrative assistance. We also thank Sylviane Lafont for her help in the beginning of the project. BPH IETO Team activities are supported by the Institut National de Santé et de la Recherche Médicale (INSERM), University of Bordeaux, Ministère de l'Intérieur (Délégation à la Sécurité Routière).

Funding

The study was founded by the French Agence Nationale de la Recherche (ANR-20-COV1-0004-01).

Availability of data and materials

A subset of the dataset analysed during the current study can be made available from the corresponding author on reasonable request.

Figure and

Confidentiality, ethics and data protection

No personal data were necessary for this work. All reports were automatically de-identified using a grep-based textsearch procedure that was applicable because of the standardized format of personal information inserted in the reports. This work conforms in terms of the protection of personal health data and the protection of privacy to the application framework provided by Article 65-2 of the amended French Data Protection Act and the General Regulation on the protection of personal data. It was approved by the Bordeaux Teaching Hospital committee for ethics and data protection.

Consent for publication

Not applicable

Competing interests

The authors declare that they have no competing interests.

Authors' contributions

CGJ and PC collected the data. GC and EL were involved in NLP models design. CGJ and EL analyzed the data and all authors were involved in results interpretation. EL and CGJ was a major contributor in writing the manuscript. All authors read and approved the final manuscript.