Emiliano Lorini

Mario Verdicchio

Towards a logical model of social agreement for agent societies

, comprised of autonomous entities with the aim to cooperate to reach a common goal, may be viewed as computational models of distributed complex systems such as organizations and institutions.

There have been several model proposals in the agent literature with the aim to support, integrate, substitute human organizations, but no attempt has gone beyond the boundaries of this research context to become a mainstream software engineering implementation guideline, nor has it been adopted as a universal model of multi-agent interaction in economics or social sciences. In this work we counter top-down, operational organization specifications with a logical model of a fundamental concept: agreement, with the long-term aim to create a formal model of multi-agent organization that can serve as a universally accepted basis for implementation of collaborative distributed systems.

Introduction

Multi-agent systems (MASs) can provide an effective computational model of autonomous individuals interacting in a complex distributed system. The models that simulate the operations of multiple entities can show how agent technology can be exploited in economics and social sciences. The lack of a breakthrough so far is possibly paralleled by some lack of generality in the proposed MAS implementations. Several research works aim at proposing operational models of multi-agent organizations in the form of templates of norms, roles, interaction patterns, and so on, that have a significant impact on the agent community, but whose adoption by a wider audience may be hindered by a discrepancy between how organizations are conceived in this research context and how they actually emerge in the real world.

In this work we begin our attempt to formalize the concept of organization starting from what we consider its most fundamental component: agreement. We see an organization as a way to coordinate agent interaction that starts from an agreement between the relevant agents. Moreover, we adopt a bottom-up, formal approach to keep our analysis as general as possible, and, as a consequence, the application field of our current and future results as wide as possible.

The paper is organized as follows: Section 2 illustrates more in detail the motivations to our efforts; Section 3 presents the syntax and the semantics of our logical model, and some choices made in the model are discussed in Section 4, while Section 5 presents some theorems; Sections 6 and 7 illustrate how agreements are formed and how commitments and norms can be grounded on them, respectively; Section 8 provides some pointers to significant related literature, and, finally, Section 9 concludes.

Motivation

MASs can be seen as conceived with two distinct purposes. In the scenarios envisioned by the pioneers of this field, whose hopes were boosted also by the unprecedented success of Internet technologies, agents were viewed as a further development of the object-oriented paradigm, leading to the implementation of goal-driven, mobile programs that could cooperate with each other autonomously to reach a common objective. In a broader interpretation including social, economic, legal aspects, MASs are seen as a computational model of groups of interacting entities: Agents are programs that simulate a real-life complex system whose properties are to be analyzed by means of a computer system.

The lack (so far) of a so-called 'killer application' based on MAS technology does not mean that the latter interpretation traces the only viable path for agent researchers. Nevertheless, in our opinion, significant achievements in the simulation-oriented MAS research are a necessary step to finally reach a breakthrough also in mainstream software development. We agree with DeLoach [START_REF] Deloach | Moving multiagent systems from research to practice[END_REF]: MAS researchers have not yet demonstrated that the agent approach can yield competitive or even better solutions than other programming paradigms by providing reliable, complex, distributed systems.

We refer to virtual organizations, and think that the relevance of MAS technologies can be shown by a believable agent-based simulation of real-life, human organizations. Once agents are proven to be capable of delivering detailed models of complex organizations, then they can become a very appealing candidate for cutting-edge software solutions aiming at supporting, or even substituting, their human counterparts.

Several models of virtual organizations have been proposed in the literature [START_REF] Sycara | The Retsina MAS infrastructure[END_REF], [START_REF] Esteva | Islander: an electronic institutions editor[END_REF]. In particular, Electronic Institutions [START_REF] Noriega | Electronic institutions: Future trends and challenges[END_REF] have been introduced to regulate agent interaction in open environments. We see some issues rising from this research line: How really open are these environments with respect to the constraints introduced by the proposed organizational models? How does the operational nature of these models (as opposed to logical) affect their impact on the potential adopters? These questions are facets of our main concern: The affinity of virtual organizations with real ones is a key factor in MAS technology's shift from research to practice. Although we can provide detailed specifications of virtual organizations in terms of roles, scenarios, interaction patterns, communication protocols and so on, we think that such approach inevitably narrows down the scope of a proposal to the researchers' working hypotheses. The topdown specification of a predefined template is not the way organizations are born in the real world, and this distance between theoretical research and actual organizational dynamics might correspond to the gap between the agent-based proposals and the solutions adopted in the industry.

Our work has a rather different, if not opposite, starting point. We intend to provide a logical model (as opposed to operational) that allows for the formalization of the creation of organizations in a bottom-up fashion (as opposed to top-down). It might seem surprising that researchers who call for the elimination of the gap between theory and practice opt for a logic-based approach. However, this is a research field where universal models for basic concepts, including the very concept of 'agent', are still missing. We think that theoretical definitions of general concepts might work as wider and more solid foundations for the construction of a model of organizations that can eventually provide effective implementation guidelines. This is also the idea behind the choice of a bottom-up approach: To keep a model of organizations as general as possible, instead of trying to impose a standard template, which is a surely successful approach only in monopoly contexts, we aim at shedding some light on the basic mechanisms that lead a group of independent individuals (or autonomous agents) to form an organization.

In a top-down approach, agents join an organization with pre-established rules. In our bottom-up approach, we see an organization as the product of the agreement of several agents on how their future interactions should be regulated. Thus, the aim of this work is to formally define 'agreement' as a fundamental concept for the creation of multi-agent organizations, that is, we intend to propose a logic of social agreement.

A modal logic of social agreement

