Vladimir Lokshin

Hervé Clavier

Vladimir Khodorkovsky

published or not. The documents may come

Spiro 1,3-indandiones: intramolecular photochemical reactions of carbonyl groups with carbon-carbon double bonds


Nahla Ben Amor
email: nahla.benamor@gmx.fr

Hélène Fargier
email: helene.fargier@irit.fr

Régis Sabbadin
email: regis.sabbadin@inrae.fr

Meriem Trabelsi
email: merieme.trabelsi@gmail.com

Ordinal Polymatrix Games with Incomplete Information

Possibilistic games with incomplete information (Π-games) constitute a suitable framework for the representation of ordinal games under incomplete knowledge. However, representing a Π-game in standard normal form requires an extensive expression of the utility functions and the possibility distribution, namely, on the product spaces of actions and types. In the present work, we propose a less costly view of Π-games, namely min-based polymatrix Π-games, which allows to concisely specify Π-games with local interactions. This framework allows, for instance, the compact representation of coordination games under uncertainty where the satisfaction of an agent is high if and only if her strategy is coherent with all of her neighbors, the game being possibly only incompletely known to the agents. Then, an important result of this paper is to show that a min-based polymatrix Π-game can be transformed, in polynomial time, into a (complete information) min-based polymatrix game with identical pure Nash equilibria. Finally, we show that the latter family of games can be solved through a MILP formulation. Experiments on variants of the GAMUT problems confirm the feasibility of this approach.

Introduction

Game theory [START_REF] Morgenstern | Theory of games and economic behavior[END_REF][START_REF] Nash | Equilibrium points in n-person games[END_REF]) essentially aims at representing, explaining, and optimizing situations in which several agents, the "players", have to choose between several decisions, the "actions",the final utility of each player depending on the actions of the other players. In non-cooperative games under complete information, the players cannot coordinate their actions but each of them knows everything about the game: the players, their available actions and all their utilities.

This assumption of complete knowledge cannot always be satisfied. In the real world, players are not so well informed and have only limited knowledge about the game. This is why incomplete information games, and more particularly Bayesian games [START_REF] Harsanyi | Games with incomplete information played by "Bayesian" players[END_REF] have been proposed to model problems where the utility degrees are additive in essence and the knowledge of the players is quantified in a probabilistic way. If a rich, quantifiable, information about the real world is not attainable, pure ordinal frameworks should rather be considered. This is why the original framework of ordinal games [START_REF] Xu | Computation of noncooperative equilibria in ordinal games[END_REF][START_REF] Cruz | Ordinal games and generalized nash and stackelberg solutions[END_REF][START_REF] Ouenniche | An ordinal game theory approach to the analysis and selection of partners in public-private partnership projects[END_REF] has been recently extended:

• In possibilistic Boolean games [START_REF] De Clercq | Modelling incomplete information in boolean games using possibilistic logic[END_REF], the knowledge of each player is expressed in the framework of possibilistic logic and the players do not receive any private information before playing. Therefore, the authors consider the problem from the external point of view of an observer who proceeds to a fusion of these pieces of knowledge and computes the possibility and the necessity of a given profile of actions being a Nash equilibrium in the usual sense;

• The framework described in (Ben Amor et al. 2019a) stays at the semantic level. Nevertheless, it allows both the expression of common knowledge and the possibility for the players to get some information -captured by the notion of "type", in the same way as in Harsanyi's incomplete information games. These "possibilistic games with incomplete information" (called Π-games) provide a purely ordinal notion of best response and pure equilibrium in the sense of Nash. It has been shown that any Π-game can be transformed into a standard normal form game with equivalent pure Nash equilibria (PNE) -this transformation being interesting from a descriptive point of view only, since exponentially costly in the size of the input. Notice that the input itself (the Π-game) is not precisely compact: it requires an extensive expression of the utility functions and of the possibility distributionnamely, on the product spaces of actions and types.

In the present work, we propose a less costly view of Πgames. We define the framework of min-based polymatrix Π-games, which allows to concisely specify Π-games with local interactions. This framework allows, for instance, the compact representation of coordination games under possibilistic uncertainty. A motivating example, along with the basic notions on which the paper relies, is presented in Section 2. Section 3 then defines the general representation framework that we propose: min-based polymatrix Π-games, and applies it to the running example. Section 4 shows that any 2-player Π-game can be transformed into an equivalent min-based polymatrix game. This result is the qualitative counterpart of Howson and Rosenthals's theorem (1974) linking Bayesian games to polymatrix games. Furthermore, as soon as a simple condition on the coherence of the players' knowledge about the world is satisfied, any polymatrix Π-game can be transformed in polytime into an equivalent min-based and complete information polymatrix game. Finally, Section 5 proposes a MILP formulation of the problem of deciding whether a polymatrix Π-game admits a PNE and presents experimental results.

Background

A Motivating Example

Let us consider a game where several agents have to choose between multiple competing offers, e.g., choosing an internet provider. This game is a kind of "coordination game" [START_REF] Simon | Constrained pure Nash equilibria in polymatrix games[END_REF]). An agent is satisfied at a high degree if and only if all her neighbors choose the same service as she does -for instance, because the satisfaction of the agent is relative to the security of her communications with her neighbors and the security level of the network is not guarantee when different services are used.

This kind of game is typically based on a graph and the satisfaction of an agent is the minimum, over all her neighbors, of the satisfaction she gets in local games with single neighbor. Of course, agents may have more gradual preferences, e.g., because they prefer some providers to other ones.

The preferences of the agents may also depend on an external event, e.g., an incentive that some of them receivetypically, an offer from some provider. Of course, the belief of a player about what offers her neighbors receive depends on what the player receives herself: normally, if I receive an offer, so do my neighbors; and if I do not receive anything, they do not either. But I may receive something while my neighbors do not.

In order to model such an example, we rely on two groups of works: polymatrix games on the one hand and games under incomplete information on the other hand.

Standard Normal Form Games and Polymatrix Games

A strategic game or standard normal form game is defined as follows: Definition 1 (Standard normal form game (SNF)). A standard normal form game is a triple G = N, A, µ where:

• N = {1, . . . , n} is a finite set of players; • A = × i∈N A i
, where A i is a finite set of actions available to player i. ∀a ∈ A, a i is the action of i in the joint action a, a -i = (a 1 , . . . , a i-1 , a i+1 , . . . , a n ) ∈ A -i = × j =i A j is its restriction to all the players but i and "." denotes the concatenation, e.g., ∀(a i , a -i ),

a i .a -i = (a 1 , . . . , a i-1 , a i , a i+1 , . . . , a n ); • µ = {(µ i ) i∈N } is a set of real-valued utility functions:
µ i (a) captures the utility i gets from the joint action a. In a SNF game, each µ i is given explicitly, by a table of |A| entries.

A joint (or "pure") strategy a ∈ A is a pure Nash equilibrium (PNE) if no player can improve her utility by unilaterally changing her strategy. Formally: Definition 2 (Pure Nash equilibrium (PNE)). A strategy profile a ∈ A is a PNE iff: ∀i ∈ N, ∀a i ∈ A i :

µ i (a i .a -i ) ≥ µ i (a i .a -i ) (1)
Example 1. Consider a coordination game between n players, each choosing between two actions, x and y. A player is satisfied iff all her neighbors play the same action, and is satisfied to a lower level otherwise. Of course, players may have an prior preference for x or for y (e.g. a preference for some provider).

Let Neigh(i ) denotes the set of neighbors of player i.

In this game N = {1, . . . , n} and for any i: A i = {x, y} and µ i is defined as follows:

• µ i (x.a -i ) = α i,x if ∀j ∈ Neigh(i ), a i = a j = x; • µ i (y.a -i ) = α i,y if ∀j ∈ Neigh(i ), a i = a j = y; • µ i (a) = β if ∃j ∈ Neigh(i ), s.t.
, a i = a j , i.e., when, for some j, players i and j do not coordinate. Typically, in a coordination game, β is lower than the α's. For players who prefer to coordinate on x rather than to coordinate on y, we have α i,x > α i,y and the contrary for players who prefer a coordination on y than on x. Table 1 presents such a game for the two players case.

Player 2 x y

Player 1 When only two players are involved in N , (x.x) and (y.y) are the two PNE of the game (because β is low).

x α 1,x , α 2,x β, β y β, β α 1,y , α 2,y
If we consider the three-player game where a central player, say player 2, is related to the two other ones, while player 1 and 3 are related to the central player only (see the graph of Figure 1), (x.x.x) and (y.y.y) are still the only two PNE when β is low. Suppose now that player 1 really dislikes action x, i.e., β > α 1,x . Then (x.x.x) is not a PNE anymore (player 1 would prefer to move to y).

2 3

Figure 1: A graph of neighborhood between three players.

Without placing constraints on the players' utilities, describing a game in SNF involving n players, each facing d possible actions, requires listing n utility functions of size d n . Therefore, as mentioned by [START_REF] Gottlob | Pure nash equilibria: Hard and easy games[END_REF], "for large population games (modeling for instance, agents interactions over the internet), the SNF is practically unfeasible, while the more succinct graphical normal form works very well, and is actually a more natural representation". In many cases indeed, the utility of a player does not depend on the actions of all the other ones -the influence of what the other players decide is often local, as in our running example.

Polymatrix games [START_REF] Yanovskaya | Equilibrium points in polymatrix games[END_REF]) have been proposed in the late 60's as a convenient way to represent games with multiple players and pairwise interactions. Polymatrix games are defined as: Definition 3 (Polymatrix game). A polymatrix game is a four-tuple G = N, E, A, µ where:

• N = {1, . . . , n} is a finite set of players; • E is a set of pairs of players of N ; • A = × i∈N A i ,
where A i is the set of actions available to player i; • µ = {(µ i,j , µ j,i ), {i, j} ∈ E} is a set of pairs of utility functions on A i × A j : µ i,j (a i .a j ) is the local utility for player i of the joint action (a i .a j ) ∈ A i × A j .

(N, E) is a graph where nodes N represent the players and edges E capture the interactions between players. An absence of edge corresponds to a pair of players which utilities are independent of the actions of the other. Each edge (i, j) ∈ E corresponds to a local 2-player game G i,j = {i, j}, A i × A j , {µ i,j , µ j,i } . G i,j is a game in SNF, i.e., represented by two matrices -hence the name "polymatrix game". Classical polymatrix games are sum-based: the global utility function of a player is the sum of the utilities gathered by this player in the local games she is involved in.

Definition 4 (Sum-based polymatrix game). A sum-based polymatrix game is a game G = N, E, A, µ where the utility of any player i for the joint action a is defined as:

∀i ∈ N, µ i (a) = j,{i,j}∈E µ i,j (a i .a j ) (2)
In other terms, if G is sum-based, its equivalent standard normal form is the game N, A, µ where utilities are computed using Equation (2).

Polymatrix games can be much more frugal in memory space than SNF games -a polymatrix game indeed involves at most 2 • n • (n -1) utility functions of size d 2 (d being the maximum number of actions available to one player) -to be compared to the n utility functions of size d n required by its standard normal form equivalent. For instance, in coordination games, the satisfaction of an agent may depend on the number of neighbors choosing the same provider as this agent [START_REF] Simon | Constrained pure Nash equilibria in polymatrix games[END_REF]. Unfortunately, since a min operation cannot be captured by a sum (min is idempotent, sum is not), sum-based polymatrix games cannot capture the problem of Example 1, as soon as more than two players are involved. Thus, min-based polymatrix games have been recently proposed by [START_REF] Azzabi | Ordinal graph-based games[END_REF].