We present in this section the syntax and semantics of the modal logic SAL (Social Agreement Logic). The logic SAL specifies the conditions under which agreements are established and annulled. The main idea behind the formalism is to take agreement as a primitive object and to clarify its relationships with the concept of preference (i.e. how agreement formation depend on agents' preferences). We make a general assumption about rationality of agents in our logical approach to agreement. In particular, we suppose that the agents in a group I agree about a certain issue ϕ only if ϕ is something satisfactory for the agents in I. In other words, an agreement between certain agents is formed only if the content of agreement is something good for every agent.

Syntax

Let ATM = {p, q, . . .} be a nonempty set of atomic formulas, AGT = {i, j, . . .} a nonempty finite set of agents, and ACT = {α, β, . . .} a nonempty set of atomic actions. We note 2 ACT * = 2 ACT \ ∅ the set of all non-empty sets of actions, and 2 AGT * = 2 AGT \ ∅ the set of all non-empty sets of agents.

We introduce a function REP that associates to every agent i in AGT a non-empty set of atomic actions called action repertoire of agent i:

REP : AGT -→ 2 ACT * . For every agent i ∈ AGT we define the set of i's action tokens of the form i:α, that is,

∆ i = {i:α | α ∈ REP (i)}.
That is, i:α is an action token of agent i only if α is part of i's repertoire. We note ∆ = i∈AGT ∆ i the pointwise union of the sets of possible action tokens of all agents.

The following abbreviations are convenient to speak about joint actions of groups of agents. For every non-empty set of agents I we note JACT I the set of all possible combinations of actions of the agents in I (or joint actions of the agents in I), that is, JACT I = i∈I ∆ i . For notational convenience we write JACT instead of JACT AGT . Elements in every JACT I are tuples noted δ I , δ I , δ I , . . .. Elements in JACT are simply noted δ, δ , δ , . . . For example suppose that I = {1, 2, 3} and δ I = 1:α, 2:β, 3:γ . This means that δ I is the joint action of the agents 1, 2, 3 in which 1 does action α, 2 does action β and 3 does action γ. For notational convenience, we write δ i instead of δ {i} for every i ∈ AGT .

The language of SAL is the set of formulas defined by the following BNF:

ϕ ::= p | ⊥ | ¬ϕ | ϕ ∨ ϕ | Agree I ϕ | Do i:α ϕ
where p ranges over ATM , i ranges over AGT , i:α ranges over ∆ i , and I ranges over 2 AGT * . The classical Boolean connectives ∧, →, ↔ and (tautology) are defined from ⊥, ∨ and ¬ in the usual manner.

The operators of our logic have the following reading.

-Agree I ϕ: 'the agents in the group I agree that ϕ'.

-Do i:α ϕ: 'agent i is going to do α and ϕ will be true afterwards' (therefore Do i:α is read: 'agent i is going to do α').

Operators of the form Agree I enable one to express those issues on which the agents in I agree, while forming a coalition. For example, Agree I ¬smokePublic expresses that the agents in I agree that people should not smoke in public spaces.

The formula Agree I ⊥ literally means that 'the agents in I agree on a contradiction'. We assign a special meaning to this formula by supposing that 'agreeing on a contradiction' means 'not being part of the same group' (or 'not forming a coalition'). This is because we assume that functioning as members of the same coalition is (at least in a minimal sense) a rational activity, and a rational group of agents cannot agree on a contradiction. Thus, Agree I ⊥ should be read 'the agents in I do not function as members of the same group' or 'the agents in I do not form a coalition' or 'the agents in I do not constitute a group'. Conversely, ¬Agree I ⊥ has to be read 'the agents in I function as members of the same group' or 'the agents in I form a coalition' or 'the agents in I constitute a group'. This concept of constituted group is expressed by the following abbreviation. For every I ∈ 2 AGT * :

Group(I) def = ¬Agree I ⊥.
Note that this definition of group demands for some form of agreement, in particular if the agents in I form a coalition (i.e. Group(I)) then the agents in I agree that they form a coalition (i.e. Agree I Group(I)). Indeed, as we will show in Section 3.3, our agreement operators satisfy the axiom ¬Agree I ϕ → Agree I ¬Agree I ϕ.

If I is a singleton then Agree I is used to express the individual preferences of agent i. That is, for every i ∈ AGT :

Pref i ϕ def = Agree {i} ϕ.
Formula Pref i ϕ has to be read 'agent i prefers that ϕ is possible' (semantically this means that 'ϕ is true in all states that are preferred by agent i').

The following additional abbreviations will be useful to make more compact our notation in the sequel of the article. For every i ∈ AGT :

Sat i ϕ def = ¬Pref i ¬ϕ.
Formula Sat i ϕ has to be read 'ϕ is a satisfactory state of affairs for agent i' (semantically this means that 'there exists at least one preferred state of agent i in which ϕ is true').

For every I ∈ 2 AGT * and δ I ∈ JACT I :

Do δ I ϕ def =
j∈I Do δj ϕ. Formula Do δ I ϕ has to be read 'the agents in I execute in parallel their individual actions δ i in the vector δ I and ϕ will be true after this parallel execution'. We shorten this to 'the joint action δ I is going to be performed by group I and ϕ will be true afterwards'. In other words, we consider a weak notion of joint action δ I as the parallel execution of the individual actions δ i by every agent in I.

For every I ∈ 2 AGT * :

Pref I ϕ def = j∈I Pref j ϕ; Sat I ϕ def =
j∈I Sat j ϕ. Formula Pref I ϕ has to be read 'every agent in I prefers that ϕ is true', whilst Sat I ϕ has to be read 'ϕ is satisfactory for every agent in I'.

Semantics

Frames of the logic SAL (SAL-frames) are tuples F = W, R, A defined as follows.

-W is a non empty set of possible worlds or states.

-R : ∆ -→ W × W maps every possible action token i:α to a deterministic relation R i:α between possible worlds in W .3 -A : 2 AGT * -→ W × W maps every non-empty set of agents I to a transitive 4 and Euclidean5 relation A I between possible worlds in W .

It is convenient to view relations on W as functions from W to 2 W ; therefore we write A I (w) = {w : (w, w ) ∈ A I } and R i:α (w) = {w : (w, w ) ∈ R i:α }. If A I (w) = ∅ and R i:α (w) = ∅ then we say that A I and R i:α are defined at w. Given a world w ∈ W , A I (w) is the set of worlds which are compatible with group I's agreements at world w. If I is a singleton {i} then A {i} (w) is the set of worlds that agent i prefers. If (w, w ) ∈ R i:α then w is the unique actual successor world of world w, that will be reached from w through the occurrence of agent i's action α at w. (We might also say that R i:α is a partial function). Therefore, if R i:α (w) = {w } then at w agent i performs an action α resulting in the next state w .

It is convenient to use

R δ I = i∈I R δi . If R δ I (w) = ∅ then coalition I performs joint action δ I at w. If w ∈ i∈I R δi (w)
then world w results from the performance of joint action δ I by I at w.

Frames will have to satisfy some other constraints in order to be legal SAL-frames. For every i, j ∈ AGT , α ∈ REP (i), β ∈ REP (j) and w ∈ W we have:

S1 if R i:α and R j:β are defined at w then R i:α (w) = R j:β (w).
Constraint S1 says that if w is the next world of w which is reachable from w through the occurrence of agent i's action α and w is also the next world of w which is reachable from w through the occurrence of agent j's action β, then w and w denote the same world. Indeed, we suppose that every world can only have one next world. Note that S1 implies the determinism of every R i:α . Moreover, note that constraint S1 justifies the reading of formula Do i:α ϕ as 'agent i is going to do α and ϕ will be true afterwards'. Indeed, we intend to express in our logic what agents will do as the result of their agreement on what to do together, rather than what agents will possibly do.

We also suppose that every agent can perform at most one action at each world. That is, for every i ∈ AGT and α, β ∈ REP (i) such that α = β we have:

S2 if R i:α is defined at w then R i:β is not defined at w.
We impose the following semantic constraint for individual preferences by supposing that every relation A {i} is serial, i.e. an agent has always at least one preferred state. For every w ∈ W and i ∈ AGT :

S3

A {i} (w) = ∅.

The following semantic constraint concerns the relationship between agreements and individual preferences. For every w ∈ W and I, J ∈ 2 AGT * such that J ⊆ I:

S4 if w ∈ A I (w) then w ∈ A J (w ).
According to the constraint S4, if w is a world which is compatible with I's agreements at w and J is a subgroup of group I, then w belongs to the set of worlds that are compatible with J's agreements at w . The last two semantic constraints we consider are about the relationships between preferred states of an agent and actions. For every w ∈ W , i ∈ AGT and δ i ∈ ∆ i :

S5

if R δi is defined at w for every w ∈ A {i} (w) then R δi is defined at w.

According to the constraint S5, if action δ i of agent i occurs in every state which is preferred by agent i, then the action δ i occurs in the current state.

For every w ∈ W and i ∈ AGT : S6 if R δi is defined at w then there exists I ∈ 2 AGT * such that i ∈ I and R δi is defined at w for every w ∈ A I (w).

According to the constraint S6, if agent i's action δ i occurs at world w then there exists a group I to which i belongs such that, for every world w which is compatible with I's agreements at w, i's action δ i occurs at w . Models of the logic SAL (SAL-models) are tuples M = F, V defined as follows.

-

F is a SAL-frame. -V : W -→ 2 ATM is a valuation function.
Given a model M , a world w and a formula ϕ, we write M, w |= ϕ to mean that ϕ is true at world w in M . The rules defining the truth conditions of formulas are just standard for p, ⊥, ¬ and ∨. The following are the remaining truth conditions for Agree I ϕ and Do i:α .

-M, w |= Agree I ϕ iff M, w |= ϕ for all w such that w ∈ A I (w) -M, w |= Do i:α ϕ iff there exists w ∈ R i:α (w) such that M, w |= ϕ Note that Agree I is a modal operator of type necessity, whilst Do i:α is of type possibility. The following section is devoted to illustrate the axiomatization of SAL.

Axiomatization

The axiomatization of the logic SAL includes all tautologies of propositional calculus and the rule of inference modus ponens (MP).

From SAL ϕ and SAL ϕ → ψ infer SAL ψ (MP)

We have the following four principles for the dynamic operators Do i:α .

(Do i:α ϕ ∧ ¬Do i:α ¬ψ) → Do i:α (ϕ ∧ ψ) (K Do ) Do i:α ϕ → ¬Do j:β ¬ϕ (Alt Do ) Do i:α → ¬Do i:β if α = β (Single) From SAL ϕ infer SAL ¬Do i:α ¬ϕ (Nec Do )
Dynamic operators of the form Do i:α are modal operators which satisfy the axioms and rule of inference of the basic normal modal logic K (Axiom K Do and rule of inference Nec Do ). Moreover, according to Axiom Alt Do , if i is going to do α and ϕ will be true afterwards, then it cannot be the case that j is going to do β and ¬ϕ will be true afterwards. According to Axiom Single, an agent cannot perform more than one action at a time. This axiom makes perfectly sense in simplified artificial settings and in gametheoretic scenarios in which actions of agents and joint actions of groups never occur in parallel.

We have the following principles for the agreement operators and the preference operators, and for the relationships between agreement operators, preference operators and dynamic operators.

(Agree I ϕ ∧ Agree I (ϕ → ψ)) → Agree I ψ (K Agree ) ¬Pref i ⊥ (D Pref ) Agree I ϕ → Agree I Agree I ϕ (4 Agree ) ¬Agree I ϕ → Agree I ¬Agree I ϕ (5 Agree ) Agree I (ϕ → ¬Agree J ¬ϕ) if J ⊆ I (Subgroup Agree ) Pref i Do δi → Do δi (Int1 Pref,Do ) Do δi → i∈I Agree I Do δi (Int2 Pref,Do ) From SAL ϕ infer SAL Agree I ϕ (Nec Agree )
Operators for agreement of the form Agree I are modal operators which satisfy the axioms and rule of inference of the basic normal modal logic K45 [START_REF] Chellas | Modal logic: an introduction[END_REF] (Axioms K Agree , 4 Agree and 5 Agree , and rule of inference Nec Agree ). It is supposed that the agents in a coalition always agree on the contents of their agreements and on the contents of their disagreements (Axioms 4 Agree and 5 Agree ). That is, if the agents in I agree (resp. do not agree) that ϕ should be true then, they agree that they agree (resp. do not agree) that ϕ should be true.

We add a specific principle for individual preferences by supposing that an agent cannot have contradictory preferences (Axiom D Pref ).

Axiom Subgroup Agree is about the relationship between the agreements of a group and the agreements of its subgroups. The agents of a group I agree that ϕ should be true only if there is no subgroup J of I such that J agree that ϕ should be false. A specific instance of Axiom Subgroup Agree is Agree I (ϕ → Sat i ϕ) if i ∈ I. This means that the agents of a group I agree that ϕ should be true only if ϕ is satisfactory for every agent in I. A more detailed explanation of the logical consequences of Axiom Subgroup Agree is given in Section 5.

Axiom Int1 Pref,Do and Axiom Int2 Pref,Do are general principles of intentionality describing the relationship between an agent's action, his preferences, and the agreements of the group to which the agent belongs. According to Axiom Int1 Pref,Do , if agent i prefers that he performs action δ i (δ i occurs in all states that are preferred by agent i) then agent i starts to perform action δ i . A similar principle for the relationship between individual intentions and action occurrences has been studied in [START_REF] Lorini | A logic of intention and attempt[END_REF]. According to Axiom Int2 Pref,Do , if an agent i starts to perform a certain action δ i then it means that either agents i prefers to perform this action or there exists some group I to which agent i belongs such that the agents in I agree that i should perform action δ i . In other terms, an agent i's action δ i is intentional in a general sense: either it is driven by i's intention to perform action δ i or it is driven by the collective intention that i performs action δ i of a group I to which agent i belongs.

We call SAL the logic axiomatized by the axioms and rules of inference presented above. We write SAL ϕ if formula ϕ is a theorem of SAL (i.e. ϕ is the derivable from the axioms and rules of inference of the logic SAL). We write |= SAL ϕ if ϕ is valid in all SAL-models, i.e. M, w |= ϕ for every SAL-model M and world w in M . Finally, we say that ϕ is satisfiable if there exists a SAL-model M and world w in M such that M, w |= ϕ. We can prove that the logic SAL is sound and complete with respect to the class of SAL-frames. Namely: Theorem 1 SAL is determined by the class of SAL-frames.

Proof. It is a routine task to check that the axioms of the logic SAL correspond one-toone to their semantic counterparts on the frames. In particular, Axioms 4 Agree and 5 Agree correspond to the transitivity and Euclideanity of every relation A I . Axiom D Pref corresponds to the seriality of every relation A {i} (constraint S3). Axiom Alt Do corresponds to the semantic constraint S1. Axiom Single corresponds to the semantic constraint S2. Axiom Subgroup Agree corresponds to the semantic constraint S4. Axiom Int1 Pref,Do corresponds to the semantic constraint S5. Int2 Pref,Do corresponds to the semantic constraint S6.

It is routine, too, to check that all of our axioms are in the Sahlqvist class. This means that the axioms are all expressible as first-order conditions on frames and that they are complete with respect to the defined frames classes, cf. [2, Th. 2.42].

Discussion

One might wonder why we did not include a principle of monotonicity of the form Agree I ϕ → Agree J ϕ for J ⊆ I in our logic of agreement: for every sets of agents I and J such that J ⊆ I, if the agents in I agree that ϕ should be true then the agents in the subgroup J agree that ϕ should be true as well. We did not do include this principle because we think that it is not sufficiently general to be applied in all situations. Indeed, a minority group J of a larger group I might exist which does not have the same view than the larger group. For example, imagine I is the group of members of a political party who are choosing the leader of the party for the next years. All agents in I agree that a certain member of the party called Mr. Brown should be the leader for the next years. This is the official position of the party. At the same time, a small minority of I in conspiracy agree that Mr. Black should be the leader.

Consider now the following principle Agree I (ϕ → i∈I Pref i ϕ) and even the weaker Agree I (ϕ → i∈I Pref i ϕ): every group of agents I agree that ϕ should be true only if all of them prefer ϕ, and every group of agents I agree that ϕ should be true only if some of them prefers ϕ. These two principles are also too strong. Indeed, the agents in a group I might agree that ϕ should be true, without claiming that ϕ must be preferred by every agent in I and without claiming that ϕ must be preferred by some agent in I. For example, the members of a community I might agree that taxes should be payed by every agent in I without claiming and agreeing that tax payment must be preferred by every agent in I, and without claiming and agreeing that tax payment must be preferred by some agent in I. The members of the community just agree that tax payment must be something preferable by the whole community.

Finally, let us explain why we did not include stronger versions of Axiom Int1 Pref,Do and Axiom Int2 Pref,Do of the form Agree I Do δ I → Do δ I and Do δ I → Agree I Do δ I in the axiomatization of our logic SAL for every I ∈ 2 AGT * . On the one hand Agree I Do δ I → Do δ I is too strong because autonomous agents should be capable to violate norms and to decide not to conform to agreements with other agents (see Section 7). For example, agents might agree at the public level that each of them should pay taxes (i.e. Agree {1,...,n} Do 1:payTaxes,...,n:payTaxes ) but, in private, some of them does not pay taxes (i.e. ¬Do 1:payTaxes,...,n:payTaxes ). On the other hand, Do δ I → Agree I Do δ I is too strong because there are situations in which the agents in a set I perform a joint action δ I without agreeing that such a joint action should be performed. Each agent in I is doing his part in δ I without caring what the other agents in I do. For example, i might be cooking while j is reading a book without reciprocally caring what the other does, and without agreeing that the action of cooking performed by i and the action of reading performed by j should occur together. One might say that i and j do not have interdependent reasons for jointly preferring that i cooks while j reads a book.

Some SAL-theorems

Let us now discuss some SAL-theorems. The first group of theorems present some generalizations of Axioms Alt Do and Single for joint actions of groups.

Proposition 1. For every I, J ∈ 2 AGT * and δ I , δ I , δ J such that δ I = δ I :

SAL Do δ I ϕ → ¬Do δ J ¬ϕ (1a) SAL Do δ I → ¬Do δ I (1b)
According to Theorem 1a, if group I is going to perform the joint action δ I and ϕ will be true afterwards, then it cannot be the case that group J is going to perform the joint action δ J and ϕ is going to be false afterwards. According to Theorem 1b, every group of agents can never perform more than one joint action at a time.

The second group of theorems present some interesting properties of agreement. Theorems 2a and 2b are derivable from Axioms 4 Agree , 5 Agree and D Pref . According to these two theorems, the agents in I agree (resp. do not agree) that ϕ if and only if they agree that they agree (resp. do not agree) that ϕ. According to Theorem 2c, a group of agents I can intend to perform at most one joint action. Theorem 2d expresses a unanimity principle for agreement: for every set of agents I, the agents in I agree that if each of them prefers ϕ then ϕ should be the case. Theorem 2e expresses an interesting property about coalition formation and coalition disintegration: if the agents in I agree that a minority part J of I agrees that ϕ and another minority part J of I agrees that ¬ϕ, then the agents in I do not form a coalition (i.e. I is not a constituted group).

Proposition 2. For every I, J, J ∈ 2 AGT * and δ I , δ I such that δ I = δ I and J, J ⊆ I:

SAL Agree I ϕ ↔ Agree I Agree I ϕ (2a) SAL ¬Agree I ϕ ↔ Agree I ¬Agree I ϕ (2b) SAL Agree I Do δ I → ¬Agree I Do δ I (2c) SAL Agree I ( i∈I Pref i ϕ → ϕ) (2d) SAL Agree I (Agree J ϕ ∧ Agree J ¬ϕ) → ¬Group(I) (2e)
At the current stage, our logic does not allow to deal with situations in which I is a constituted group, the agents I agree about a certain fact ϕ and, at the same time, they agree that some agents in I prefer ¬ϕ. Formally, by Theorem 2e and Axiom 4 Agree , we can prove that formula Agree I ϕ ∧ Agree I Pref i ¬ϕ implies ¬Group(I), if i ∈ I. This means that at the current stage our logic SAL does not allow to handle collective decisions based on special procedures like majority voting in which certain agents might find a collective agreement about something while agreeing that it is not based on unanimous preferences. For example, the agents in I might be the members of the Parliament of a certain country and form a coalition (i.e. Group(I)). They might collectively decide by majority voting to declare war upon another country (i.e. Agree I war ), although they agree that there is a (pacifist) minority i, j ∈ I preferring that war is not declared upon another country (i.e. Agree I (Pref i ¬war ∧ Pref j ¬war )). Although we are aware that this is a limitation of our proposal, we think that our logic of agreement is still sufficiently general to model informal and non-structured groups in which there are no special voting procedures nor special roles (e.g. legislators, officials of the law, etc.) which are responsible for agreement creation. In fact, in such a kind of groups agreements are often about solutions to coordination (or cooperation) problems which are satisfactory for all agents in the group (e.g. some agents find an agreement to have dinner together at a Japanese restaurant rather than at an Indian restaurant).

Reaching an agreement on what to do together

We can provide in our logic SAL the formal specification of some additional principles explaining how some agents might reach an agreement on what to do together starting from their individual preferences. We do not intend to add these principles to the axiomatization of SAL presented in Section 3.3. We just show that SAL is sufficiently expressive to capture them both syntactically and semantically so that the can be easily integrated into our formal framework. The principles we intend to characterize are specified in terms of agreements about the conditions under which a certain joint action should be performed.

In certain circumstances, it is plausible to suppose that a group of agents I agree that if there exists a unique satisfactory joint action δ I for all agents in I, then such a joint action should occur. In other terms, the agents in a group I agree on the validity of the following general principle: 'Do together the joint action δ I , if it is the only joint action that satisfies every agent in I!'. This criteria is often adopted by groups of agents in order to find cooperative solutions which are satisfactory for all them. For example, in a Prisoner Dilemma scenario with two agents i and j the joint action i:cooperate,j:cooperate is the only satisfactory solution for both agents. If the two agents i and j agree on the previous principle and face a PD game, then they will agree that i:cooperate,j:cooperate is the joint action that they should perform. The previous principle of agreement creation is formally expressed in our logic as follows. For every I ∈ 2 AGT * and δ I ∈ JACT I :

Agree I ((Sat I Do δ I ∧ δ I =δ I ¬Sat I Do δ I ) → Do δ I ) (*)
Principle * corresponds to the following semantic constraint over SAL-frames. For every w ∈ W , I ∈ 2 AGT * and δ I ∈ JACT I :

S6

if w ∈ A I (w) and A {i} • R δ I (w ) = ∅ for all i ∈ I and, for all δ I = δ I there exists i ∈ I such that

A {i} • R δ I (w ) = ∅ then, R δ I (w ) = ∅ where A {i} • R δ I (w ) is defined as {R δ I (v) | v ∈ S i (w )}.
If we suppose that the Principle * is valid then the following consequence is derivable for every I ∈ 2 AGT * and δ I ∈ JACT I :

(3)

Agree I (Sat I Do δ I ∧ δ I =δ I ¬Sat I Do δ I ) → Agree I Do δ I REMARK.
Note that in the previous Principles * and 3 of agreement creation mutual trust between the agents in the group is implicitly supposed, that is, it is supposed that every agent i in I thinks it possible that the other agents in I will do their parts in the joint action δ I . Indeed, trust between the members of the group is a necessary condition for agreement creation (on this point, see [START_REF] Andrighetto | A convention or (tacit) agreement between us[END_REF] for instance). We postpone to future work a formal analysis of the relationships between trust and agreement. To this aim, we will have to extend our logic SAL with doxastic modalities to express agents' beliefs.

Example 1. Imagine a situation of exchange of goods in EBay between two agents i and j. Agent i is the buyer and agent j is the seller. They have to perform a one-shot trade transaction. We suppose AGT = {i, j}. Agent i has the following two actions available: pay and skip (do nothing). Agent j has the following two actions available: send and skip (do nothing). That is, ∆ i = {i:send , i:skip} and ∆ j = {j:pay, j:skip}. Therefore, the set of possible joint actions of the two agents is JACT = { i:skip, j:skip , i:send , j:skip , i:skip, j:pay , i:send , j:pay }. The two agents i and j agree that the situation in which i sends the product and j pays is satisfactory for both of them.

(A) Agree {i,j} Sat {i,j} Do i:send,j:pay .

Moreover, agent i and agent j agree that the situation in which i does nothing and j pays the product, the situation in which i sends the product and j does not nothing, and the situation in which i and j do nothing, always leave one of them unhappy. Thus we have that agent i and agent j agree that there is no other situation different from i:send , j:pay that is a satisfactory situation for both of them: (B) Agree {i,j} δ {i,j} = i:send,j:pay ¬Sat {i,j} Do δ I .

From items A and B, by using Principle 3, we infer that agent i and agent j agree that they should perform the joint action i:send , j:pay : (C) Agree {i,j} Do i:send,j:pay .

Other conditions under which the agents in a group can reach an agreement on what to do together could be studied in our logical framework. For instance, one might want to have general principles of the following form which can be used to find a solution in coordination problems. Suppose that δ I and δ I are both satisfactory joint actions for all agents in group I. Moreover, there are no joint actions δ I different from δ I and δ I which are satisfactory for all agents in I. Then, either the agents in I agree that δ I should be performed or they agree that δ I should be performed. In other terms, if the agents in a group I face a coordination problem then they strive to find a solution to this problem.

Grounding norms and commitments on agreements

The logic of agreement SAL presented in the previous section provides not only a formal framework in which the relationships between individual preferences of agents in a group and group agreements can be studied, but also it suggests a different perspective on concepts traditionally studied in the field of deontic logic.

Consider for instance deontic statements of the following form "within the context of group I it is required that agent i will perform action δ i " or "within the context of group I it is required that agent i will perform his part in the joint action δ I together with the other agents in I". These statements just say that i has a directed obligation towards his group I to do a certain action as part of a joint plan of the group I (see e.g. [START_REF] Kanger | Rights and parliamentarism[END_REF][START_REF] Lindahl | Stig Kanger's theory of rights[END_REF] for a different perspective on directed obligations). By way of example, imagine the situation in which agent i and agent j are trying to organize a party together. After a brief negotiation, they conclude that i will prepare the cake, while j will buy drinks for the party. In this situation, "within the context of group {i, j} it is required that agent i will prepare the cake for the party and it is required that agent j will buy drinks for the party". The following abbreviation expresses the classical deontic notion of directed obligation in terms of the concept of agreement. For every I ∈ 2 AGT * , i ∈ I and δ i ∈ ∆ i :

Oblig i (δ i ,I) def = Agree I Do δi . Formula Oblig i (δ i ,I) has to be read 'within the context of group I it is required that agent i will perform action δ i '. 6 It is to be noted that the notion of directed obligation represents an essential constituent of the notion of social commitment. Thus, in our approach, an essential aspect of an agent i's commitment with respect to his group I to do a certain action δ i is the fact that all agents in I agree that i should perform action δ i . Since all agents in the group I agree on this, they are entitled to require agent i to perform this action. Moving beyond the notion of directed obligation as an essential constituent of social commitment, our logic SAL can be used to provide a a formal characterization of the notion of mutual (directed) obligation in a group I, as 'every agent in I is required to perform his part in a joint action δ I of the group'. Formally, for every I ∈ 2 AGT * and δ I ∈ JACT I :

MutualObg I (δ I ) def =
i∈I Oblig i (δ i ,I). Formula MutualObg I (δ I ), which is equivalent to Agree I Do δ I , has to be read 'the agents in the group I are mutually obliged to perform their parts in the joint action δ I '. This notion of mutual (directed) obligation is an essential constituent of the notion of mutual (social) commitment. As already emphasized in Section 4, in our logic agents can violate obligations assigned to them (breaking their social commitments). Violation of a directed obligation is expressed in our logic by the construction Oblig i (δ i ,I) ∧ ¬Do δi : within the context of group I it is required that agent i will perform action δ i , but agent i does not perform action δ i . The discussion on the notion of commitment will be extended in Section 8 where our approach will be compared with some formal approaches to agreement recently proposed in the MAS area.

Related work

The literature on agents, organizations, agreements is too vast to be given an exhaustive overview here: let us provide pointers to some significant works that relate to our effort or that are set against it in a way that stimulates discussion. We take inspiration from Garcia et al. [START_REF] Garcia | Issues for organizational multiagent systems development[END_REF] to determine the dimensions along which multi-agent organizational concepts are developed: structural, functional, dynamic, and normative.

From a conceptual perspective, the formalization of agreements comes before any structural consideration. As an example, Dignum et al. [START_REF] Dignum | Open agent systems???[END_REF] propose an attempt to describe minimum requirements for agents to be organized into an institution. The minimum requirements rely on an existing institution designed with the ISLANDER tool [START_REF] Esteva | Islander: an electronic institutions editor[END_REF], and call for a middle agent. ISLANDER is probably the most complete tool to date for the specification of institutions in terms of roles and scenes. The tool is kept as general as possible to allow for the widest possible variety of definable institutions. Nevertheless, the specification of an institution is entirely performed by a human designer, and agents join an institution by assuming one or more roles, with no account of the process by which individuals look for and reach agreements that give rise to an institution. Thus, the platform is an effective means to translate an existing institution into a MAS, but the automatization of the creation of organizations is out of scope.

With respect to the functional dimension of organizations, that is, their goals and how to achieve them, we adopt the conceptual distinction drawn by Griffiths and Luck [12] between teamwork and coalition formation. The former is seen as focused on task assignment and action coordination among agents in the short term, whereas the latter is said to be dealing with the establishment in the long term of a group of agents with a common aim or goal. Although agreeing with the authors in viewing multi-agent organizations as a means to achieve long-termed objectives and in considering trust as a key concept for an organization that influences an agent's decisions on undertaking cooperations, our focus is slightly different in the context of this research: we consider an organization to be born when an agreement is made, so our efforts are on the formalization of agreements. An investigation on the relationship between trust and agreements lies ahead in our research path. Nevertheless, we share the authors' aim to determine the basic principles that lead to the creation of organizations, as opposed to several coalition formation research works optimizing match-making algorithms between a set of tasks and a set of agent capabilities (e.g.: [START_REF] Shehory | Multi-agent coordination through coalition formation[END_REF]).

We can consider dynamic and normative dimensions as intrinsic to any attempt to formalize a concept like a multi-agent organization. Dynamic aspects include the formation and the evolution of coalitions of agents and, on a smaller scale, the preconditions and the consequences of an agent's action. When these conditions deal with deontic concepts the MAS is characterized also by a normative dimension. An important question is which normative concept or set of concepts to choose as the fundamental basis for the formalization of organizations. Dignum et al., for instance, choose violation as a fundamental concept to define deadlines in a MAS [START_REF] Dignum | Meeting the deadline: Why, when and how[END_REF]. Violation is surely a very important concept in any normative context, and especially in those where deadlines are the central focus. Nevertheless, we argue that it does not play a primary role when one wants to deal with a more general overview of organizations, especially electronic ones. As pointed out by Cardoso et al. [START_REF] Cardoso | Supporting virtual organizations through electronic institutions and normative multi-agent system[END_REF], while in real life a coercive action is eventually enforced against individuals not able or willing to abide by a sanction deriving by some misdemeanor, such coercions are not (yet?) implementable in a distributed information system, so that effectiveness of violations and relevant sanctions is somehow diminished. Boella and van der Torre [START_REF] Boella | Contracts as legal institutions in organizations of autonomous agents[END_REF] propose contracts, defined as a special type of beliefs ascribed to a group of agents, as a foundational means for the creation of legal institutions. We follow a similar approach, but consider agreement as a more basic concept that precedes contracts.

In [START_REF] Wan | Formalizing and achieving multiparty agreements via commitments[END_REF] a formal approach to multiparty agreement between agents is proposed based on the notion of social commitment: A multiparty agreement among the agents in {1, . . . , n} is given by a set of commitments {C 1 , . . . , C n } where C i the commitment that agent i has towards the other agents. In this approach the notion of commitment is taken as a primitive concept and the notion of agreement is built on it, which we counter by starting from a primitive notion of agreement in a group I (which depends on the individual preferences of the agents in I), on the top of which we built a notion of directed obligation, the essential constituent of the notion of social commitment. The logic of agreement SAL has some similarities with the logical framework based on the concept of acceptance we presented in [START_REF] Lorini | The logic of acceptance: Grounding institutions on agents' attitudes[END_REF] and [START_REF] Gaudou | Anchoring institutions in agents' attitudes: Towards a logical framework for autonomous mas[END_REF], in which a logical analysis of the relationships between the rules and norms of an institution and the acceptances of these rules and norms by the members of the institution has been provided. However, these works do not analyze the relationships between individual preferences of agents and collective acceptances (or agreements) which we presented in this paper.

Conclusions

This work is a starting point of a long enterprise. Our long-term aim is to provide a formal specification of all the basic notions that characterize organizations in general, including those in the real world, and we started with what we consider to be a fundamental concept: agreement. The formalization of this concept with a logical approach aims at analyzing in detail both its static characteristics and its dynamic properties, that is, what is meant by the term agreement and how it is supposed to influence agents' behavior when cooperation is the common goal. Once a model is universally established which is formal and general enough to abstract from particular types of organizations or specific operational details, such a model may be used as a sound basis for an agentbased implementation that can really have a significant impact on economic or social scientific contexts. The relations between our formalization of agreement and the notions of norms and commitments have been investigated in this work, but other dimensions of multi-agent interaction, such as trust, are still to be tackled, which is what we intend to pursue in the future.

A relation Ri:α is deterministic iff, if (w, w ) ∈ Ri:α and (w, w ) ∈ Ri:α then w = w .

A relation AI is transitive iff for every w ∈ W , if (w, w ) ∈ AI and (w , w ) ∈ AI then (w, w ) ∈ AI .

A relation AI is Euclidean iff for every w ∈ W , if (w, w ) ∈ AI and (w, w ) ∈ AI then (w , w ) ∈ AI .

Note that Oblig i (δi,I) captures a specific notion of obligation based on agreement. We are aware that other forms of obligations exist in social life like legal obligations or moral obligations (an agent may feel obliged to do something for his own moral reasons).

Acknowledgements

Emiliano Lorini is supported by the project ForTrust "Social trust analysis and formalization" ANR-06-SETI-006 financed by the French ANR.


Aji A Anappara

Simone De Liberato

Alessandro Tredicucci
email: a.tredicucci@sns.it

Cristiano Ciuti

Giorgio Biasiol

Lucia Sorba

Fabio Beltram

J M Raimond

M Brune

Rev. Mod. Phys S Haroche

Light-matter excitations in the ultra-strong coupling regime

Keywords: numbers: 71.36.+c, 78.67.De, 42.50.Pq, 73.21.Fg

In a microcavity, light-matter coupling is quantified by the vacuum Rabi frequency ΩR. When ΩR is larger than radiative and non-radiative loss rates, the system eigenstates (polaritons) are linear superposition of photonic and electronic excitations, a condition actively investigated in diverse physical implementations. Recently, a quantum electrodynamic regime (ultra-strong coupling) was predicted when ΩR becomes comparable to the transition frequency. Here we report unambiguous signatures of this regime in a quantum-well intersubband microcavity. Measuring the cavity-polariton dispersion in a room-temperature linear optical experiment, we directly observe the anti-resonant light-matter coupling and the photon-energy renormalization of the vacuum field.

The strong-coupling regime between a dipole-allowed electronic transition and the photonic mode of a microcavity manifests itself in the lifting of the degeneracy between the two modes, with an anti-crossing behaviour of the new polariton eigenstates, separated by an energy termed vacuum-Rabi splitting (VRS) in atomic physics [1], or cavity-polariton splitting in solid-state systems [2]. This regime is actively investigated in many research fields, such as ultracold atoms in optical cavities [3], Cooper-pair boxes in microwave resonators [4], excitonic transitions in semiconductor microcavities [5] and surface-plasmon resonators [6].

The magnitude of light-matter coupling in atomic systems is limited by the intrinsically small dipole moment of the transitions. Typical values for a single atom are Ω R ≈ 10 -7 -10 -6 ω 12 , ω 12 being the transition frequency [1]. Circuit quantum electrodynamics in superconducting systems, instead, can generally produce much larger Ω R /ω 12 ratios, of the order of few percent [4]. Even larger values are possible using intersubband transitions between two-dimensional electronic states within the conduction band of semiconductor heterostructures [7].

With increasing Ω R /ω 12 , terms of the interaction Hamiltonian that are otherwise negligible become more and more relevant. This leads to profound modifications in the very nature of the quantum states of the system. These changes stem from the renormalization of the electromagnetic field and non-resonant contributions, effects one intuitively associates only to strongly-driven systems and not to vacuum-field interaction. The energy of the excitations is affected and a new squeezed ground state is defined containing a finite non-zero number of virtual photons. Theoretical investigations reveal that these vir-tual photons can be released in correlated pairs by nonadiabatic manipulation of the light-matter coupling, a phenomenon reminiscent of the dynamical Casimir effect [8,9]. These peculiar phenomena prompted researchers to coin the term ultra-strong coupling to identify this condition.

In this report we demonstrate a semiconductor microcavity displaying unambiguous signatures of the ultrastrong coupling regime of light-matter interaction, even at room temperature. The structure is based on intersubband transitions, which, beyond the large coupling strength, also offer ample possibilities for its external control [10,11].

Intersubband transitions involve levels originating from the quantum-mechanical confinement of charge carriers in one direction. Energy, carrier density, and matrix elements are the relevant parameters of the resonance, and can be tailored through structural design. The strong coupling with the electromagnetic mode of a planar semiconductor resonator, and the corresponding formation of intersubband polaritons, was observed in GaAs/AlGaAs [10,12] and InAs/AlSb [13] material systems, up to room temperature. These solid-state systems can be grown by mature epitaxial growth techniques such as molecular beam epitaxy (MBE) and represent optimal candidates to realize the ultra-strong coupling regime of light-matter interaction.

The Hamiltonian of the intersubband microcavity can be written using a bosonic approximation, since the excitation density of the transition (intersubband excitations per unit area of the sample) is very small compared to the density of the two-dimensional electron gas [8]. The Hopfield-like Hamiltonian then takes the form:

H = H res + H dia + H anti-res .
(1)

It consists of three qualitatively different contributions that correspond to the three main terms of the electro-magnetic interaction. H res is given by:

H res = h k ω cav (k) a † k a k + 1 2 + ω 12 b † k b k + iΩ R,k a † k b k -a k b † k , (2)
where a † k (a k ) is the creation (annihilation) operator for the fundamental cavity-photon mode with in-plane wavevector k and frequency ω cav (k), Ω R,k is the kdependent Rabi coupling frequency, and b † k (b k ) is the creation (annihilation) operator of the bright intersubbandexcitation mode of the doped multiple quantum well structure. H res describes the energy of the bare cavity photon, the intersubband polarization field, and the resonant part of the light-matter interaction (corresponding to the creation / annihilation of one photon with the concomitant annihilation / creation of an intersubband excitation with the same in-plane wavevector).

The middle contribution in Eq. ( 1) contains the dia-magnetic term (proportional to the square of the vector potential A) and gives a renormalization of the photon energy due to the interaction with matter:

H dia = h k D k a † k a k + a k a † k , (3)
where, for a quantum well, the diamagnetic coupling constant D k is approximately given by [8]. The last contribution in Eq. ( 1) is represented by the so-called anti-resonant terms, corresponding to the simultaneous creation and annihilation of two excitations with opposite in-plane wavevectors:

D k ≈ Ω 2 R,k /ω 12
H anti-res = h k iΩ R,k a k b -k -a † k b † -k + D k a k a -k + a † k a † -k . (4)
Matrix elements of Eq. ( 4) are non-zero only when coupling states with different total number of cavity photons and intersubband excitations. This term is suppressed in first order perturbation theory. Neglecting H anti-res , the Hamiltonian (1) commutes with the boson number and can be block-diagonalized in a finite dimension subspace. This kind of approximation is the keystone of all analytical results in the field of light-matter interaction, and is usually known as rotating wave approximation (RWA) [14]. Normally, it is violated only in the case of dressed states in strongly driven systems with a large number of photons; experimental evidence stemming from the observation of energy shifts or forbidden transitions [14,15].

The H dia and H anti-res contributions to the interaction with the vacuum-field have long been elusive, owing to the fact that the process involves states with zero photon number, and, as such, these terms are usually negligible. Yet they represent the hallmark of the ultrastrong-coupling regime and are at the origin of the peculiar quantum nature of the states. A simple spectroscopic identification (e.g. based on the excitation energies) would be impossible in most microcavity systems.

On the other hand, the situation of intersubband microcavities, which use a planar geometry with a resonator designed to operate at oblique incidence, is quite special. Measurements at large angles, in fact, highlight energy deviations of the polariton dispersion, which can easily become of the order of several percent (see Fig. 1). Furthermore the dispersion of the uncoupled modes can be separately measured to allow a fair comparison with theoretical models.

Optical confinement in the microcavity used in this investigation is based at the bottom end on the totalinternal reflection from a low refractive-index cladding and at the top on the reflection from a semiconductormetal interface (Fig. 2). The heterostructure was grown by solid-source MBE on an undoped GaAs (001) substrate [16]. The cladding region was realized by sandwiching a 1.65 µm AlAs layer between two GaAs layers doped to 5 × 10 18 cm -3 , each having a thickness of 150 nm. The active region consists of 70 repeats of ndoped 6.5 nm thick GaAs quantum wells separated by 8 nm thick Al 0.35 Ga 0.65 As barriers. Layer thickness was chosen so as to have only two bound subbands and ensure quantum de-coupling of adjacent wells. Doping level (3.25 × 10 12 cm -2 in each well) leads to population of the ground state only and to a single intersubband transition. Light was coupled into the microcavity through the substrate, and the cavity throughput was probed by angle-resolved reflectance measurements. The experimental geometry is detailed in Fig. 2: the sample was mechanically lapped into a wedge-shaped prism with the polished facets at an angle of 70 • with respect to the cavity plane. The prism was mounted inside a Fouriertransform infrared spectrometer (FTIR), equipped with a cooled HgCdTe detector. A metallic wire-grid polarizer was inserted in the optical path to select the TM polarization of the probe beam. By manually rotating the sample holder, the angle between the infrared beam and the prism facet could be varied, enabling us to change the incident angle (θ int ) on the cavity surface around the central value of 70 • defined by the prism shape. In the bottom panels of Fig. 3 are visible the angle-resolved peaks of the TM reflectance spectra for lower (b) and upper (c) polaritons in the frequency range of the intersubband transition as function of θ int . The spectra were collected at room temperature, with a resolution of 0.25 meV. The minimum splitting between the polariton dips is about 90 meV, ∼ 59 % of the transition energy, although a precise anti-crossing point cannot be defined, this stems from the fact that polariton peaks at the same internal angle do not correspond to the same k [17].

The bare intersubband-transition energy of the active region was measured in another wedge shaped prism, pol- ished at 45 • angle. The reflectance spectrum was collected at an internal angle of about 37 • , which excluded any cavity-induced shift of the intersubband absorption. The recorded transition energy is 152 meV, with a full width at half maximum (FWHM) of about 12 meV [16].

Since the bottom mirror utilizes total internal reflection, one cannot determine precisely the cavity resonance energy through measurements at zero incidence angle, where the intersubband transition does not couple to the radiation. We decided then to use a second sample, identical in the growth sequence, but without any doping in the active region in order to determine the energy dispersion of the cavity mode. The shift of the cavity refractive index induced by the absence of doping in the quantum wells was computed to be at most ∼ 1 %, owing to the FIG. 3: Panel (a): root mean square deviation from measured dispersion of the calculated polariton energies as a function of the vacuum Rabi energy, the only fitting parameter. The red curve refers to the case of no Hanti-res terms, while the blue to the case without both H dia and Hanti-res contributions. The black line is for the full Hamiltonian. Bottom panels: angular dispersions of the lower (b) and upper (c) polaritons in the three cases (full Hamiltonian for the black solid line, without Hanti-res for the dashed red line and without both H dia and Hanti-res for the dash-dotted blue line), compared to experimental data (black crosses). The ΩR used are the ones that minimize the root mean square deviation in the panel (a).

TM polarization of the light and large propagation angle. The quality of the growth and the thickness difference between the two samples were checked using X-ray diffraction (XRD). No deviations were found within the XRD resolution of less than one percent [16]. The reference sample was also wedged at an angle of 70 • and the cavity dispersion determined from angle-resolved reflectance measurements [16]. Scanning electron microscope (SEM) images of the cleaved facets of the two wedge-shaped samples were recorded to check the angular difference between the mechanically polished facets [16]. The deviation between the two samples was about 0.1 • , which does not cause a significant shift of the polariton peaks.

Having determined experimentally the intersubband transition energy and the angle-dependent cavity mode frequency, we can fit the data with the polariton dispersions calculated respectively using the full Hamiltonian of Eq. 1, the Hamiltonian without the anti-resonant terms, and the Hamiltonian in Eq. 2, that is the Hamiltonian without both the anti-resonant terms and the diamagnetic terms. The only free fitting parameter in the three cases is the vacuum Rabi energy hΩ R . We calculated the root mean square deviation from the experimental data in the three cases and thus found the respective optimal fitting vacuum Rabi energies. Our analysis shows that only using the full Hamiltonian of Eq. 1, including both antiresonant terms and diamagnetic terms, it is possible to have a good fit.

In order to prove that our intersubband microcavity is indeed in the ultra-strong coupling regime, in the panel (a) of Fig. 3 we plotted the root mean square deviation from the measured dispersion of the full Hamiltonian in Eq. 1 (solid black line), the Hamiltonian without the anti-resonant terms (red dashed line) and the Hamiltonian without both the anti-resonant terms and the dimagnetic terms (blue dash-dotted line). For the full Hamiltonian a perfect agreement is found for a vacuum Rabi energy hΩ R = hΩ R,kres = 16.5 meV ∼ 11 % of the intersubband transition energy, with a fit RMS error of only 0.9 meV. For the other two lines the agreement is much worser, with a minimum error of 4.0 and 7.2 meV respectively, well beyond the experimental resolution. These minima occurs at hΩ R,kres = 16.5 meV and 14.5 meV respectively. In the bottom panels of Fig. 3 the optimal angular dispersions are plotted in the three cases and compared with the experimental values (black crosses).

Note that, as discussed in [17], the actual value of the vacuum Rabi energy is much smaller than half the splitting observed in the spectra, owing to the fact that the two polariton energies, once measured at the same angle, do not correspond to the same k.

These data provide a clear demonstration that antiresonant light-matter coupling and photon-energy renormalization can become very significant even in the interaction with the vacuum electromagnetic field of a microcavity. These anomalous contributions represent unambiguous evidence that the optoelectronic coupling is in the ultrastrong regime. We believe the results show that intersubband transitions will play a key role for the development of a new quantum-optics field, thanks also to the possibility of manipulating coupling by controlling the charge density. Additionally, the fact that these phenomena can be observed at room temperature and in solid-state structures is a crucial aspect for novel device implementations.

This work was supported in part by the EC Research and Training Network POISE. We thank I. Carusotto for useful discussions.

12 FIG. 1 :

 121 FIG.1: Difference from the full-Hamiltonian eigenvalues of the polariton energies calculated either without the Hanti-res term (red) or without both Hanti-res and H dia (blue) plotted as a function of coupling strength (solid and dashed lines refer to the lower and upper polariton branch, respectively). This calculation was performed considering a fixed resonant angle of 60 • . As one can see, deviations amount to ∼ 5 % already for ΩR/ω12 ∼ 0.1.

FIG. 2 :

 2 FIG. 2: Scheme of the experimental set-up employed for the angle-resolved reflectance measurements. The prism-shaped sample is mounted on a copper block and can be rotated to vary the internal incidence angle. The blown up detail of the waveguide illustrates the working principle of the resonator. The band profile and squared moduli of the subband envelope functions of one of the quantum wells (calculated solving selfconsistently the Poisson-Schrödinger equation) are shown in the top left diagram.

FIG. 4 :FIG. 5 :FIG. 7 :

 457 FIG.4: Supplementary material. Layer sequence of the intersubband microcavity structure


Pierre Humbert

Laurent Oudre

Clément Dubost

Learning spatial filters from EEG signals with Graph Signal Processing methods

In this paper, we propose to learn a spatial filter directly from Electroencephalography (EEG) signals using graph signal processing tools. We combine a graph learning algorithm with a high-pass graph filter to remove spatially large signals from the raw data. This approach increases topographical localization, and attenuates volume-conducted features. We empirically show that our method gives similar results that the surface Laplacian in the noiseless case while being more robust to noise or defective electrodes.

Clinical relevance-The proposed method is an alternative to the surface Laplacian filter that is commonly used for processing EEG signals. It could be used in cases where this standard approach does not provide satisfying results (low signal-to-noise ratios due to a low number of epochs, defective electrodes). This could be particularly interesting in case of an electrode defect, as it can happen in clinical practice.

I. INTRODUCTION

Electroencephalography (EEG) is commonly used to track the brain activity by measuring the scalp electrical potentials generated by cortical postsynaptic currents. However, the analysis of EEG data remains a major challenge. Indeed, because the spatial-temporal information is mixed at the source level, the signal recorded from each electrode reflects a complex combination of electrophysiological dynamics from multiple brain regions [START_REF] Cohen | Comparison of different spatial transformations applied to eeg data: a case study of error processing[END_REF]. To extract meaningful and physiologically interpretable patterns of activity from EEG signals, one standard approach consists of using filters (temporal and/or spatial) that will allow to highlight the phenomena of interest. Although there are several different types of temporal filters, most of the filters that are applied in cognitive electrophysiology (e.g., Morlet wavelet convolution, filter-Hilbert, and short-time FFT-based procedures such as Welch's method or multitapers) produce nearly identical results [START_REF] Cohen | Comparison of different spatial transformations applied to eeg data: a case study of error processing[END_REF]. This can be contrasted with spatial filters, the topic of this paper.

In EEG analysis, a spatial filter is a mathematical method that produces new values by taking weighted combinations of signals from other electrodes. As in temporal filtering, the purpose is to highlight features present in the raw data but difficult to observe without applying any transformations. One popular example of such filter is the surface Laplacian. The most common motivations for using the surface Laplacian are to increase topographical localization, to facilitate electrode-level connectivity analyses, and to attenuate volume-conducted features of the data. However, because the surface Laplacian is inherently computed from signal differences, it is very sensitive to noise [START_REF] Kayser | Issues and considerations for using the scalp surface laplacian in EEG/ERP research: a tutorial review[END_REF] e.g. if one electrode is defective, it would affect all the others surrounding in the filter's computation. Another concern is linked to the difficulty of computing the surface Laplacian at the edge of the EEG montage. Indeed, while an approximation, (usually referred to as Hjorth's approximation) [START_REF] Carvalhaes | The surface laplacian technique in EEG: theory and methods[END_REF] is used for central electrodes, we cannot compute it for estimates along the border of the electrode grid and in this case, a less accurate approximation has to be used.

To overcome these issues, one idea is to construct adaptive filters that will be able to model the irregular domain the signals are residing on. Thus, rather than considering that the neighbouring electrodes record similar signals, we quantify the similarity between electrodes based on their corresponding signals. Two electrodes that are not necessarily close in space could now be close in the resulting irregular domain. To define this domain, Graph Signal Processing (GSP) [START_REF] Shuman | The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains[END_REF] has emerged as a powerful alternative to standard approaches. In this formalism, a graph defines a support (the irregular domain), and signals, now called graph signals, are defined on this support. This allows to capture the structure on which a signal evolves, thus providing more information than considering the signal alone. By generalizing concepts and tools of signal processing to signals recorded over graphs, GSP has proven its success in many tasks such as reconstruction [START_REF] Chen | Signal recovery on graphs: variation minimization[END_REF], sampling [START_REF] Marques | Sampling of graph signals with successive local aggregations[END_REF], and filtering [START_REF] Sandryhaila | Discrete signal processing on graphs[END_REF].

In this paper, we show that it is possible to automatically learn a spatial filter from the raw signals. More specifically, using techniques from the GSP field, we first learn a graph on which the raw EEG signals are smooth and well-represented, a property known as bandlimitedness. Then, we removed the graph low-frequencies (i.e. the spatially large signals) present in the raw signals with a graph filter constructed from the learned graph. Results suggest that our method is more robust to defective electrodes than the surface Laplacian. Furthermore, the modularity of our framework allows to define multiple types of spatial filters which may pave the way to others possibilities of analysis.

II. BACKGROUND

a) Surface Laplacian: The proposed method is an alternative to the surface Laplacian, also commonly referred to as Current Source Density (CSD) or Scalp Current Density (SCD) [START_REF] Perrin | Scalp current density mapping: value and estimation from potential data[END_REF], [START_REF] Cohen | Comparison of different spatial transformations applied to eeg data: a case study of error processing[END_REF]. This is a spatial filter that is useful for attenuating volume conduction effects for better connectivity analyses. It is computed using the methods from [START_REF] Perrin | Spherical splines for scalp potential and current density mapping[END_REF]. The three parameters for the Laplacian are smoothing (lambda), Lagrange order (number of iterations when computing the Legendre polynomial), and spherical spline order (m).

b) Graph notations: Throughout the paper, let consider a weighted and undirected graph G = (V, E), where V is a set of N nodes and E is a set of edges. The combinatorial Laplacian matrix of this graph is a N by N matrix defined as L = D -W , where D is the degree matrix and W the weight matrix. Since G is an undirected graph, L is a symmetric and positive semi-definite matrix verifying L = XΛX T with Λ the diagonal matrix of non-negative eigenvalues of L and X the matrix of the corresponding eigenvectors as columns. Assuming that G has one connected component, L has λ 1 = 0 for first eigenvalue associated with the eigenvectors X :,1 = 1 N /

√

N with 1 N the unitary vector of size N . Care should be taken not to confuse the Laplacian matrix and the surface Laplacian in the following.

c) Graph Signal Processing: A graph signal is a function y : V → R N assigning a scalar value to each node of a graph G. This function can be represented as a vector y ∈ R N , where y i is the function value at the i-th node. The eigenvectors of the Laplacian of G provide a Fourier-like basis for graph signals, allowing to decompose any signal into its spectral components. From this formalism, the Graph Fourier Transform (GFT) of y is defined by h = X T y. A K-bandlimited graph signal is thus a signal for which h i = 0 in K entries [START_REF] Shuman | The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains[END_REF]. Finally, a smooth graph signal is a signal for which the quantity y T Ly is small.

III. PROPOSED METHOD

In our context, the input corresponds to multichannel EEG signals which can be represented by a matrix Y = [y 1 , . . . , y T ] in R P ×T , with P the number of channels and T the number of time points. Throughout this paper our goal is to learn the underlying structure of the channels in order to construct an adapted spatial filter. To do so, we consider a particular factor analysis model first introduced in [10]: ∀i, y i = z i + ε i where y i follows a N (0, L † + σI P ) with noise parameter σ ∈ R and pseudo-inverse † ; Here, L is the Laplacian of the spatial graph we want to learn. These assumptions implies that Y is smooth and (mutually) Kbandlimited under the spatial graph characterized by L. In matrix notation, this means that (i) tr(Y T LY) is small and (ii) there exist a set of indices K of size K such that H K,: = 0 where H has the same size as Y and corresponds to the spectral representation of the graph signals through the GFT. Note that, in our context, smoothness makes sense because of the volume conductivity which implies that electrodes tend to record very similar signals.