Definition 5 (Min-based polymatrix game). A min based polymatrix game is a polymatrix game G = N, E, A, µ where the utility of player i for the joint action a is defined as:

∀i ∈ N, µ i (a) = min j,{i,j}∈E µ i,j (a i .a j ) (3)
The µ i,j functions take their value in an ordinal scale ∆ Any ordered scale equipped with an order reversing operator n may be used. For the sake of readability (and without any loss of generality), in the following we take ∆ = [0, 1] with n(x) = 1 -x.

Games with Incomplete Information

A game with incomplete information can be first understood as a set S of states of nature, each state corresponding to a classical game. The utility of a player depends not only on the actions played but also on the real state of nature. Just before playing, each player i will receive some information τ i (s) (a "signal"). After having observed τ i (s), player i knows more about the real game, but several games may still be plausible; the player then conditions her knowledge according to the information received and decides which action to play. Notice that the players may have different information functions τ i , and thus will not share the same posterior knowledge on S. Let Θ i be the possible pieces of information which can be received by player i: Θ i is called the set of "types" of i. The question is then, for each player, to determine an action for each of her types. Thus, in games with incomplete information, as defined by [START_REF] Harsanyi | Games with incomplete information played by "Bayesian" players[END_REF], the set of states of the world is omitted and only the types are considered. Θ i is the local state space for player i and

Θ = Θ 1 × • • • × Θ n is the effective global state space 1 .
The question is then to determine which action to play for each type received: a pure strategy for player i is a function σ i that maps each possible information θ i ∈ Θ i to an action a i ∈ A i and a joint strategy is a tuple σ = (σ 1 , . . . , σ n ) of such functions. Formally:

Definition 6. A strategy is a vector σ = (σ 1 , . . . , σ n ) of functions σ i : Θ i → A i .
σ i (θ i ) specifies the action that player i will execute when receiving the private information θ i . In the following, Σ i denotes the set of all functions from Θ i to A i and Σ = Σ 1 × • • • × Σ n the set of all joint strategies. Sticking to our notation, any σ ∈ Σ is the concatenation of σ i (the strategy of i) and σ -i (the strategies of all the players except i).

Example 2. Let us consider the coordination game with incentives (for the sake of brevity we assume that incentives concern only action x): each player has two types r i ("i receives an incentive for x") and r i ("i does not receive an incentive for x"), so

Θ = {r 1 , r 1 } × • • • × {r n , r n }. A possible strategy is σ i (r i ) = x; σ i (r i ) = y if (α i,y > α i,x
) and σ i (r i ) = x otherwise: a player plays x if receiving an incentive and her preferred action otherwise.

In Bayesian games, the common knowledge over Θ is given by a probability distribution and each strategy is evaluated by its expected utility. If quantitative information about the real world is not attainable, the framework of possibilistic games should rather be considered: in a possibilistic game with incomplete information (Π-game) (Ben Amor et al. 2019a), the common knowledge is given by a possibility distribution π over the possible combinations of types, i.e., is a mapping from Θ to the ordered scale ∆.

Possibilistic games with incomplete information (Πgames) are defined as: Definition 7 ((Standard Normal Form ) Π-game). A Π-game is a tuple N, A, Θ, π, µ where:

• N = {1, . . . , n} is a finite set of players; • A = × i∈N A i where A i is the set of actions of player i; • Θ = × i∈N Θ i , where Θ i is the set of types of player i; • π: Θ → ∆ is a joint possibility distribution over Θ; • µ = {(µ i ) i∈N } where µ i : A × Θ → ∆ is the utility function of player i.
Recall that according to possibility theory [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF][START_REF] Dubois | Possibility theory: An approach to computerized processing of uncertainty[END_REF], a possibility distribution is a function from a universe of discourse (here, Θ) to an ordered scale (typically, the unit interval). π is assumed to be normalized: there is at least one totally possible state (s such that π(s) = 1). From π, one can compute the possibility Π(E) and the necessity N (E) of any event E ⊆ S:

Π(E) = sup s∈E π(s) evaluates to what extent E is con- sistent with the knowledge represented by π while N (E) = 1 -Π(E) = 1 -sup s /
∈E π(s) corresponds to the extent to which ¬E is inconsistent and thus evaluates at which level E is certainly implied by the knowledge. As for conditioning, Π-games use Hisdal's definition (1978) in order to stick to the ordinal framework:

π(θ j |θ i ) = 1 if π(θ i .θ j ) = π(θ i ) π(θ i .θ j )
otherwise.

Example 3. In our example ∀i ∈ N , A i = {x, y} and Θ i = {r i , r i }. The satisfaction of player i is equal to β if she does not coordinate with her neighbors. If she coordinates, her satisfaction when playing x is increased to δ > max{α i,x , α i,y } if she receives an incentive and remains α i,x if not. Hence the following utility functions:

• if ∃j ∈ Neigh(i ), s.t., a i = a j then: -µ i (a, θ) = β, ∀θ; • if ∀j ∈ Neigh(i ), a i = a j then: -µ i (x.a -i , r i .θ -i ) = α i,x , ∀θ -i ; -µ i (x.a -i , r i .θ -i ) = δ, ∀θ -i ; -µ i (y.a -i , θ) = α i,y , ∀θ.
Table 2 details the utility functions for the two players case.

There are two "normal" states in Θ = {r 1 , r 1 } × • • • × {r n , r n }: everybody receives an incentive for x (state r = (r 1 , r 2 , . . . , r n )) and nobody receives anything (state r = (r 1 , r 2 , . . . r n )). Cases were only some players have an incentive are of course possible. This knowledge is captured by a joint possibility distribution on Θ: π(r) = π(r) = 1 and π(θ) = γ (with 0 ≤ γ ≤ 1 for other combinations of types θ ∈ Θ\{r, r}.

If player i receives an incentive, she conditions her knowledge and we get:

π(r -i |r i ) = 1 and π(θ -i |r i ) = γ if θ -i = r -i , i.e.
, she rather believes that her neighbors also receive an incentive. Symmetrically, when she does not receive an incentive, we get:

π(r -i |r i ) = 1 and π(θ -i |r i ) = γ if θ -i = r -i .
Considering qualitative (possibilistic) problems of decision under uncertainty, qualitative decision theory [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF][START_REF] Dubois | Decisiontheoretic foundations of qualitative possibility theory[END_REF] proposes to evaluate the satisfaction of a player on the totally ordered scale ∆ (the higher µ i (a, θ) (resp. π(θ)), the more satisfied player i (resp. the more plausible θ)). µ i (a, θ) evaluates to what extent i is satisfied by a if the real situation is θ. But, when receiving θ i and deciding what to play, player i does not know the full θ. Her posterior knowledge about Θ -i is the distribution π(.|θ i ). In other words, the utility of player i of type θ i for the joint action a depends on (i) the posterior knowledge of i on the types of the other players and (ii) on the strategy σ -i of the other players. Then, the principles of qualitative decision theory yield the following definitions for the utility of joint strategies: Definition 8 (Utility of an action / of a strategy). The utility of the action a i for player i of type θ i in the context of σ -i is:

U pes i (a i , σ -i , θ i ) = min θ-i∈Θ-i max 1-π(θ -i |θ i ), µ i (a i .σ -i (θ -i ), θ i .θ -i ) (4)
The utility of strategy σ to player i of type θ i is:

U pes i (σ, θ i ) = U pes i (σ i (θ i ), σ -i , θ i ) (5)
Note that U pes i (σ i (θ i ), σ -i , θ i ) is independent of the choices of player i when her type is different from θ i .

When considering her possible strategies σ i : Θ i → A i , player i aims at maximizing the response given the strategy σ -i of the other players. As in any kind of game, a pure Nash equilibrium (PNE) is a joint strategy from which no player i will deviate unilaterally knowing σ -i . In the possibilistic context, this leads to the following definition:

Definition 9 (Pure Nash equilibrium in a Π-game). σ is a pure Nash equilibrium (PNE) iff: ∀i ∈ N, ∀θ i ∈ Θ i , ∀a i ∈ A i , U pes i (σ i (θ i ), σ -i , θ i ) ≥ U pes i (a i , σ -i , θ i ) Example 4.
In the small three-player game (based on the graph of Figure 1), the equilibria are the following:

• The pure joint strategy σ x = x (every player unconditionally plays x) is a PNE when β ≤ min{δ, α 1,x , α 2,x , α 3,x }. • The pure joint strategy σ y = y (every player unconditionally plays y) is a PNE when β ≤ min{{α i,x , α i,y } i=1,2,3 }. • The pure joint strategy σ such that any player i plays

σ i (r i ) = x and σ i (r i ) = y is also a PNE, when γ is low (1 -γ ≥ max{β, α i,x , α i,y } i=1,2,3 ) and β is low (β ≤ min{δ, α 1,y , α 2,y , α 3,y }).
Notice that when γ and β increase (knowledge tends to total ignorance), there will be a point where the above third strategy will not be an equilibrium anymore.

Polymatrix Π-games

The normal form representation of an incomplete information game with n players, t types and d actions per player is very costly (n utility functions of size t n .d n and a distribution over Θ, i.e., of size t n ) even when the problem involves local interactions only. In our example, the type vector is fixed, the satisfaction of one player is the minimum of what this player gets in a series of two-player games as the one presented in Table 1. In order to efficiently represent such games, we now define polymatrix Π-games as min-based polymatrix games where each local game is a Π-game. Such a game can be much more compact than the equivalent SNF Π-game.

Definition 10 (Polymatrix Π-game). A polymatrix Π-game is a tuple G = N, E, A, Θ, µ, π where:

• N = {1, . . . , n} is the set of players; • E is a set of pairs of players of N ; • A = × i∈N A i , where A i is the set of actions of player i; • Θ = × i∈N Θ i , where Θ i is the set of types of player i; • µ = {(µ i,j , µ j,i ), {i, j} ∈ E}, a set of pairs of utility functions on A i × A j × Θ i × Θ j taking their values in ∆; • π = {π i,j : θ i × θ j → ∆, {i, j} ∈ E} a set of pairwise possibility distributions on the Θ i × Θ j product sets.
In other terms, a polymatrix Π-game is a polymatrix game where each local game is a Π-game {i, j}, A i × A j , Θ i × Θ j , π i,j , {µ i,j , µ j,i } .

The condition of "common knowledge" is less natural in the present context of a series of local games than in SNF Πgames -here, we assume that the knowledge of each local Π-game is common to the two players involved in, but not to the full community of players. Each player is "myopic" and her knowledge is restricted to what she knows about her neighborhood. The knowledge of player i about the configurations of types of the global incomplete information game is:

π i (θ) = min j,{i,j}∈E π i,j (θ i .θ j )
We thus replace the condition of "common knowledge" by a condition of "coherent knowledge": there should be a π on Θ from which the π i,j 's derive:

Assumption 1. ∃π : Θ → ∆ such that ∀i, j ∈ N, π i,j (θ i .θ j ) = max θ -{i,j} π(θ i .θ j .θ -{i,j} )
π is unknown, but one knows that π i,j (θ i .θ j ) = max θ -{i,j} π(θ i .θ j .θ -{i,j} ).

Let us now study the global utility functions of the players. Each θ defines a min-based polymatrix game. The global utility of player i for the joint action a when the configuration of types is θ is thus:

Definition 11 (Global utility in a polymatrix Π-game). µ i (a, θ) = min j,{i,j}∈E µ i,j (a i .a j , θ i .θ j )
If one considers all the types and the associated distribution, the polymatrix Π-game (compactly) represents the SNF Π-game N, A, Θ, π, µ . Then from the definition of the utility of a joint action/strategy for a player in a Π-game (Definition 8) we have:

Definition 12 (Utility of a strategy in a polymatrix Π-game).

U pes i (σ, θ i ) = min θ-i∈Θ-i max(1-π(θ -i |θ i ), µ i (σ(θ i .θ -i ), θ))
Definitions 10, 11 and 12 constitute, to the best of our knowledge, the first attempt to introduce a way to cope with uncertainty in ordinal polymatrix games and more generally in ordinal graphical games.

Notice that in Definition 11, we compute, for each player and each type configuration, the utility of a player in the configuration and then compute the pessimistic utility of the player. We could have proceeded in the other way: compute the pessimistic utility in each local game and then aggregate the pessimistic utilities. The theory is fortunately sound: the two approaches (that we can call "ex-ante" and "ex-post" by reference to [START_REF] Harsanyi | Games with incomplete information played by "Bayesian" players[END_REF][START_REF] Myerson | Comments on "games with incomplete information played by 'bayesian'players, i-iii harsanyi's games with incoplete information[END_REF])) coincide. We can indeed prove that2 Proposition 1.

U pes i (σ, θ i ) = min j,{i,j}∈E min θj ∈Θj max 1 -π i,j (θ j |θ i ), µ i,j (σ(θ i .θ j ), θ i .θ j )
As far as spatial complexity is concerned, it is easy to show that a polymatrix Π-game can be exponentially more compact than its standard normal form equivalent. Consider our running example:

Example 5. The SNF Π-game of Example 3 is captured by the polymatrix Π-game G = N, E, A, Θ, µ, π (same players, same actions and same types) where E is the neighborhood relation of the original game and where the utility function µ i,j of player i (w.r.t. j, (i, j) ∈ E) is:

• µ i,j (x.y, θ i .θ j ) = µ i,j (y.x, θ i .θ j ) = β; • µ i,j (x.x, r i .θ j ) = δ since δ ≥ α i,x , α i,y ; • µ i,j (x.x, r i .θ j ) = α i,x ; • µ i,j (y.y, θ i .θ j ) = α i,y .
This polymatrix game contains 2 • |E| possibility distributions of size 2 • 2, and 2 • |E| utility functions of size 2 • 2 • 2 • 2, while the original SNF game involves one possibility distribution of size 2 n and n utility functions of size 2 n • 2 n , whatever the connectivity of the neighborhood graph.

As far as time complexity is concerned, deciding whether a polymatrix Π-game admits a pure Nash equilibrium is an NP-hard problem because (i) any 2-player Π-game is a (degenerated) polymatrix game and (ii) deciding whether a Πgame admits a pure Nash equilibrium is an NP-complete problem (Ben Amor et al. 2019a). We show in the following Section that the question is "only" NP-complete. In other terms, the possible gain in compactness does not result in an increase in complexity.

From Polymatrix Π-games to Min-based Polymatrix Games

In the following, we show that any polymatrix Π-game can be transformed into a min-based polymatrix game, the Nash equilibria of which are in bijection the ones of the original game. To this extent, we first show that any 2-player Π-game can be transformed into an equivalent min-based polymatrix game -this result can be viewed as a qualitative counterpart of Howson and Rosenthals's theorem linking Bayesian games to polymatrix games (1974).

Transforming a 2-player Π-game into a Min-based Polymatrix Game

The idea is to consider as many players as the number of pairs (i, θ i ), i.e., the number of players is equal to

|Θ 1 | + |Θ 2 |.
Each player (i, θ i ) has A i as a set of available actions.

For each joint strategy a ∈ A, the utility of player (i, θ i ) in the game ((i, θ i ), (j, θ j )) ∈ E in the polymatrix game is equal to the utility of the joint action a ∈ A, to player i of type θ i where j is of type θ j . Definition 13 (Polymatrix repr. of a 2-player Π-game).

Given a 2-player Π-game G = N = {1, 2}, A, Θ, π, µ , G = Ñ , Ẽ, Ã, μ is the min-based polymatrix game where:

• Ñ = {(i, θ i ), ∀i ∈ {1, 2}, ∀θ i ∈ Θ i }; • Ẽ = {((i, θ i ), (j, θ j )), i = j}; • Ã(i,θi) = A i , ∀(i, θ i ) ∈ Ñ ; • μ(i,θi),(j,θj) (a) = max 1 -π(θ j |θ i ), µ i (a, θ i .θ j ) , ∀a ∈ Ã, ∀i, j ∈ N , s.t., i = j, ∀θ i ∈ Θ i , ∀θ j ∈ Θ j .
Intuitively, each combination of types (θ 1 .θ 2 ) in G is mapped to an edge ((1, θ 1 ), (2, θ 2 )) ∈ E.

Definition 14 (Transformation of a pure strategy). Let G = N, A, Θ, π, µ be a 2-player Π-game, G = Ñ , Ẽ, Ã, μ its polymatrix representation and σ be a pure strategy in G.

We define a σ as the joint action in à such that:

a σ (i,θi) = σ i (θ i )
Based on Definition 5: μ(i,θi) (a σ ) = min θj ∈Θj μ(i,θi),(j,θj) (a σ (i,θi) .a σ (j,θj ) ).

We can then show that the utilities of σ in G and a σ in G are equal:

Proposition 2. Let G be a 2-player Π-game, G its polymatrix game representation. It holds that, for any pure strategy σ of G: ∀i = 1, 2, j = i, (θ i .θ j ) ∈ Θ:

U pes i (σ, θ i ) = μ(i,θi) (a σ ) = min θj ∈Θj μ(i,θi),(j,θj) (a σ (i,θi) .a σ (j,θj )
). Finally, we can show that the PNE are the same in both games:

Proposition 3. σ is a PNE in the 2-player Π-game G = N, A, Θ, π, µ iff a σ is a PNE in its polymatrix representa- tion G = Ñ , Ẽ, Ã, μ .
Example 6. The equivalent polymatrix game G of the two players coordination Π-game depicted in Table 2 contains four players: Ñ = {(1, r 1 ), (1, r 1 ), (2, r 2 ), (2, r 2 )}, all having the same set of actions {x, y}.

G contains 4 local games (4 edges) and the utilities of each player in the equivalent game are detailed in Figure 2.

1,r1 2,r2 2,r2 1,r1 G (1,r 1 ),(2,r 2 ) G (1,r 1 ),(2,r 2 ) G (1,r 1 ),(2,r 2 ) G (1,r 1 ),(2,r 2 ) • G (1,r1),(2,r2) 2, r 2 1, r 1 x y x δ, δ β, β y β, β α 1,y , α 2,y • G (1,r1),(2,r2) 2, r 2 1, r 1 x y x max(1 -γ, δ), max(1 -γ, α 2,x ) max(1 -γ, β), max(1 -γ, β) y max(1 -γ, β), max(1 -γ, β) max(1 -γ, α 1,y ), max(1 -γ, α 2,y ) • G (1,r1),(2,r2) 2, r 2 1, r 1 x y x max(1 -γ, α 1,x ), max(1 -γ, δ) max(1 -γ, β), max(1 -γ, β) y max(1 -γ, β), max(1 -γ, β) max(1 -γ, α 1,y ), max(1 -γ, α 2,y ) • G (1,r1),(2,r2) 2, r 2 1, r 1 x y x α 1,x , α 2,x β, β y β, β α 1,y , α 2,y
Figure 2: The polymatrix game equivalent of the 2-player Π-game depicted in Table 2.

The joint action a σ = (x.x.x.x) of G corresponds to σ x in G. Using Equation (3), the utilities of a σ in G are:

µ (1,r1) (a σ ) = min δ, max(1 -γ, δ) = δ, µ (1,r1) (a σ ) = min max(1 -γ, α 1,x ), α 1,x = α 1,x , µ (2,r2) (a σ ) = min δ, max(1 -γ, δ) = δ, µ (2,r2) (a σ ) = min max(1 -γ, α 2,x ), α 2,x = α 2,x .
It can be checked that a σ is a PNE in the equivalent minbased polymatrix game.

Notice that the nodes of the polymatrix game G represent the types in Θ 1 ∪Θ 2 , that the edges of G correspond to types combinations θ in the Π-game G and that the graph of G is bipartite. More generally, the transformation of G to G is polynomial: Proposition 4. The transformation of a 2-player Π-game G into an equivalent polymatrix representation G is in O(d 2 • t 2 ) where t (resp. d) is the maximal number of types (resp. actions) per player.

Therefore, the transformation of G into G is polynomial in time and space, contrarily to the transformation into a SNF game proposed in (Ben Amor et al. 2019a).

From polymatrix Π-games to Min-based Polymatrix games with Complete Information

When it comes to general polymatrix Π-games, we can show that polymatrix Π-games are not more expensive than classical (complete information) min-based polymatrix games. Indeed, recall that for any polymatrix Π-game, we have shown (Proposition 1) that:

U pes i (σ, θ i ) = min j,{i,j}∈E θ j ∈Θ j max 1 -π i,j (θ j |θ i ), µ i,j (σ i (θ i ).σ j (θ j ), θ i .θ j )
We now reuse, for every pairs of players, the transformation of the previous Section, transforming a 2-player Πgame into an equivalent min-based polymatrix game: Definition 15. Given a polymatrix Π-game G = N, E, A, Θ, µ, π , G = Ñ , Ẽ, Ã, Ũ is the min-based polymatrix game where:

• Ñ = {(i, θ i ), ∀i ∈ N, ∀θ i ∈ Θ i }; • Ẽ = {((i, θ i ), (j, θ j )), i = j, θ i ∈ Θ i , θ j ∈ Θ j }; • Ã(i,θi) = A i , ∀(i, θ i ) ∈ Ñ ; • Ũ(i,θi),(j,θj) (a i .a j ) = max 1 -π i,j (θ j |θ i ), µ i (a i .a j , θ i .θ j ) , ∀(i, j) ∈ E, ∀a i .a j ∈ A i × A j , ∀θ i .θ j ∈ Θ i × Θ j .
Using this definition and Proposition 1, it follows that: Proposition 5. Let G be a n-player polymatrix Π-game, G be the corresponding min-based polymatrix representation, σ be a pure strategy for G and a σ its transformation according to Definition 14. It holds that ∀i ∈ N, ∀θ i ∈ Θ i ,

U pes i (σ, θ i ) = min j,{i,j}∈E θ j ∈Θ j { Ũ(i,θi),(j,θj) (a σ (i,θi) .a σ (j,θj ) )}
So, the utility of σ in G is equal to the utility of a σ in G.

Since the set of pure strategies in G is bijectively related to the action set à of G, the following proposition holds:

Proposition 6. σ is a PNE in the n-player polymatrix Π- game G = N, E, A, Θ, µ, π iff a σ is a PNE in the min- based polymatrix game G = Ñ , Ẽ, Ã, Ũ .

Complexity

We can show that the size of the transformed min-based polymatrix game G is in O(|E| • d 2 • t 2 ) where t (resp. d) is the maximal number of types (resp. possible actions) per player: each local Π-game (we have |E| local Π-games) is transformed using the transformation described in Section 4.1, the complexity of which is in

O(d 2 • t 2 ). Hence, the global computation cost is O(|E| • d 2 • t 2
) in time and space. Now, recall that deciding the existence of a PNE in a 2-player Π-game is a NP-hard problem (Ben Amor et al. 2019a). Because any Π-game can be transformed in polytime and space into an equivalent min-based polymatrix game, we first derive that3 : Proposition 7. Determining whether there exists a PNE in a min-based polymatrix game is NP-complete. The result holds even when the graph is bipartite.

A second consequence is that deciding whether a polymatrix Π-game admits a PNE is NP-complete but not harder. The problem is NP-hard because deciding whether a 2player Π-game admits a PNE is NP-complete and belongs to NP since the previous transformation allows to solve it through a polytime reduction to a polymatrix min-based game.

Proposition 8. Determining whether there exists a PNE in a polymatrix Π-game is NP-complete.

Hence, the possible gain in compactness offered by polymatrix Π-games w.r.t. SNF Π-games come with no increase in theoretical complexity.

Computing a Pure Nash Equilibrium in

Min-based Polymatrix Games

A MILP Formulation

The basic computational problem is the search for an equilibrium in min-based polymatrix games. Taking advantage of the efficiency of modern solvers, we propose a Mixed Integer Linear Programming (MILP) formulation of the problem.

The main decision variables are boolean variables encoding the strategy searched for: each σ i,ai is a boolean variable indicating whether action a i is prescribed for player

i, ∀i ∈ N, ∀a i ∈ A i , σ i,ai ∈ {0, 1}.
Utilities are encoded by continuous variables (we assume ∆ = [0, 1]). U i,ai,j is a continuous variable indicating the utility of player i playing action a i given the strategy of player j. ∀{i, j} ∈ E, ∀a i ∈ A i , U i,ai,j ∈ [0, 1]. U i,ai is a continuous variable indicating the utility of player i playing action a i : ∀i ∈ N, ∀a i ∈ A i , U i,ai ∈ [0, 1].

We will also use boolean variables V i,ai,j ∈ {0, 1} (∀i, j ∈ N , s.t., {i, j} ∈ E, ∀a i ∈ A i ) to express the constraints that U i,ai = min j,{i,j}∈E U i,ai,j (and not only lower than).

The constraints are the following:

∀i ∈ N, ai∈Ai σ i,ai = 1 (6) ∀i ∈ N, ∀a i , a i ∈ A i , s.t., a i = a i , U i,ai -U i,a i ≥ σ i,ai -1 (7) ∀i, j ∈ N , s.t., {i, j} ∈ E, ∀a i ∈ A i , U i,ai,j = aj ∈Aj µ (i,j) (a i .a j ) × σ j,aj (8)
U i,ai ≤ U i,ai,j (9)
U i,ai + V i,ai,j ≥ U i,ai,j (10) ∀i ∈ N, ∀a i ∈ A i , j,{i,j}∈E (1 -V i,ai,j ) = 1 (11)
Constraints ( 6) ensure that the strategy σ searched for specifies exactly one action a i for each player i. Constraints (7) require that the strategy built (the σ i,ai which are set to 1) is a PNE: when σ i,ai = 1, it writes U i,ai ≥ U i,a i , and thus requires that player i has no incentive to deviate from a i . When action a i is not chosen for player i, (σ i,ai = 0) the constraint is always satisfied (U i,ai -U i,a i is always greater than -1). Constraints ( 9), ( 10) and ( 11) implement Equation (3). Constraints (9) ensure that the utility of player i playing a i is lower than the minimum of utilities in local games played with players j ∈ N , i.e., the µ (i,j) (a i .a j ). Constraints ( 10) and ( 11) ensure that U i,ai is equal to the above minimum. Whenever V i,ai,j = 1, Equation (10) holds, and Equation (11) ensures that ( 10) is an equality for a single j (minimizing U i,ai,j ).

Let us denote d the maximal number of actions of any player in the polymatrix game and b the maximal number of local games in which a player can be involved. The MILP formulation contains:

• O(n • d • b) continuous variables U i,ai,j , O(n • d) contin- uous variables U i,ai , O(n • d) boolean variables σ i,ai and O(n • d • b) boolean variables V i,ai,j ; • O(n) constraints (6), each involving O(d) variables; • O(n • d 2 ) constraints (7), each involving 3 variables; • O(n • b • d) constraints (8), each involving O(d) variables; • O(n • b • d) constraints (9),

Experiments

The goal of the first part of the experimental study is to compare the efficiency of the polymatrix encoding (PE) of 2player Π-games to the one of the direct encoding (DE) (proposed by (Ben Amor et al. 2019a)), and beyond, to prove that the resolution of polymatrix Π-games is not out of reach.

To conduct our experimental study, we have used the generator of Π-games proposed in (Ben Amor et al. 2019a). This generator, based on GAMUT [START_REF] Nudelman | Run the gamut: A comprehensive approach to evaluating game-theoretic algorithms[END_REF], is available at [START_REF] Ben Amor | The Possibilistic Games Page[END_REF]) and is essentially based on the approach of [START_REF] Ceppi | Computing bayes-nash equilibria through support enumeration methods in bayesian two-player strategic-form games[END_REF] for the generation of Bayesian games. The Π-game generator first takes as input the class of the game, the number of degrees in ∆, if necessary the number of players n, the number of actions |A i | and types |Θ i | of player i. Then, this generator uses GAMUT to generate |Θ| normal form games of the class given in input. Finally, a normalized distribution π : Θ → ∆ is generated.

In our experiments, we study the results of the class of coordination games available on GAMUT: Battle Of The Sexes (BoS), Collaboration Game (CG) and Minimum Effort Game (MEG) [START_REF] Vaughan | Gamut user guide[END_REF].

We start by studying 2-player Π-games. We varied, for each player, the number of types from 2 to 10. Then, according to the game's parameters, we varied just for MEG games the number of actions of each player (since in the BoS games both players have just 2 actions and CG games the number of actions of each player is equal to the number of players in the game). Then, we fixed the number of degrees ∆ to 5, i.e., ∆ = {0, 0.25, 0.5, 0.75, 1}.

Furthermore, for each combination of the parameters, we generated 100 different instances and we measured the average time necessary to get a PNE by solving the MILP proposed in (Ben Amor et al. 2019a) (we denote this approach DE, for direct encoding) and by transforming the Π-game into an equivalent min-based polymatrix game and solving the above MILP of the equivalent polymatrix game proposed in Definition 13 (we denote this approach PE, for polymatrix encoding). All experiments were conducted on an Intel Xeon E5540 processor and 64GB RAM workstation. We used CPLEX (CPLEX 2009) as a MILP solver. Table 3 presents the average of execution times (in seconds) needed by DE and PE to find one PNE, for 3 games classes. In the experiment reported in Table 3, we fixed the number of actions per player to 2, i.e., |A i | = 2 and we varied the number of types |Θ i | from 2 to 10.

Table 4 presents the average of execution times (in seconds), to find one PNE in a MEG (we tested just for MEG since the numbers of players and of actions per player in the BoS (resp. CG) game is equal to 2). We varied the number of types |Θ i | from 2 to 10 and we varied the number of actions per player |A i | from 2 to 10. We present the results for 3 different types' numbers (4,7 and 10).

The results show that whether we vary the number of actions or the number of types, the execution time needed to find a PNE in a 2-player Π-game using direct encoding is very close to the execution time needed to find a PNE using polymatrix encoding.

The second part of experiments was dedicated to polymatrix Π-games. We generated coordination games with different numbers of players. We varied the number of players from 5 to 80. Then, we generated random interactions between players (ensuring that the interaction graph was connected). Then, for each edge, i.e., interaction, we generated a Π-game between 2 players using the Π-game generator proposed in [START_REF] Ben Amor | The Possibilistic Games Page[END_REF]). We varied the number of types from 2 to 9 and the number of actions (for MEG) from 2 to 10. Then we computed the average execution time needed to find a PNE by transforming the original game into its equivalent min-based polymatrix game (using Definition 15) and solving the MILP of the latter. Notice that, the equivalent min-based polymatrix game contains n • t 2 players where t is the maximal number of types per player.