A. Denoising with graph learning

To learn L, we choose to minimize the following objective function:

min H,X,Λ Y -XH 2 F + α Λ 1/2 H 2 F + β H 2,1 , (1) s
.t.        X T X = I P , x 1 = 1 √ N 1 P , (a) (XΛX T ) k, ≤ 0 k = , (b) Λ = diag(0, λ 2 , . . . , λ P ) 0 , (c) tr(Λ) = N ∈ R + * , (d)
where I P is the identity matrix of size P , tr(•) denotes the trace of an input matrix, and Λ 0 indicates that the matrix Λ is semi-definite positive. This problem conjointly learns the Laplacian L (i.e. (X, Λ)) and a bandlimited smooth approximation XH of the true EEG signals Y -E. Finally, notice that X H is a filtered version of Y obtained with a non-linear low-pass filter adapted to the learned graph L. Hence, this approximation should have less noise than Y.

The solution of (1) can be computed using one of the two algorithms proposed in [START_REF] Bars | Learning Laplacian matrix from bandlimited graph signals[END_REF], [START_REF] Humbert | Learning Laplacian matrix from graph signals with sparse spectral representation[END_REF]. The first one solved the problem by combining barrier methods, alternating minimization, and manifold optimization. The second one is a relaxed algorithm which is more scalable with respect to the graph dimensions. In the following, we will use the relaxed algorithm.