Figure 3 presents the average execution time needed to get one PNE in 3 different game classes. We fixed the number of actions per player to 2.

Figures 4 (resp. 5) presents the average execution time needed to find one PNE in a MEG fixing the number of types per player to 2 (resp. the number of player to 25). Globally, MILP results confirm the feasibility of the qualitative approach of min-based polymatrix. Furthermore, the results also show that the execution time needed to solve a polymatrix Π-game increases "reasonably" (less than 20 seconds for any configuration) when increasing the number of actions or types of players.

Conclusion

The main contributions of this paper are threefold. First, we have defined a new framework for ordinal games, namely polymatrix Π-games, where local games are Π-games. Such games can be exponentially more compact than the equivalent SNF Π-games. Second, we have shown that any 2player Π-game can be transformed into an equivalent minbased polymatrix game, proving a qualitative counterpart of Howson and Rosenthal's theorem linking Bayesian games to polymatrix games [START_REF] Howson | Bayesian equilibria of finite two-person games with incomplete information[END_REF]. Then we have shown that any polymatrix Π-game can itself be transformed in polytime into an equivalent min-based polymatrix game. As a consequence, the potential gain in succinctness comes with no increase in time complexity.

We have also studied the problem of deciding whether a min-based polymatrix game admits a pure Nash equilibrium (the problem is NP-hard) and we have proposed a MILP formulation of this NP-hard problem. The experimental results confirm the theoretical ones: solving a 2-player Π-game through the transformation is not more expensive than a direct solution. This underlines the importance of the basic problem, solving min-based polymatrix games.

From the point of view of knowledge representation, a straightforward extension of our work is to study, theoretically and algorithmically, the search for mixed equilibria in the sense of [START_REF] Ben Amor | Equilibria in ordinal games: A framework based on possibility theory[END_REF][START_REF] Hosni | Possibilistic randomisation in strategic-form games[END_REF]. Other developments include the extension of our results to other kinds of succinct games, e.g., hypergraphical games.

Finally, in the present paper, we have suggested solving the problem through a MILP formulation, taking advantage of the available state of the art solvers. This allowed us to prove the feasibility of our approach, but a detailed algorithmic study of the direct solution of min-based polymatrix games with incomplete information is still an objective of further research. A natural extension of this paper is the development of dedicated algorithms inspired, for example, by the NashProp algorithm [START_REF] Ortiz | Nash propagation for loopy graphical games[END_REF], adapted to the possibilistic framework.

  each involving 2 variables; • O(n • b • d) constraints (10), each involving 3 variables; • O(n • d) constraints (11), each involving O(b) variables. The MILP can then be easily encoded in a matrix of size O(n 2 • b • d 2 • (b + d)).

Figure 3 :Figure 4 :

 34 Figure 3: Average execution time (s) to find one PNE in a polymatrix Π-game, |Ai| = 2.

Figure 5 :

 5 Figure 5: Average execution time (s) to find one PNE in a polymatrix Π-game, n = 25.

Table 1 :

 1 A coordination game with two players.

Table 3 :

 3 Average execution time (s) of direct encoding (DE) and polymatrix encoding (PE), |Ai| = 2.

	|Θi|		2	3	4	5	6	7	8	9	10
	BoS	0.12 0.02	0.02 0.02	0.15 0.03	0.03 0.02	0.22 0.04	0.05 0.06	0.22 0.06	0.08 0.10	0.26 0.09	DE PE
	CG	0.12 0.02	0.02 0.02	0.15 0.03	0.04 0.03	0.52 0.35	0.75 0.77	1.33 1.12	1.52 1.50	2.08 1.89	DE PE
	MEG	0.12 0.02	0.02 0.02	0.15 0.03	0.02 0.02	0.22 0.04	0.04 0.05	0.22 0.05	0.07 0.09	0.25 0.08	DE PE
	|Ai|		2	3	4	5	6	7	8	9	10
	|Θi| = 4		0.07 0.07	0.08 0.07	0.23 0.18	0.19 0.15	0.19 0.18	0.19 0.20	0.24 0.23	0.26 0.23	0.36 0.33	DE PE
	|Θi| = 7		0.14 0.14	0.16 0.14	0.18 0.16	0.28 0.26	0.33 0.28	0.39 0.39	0.39 0.40	0.53 0.51	0.73 0.78	DE PE
	|Θi| = 10	0.14 0.13	0.28 0.26	0.31 0.31	0.48 0.44	0.51 0.51	0.67 0.74	0.72 0.70	1.11 1.16	3.28 3.32	DE PE
	Table 4: Average execution time (s) of direct encoding (DE) and
	polymatrix encoding (PE) for MEG.

The idea of Harsanyi when defining types was that a player's local state can encapsulate all the information to which the player has access: it contains the status of the external world that the player has observed but can also contain her introspective mental states. See[START_REF] Brandenburger | Hierarchies of beliefs and common knowledge[END_REF][START_REF] Aumann | Epistemic conditions for nash equilibrium[END_REF][START_REF] Battigalli | Recent results on belief, knowledge and the epistemic foundations of game theory[END_REF]

[START_REF] Brandenburger | Epistemic Game Theory: An Overview[END_REF][START_REF] Eddie | Epistemic Game Theory[END_REF] for the links between belief states and types, and more generally for further developments about epistemic game theory. This kind of interpretation also complies with the semantics of epistemic logic[START_REF] Fagin | Common knowledge revisited[END_REF]).

The proofs are omitted to the sake of brevity; a version with the proof can be found at[START_REF] Ben Amor | Ordinal polymatrix games with incomplete information -long version[END_REF]

The membership to NP is easy to show, by a simple loop over players, actions and neighbors.

* Helene Fargier has benefitted from the AI Interdisciplinary Institute ANITI. ANITI is funded by the French "Investing for the Future -PIA3" program under the Grant agreement n ANR-19-PI3A-0004.

Proof of Proposition 1. Note that

Now, from Definition 11, we have (slightly simplifying notations for readability):

So, we have, for all j such that {i, j} ∈ E:

Thus,

Conversely, let j * be such that µ i (σ(θ), θ) = µ ij * (σ, θ i , θ j * ). We have,

Thus,

Proof of Proposition 2. Let us consider player 1 (the same proof holds for player 2, by symmetry). By Definition 8, we get that:

Now, in G, we have, by definition of σ = a σ and of the utility of a joint strategy in a min-based polymatrix game, and the fact that player (i, θ i )'s utility is independent of the actions of players (i, θ i ) for θ i = θ i :

and, from the definition of μ(1,θ1),(2,θ2) in Definition 13:

Proof of Proposition 3. We have proved in Proposition 2 that the utility of any pure strategy σ in G is equal to the utility of a σ in G. In order to prove the equivalence of PNE in both games, it is enough to prove that the relation σ → a σ forms a bijection between Σ = Σ 1 × Σ 2 and Ã.

To do so, simply note that (i) the cardinals of à and Σ are equal (to i |A i | |Θi| ), and (ii) the transformation is injective, i.e., if σ i (θ i ) differs from σ i (θ i ) for any (i, θ i ), then the pure strategies a σ and a σ will differ in their components a σ (i,θi) = a σ (i,θi) . As a result, the transformation is bijective, and since utilities of strategies are preserved, Nash equilibria are identical.

Proof of Proposition 4. Note that the space and computation times of the transformation are dominated by the computation of the tables μ(i,θi),(j,θj) (a). There are 2

The computation of μ(i,θi),(j,θj) (a) for a given tuple (θ i , θ j , a i , a j ) is given in Definition 13:

This computation takes constant time, so the overall time (and space) complexity is O(d 2 .t 2 ).

Proof of Proposition 5. The proof follows immediately from Proposition 1 and Definition 15.

Proof of Proposition 6. The proof is similar to that of Proposition 3 and is based on the bijection between the actions set in G and the pure strategies set in G.

The proofs of the two last propositions are immediate and sketched in the main text.


Pengbo Liang

Clara Schmitz

Franck Beatrice Lace

Anicet Ditengou

Jean Keller

Cyril Libourel

Pierre-Marc Delaux

Thomas Ott
email: thomas.ott@biologie.uni-freiburg.de

A formin-mediated cell wall-plasma membranecytoskeleton continuum is required for symbiotic infections in Medicago truncatula

Keywords: Nodulation, symbiosis, actin, rhizobial infection, legume

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

INTRODUCTION

Legumes have the unique ability to symbiotically associate with rhizobia to maintain a nitrogen-fixing mutualism. Intracellular colonization of Medicago truncatula roots by the compatible rhizobium Sinorhizobium meliloti initiates from young, growing root hairs. In the course of the interaction an organogenetic program is executed in the root cortex and the pericycle that results in the development of nodules, in which symbiotic nitrogen fixation takes place [START_REF] Mylona | Symbiotic Nitrogen-Fixation[END_REF][START_REF] Oldroyd | Coordinating nodule morphogenesis with rhizobial infection in legumes[END_REF]. The first morphological step to establish this symbiosis comprises a rhizobial trap, where a growing root hair engulfs the symbiont by physically curling around it [START_REF] Brewin | Plant cell wall remodelling in the rhizobium-legume symbiosis[END_REF][START_REF] Gage | Infection and invasion of roots by symbiotic, nitrogen-fixing rhizobia during nodulation of temperate legumes[END_REF].

Phenomena such as root hair deformation and root hair branching, steps that precede bacterial trapping in legumes [START_REF] Esseling | Nod factor-induced root hair curling: Continuous polar growth towards the point of nod factor application[END_REF][START_REF] Oldroyd | Calcium, kinases and nodulation signalling in legumes[END_REF], have been generally observed in plants in response to the microtubule-stabilizing agent taxol [START_REF] Bibikova | Microtubules regulate tip growth and orientation in root hairs of Arabidopsis thaliana[END_REF], in mutants like the kinesin mrh2 [START_REF] Yang | A Mutation in MRH2 Kinesin Enhances the Root Hair Tip Growth Defect Caused by Constitutively Activated ROP2 Small GTPase in Arabidopsis[END_REF] or upon overexpression of the formin protein AtFH8 [START_REF] Yi | Cloning and functional characterization of a formin-like protein (AtFH8) from Arabidopsis[END_REF] and the ROP GTPase RHO-OF PLANTS 2 [START_REF] Jones | The Arabidopsis Rop2 GTPase is a positive regulator of both root hair initiation and tip growth[END_REF].

In contrast, incomplete curls were only observed at low frequency in Arabidopsis mutants affected in the loci CEN1, CEN2, CEN3 [START_REF] Parker | Genetic interactions during root hair morphogenesis in Arabidopsis[END_REF] and in the scn1-1 mutant, where the corresponding locus encodes the RhoGTPase GDP dissociation inhibitor SUPERCENTIPEDE1 [START_REF] Carol | A RhoGDP dissociation inhibitor spatially regulates growth in root hair cells[END_REF]. This indicates full root hair curling to represent a rather specific invention. The entrapment of the symbiont completes with its full enclosure between root hair cell walls in a structure called the 'infection chamber' (IC) [START_REF] Brewin | Plant cell wall remodelling in the rhizobium-legume symbiosis[END_REF][START_REF] Gage | Infection and invasion of roots by symbiotic, nitrogen-fixing rhizobia during nodulation of temperate legumes[END_REF][START_REF] Esseling | Nod factor-induced root hair curling: Continuous polar growth towards the point of nod factor application[END_REF][START_REF] Fournier | Remodeling of the infection chamber before infection thread formation reveals a two-step mechanism for rhizobial entry into the host legume root hair[END_REF]. This is followed by exocytotic secretion of host-derived cell wall loosening enzymes such as NODULE PECTATE LYASE [START_REF] Xie | Legume pectate lyase required for root infection by rhizobia[END_REF] which, most likely, subsequently allows the formation of a negatively curved plasma membrane (PM) structure that further elongates into a tube-like channel, the 'infection thread' (IT) [START_REF] Brewin | Plant cell wall remodelling in the rhizobium-legume symbiosis[END_REF][START_REF] Gage | Infection and invasion of roots by symbiotic, nitrogen-fixing rhizobia during nodulation of temperate legumes[END_REF][START_REF] Gage | Hanging by a thread: invasion of legume plants by rhizobia[END_REF]. Parallel to these morphological changes a set of transcription factors genetically re-programs host root cells to allow transcellular IT progression and nodule organogenesis [START_REF] Heckmann | Lotus japonicus nodulation requires two GRAS domain regulators, one of which is functionally conserved in a non-legume[END_REF][START_REF] Bek | Improved Characterization of Nod Factors and Genetically Based Variation in LysM Receptor Domains Identify Amino Acids Expendable for Nod Factor Recognition in Lotus spp[END_REF][START_REF] Madsen | The molecular network governing nodule organogenesis and infection in the model legume Lotus japonicus[END_REF][START_REF] Cerri | The ERN1 transcription factor gene is a target of the CCaMK/CYCLOPS complex and controls rhizobial infection in Lotus japonicus[END_REF][START_REF] Kawaharada | The ethylene responsive factor required for nodulation 1 (ERN1) transcription factor is required for infection-thread formation in Lotus japonicus[END_REF][START_REF] Schauser | A plant regulator controlling development of symbiotic root nodules[END_REF][START_REF] Combier | MtHAP2-1 is a key transcriptional regulator of symbiotic nodule development regulated by microRNA169 in Medicago truncatula[END_REF].

Molecularly, initial root hair responses are triggered upon the recognition of bacterial signalling molecules, called Nod Factors, by host LysM-type receptor-like kinases [START_REF] Ben Amor | The NFP locus of Medicago truncatula controls an early step of Nod factor signal transduction upstream of a rapid calcium flux and root hair deformation[END_REF][START_REF] Limpens | LysM domain receptor kinases regulating rhizobial Nod factor-induced infection[END_REF][START_REF] Madsen | A receptor kinase gene of the LysM type is involved in legume perception of rhizobial signals[END_REF][START_REF] Arrighi | The Medicago truncatula lysine motif-receptor-like kinase gene family includes NFP and new nodule-expressed genes[END_REF][START_REF] Smit | Medicago LYK3, an entry receptor in rhizobial nodulation factor signaling[END_REF][START_REF] Radutoiu | Plant recognition of symbiotic bacteria requires two LysM receptor-like kinases[END_REF].