B. High-pass graph filtering

From the learned Laplacian L, we can construct a spatial graph filter that will adapt to the structure of the recorded signals. Because of the volume conductivity problem, we need to remove parts of the signals which are common in all channels i.e. spatially broad features which are characterized by low frequencies on the learned graph. In the following, we will therefore design a high-pass graph filter. Formally, a graph filter is a linear operator acting on a graph signal by amplifying or attenuating parts of its spectrum [START_REF] Tremblay | Design of graph filters and filterbanks[END_REF]. Denoting this operator by F , a filtered graph signal y F is then obtained through y F = F y. Probably one of the most used low-pass graph filter is the one obtained via Tikhonov regularization. Given a scalar γ ≥ 0 and a graph signal y, the filtered signal y F is the solution of

y F = arg min s y -s 2 2 + γs T Ls . (2)
The left term asks for a signal to be close to the input y, while the second term enforces a smoothness prior. The solution has an explicit formulation given by y F =

I + γ L -1
y = F y with F the low-pass graph filter associated to [START_REF] Kayser | Issues and considerations for using the scalp surface laplacian in EEG/ERP research: a tutorial review[END_REF]. As this filter extracts the low frequencies of the input signal that we want to remove, we will use the residual ŷ = (y -y F ) as the high-pass version of our original signal. Note that, we filter the reconstruction X H instead of Y as it is consider closer to the true signals. The full process of our method is provided in Algorithm 1.

IV. RESULTS

Our approach is tested both on synthetic and real EEG data. All experiments are performed in Python using MNE [START_REF] Gramfort | MEG and EEG data analysis with MNE-Python[END_REF]. Code is available online. A. Experimental setup a) Synthetic data: We simulate 60 EEG signals with sampling frequency of 600 Hz for 5 phase-locked epochs of 150 points (250 ms) as follows. First, we define a dipole time series consisting of a sine wave at 18 Hz with a peak amplitude of 10 nAm (signal at the cortical level). This dipole is activated in a region located at the bottom left of the brain (i.e. cortical areas around superior temporal sulcus). To obtain simulated sensor data we project the time series onto 60 virtual EEG electrodes arranged according to the 10-20 system (forward problem). Reference is set to average. Finally, we add a multivariate Gaussian noise. We repeat these operations 10 times and for 10 different amount of noise in order to have a Signal to Noise Ratio (SNR) between 10 and 60. We therefore obtain 10 average the 99 epochs to obtain the approximated ERP. The proposed method is compared to the surface Laplacian with smoothing parameter, Lagrange order, and spherical spline order respectively set to 10 5 , 10, and 4. The smoothing and spline order values are typical parameters for 64-channel EEG [START_REF] Cohen | Analyzing neural time series data: theory and practice[END_REF].