. CC-BY 4.0 International license made available under a (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is

The copyright holder for this preprint this version posted July 14, 2020. ; https://doi.org/10.1101/2020.07. 10.197160 doi: bioRxiv preprint 4 These include root hair swelling, deformation and branching that precede root hair curling. This is aided by a tip-localized cytosolic calcium gradient [START_REF] De Ruijter | Lipochitooligosaccharides re-initiate root hair tip growth in Vicia sativa with high calcium and spectrin-like antigen at the tip[END_REF][START_REF] Cardenas | Rhizobium Nod factors induce increases in intracellular free calcium and extracellular calcium influxes in bean root hairs[END_REF], global actin rearrangements and dense subapical fine actin bundles that are required for the delivery of Golgiderived vesicles to the root hair tip [START_REF] Esseling | Nod factor-induced root hair curling: Continuous polar growth towards the point of nod factor application[END_REF][START_REF] Miller | The role of actin in root hair morphogenesis: studies with lipochito-oligosaccharide as a growth stimulator and cytochalasin as an actin perturbing drug[END_REF][START_REF] Miller | Lipochitooligosaccharide nodulation factors stimulate cytoplasmic polarity with longitudinal endoplasmic reticulum and vesicles at the tip in vetch root hairs[END_REF][START_REF] Zepeda | Visualization of Highly Dynamic F-Actin Plus Ends in Growing Phaseolus vulgaris Root Hair Cells and Their Responses to Rhizobium etli Nod Factors[END_REF]. However, the molecular machinery steering actin reorganisation and polarity during root hair curling remains elusive. Altered actin dynamics during early responses to NFs or rhizobia have been shown in mutants such Lotus japonicus pir1/nap1 and scarn that are affected in the actin-related SCAR/WAVE complex [START_REF] Yokota | Rearrangement of Actin Cytoskeleton Mediates Invasion of Lotus japonicus Roots by Mesorhizobium loti[END_REF][START_REF] Qiu | SCARN a Novel Class of SCAR Protein That Is Required for Root-Hair Infection during Legume Nodulation[END_REF]. In addition, the presence of highly dynamic F-actin plus ends in swelling root hairs and during root hair deformation implies that newly accumulated actin physically pushes towards the PM to re-initiate the growth [START_REF] Zepeda | Visualization of highly dynamic Factin plus ends in growing phaseolus vulgaris root hair cells and their responses to Rhizobium etli nod factors[END_REF]. But, different to metazoan cells, where membrane protrusions such as filopodia are driven, among others, by formin-mediated polar growth of actin filaments [START_REF] Yang | Novel roles of formin mDia2 in lamellipodia and filopodia formation in motile cells[END_REF], any membrane protrusions in plant cells ultimately require local cell wall modifications and thus this membrane-cell wall continuum to be coordinatively regulated.

Here, we identified SYMBIOTIC FORMIN 1 (SYFO1) as an essential gene controlling symbiotic responses in root hairs. SYFO1 transiently re-localizes to the root hair tip upon inoculation of M. truncatula root hairs with S. meliloti and mediates the formation of polar actin accumulations. Its function strictly depends on the protein extracellular domain that mediates cell wall attachment. Taken together we demonstrate SYFO1 as the first player regulating the continuum between the plasma membrane and the cell wall during the onset of rhizobial infections.

5

RESULTS

Evolutionary and transcriptional patterns identify symbiotically regulated formins

Since formins are well known proteins conferring polar growth of actin filaments, we searched for candidates within this family that could control symbiotically induced root hair responses.

Based on the presence of a conserved Formin Homology 2 (FH2) domain, we identified 19 candidates in the Medicago truncatula genome (Table S1). Using publicly available transcriptome data, two of them (Medtr5g036540.1 and Medtr8g062830.1) were found to be transcriptionally up-regulated during early stages of symbiotic interactions [START_REF] Larrainzar | Deep Sequencing of the Medicago truncatula Root Transcriptome Reveals a Massive and Early Interaction between Nodulation Factor and Ethylene Signals[END_REF]. We independently verified these data using quantitative RT-PCR (qRT-PCR) with Medtr5g036540.1 being induced by about 60-fold at one day post inoculation (dpi) of roots with S. meliloti while only a weak induction could be confirmed for Medtr8g062830.1 at 5 dpi (Fig. S1A). Therefore, we named the genes SYMBIOTIC FORMIN 1 (SYFO1 (Medtr5g036540.1, MtrunA17_Chr5g0414941 in the v5r1.6 M. truncatula genome version) and SYFO1-like (SYFO1L, Medtr8g062830. [START_REF] Mylona | Symbiotic Nitrogen-Fixation[END_REF]MtrunA17_Chr8g0364331). Both encoded proteins contain a predicted signal peptide (SP) in the extracellular domain (ECD) followed by a single-span transmembrane domain (TMD), and FH2 domain in the cytoplasmic side.

To spatially resolve the observed transcriptional patterns for SYFO1, we generated a fluorescent reporter where a nuclear localized tandem GFP was driven by the endogenous SYFO1 promoter (ProSYFO1-NLS-2xGFP). Consistent with the qRT-PCR results (Fig. S1A), the SYFO1 promoter was activated at 1 dpi in root hairs and cortical cells (Fig. S1 B-C) while no activity was observed in the absence of the symbiont.

To supplement the identification strategy and to search for putative genetic redundancy, we studied evolutionary patterns within the formin family. The SYFO1/1L clade contains genes from all Eudicots species included in the analysis, and SYFO1 and SYFO1L derived from the Papilionoideae duplication. In A. thaliana, three co-orthologs of SYFO1 and SYFO1L are found: AtFH4, AtFH7, AtFH8 likely deriving from the Brassicaceae triplication (Fig. S2). While AtFH4 and AtFH8 resemble a similar protein domain structure compared to SYFO1 and SYFO1L, AtFH7 has lost the signal peptide and displays an altered TMD domain. Mining the gene expression atlas of other Papillionoideae, we found SYFO1 (in common bean, Phvul.002G077100.2) or SYFO1L (in Lotus japonicus Lj0g3v0115049.1) upregulated during nodulation, pinpointing for a potential shared function in nodulation within this clade.

Based on the phylogeny, we tested for relaxed or intensified selective pressure acting on different branches of interest in eudicot sequences (represented by circles) (Fig. S2; Supplemental Table S3). We identified relaxed selective pressure indicated by a higher overall ratio of non-synonymous (dN) vs. synonymous (dS) mutations (dN/dS) on the branch supporting the clade that includes all species that develop the root nodule symbiosis (NFN; K=0.54, LRT=85.3 and p-val < 1e-16). This relaxation was individually confirmed for Fabales (which includes legumes; K=0.66, LRT=18.3 and p-val< 14.1e-09), Cucurbitales (K=0.78, LRT=25.0 and p-val=5.6e-07) and Fagales (K=0.65, LRT=18.3 and p-val< 1.9e-05) but not for Rosales (K=1.17, LRT=7.4 and p-val< 6.7e-03) for which a slight intensification of selective pressure (lower overall dN/dS ratio) was detected. In contrast, Brassicaceae species are under strong intensification of the selective pressure (K=4.6, LRT=84.5 and p-val < 1e-16) that is not even relaxed by the triplication of the branch in this family. The relaxed selection pressure detected at the base of the NFN clade and at the base of the Fabales may both reflect neofunctionalization that would have occurred for the recruitment of SYFO1/1L in root nodule symbiosis. Interestingly, the corresponding orthologs of Parasponia andersonii, a non-legume tree that forms a Frankia-type symbiosis with rhizobia, are not induced during the symbiotic interaction. This further supports a possible functional specialisation of these formins in legumes /Papilionoidae [START_REF] Van Velzen | Comparative genomics of the nonlegume Parasponia reveals insights into evolution of nitrogen-fixing rhizobium symbioses[END_REF].

SYFO1 controls rhizobial infection and root hair responses

In order to genetically assess the function of SYFO1 and SYFO1L, we identified two independent Tnt1 transposon insertion lines for SYFO1 [syfo1-1 (NF9730) at 485bp and syfo1-2 (NF9495) at 1834bp downstream of the start codon] and SYFO1L [syfo1L-1 (NF20350) at 1279bp and syfo1L-2 (NF15608) at 1370bp downstream of the start codon] in Medicago wild type R108 (Fig. 1A). Endogenous SYFO1 and SYFO1L transcripts were significantly reduced in both lines, respectively (Fig. S3), while only the syfo1-1 and syfo1-2 alleles showed a significant nodulation phenotype developing fewer nodules per root at 3 weeks post inoculation (wpi) with about half of them being aborted and/or white, indicative of non-functional nodules (Fig. 1B-D). In contrast, bacterial infection patterns of Medicago wild-type and syfo1L-1 and syfo1L-2 mutant nodules were identical (Fig. 1C, D and Fig. S4A,B). The infection zones were found to be reduced in white but elongated (Fig. S4C) or spherical (Fig. S4D) syfo1 mutant nodules. The latter failed to maintain a persistent meristem (Fig. S4D). Therefore, we selected SYFO1 as the prime candidate of interest.

Although cytoskeleton-related mutants, like Lotus pir1, nap1 and scarn [START_REF] Yokota | Rearrangement of Actin Cytoskeleton Mediates Invasion of Lotus japonicus Roots by Mesorhizobium loti[END_REF][START_REF] Qiu | SCARN a Novel Class of SCAR Protein That Is Required for Root-Hair Infection during Legume Nodulation[END_REF], exhibit an impaired root hair growth, this was not observed for syfo1-1 and syfo1-2 where root hair length was indistinguishable from wild-type (Fig. S5). In agreement with this, we did not observe any differences in actin arrangement in growing root hairs within the symbiotically susceptible infection zone [START_REF] Gage | Infection and invasion of roots by symbiotic, nitrogen-fixing rhizobia during nodulation of temperate legumes[END_REF] under non-inoculated conditions (Fig. S6). These data demonstrate that SYFO1 is not required for normal root hair development under non-symbiotic conditions. As SYFO1 transcripts were upregulated at 1-3 dpi, a stage where we observe most root hairs responding to the presence of the symbiont by root hair deformation (1-2 dpi) (Fig. 2A) and curling (2-3 dpi) (Fig. 2B), we phenotypically assessed syfo1 mutants at these stages. Both mutant alleles showed significantly fewer deformations (Fig. 2C) as well as infection chambers and infection threads (Fig. 2E) at the respective time points. Both phenotypes were fully rescued when generating independent transgenic roots expressing a ProSYFO1:SYFO1-GFP (e.g. syfo1-1c) construct in these mutant backgrounds (Fig. 2D,F), demonstrating that the insertion in the SYFO1 locus is causative for these phenotypes.

As it was previously demonstrated that the inoculation of Lotus root hairs with its symbiont M. loti resulted in a strong polarization and bundling of actin filaments with a strong accumulation of F-actin in the root hair tip [START_REF] Yokota | Rearrangement of Actin Cytoskeleton Mediates Invasion of Lotus japonicus Roots by Mesorhizobium loti[END_REF][START_REF] Qiu | SCARN a Novel Class of SCAR Protein That Is Required for Root-Hair Infection during Legume Nodulation[END_REF], we tested whether this pattern is affected in syfo1 mutants.

In the absence of S. meliloti, longitudinal actin filaments were observed in young growing root hairs within the infection zone of Medicago wild-type plants (Fig. S7A). In agreement with the observations in Lotus, actin strongly bundled and polarized with an accumulation of F-actin at the apex (Fig. S7B-C) or occasionally at the apical shank of responding root hairs (Fig. S7D) in almost 90% of all root systems of wild-type plants (Fig. S7E). However, this pattern was strongly reduced in both syfo1 mutant alleles where only about 30% of all tested roots contained root hairs responding with the above-mentioned pattern (Fig. S7E).

SYFO1 associates with polar actin assemblies under symbiotic conditions

Since our data indicated a symbiosis-specific role of SYFO1 in root hair polarization, we investigated spatial and temporal dynamics of SYFO1 at subcellular resolution. In roots expressing the ProSYFO1:SYFO1-GFP construct, we observed a weak homogenous signal of the SYFO1 protein at the PM of root hairs in the absence of rhizobia (Fig. 3A). The underlying low, basal expression was also detected by qRT-PCR (Fig. S3A) while it was most likely too weak when using the nuclear-localized GFP reporter to test promoter activity (Fig. S1).

Interestingly, SYFO1 strongly accumulated in subapical and apical foci at root hair tips prior to deformation at 2 dpi with S. meliloti (Fig. 3B,C), which strongly resembled actin patterns observed upon Nod Factor application as reported earlier [START_REF] Yokota | Rearrangement of Actin Cytoskeleton Mediates Invasion of Lotus japonicus Roots by Mesorhizobium loti[END_REF]. In root hairs that morphologically responded by deformation (Fig. 3D) and curling (Fig. 3E), SYFO1 distributed again along the PM with only mild accumulations at the apical region (Fig. 3D). SYFO1 also resided along the infection thread membrane even though to a much weaker extent (Fig. 3F-F'). When co-localizing actin and SYFO1 (here: ProUbi-SYFO1-GFP) we frequently observed transient SYFO1 accumulations in close proximity to enlarged nuclei, a hallmark for symbiotically activated root hairs [START_REF] Oldroyd | Speak, friend, and enter: signalling systems that promote beneficial symbiotic associations in plants[END_REF], with actin bundles orienting towards a nucleation centre at the apical shank of the root hair (Fig. 3G-G').

Ligand-dependent morphological change mediated by SYFO1

To test whether SYFO1 acts in membrane-associated actin nucleation and polar filament elongation, we made use of the fact that extension of actin filaments can drive membrane protrusions as shown in cells lacking a rigid cell wall such as Drosophila Schneider 2 and mouse P19 cells [START_REF] Matusek | Formin proteins of the DAAM subfamily play a role during axon growth[END_REF][START_REF] Gombos | The Formin DAAM Functions as Molecular Effector of the Planar Cell Polarity Pathway during Axonal Development in Drosophila[END_REF]. For this, we generated a transgenic Medicago root organ culture (ROC) constitutively expressing SYFO1-GFP for 8 weeks. When isolating protoplasts from this culture, SYFO1 resided in the PM where it co-localized with the membrane stain FM4-64 with some accumulations in the sub-membrane space (Fig. 3H-H''). While no membrane protrusions were formed in the absence of bacteria, we observed these membrane outgrowths upon inoculation of protoplasts with S. meliloti for 5 hours. They coincided with SYFO1 accumulations inside these structures and often formed adjacent to bacterial aggregates (Fig. 3I-I''). To unambiguously verify that SYFO1 is the key driver of these protrusions we isolated protoplasts from our syfo1-1 and syfo1L-1 mutants. No protrusions were found in the absence of rhizobia in any of the used genotypes. Upon inoculation of protoplasts with S. meliloti, those expressing wild-type SYFO1 (wild-type, syfo1L-1) or over-expressing SYFO1-GFP (OE) developed protrusions while they were entirely absent on protoplasts isolated from the syfo1-1 mutant (Fig. 3J). This demonstrates that focal accumulation of SYFO1 can drive cell polarisation and membrane deformations in a stimulus-dependent manner.

A SYFO1-mediated cell wall-plasma membrane-cytoskeleton continuum is required for symbiotic responses in root hairs.

As actin binding of formins is generally mediated by the FH2 domain that is also present in the cytosolic domain of SYFO1 (Fig. 1A'), we examined the extracellular region, which is less prominently found among formin proteins. Further sequence analysis of the SYFO1 ECD (extracellular domain) revealed the presence of a proline-rich repeat (PRR) (e.g. Ser-Pro-Pro-Pro-Ser-Pro-Ser-Ser [SPPPSPSS]) between SP and TMD, which resembles a canonical motif of extensin proteins that have been proposed to contribute to cell wall architecture and tensile strength [START_REF] Estevez | Characterization of synthetic hydroxyproline-rich proteoglycans with arabinogalactan protein and extensin motifs in Arabidopsis[END_REF][START_REF] Lamport | Role of the extensin superfamily in primary cell wall architecture[END_REF]. Thus we investigated a possible role in cell wall association of the ECD. For this, we fused the 82 amino acids of the SYFO1 ECD to GFP (SYFO1 ECD -GFP) and expressed it in Nicotiana benthamiana leaf epidermal cells. The fluorescent label was found in the cell periphery in control cells (Fig. 4A-A'') while it remained predominantly associated with the cell wall upon plasmolysis (Fig. 4B-B''). In order to test whether this extensin-like motif contributes to the lateral immobilization of SYFO1 via cell wall anchoring we performed Fluorescence Recovery After Photobleaching (FRAP) experiments on root hairs constitutively expressing a full-length SYFO1 (SYFO1-GFP) or a mutant variant where we deleted the proline-rich repeat (SYFO1 ΔPRR -GFP). These experiments revealed a slow recovery of the bleached region and a mobile fraction of about 24% for wild-type SYFO1 whereas the mobile fraction for SYFO1 ΔPRR was significantly higher (57%) (Fig. 4C-E). This clearly indicates that the PRR segment within the SYFO1 ECD anchors this formin to the cell wall. To address whether the cell wall association is required for SYFO1 function we conducted genetic complementation experiments, we generated transgenic roots expressing SYFO1 ΔPRR under the control of the native SYFO1 promoter in our syfo1-1 and syfo1-2 alleles. In contrast to the fulllength SYFO1 (Fig. 2), the deletion of the PRR fully abolished the ability to complement the root hair deformation phenotype of syfo1 mutants (Fig. 4F), demonstrating that a SYFO1-mediated cell wall-plasma membrane-actin continuum is required for symbiotic responsiveness of root hairs in M. truncatula.

DISCUSSION

The engulfment of a single rhizobium by a tightly curled root hair represents a fascinating process that allows most legumes to keep full control over the onset of root hair infection and might minimize the risk of infection by non-symbiotic bacteria. Considering that the formin protein SYFO1 serves symbiotic but not general functions in root hair responsiveness (Fig. S5 and Fig. S6) demonstrates that Medicago genetically re-wired few components of the actin machinery to drive root hair curling. However, the generic set of actin and polarity factors such as NAP1/PIR1, members of the SCAR/WAVE complex [START_REF] Yokota | Rearrangement of Actin Cytoskeleton Mediates Invasion of Lotus japonicus Roots by Mesorhizobium loti[END_REF], and RHO OF PLANTS 10 [START_REF] Lei | The Small GTPase ROP10 of Medicago truncatula Is Required for Both Tip Growth of Root Hairs and Nod Factor-Induced Root Hair Deformation[END_REF] are additionally required for root hair growth per se. Consequently, these mutants show impaired growth also under non-symbiotic conditions. In contrast, legumes specifically evolved SCARN, another member of the SCAR/WAVE complex, which is required for rhizobial infection but not for growth under fully fertilized conditions [START_REF] Qiu | SCARN a Novel Class of SCAR Protein That Is Required for Root-Hair Infection during Legume Nodulation[END_REF]. The fact that the number of infection chambers was higher in Lotus scarn mutants compared to wild-type plants [START_REF] Qiu | SCARN a Novel Class of SCAR Protein That Is Required for Root-Hair Infection during Legume Nodulation[END_REF], places SCARN downstream of SYFO1. Since the bacterial colonization phenotypes in nodules are comparable between both mutants, both may contribute to actin function at this stage.

SYFO1 with its transmembrane helix and the extracellular proline-rich repeat carries all features of a group 1 formin [START_REF] Deeks | Formins: intermediates in signaltransduction cascades that affect cytoskeletal reorganization[END_REF]. As previously described for AtFH1 [START_REF] Martiniere | Building bridges: formin1 of Arabidopsis forms a connection between the cell wall and the actin cytoskeleton[END_REF], the PRR mediates cell wall association and consequently restricts the lateral mobility also in SYFO1 (Fig. 4E).

Its ability to initiate membrane protrusions in cell wall-depleted protoplasts further suggests that SYFO1 is involved in actin nucleation and filament elongation (Fig. 3G-G'; Fig. S8). In line with non-symbiotic formins, such as AtFH4 from Arabidopsis that re-localizes to infection sites of the powdery mildew fungus Blumeria graminis [START_REF] Sassmann | An Immune-Responsive Cytoskeletal-Plasma Membrane Feedback Loop in Plants[END_REF], we hypothesize that SYFO1 evolved to specifically mediate targeted secretion of cell wall constituents and other cargo material to sustain symbiotic root hair responses including root hair curling and later stages of infection. This entirely depends on the ability of SYFO1 to associate with the cell wall (Fig. 4)

where it maintains a cell wall-plasma membrane-cytoskeleton continuum that cannot be functionally complemented by other, non-symbiotic formins that remain being expressed in syfo1 mutants.

MATERIALS AND METHODS

Plant growths and phenotypical analysis

For phenotypical analysis Medicago truncatula wild-type R108, syfo1-1, syfo1-2, syfo1L-1 and syfo1L-2 seeds were scarified and sterilized before being sown on 1% agar plates for germination and kept in darkness at 4°C for 3 days for vernalization. Germination was allowed for up to 24 hours at 24°C before transferring the seedlings to plates containing Fahraeus medium [START_REF] Fahraeus | The Infection of Clover Root Hairs by Nodule Bacteria Studied by a Simple Glass Slide Technique[END_REF] for 4 days in the presence of 1 mM nitrate before being transferred to a plate culture system without nitrogen for phenotyping studies. Plants were inoculated with 1ml Sinorhizobium meliloti 2011 (mCherry) at an OD600 of 0.05 (on plates or open pots with 1:1 ratio of vermiculite and sand mixture). Symbiotic responses including root hair deformations, infection chamber formation and IT development were scored 5 dpi of plants with S. meliloti on plates. Soil-based nodulation phenotyping samples were harvested and quantified at 3 wpi.

Nodules were embedded in 7% Agar and sectioned with a thickness of 60 µm using a vibratome.

Genotyping of Tnt1 insertion lines and quantitative Real-Time PCR

R0 or R1 seeds of M. truncatula R108 Tnt1 transposon insertion lines were obtained from the Noble Research Institute (OK, USA) and insertions were verified using primers listed in Table S4. Total RNA of control and insertion lines was extracted using a commercial kit (Spectrum TM Plant Total RNA Kit, Sigma life science) following the supplier's instructions. An additional DNaseI treatment was performed. Synthesis of cDNA and qRT-PCR were conducted as described earlier [START_REF] Liang | Symbiotic root infections in Medicago truncatula require remorinmediated receptor stabilization in membrane nanodomains[END_REF] using the SuperScriptIII reverse Transcriptase (Invitrogen). All data were normalized to Ct values of the housekeeping gene ubiquitin [START_REF] Satge | Reprogramming of DNA methylation is critical for nodule development in Medicago truncatula[END_REF] using primers listed in Table S4.

Hairy root transformation and inoculation of rhizobia

M. truncatula hairy root transformation was performed as previously described [START_REF] Boisson-Dernier | Agrobacterium rhizogenes-transformed roots of Medicago truncatula for the study of nitrogen-fixing and endomycorrhizal symbiotic associations[END_REF] using the Agrobacterium rhizogenes strain ARqua1. Plants were transferred weekly to fresh plates containing Fahraeus medium (pH 6.0) supplemented with 0.5 mM NH4NO3 and followed by 2 days of growth on nitrogen-free Fahraeus medium containing 0.1 µM AVG prior to inoculation.

Images for localisation studies and root hair phenotyping analyses were taken on plants inoculated for 2 days and 5 days, respectively.

Phylogenetic and selective pressure analysis SYFO1 (Medtr5g036540.1) and SYFO1L (Medtr8g062830.1) protein sequences were used as queries for a tBLASTn v2.8.1+ (10.1186/1471-2105-10-421) search against a database of 101 Angiosperms genomes (Table S2, sequences can be downloaded from the SymDB database (10.1038/s41477-020-0613-7): http://www.polebio.lrsv.ups-tlse.fr/symdb) with an e-value threshold of 1e-10. Sequences were then aligned using MAFFT v7.407 (10.1093/molbev/mst010) with default parameters. The resulting alignment was trimmed using trimAl v1.4 rev22 (10.1093/bioinformatics/btp348) to remove positions containing more than 20% of gaps. The cleaned alignment was then subjected to a Maximum Likelihood (ML) analysis using IQ-TREE v1.6.7 (10.1093/molbev/msu300) as described here after. First, the best-fitting evolutionary model was tested using ModelFinder (10.1038/nmeth.4285). Then a ML search was performed using 10,000 replicates of SH-aLRT (10.1093/sysbio/syq010) for testing branches support. The tree was finally visualized and annotated with iTOL v4.4 (10.1093/nar/gkw290).

Signal peptide and transmembrane domains were predicted from proteins using signal v5.0 (10.1038/s41587-019-0036-z) and TMHMM v2.0c (PMID: 9783223G) respectively using default parameters.

To look for relaxation (K<1) or intensification (K>1) of selection acting on different lineages of interest in Eudicots (Table S3), we used the RELAX program (10.1093/molbev/msu400). This method calculates different synonymous and non-synonymous substitution rates (ω = 𝑑N/𝑑S) using the phylogenetic tree topology for both foreground and background branches.

Because (i) the programs used does not accept gaps in codon sequences and (ii) there is a negative correlation between the number of sequences and the number of ungapped positions, we used different numbers of input sequences for RELAX analysis. Protein sequences from SYFO1 and SYFO1L orthologs were aligned using MUSCLE v3.8.382. Short sequences were excluded to maximize sequence number while limiting gapped positions compared to SYFO1 and SYFO1L sequences of Medicago using a custom R script. We opted for 151 CDS sequences corresponding to 1008 positions (Table S3).

Construct design

The constructs used in this study were designed using Golden Gate cloning [START_REF] Binder | A Modular Plasmid Assembly Kit for Multigene Expression, Gene Silencing and Silencing Rescue in Plants[END_REF]. 2.5 kb upstream of the SYFO1 start codon were chosen as putative promoter region. A Golden Gate compatible full-length genomic DNA version (Medtr5g036540.1) was synthesized (GENEWIZ, Germany) by removing the BpiI and BsaI restriction sites via silent mutations.

All cloning primers are listed in Table S4. To select transgenic roots a pUbi:NLS-mCherry or pUbi:NLS-2xCerulean cassette was additionally inserted into the different T-DNAs containing the transgenes of choice as previously described [START_REF] Liang | Symbiotic root infections in Medicago truncatula require remorinmediated receptor stabilization in membrane nanodomains[END_REF]. Level II and level III constructs were assembled based on the principle described earlier [START_REF] Binder | A Modular Plasmid Assembly Kit for Multigene Expression, Gene Silencing and Silencing Rescue in Plants[END_REF]. An overview about all designed constructs is provided in Table S5.

Confocal Laser-Scanning Microscopy and FRAP

For imaging the NLS-GFP reporter module, sectioned nodules, protein localisation and plasmolysis we used a Leica TCS SP8 confocal microscope equipped with a 20x HCX PL APO water immersion lenses (Leica Microsystems, Mannheim, Germany). GFP was excited with a White Light Laser (WLL) at 488 nm and the emission was detected at 500-550 nm. mCherry fluorescence was excited using a WLL at 561nm and emission was detected between 575-630 nm. Samples, co-expressing two fluorophores were imaged in sequential mode between frames.

FRAP analysis was conducted using a Zeiss LSM 880 Airyscan confocal microscope. For this, the VP (Virtual Pinhole) mode was adapted based on the fluorescence intensity of probe and Airyscan processing was performed using the ZEN (black edition) software package. The bleaching region, reference region and background region were selected at identical size. A pre-bleaching time of 5 seconds was chosen. Bleaching was set to stop upon the intensity dropping to 50% of the initial intensity before fluorescence recovery was recorded for 10 minutes. Using the FRAP data process package in ZEN (black version), the mobile fraction was calculated by the following equation (mobile fraction= 𝐼1/ 𝐼𝐸), where 𝐼1 represents the dropped intensity and the 𝐼𝐸 represents the recovered intensity normalized to the reference intensity.

Root organ culture, protoplast extraction, and inoculation

Transgenic Root Organ Culture (ROC) of M. truncatula expressing SYFO1-GFP were obtained via hairy root transformation according to [START_REF] Boisson-Dernier | Agrobacterium rhizogenes-transformed roots of Medicago truncatula for the study of nitrogen-fixing and endomycorrhizal symbiotic associations[END_REF]. Fully transformed root segments were cut and initially transferred to M-Media plates (Becard & Fortin, 1988) containing Augmentin (Sigma). 1 g of amoxicillin-200 mg of clavulanic acid) (400 mg/L) for two weeks and then subcultured on plates supplemented with 200 mg/L Augmentin for additional two weeks to remove A. rhizogenes contamination. Plates were sealed with micropore tape and incubated at 24°C in dark. Afterwards, the ROC was transferred to M-media plates without Augmentin to support faster tissue growth. Continuous expression of the transformation marker was monitored throughout the entire experiment.

Protoplasts were isolated from ROC by cutting the roots in small pieces of 2-5 mm length and processed as described previously [START_REF] Jia | An Efficient Protocol for Model Legume Root Protoplast Isolation and Transformation[END_REF]. For inoculation, an S. meliloti culture was diluted in W5 solution [START_REF] Jia | An Efficient Protocol for Model Legume Root Protoplast Isolation and Transformation[END_REF] to an OD600 of 0.05 before being added to the protoplasts.

Actin phalloidin staining and plasma membrane FM4-64 staining

Phalloidin-based actin staining was performed according to a published protocol [START_REF] Miller | The role of actin in root hair morphogenesis: studies with lipochito-oligosaccharide as a growth stimulator and cytochalasin as an actin perturbing drug[END_REF]. In brief, Medicago roots were transferred into Fahraeus medium containing 300 µM MBS (mmaleimidobenzoyl-N-hydroxysuccinimide ester) for 30 minutes to stabilize the actin filaments.

The material was then fixed in 2 % formaldehyde in actin-stabilizing buffer (ASB) solution [START_REF] Yokota | Rearrangement of Actin Cytoskeleton Mediates Invasion of Lotus japonicus Roots by Mesorhizobium loti[END_REF]. Phalloidin was added to a final concentration of 16 µM and staining was performed in the dark for 30 minutes. Root-derived protoplasts were submerged in a FM4-64 solution with a final concentration of 20 µM and incubated on ice for 5-10 mins before imaging.

Figures and Legends

1 .

 1 Figure 1. SYFO1 but not SYFO1L is required for nodulation. (A-A') Isolation of independent mutant alleles with Tnt1 transposon insertions mapping to different regions of the SYFO1 and SYFO1L gene (A) and protein (A') models, the extracellular domain is indicated as ECD and the orange box indicated the location of proline-rich repeat (PRR). (B-B'') Nodule phenotypes observed on the different genotypes at 3 wpi with S. meliloti in open pots using WT R108 plants as a control. Scale bars indicate 200 µm. (C-D) Quantification of nodule numbers (C) and the ratio of aborted/wild-type like nodules (D) (n=10). Asterisks indicate a significant statistical difference based on a Tukey-Kramer multiple-comparison test with p-values <0.01 (**), < 0.001 (***). Data are shown as mean ± SE.

Figure 2 .

 2 Figure 2. syfo1 mutants are impaired in symbiotic root hair responses. Images show deformed root hairs (A), infection chambers (ICs) and infection threads (ITs) (B) on wild-type plants to illustrate the scored structures. Scale bars indicate 10 µm. syfo1 mutants show significantly reduced responsiveness to the presence of compatible rhizobia when assessing root hair deformations (C) and infection-related structures such as ICs + ITs (E). These phenotypes were complemented by introducing a genomic version of a full-length SYFO1 gene driven by the endogenous SYFO1 promoter (syfo1-1c, syfo1-2c) with an empty vector (ev) transformation control aside (D and F). Asterisks indicate a significant statistical difference based on a Tukey-Kramer multiple-comparison test with p-values <0.01 (**), < 0.001 (***). Data are shown as mean ± SE with independent 9-14 plants for phenotypical analysis, and 10 plants for complementation analysis.

Figure 3 .

 3 Figure 3. SYFO1 functions as a symbiotic polarity factor in root hairs. SYFO1-GFP localizes homogeneously to the PM of root hairs under mock conditions (A). At 2 dpi with S. meliloti, SYFO1 transiently polarizes at subapical (B) and apical regions (C) of root hairs, before distributing equally along the PM during root hair deformation (D) and curling (E). The arrowhead marks cell wall autofluorescence around the IC (E and F). SYFO1 remains on the IT membrane (F and inset F'). Co-localisation between SYFO1-GFP and actin marker ABD2:mCherry (G-G'). The nucleus encircled with a dash line in G-G' is based on corresponding transmitted light image (not shown). The arrowheads point towards actin bundles orienting towards a nucleation centre at the apical shank of the root hair. Scale bars indicate 10 µm. Protoplasts of a ROC expressing SYFO1 and counterstained with the styryl dye FM4-64 remain uniformly round at 0 dpi (H-H'') while focal membrane protrusions with accumulated SYFO1 were found at 5 hpi with Ds-Red expressing S. meliloti (I-I''). Scale bars indicate 5 µm. (J) Quantification of membrane protrusions in protoplasts using different genetic backgrounds. Asterisks indicate a significant statistical difference based on an ANOVA followed by a Fisher LSD test, with pvalues <0.05 (*), < 0.01 (**). Data are shown as mean ± SE of 3 independent biological replicates with n indicating the total number of protoplasts being scored.

Figure 4 .

 4 Figure 4. Cell wall association of SYFO1 is essential for its function. The constitutively expressed ECD of SYFO1 labelled the cell periphery in non-plasmolysed cells (A-A'') and remained at the cell wall upon plasmolysis (B-B''). Arrowheads and arrows mark the cell wall and the retracted plasma membrane, respectively. FRAP experiments on roots hairs revealed a low mobility of full-length SYFO1 (C-C''') while deletion of the PRR resulted in an increased mobility of the protein (D-D'''). Scale bars indicate 10 µm. (E) Quantification of the mobile fractions of SYFO1 (n=17) and SYFO1 DPRR (n=12), asterisks indicate a significant statistical difference based on a student t test. (F) The SYFO1 DPRR variant failed to genetically complement both syfo1 mutant alleles in comparison to roots transformed with the empty vector (ev) scoring n=10 independent root systems per genotype. Asterisks indicate a significant statistical difference based on a Tukey-Kramer multiple-comparison test with p-values <0.001 (***), p<0.01 (**). Data are shown as mean ± SE.

  (which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is

	bioRxiv preprint	doi:	; https://doi.org/10.1101/2020.07.10.197160	this version posted July 14, 2020.	The copyright holder for this preprint
			. CC-BY 4.0 International license made available under a

ACKNOWLEDGEMENTS

This study was supported by the project Engineering Nitrogen Symbiosis for Africa (ENSA) currently supported through a grant to the University of Cambridge by the Bill & Melinda Gates Foundation (OPP1172165) and UK government's Department for International Development (DFID) as well as by the China Scholarship Council (CSC) (grant no. 201506350004 to PL). JK, CL and PMD belong to the LRSV, which is part of the TULIP LABEX (ANR-10-LABX-41). We thank the staff of the Life Imaging Center (LIC) in the Center for Biological Systems Analysis (ZBSA) of the Albert-Ludwigs-University of Freiburg for help with their confocal microscopy resources, and the excellent support in image recording. The Medicago truncatula plants utilized in this research project, which are jointly owned by the Centre National De La Recherche Scientifique, were obtained from Noble Research Institute, LLC and were created through research funded, in part, by a grant from the National Science Foundation, NSF-0703285. We are grateful to the genotoul bioinformatics platform Toulouse Occitanie (Bioinfo Genotoul, doi: 10.15454/1.5572369328961167E12) for providing computing resources.

We would explicitly thank all the members of our team for the fruitful discussions and for providing their individual expertise throughout the course of the project.

The authors declare no competing interests.