B. Results on synthetic data

In this section, we highlight the capacity of Problem [START_REF] Cohen | Comparison of different spatial transformations applied to eeg data: a case study of error processing[END_REF] to remove the noise from the raw EEG data. Note that because of the low number of epochs, only averaging them is not enough to properly remove the noise (Figure 1, left panel). The surface Laplacian is therefore not effective in this situation. In contrast, our method returns well-localized topographies even for a large amount of noise (Figure 1, right panel). This observation is corroborated by Figure 2 where our method allows a better denoising of the initial signal than an averaging of the epochs. the capacity of our filter to separate individual components based on differences in topography. Furthermore, we see that, while providing similar results as the surface Laplacian, the proposed method could tend to sharper topographies.

To highlight the capacity of our method to attenuate the volume-conductivity, we display on Figure 4 the spectral coherence between channels [START_REF] Cohen | Analyzing neural time series data: theory and practice[END_REF] as a function of the distance between electrodes. We see that in the raw ERP (left panel of Figure 4) the coherence is driven almost entirely by interelectrode distance. In contrast, after our method or the surface Laplacian (middle and right panels of Figure 4), connectivity is no longer correlated with distance. b) Robustness to malfunction: In this second experiment, we simulate the malfunction of an electrode at the edge of the EEG montage. To do so, the signal recorded at Fp1 (Top left electrode) is replaced by max(Y). The obtained results are displayed on Figure 5. Despite electrode Fp1 dysfunction, the GSP filter is globally not affected and returns comparable results as the ones of Figure 3 (when all electrodes are good). From the learned graph, we actually see that the node corresponding to Fp1 is almost disconnected from the other ones. Hence, it does not contribute in the graph filtering. In the other hand, because the surface Laplacian is computed from spatially close signal differences, it fails to recover the true topography near Fp1. For instance, at 800 ms, we clearly see that we loose information at the top right while the GSP filter works.

V. CONCLUSION

In this article, we introduced an GSP-based spatial filter that adapts to the data. We empirically shown that thanks to an adequate graph learning procedure, it automatically provides similar if not better results than the well-known surface Laplacian, especially in presence of defective electrodes and low signal-to-noise ratio. This preliminary work paves the way for further investigations on the links between EEG study and GSP, especially regarding the design of efficient GSP filters. Possible future investigation could be to consider other filters [START_REF] Tremblay | Design of graph filters and filterbanks[END_REF], time varying graph or graph products [START_REF] Gnassounou | Adaptive subsampling of multidomain signals with product graphs[END_REF], and to incorporate physical prior in the graph learning process.

Algorithm 1 Fig. 1 .

 11 Fig. 1. On the left, the raw ERP at two given times. On the right, the approximations returned by Problem (1).

  • 10 = 100 datasets of size (5 × 60 × 150). We report the Mean Square Error (MSE) between the true Event-Related Potential (ERP) i.e. the average of the true epochs -without noise -and the ERP approximation returned by Problem (1) (i.e. average of the refold version of X H in R 5×60×150 along the first dimension) as a function of the SNR. b) Real data: We consider an EEG dataset from [14]. It consists in 64 EEG signals with sampling frequency of 256 Hz for 99 epochs of 640 points. The reference is set to the average. During the graph learning phase, we concatenate the epochs and obtain a matrix Y of size (64 × 40960). The graph is learned from this matrix. Parameters in (1) are set to β = 0.001 and α = 0.0001. Once done, we solve (2) with γ = 10 and compute Y = X H -Y F . Finally, we refold Y into an array of size (99 × 64 × 640) and

Fig. 2 .

 2 Fig. 2. Evolution of the MSE (avg ± std) between the true ERP (without noise) and: (blue) the ERP approximation returned by Problem (1) (denoising); (orange) the raw ERP, as a function of the SNR.

Fig. 3 .

 3 Fig. 3. Topographies at four given times from the experiment on real EEG data. From top to bottom: Topographies of (i) raw ERP, (ii) data returned by Problem (1), (iii) data returned by Problem (1) follow by (2), and (iv) data after applying the surface Laplacian.

  C. Results on real data a) Sharper topographies: The raw ERP and its filtered version (with our GSP filter and the standard surface Laplacian filter) are displayed in Figure3. This figure illustrates

Fig. 4 .Fig. 5 .

 45 Fig. 4. Evolution of the Coherence at 8 Hz as a function of the electrode distances. From left to right: coherence on (i) raw ERP, (ii) after Problem (denoising), and (iii) after Problem (2)

Université Paris-Saclay, ENS Paris-Saclay, CNRS, Centre Borelli, F-91190 Gif-sur-Yvette, France

[START_REF] Kayser | Issues and considerations for using the scalp surface laplacian in EEG/ERP research: a tutorial review[END_REF] Université de Paris, CNRS, Centre Borelli, F-75005 Paris,

France 3 Service d'anesthésie-réanimation, Service de Santé des Armées, Hôpital d'Instruction des Armées Bégin, F-94160 Saint Mandé, France