Perception enhancement of an autonomous vehicle through the use of UAV

Perception enhancement of an autonomous vehicle through the use of UAV Amélioration de la capacité de perception d'un véhicule autonome grâce à l'utilisation de drones

The se de doctorat de l'universite  Paris-Saclay Title : Perception Enhancement of an Autonomous Vehicle through the use of UAV Keywords : ITS, UAV, VLC, Knowledge-base Abstract : Due to the evolution of electronic calculation and communication methods, the concept of the intelligent city is rapidly taking shape. The numerous sensors and actuators positioned in inhabited spaces allow a better monitoring of the data that passes between users, and an optimization of living comfort. The use of vehicles remains one of the most widely used means of travel in the world. Here too, technological advances have allowed evolution enabling cars to drive themselves, with little to no human assistance. However, it is important to consider the safety of road users in this increasingly populated environment. This thesis proposes to improve the perception capability of an autonomous vehicle through the use of drones. Due to their advantageous positioning and small size, they can collect perception data and transmit them to the vehicle using a secure method, such as VLC communication. The data from the dierent sources are then federated and processed thanks to a knowledge base and a set of logical rules.

  Titre : Amélioration de la capacité de perception d'un véhicule autonome grâce à l'utilisation de drones Mots clés : Véhicules autonomes, Drones, VLC, Base de connaissances Résumé : Du fait de l'évolution des méthodes électronique de calcul et de communication, le concept de ville intelligente prend rapidement forme. Les nombreux capteurs et actionneurs positionnés dans les espaces habités permettent un meilleur contrôle des données qui transitent entre les usagers, et une optimisation du confort de vie. L'utilisation de véhicules reste l'un des moyens de déplacement les plus utilisés dans le monde. Làaussi, les avancées technologiques ont permis des évolutions permettant d'avoir des voitures qui se déplacent par elle-même, avec pas ou peu d'assistance humaine. Il est cependant important de considérer la sécurité des usagers de la route dans cet environnement de plus en plus peuplé. Cette thése propose d'améliorer la capacité de perception d'un véhicule autonome grâce à l'utilisation de drones. Du fait de leur positionnement avantageux et de leur taille réduite, ces derniers peuvent récolter des données de perception et les transmettre au véhicule grâce à une méthode sécurisée, par exemple une communication VLC. Les données des diérentes sources sont ensuite fédérées et traitées grâce à une base de connaissance et un jeu de règles logiques.

  École doctorale n • 580 Sciences et Technologies de l'Information et de la Communication (STIC) Spe cialite  de doctorat : Informatique Graduate School : Informatique et sciences du nume rique, Re fe rent :Universite  de Versailles -Saint-Quentin-en-Yvelines Hongyu GUAN, inge nieur de recherche et de Manolo HINA, maitre de confe rence.

	The se soutenue a  Paris, le 06 juillet 2022, par
		Abderraouf KHEZAZ
	Composition du jury
	Samir OTMANE Professeur des universite s, Universite  d'Evry Hakima CHAOUCHI	Pre sident du jury Rapporteure & Examinatrice
	Professeure des universite s, Te le com Sud Paris Nicole LEVY	Rapporteure & Examinatrice
	Professeure des universite s, CNAM Jaouhar FATTAHI	Examinateur
	Professeur, Universite  Laval Hongyu GUAN	Examinateur
	Inge nieur de recherche, LISV
	Manolo Dulva HINA

The se pre pare e dans l'unite  de recherche LISV (Universite  Paris-Saclay, UVSQ), sous la direction de Amar RAMDANE-CHERIF, professeur des universite s, et le co-encadrement de Examinateur Ma tre de confe rence, ECE Paris Ravi TOMAR Examinateur Professeur, University of Petroleum and Energy Studies Amar RAMDANE-CHERIF Directeur de the se Professeur des universite s, UVSQ


Emiliano Lorini

Giovanni Sartor

The Ethics of Controllability as Influenceability

Keywords: logic of action, influence, responsibility, control, values

We present a logical analysis of influence and control over the actions of others, and address consequential causal and normative responsibilities. We first account for the way in which influence can be exercised over the behaviour of autonomous agents. On this basis we determine the conditions under which influence leads to control on the implementation of positive and negative values. We finally define notions of causal and normative responsibility for the action of others. Our logical framework is based on STIT logic and is complemented with a series of examples illustrating the application. Our analysis applies to interactions between humans as well as to those involving autonomous artificial agents.

Introduction

As AI systems become more and more pervasive, autonomous, and powerful, their actions increasingly affect human values and interests. AI agents, however, are not alone, they rather participate in ecosystems in which multiple agents, humans and artificial ones influence one another. To understand the significance of agents' actions, and allocate responsibilities concerning their outcomes, we need to put such actions in the context of the influence patterns determining the performance of their actions as well as their indirect effects. More precisely we need to address two parallel issues. The first issue concerns incoming influences, i.e., determining to what extent and in what ways other agents have or may have influenced the agent's behaviour. The second issue concerns outcoming influences, i.e., determining to what extent and in what ways the agent has or may have influenced other agents. As an example involving both issues, consider for instance the case in which a bot is used to spread fake news, hate content, misleading ads, or to maximise engagement (in whatever way). In such cases the bot's owner influences the bot to influence the behaviour of the receivers of the bot's messages. When an agent has the ability to exercise influence over the behaviour of another agent we may say that the first agent has control over the second one. Control may cover all actions of the controlled agent, or only a subset of them.

For instance, relative to the actions by the online bot spreading unlawful or unethical content not only the user, but also the platform operator has some control, since the platform operator too could have blocked, or restricted, the operation of the bot, preventing its activity. The platform operator also has control over the users of the bot, which he can exercise, for instance, by threatening sanctions (such as the exclusion from the platform) against the use of bots for such a purpose.

Control may have a normative significance: the controller may be praised or blamed when making the controllee perform good or bad actions, respectively. In some cases, the controller can also be blamed for not preventing the controllee from performing bad actions. In fact, when agent i has the capacity to exercise control in such a way as to prevent j from behaving badly, or to ensure that j behaves well, then it may make sense to consider i to be accountable for j's failures and possibly to subject i to sanction for such failures. For instance, if the platform's owners have the possibility to exercise control over the messages exchanged over their platforms, then it may make sense to blame and sanction them because of the harm resulting from such messages, even though they do not take the initiative to send such messages. Note however that failure to exercise control does not necessarily entail blame and sanction for controllers. The exercise of control entails disadvantages, regarding both the autonomy of the controllee and the expected social outcomes. It may be the case that, all things considered, the exercise of control would entail social costs that exceed the benefits it may provide. For instance, assume that the platform's owner could prevent all unlawful behaviours on its platform only by stopping all messages. However, this would entail more harm than good. Therefore, the controller cannot be blamed for failing to take such an action.

The purpose of this paper it to provide a logical framework for modelling patterns of influence and control. Our framework can be useful for understanding contexts where agents do or do not, can or cannot, exercise influence over others, and therefore for determining how prise and blame, and consequently responsibilities, should be allocated to such agents. Consider again the case of online platforms. As an instance of a prohibition to promote bad behaviour, consider that ISPs may be ethically or legally responsible for inducing their users to engage in harmful behaviour, as in the case of websites that are devoted to enabling online revenge porn, the spreading of politically oriented fake news, or to the distribution of unauthorised copyright materials. As an instance of an obligation to prevent bad behaviour, consider that large platforms, even if they to do not actively engage in promoting such a behaviour may still be responsible for failing to terminate unethical or unlawful illegal activities of their users. It is true that US Digital Millennium Copyright Act and Communication Decency Act, or, to a lesser extent, the EU eCommerce directive, provide for immunities of ISPs relative to the unlawful behaviour by their users. However, such immunities have exceptions and there is a vast debate for limiting them, in particular in the context of the coming EU Digital Services Act [START_REF] Sartor | The secondary liability of online intermediaries[END_REF]. A precondition for a clear understanding of the ethical and legal issues just mentioned is possessing precise notions of influence and control over others' behaviour, and of the connection between control and responsibility. We think that the notion of influence-based responsibility is important not only in the law, but also in the regulation of multi-agent systems. When agents become intelligent enough as to understand that an evil outcome can also be obtained through the action of others, it becomes necessary to prohibit not only harmful actions, but also bad influence, leading to the performance of harmful actions.

The issue of influence-based responsibility has so far not been addressed in the literature on the logic of actions and norms. This paper aims to cover this gap, by providing a logical analysis of the relationship between influence, control, and responsibility.

Our logical analysis will be based on the STIT logic of action [START_REF] Belnap | Facing the future: agents and choices in our indeterminist world[END_REF], one of the most popular approaches to the study of agency. We will need to address an important logical and philosophical issue concerning the very definition of interpersonal influence. Namely, we shall consider how an agent i's influence inducing an agent j to perform an action ϕ may be consistent with j's choice to perform ϕ rather than not performing it. Clearly, the influence must not make it necessary for j to perform ϕ, as this would contradict the agency of j in realising ϕ. Preserving j's freedom of choice is indeed necessary for considering j the principal author of the unethical or illegal action for which also i may be liable. Consider, for instance the case of i managing a website devoted to revenge porn. If j publishes a video with such a content, he remains responsible for the unlawful behaviour consisting in publishing the video, but in addition i is also responsible for having enabled the publication. Or consider the case in which j asks k to publish the video in i's website. In this case k is responsible for publishing the video, j for having induced k to publish the video, and i for enabling the publication.

The article is organised as follows. Section 2 provides a gentle introduction to the STIT syntax and semantics. Section 3 discusses the concept of social influence from an informal perspective, while Section 4 addresses it from a formal point of view. Section 5 explores the connection between influence and control. Finally, Section 6 is devoted to the formalisation of the relationship between the concepts of causal and normative responsibility and the concepts of influence and control.

Background on STIT

STIT logic (the logic of seeing to it that) by Belnap et al. [START_REF] Belnap | Facing the future: agents and choices in our indeterminist world[END_REF] is one of the most prominent formal accounts of agency. It is the logic of sentences of the form "the agent i sees to it that ϕ is true". Different semantics for STIT have been proposed in the literature (see, e.g., [START_REF] Belnap | Facing the future: agents and choices in our indeterminist world[END_REF][START_REF] Broersen | Deontic epistemic stit logic distinguishing modes of mens rea[END_REF][START_REF] Wolfl | Propositional Q-Logic[END_REF][START_REF] Lorini | A logic for reasoning about counterfactual emotions[END_REF][START_REF] Lorini | Temporal STIT logic and its application to normative reasoning[END_REF][START_REF] Schwarzentruber | Complexity Results of STIT Fragments[END_REF]). Following [START_REF] Lorini | Temporal STIT logic and its application to normative reasoning[END_REF], here we adopt a Kripke-style semantics for STIT. The Kripke semantics of STIT is illustrated in Figure 1, where each moment m 1 , m 2 and m 3 consists of a set of worlds represented by points. For example, moment m 1 consists of the set of worlds {w 1 , w 2 , w 3 , w 4 }. Moreover, for every moment there exists a set of histories passing through it, where a history is defined as a linearly ordered set of worlds. For example, the set of histories passing through moment m 1 is {h 1 , h 2 , h 3 , h 4 }. Finally, for every moment, there exists a partition which characterizes the set of available choices of agent 1 in this moment. For example, at moment m 1 , agent 1 has two choices, namely {w 1 , w 2 } and {w 3 , w 4 }. Note that an agent's set of choices at a certain moment can also be seen as a partition of the set of histories passing through this moment. For example, we can identify the choices available to agent 1 at m 1 with the two sets of histories {h 1 , h 2 } and {h 3 , h 4 }.

In the Kripke semantics for STIT the concept of a world should be understood as a 'time point' and the equivalence class defining a moment should correspondingly be understood as a set of alternative concomitant 'time points'. In this sense, the concept of a moment captures a first aspect of indeterminism, as it represents the alternative ways the present could be. A second aspect of indeterminism is given by the fact that moments are related in a (tree-like) branching time structure. In this sense, the future could evolve in different ways from a given moment. In the Kripke semantics for STIT these two aspects of indeterminism are related, as illustrated in Figure 1. Indeed, if two distinct moments m 2 and m 3 are in the future of moment m 1 , then there are two distinct worlds in m 1 (w 1 and w 3 ) such that a successor of the former (w 5 ) is included in m 2 and a successor of the latter (w 7 ) is included in m 3 . The logic STIT allows us to talk about time. Specifically, existing STIT languages (see, e.g., [START_REF] Lorini | Temporal STIT logic and its application to normative reasoning[END_REF][START_REF] Schwarzentruber | Complexity Results of STIT Fragments[END_REF]) include different kinds of future and past tense operators such the 'next' operator X (where Xϕ stands for "ϕ is going to be true in the next world") and the 'yesterday' operator Y (where Yϕ stands for "ϕ was true in the previous world"). For example, the formula X¬p is true at world w 1 in Figure 1. Indeed, at w 1 it is the case that p is going to be false in the next world (as p is false at world w 5 ). Moreover, the formula Yp is true at world w 5 since at world w 5 it is the case that p was true in the previous world (as p is true at world w 1 ).

C 1 h 1 h 2 h 3 h 4 m 1 m 3 m 2 C 1 C 1 C 1 C 1 C 1 p,q p,q p p,
The STIT language also includes an operator which allows us to represent those facts that are necessarily true, in the sense of being true at every point of a given moment or, equivalently, at every history passing through a given moment. For example, the formula p is true at world w 1 in Figure 1 since p is true at every point of moment m 1 including world w 1 . The operator ♦ is the dual of : it allows to represent those facts that are possibly true (i.e., true at some history passing through the actual moment).

Finally, the logic STIT provides for different concepts of agency, all characterized by the fact that an agent acts only if she sees to it that a certain state of affairs is the case. In this paper we shall use the deliberative STIT of [START_REF] Horty | The Deliberative STIT: A Study of Action, Omission, Ability, and Obligation[END_REF] which is defined as follows: an agent i deliberately-sees-to-it that ϕ, denoted by formula [i dstit]ϕ, at a certain world w if and only if: (i) for every world v, if w and v belong to the same choice of agent i then ϕ is true at v, and (ii) at w agent i could make a choice that does not necessarily ensure ϕ. Notice that the latter is equivalent to say that there exists a world v such that w and v belong to the same moment and ϕ is false at v. For example, in Figure 1, agent 1 deliberately sees to it that q at world w 1 because q is true both at world w 1 and at world w 2 , while being false at world w 3 . Deliberative STIT captures a fundamental aspect of agency, namely, the idea that for a state of affairs to be the consequence of an action (or for an action to be the cause of a state of affairs), it is not sufficient that the action ensures that the state of affairs holds, it is also required that, without the action, the state of affairs possibly would not hold (a similar idea is also included in the logic of "bringing it about" by Pörn, see in particular [START_REF] Pörn | On the Nature of Social Order[END_REF]). In this sense, [i dstit]ϕ at w is incompatible with the necessity of ϕ at w, since it requires that at w also ¬ϕ was an open possibility.

The concept of social influence

Our analysis of social influence starts from a general view about the way rational agents make choices. Specifically, we assume that an agent might have several choices or alternatives available defining her choice set at a given moment, and that what the agent does is determined by her actual choice, which is in turn determined by the agent's choice context including her preferences and beliefs and the composition of her choice set. Our analysis of social influence expands this view by assuming that the agent's choice context determining the agent's actual choice might be determined by external causes. Specifically, the external conditions in which an agent finds herself or the other agents with whom the agent interacts may provide an input to the agent's decision-making process in such a way that a determinate action should follow. Note that here we only address the kind of influence that consists in determining the voluntary action of an agent by modifying her choice context, so that a different choice becomes preferable to the influencee on comparison to what would be her preferred option without this modification. This may happen, for instance: (a) by expanding the available choices (influence via choice set expansion), or (b)by restricting the available choices (influence via choice set restriction) or (c) by changing the payoffs associated to such choices, as when rewards or punishments are established (influence via payoff change).

To illustrate the concept of social influence, let us consider an example about influence via choice set restriction. The example is illustrated in Figure 2. It represents a situation where there are three objects to be purchased in an online marketplace, let us call them, for simplicity's sake, apple, banana and pear (they could be material objects, or stock items, etc.), and three bots acting for human buyers. The actions at issue consist in bringing about the purchase of the apple (ap), the banana (ba) or the pear (pe). Let us assume that agent 2 has certain preferences that remain constant along the tree structure. In particular, at all moments agent 2 prefers purchasing apples to bananas to pears. Let us also assume that 2 is rational, in the minimal sense that she acts in such a way as to achieve the outcome she prefers. Rational choices of agent 2 are depicted in grey. By choosing to purchase the apple at w 1 , 1 generates a situation where, given its preferences, 2 will necessarily purchase the banana, rather than the pear. Indeed, although at moment m 2 , 2 has two choices available, namely, the choice of purchasing the banana and the choice of purchasing the pear, only the former is rational, in the sense of being compatible with 2's preferences. In this sense, by deciding to purchase the apple at w 1 and removing this option from 2's choice set, 1 influences 2 to decide to purchase the banana at w 7 .

Figure 2. Example of influence via choice set restriction

As an example of influence via payoff change, consider the interaction between person 1 and bot 2, who is acting as an intermediary in an online marketplace, and has the goal of maximising the profits of its owner. Assume that 1 asks 2 to purchase for him an illegal drug (k) in exchange for a reward (r). The alternative choices for 2 are either purchasing the unlawful item or doing nothing. Let us assume that the bot has the goal of increasing its profits, so that 2 prefers purchasing the drug and getting the reward (k ∧ r) to not purchasing it and not being rewarded (¬k ∧¬r). Moreover, the bot prefers the latter combination (¬k ∧ ¬r) to purchasing the drug and not being rewarded (k ∧ ¬r), since the unlawful purchase of the drug involves the risk of a severe sanction. Under these assumptions, 1's promise of the reward at moment m 1 leads to a moment m 2 where agent 2 has the choice between producing k ∧ r or ¬k ∧ ¬r, rather than to a moment m 3 where agent 2 would have had the choice between k ∧ ¬r or ¬k ∧ ¬r (no compensation been given for the action of purchasing the drug). Given 2's preferences, its rational choice at m 2 is to purchase the drug, while its rational choice at m 3 would have been not to purchase it. Thus we may say that at moment m 1 principal 1, by promising the reward, influences agent 2 to buy the unlawful item. An example of influence via choice set restriction is the case of an online platform disabling the posting of anonymous content. The option of refraining from publishing incitements to crime or terrorism becomes preferred by a user who starts to be deterred by the possibility of being identified and of facing the legal consequences of such a behaviour. These examples lead us to the following informal definition of social influence: An agent i influences another agent j to perform a certain (voluntary) action if and only if, i sees to it that every rational/preferred choice of j will lead j to perform the action.

We distinguish influence on action from influence on inaction.

An agent i influences another agent j to abstain from performing a certain (voluntary) action if and only if, i sees to it that every rational/preferred choice of j will lead j to not perform the action.

For instance, the above example of a person who asks a bot to buy an unlawful drug fits the definition of influence on action, whereas the above example of the online platform disabling the posting of anonymous content fits the definition of influence on inaction. In the next two sections we move from an informal to a formal perspective on the concept of social influence and its relationship with the concept of controllability.

Formalization of social influence

In [START_REF] Lorini | A STIT Logic for Reasoning About Social Influence[END_REF], we provided an analysis, based on STIT logic, of the concept of influence on action discussed in the previous section. To this aim, we extended STIT logic with special 'rational' STIT operators of the form [i rdstit]. We are going to resume this analysis and extend it by the concept of influence on inaction.

The formula [i rdstit]ϕ has to be read "if agent i's current action is the result of a rational choice of i, then i deliberately sees to it that ϕ". We adopt a minimal concept of rationality, which is sufficient for our purpose: we assume that the choices of an agent are ranked according to the agent's preferences, and an agent is rational as long as she implements her preferred choices. The [i rdstit] operator is interpreted relatively to STIT branching time structures, like the ones represented in Figure 2. Specifically, the formula [i rdstit]ϕ is true at a certain world w if and only if, if the actual choice to which world w 1 belongs is a rational choice of agent i then, at world w 1 agent i deliberately sees to it that ϕ, in the sense of deliberative STIT discussed in Section 2. For example, at the world w 7 in Figure 2, the formula [2 rdstit]ba is true since the actual choice to which world w 7 belongs is a rational choice of agent 2 and at w 7 agent 2 deliberately sees to it that ba is the case. To capture the idea of influence on action, we introduce a social influence operator based on the concept of deliberative STIT (see [START_REF] Lorini | A STIT Logic for Reasoning About Social Influence[END_REF]) defining it as follows:

[i inflAct j]ϕ def = [i dstit]X[ j rdstit]ϕ. (1)
In other words, we shall say that an agent i influences another agent j to make ϕ true, denoted by [i inflAct j]ϕ, if and only if, i deliberately sees to it that if agent j's current choice is rational then j is going to deliberately see to it that ϕ. The reason why the operator [i dstit] is followed by the temporal operator X is that influence requires that the influencer's choice precedes the influencee's action. On the contrary, we do not require that [ j rdstit] is followed by X since in STIT the concept of action is simply captured by the deliberative STIT operator which does not need to be followed by temporal modalities.

In order to illustrate the meaning of the influence operator, let us go back to the example of Figure 2. Since agent 2 prefers bananas to pears, her only rational choice at moment m 2 is {w 7 }. From this assumption, it follows that formula [1 inflAct 2]ba is true at world w 1 . Indeed, at world w 1 agent 1 deliberately sees to it that, in the next world, if agent 2's choice is rational then 2 deliberately sees to it that ba is the case.

As emphasized above influence on action should be distinguished from influence on inaction. The latter concept is captured by the following abbreviation:

[i inflInact j]ϕ def = [i dstit]X(rat j → ¬[ j dstit]ϕ). (2)
This means that an agent i influences another agent j to abstain from making ϕ true, denoted by [i inflInact j]ϕ, if and only if, i's current choice guarantees that j will not be able to rationally see to it that ϕ. In other words, i's current choice will exclude the possibility that j will make ϕ true, if j will choose in conformity with his preferences. The constant symbol rat j means that agent j's current choice is rational. It is an abbreviation, adopted for notational convenience, of ¬[ j rdstit]⊥, a formula that is satisfied only when j chooses rationally in the current word.

From influence to control

The notion of influence we discussed in the previous section is the key element of the notion of control on which the present analysis is focused.

In order to formalize this concept, we have to assume there are a set of conditional positive values (+values) I + = {(ϕ 1 ,ψ 1 ), . . . , (ϕ k ,ψ k )} and a set of conditional negative values (-values) I -= {(ϕ 1 ,ψ 1 ), . . . , (ϕ h ,ψ h )}. Specifically, (ϕ,ψ) ∈ I + means that the occurrence of ψ should be promoted when ϕ is true and (ϕ ,ψ ) ∈ I -means that the occurrence of ψ should be hindered when ϕ is true.

A value i is active when its antecedent condition is satisfied. The following definition captures the concept of active value for X ⊆ I + and Y ⊆ I -:

Active(X,Y ) def = (ϕ,ψ)∈X ϕ ∧ (ϕ ,ψ )∈Y ϕ . (3)
Thus, for a conditional value (ϕ,ψ) in I + or I -to be active, its triggering condition ϕ must be true.

As the following definition highlights, for an agent i to have control over another agent j, with respect to a set of +values X and a set of -values Y , i should be capable of influencing j to realise every active +value in X and to abstain from realising any active -value in Y . Thus, for X ⊆ I + and Y ⊆ I -, positive control may be defined as follows:

Ctrl(i, j, X,Y ) def = Active(X,Y ) → ♦ (ϕ,ψ)∈X ([i inflAct j]ψ) ∧ (ϕ ,ψ )∈Y ([i inflInact j]ψ ) . (4)
The previous notion of control is different from the notion of organizational control formalized by Grossi et al. [START_REF] Grossi | Organizational structure and responsibility[END_REF]. While their notion is a primitive and is assigned to roles, our notion is assigned to agents and, more importantly, is defined from the more basic notions of action and capability.

Let us apply this notion to our online example. Let us assume that the following are the -values in I -: publishing hate speech (hate, publish) and spreading malware (malware, spread). Let us also assume that the following is the unique +value in I + : flagging or tagging fake news ( f ake,tagged). Let us assume that the online platform under consideration has the capability of influencing the publisher to perform the good action and to abstain from the bad ones. The latter is achieved by giving to the publisher the right balance of incentives and disincentives. This assumption is formally expressed as follows:

Ctrl(i, j, {( f ake,tagged)}, {(hate, publish), (malware, spread)}).

(5)

From control to responsibility

We now move to the notion of control-responsibility, namely, the responsibility that results on failing to exercise control. An agent having control over an agent relative to the achievement of some +values X and some -values Y has secondary responsibility if he does not exercise the influence as needed, i.e., if the influencee fails to realise active +values, or to realise active -values:

CtrlResp(i, j, X,Y ) def = Ctrl(i, j, X,Y ) ∧ Active(X,Y ) ∧ (ϕ,ψ)∈X (¬[i inflAct j]ψ)∨ (ϕ ,ψ )∈Y (¬[i inflInact j]ψ ) . (6)
This notion of secondary responsibility, however, raises a problem. What if the potential infuencer cannot exercise influence relatively to all values at stake. For instance, what if the provider cannot prevent hate speech and fake news without also blocking useful content (being unable to distinguish in all cases hate speech and fakes from decent and sincere communication)?

A possible solution can come from what jurists call "proportionality", i.e., by considering the relative importance of the (sets of) values being implemented. Let us assume a strict preference ordering over pairs (X,Y ) such that X ∈ 2 I + and Y ∈ 2 I -. Let us write (X ,Y ) (X,Y ) to mean that it is better to realise the +values X and refrain from realising the -values Y , than to realise the +values X and to refrain from realising the -values Y . 1 Then, i would be normatively responsible for failing to exercise control over j relative to (X,Y ) only if there is no (X ,Y ) that is preferable to (X,Y ), such that if i exercises control over j relative to (X ,Y ), i cannot at the same time exercise control over (X ,Y ). The notion of exercising control can be defined as follows:

ExCtrl(i, j, X,Y ) def = Active(X,Y ) ∧ (ϕ,ψ)∈X ([i inflAct j]ψ)∧ (ϕ ,ψ )∈Y ([i inflInact j]ψ ) . (7)
Note that ExCtrl(i, j, X,Y ) implies Ctrl(i, j, X,Y ), since ϕ → ♦ϕ is valid. This leads us to our final notion of normative responsibility. Agent i is normatively responsible for not exercising control over agent j relative to set of positive values X and the set of negative values Y if i is causally responsible for that, and her failure to exercise control is not due to the need to realise more important positive/negative values. The latter would be the case if there was a preferable pair (X ,Y ), such that i exercises control over(X ,Y ) being unable to exercise control over all values in both pairs, i.e., over (X ∪ X ,Y ∪Y ):

NormCtrlResp(i, j, X,Y ) def = CtrlResp(i, j, X,Y ) ∧ ¬ (X ,Y ) (X,Y ) ExCtrl(i, j, X ,Y )∧ ¬Ctrl(i, j, X ∪ X ,Y ∪Y ) . (8)
To illustrate the previous notion of normative responsibility, let us go back to the example of the online platform. Suppose all values in our example are active and that the provider can either (i) induce the publisher to tag fake news, or (ii) induce the publisher to abstain from spreading malware and from publishing hate speech. Finally, suppose it is impossible for the provider to jointly realise (i) and (ii), since it cannot prevent the publisher to publish hate speech unless it disables the tagging functionality. But (ceteris paribus) it is more important to realise (ii) than to realise (i). Then, the provider would not be considered normatively responsible for not guaranteeing (i) to be true if it guarantees (ii) to be true. The opposite would be the case if the preference was inverted.

Conclusion

In this paper we have modelled influence by using the framework provided by the STIT logic of action. On this basis we have defined a notion of control, as the possibility to exercise influence over another, to induce the influencee to realise positive values and refrain from realising negative values. An agent's failure to exercise control can be viewed as control-responsibility, namely as causal responsibility for the action of the potential influencee. We have then argued that causal responsibility for failing to exercise influence relative to certain values does not lead to normative control-responsibility where control has been exercised to achieve superior incompatible values. This has lead us to the final notion of normative control-responsibility.

The issues we have tackled are largely unexplored, as while primary responsibility has been addressed in STIT by [START_REF] Broersen | Deontic epistemic stit logic distinguishing modes of mens rea[END_REF][START_REF] Lorini | A logical analysis of responsibility attribution: emotions, individuals and collectives[END_REF], no account is yet available of secondary responsibility, understood as control-responsibility. [START_REF] Santos | Action Concepts for Describing Organised Interaction[END_REF] proposed to model social influence in the framework of the "bringing it about that" logic, but have not addressed the connection between influence and choice, focusing on influence through the exercise of normative powers. [START_REF] Smith | Reflex Responsibility of Agents[END_REF] modelled an agent's endorsement of the principal's goals as a source of responsibility for the principal, but did not consider how goal-alignment is put in place. This work is still preliminary and partial, as it only addresses some kinds of influence/control and some aspects of these notions. We plan to develop it further, covering both active and omissive influence, and addressing psychological influence, which changes the influencees' cognitive states (their beliefs and preferences) rather than the context of their action.

  Figure 1. Illustration of Kripke semantics of STIT

	w 5	w 6		w 7	w 8
	w 1 w 2	w 3	w 4	q

We can safely assume that the preference ordering is induced by a utility function U : (I + ∪ I -) -→ R + measuring the degree of importance of a positive/negative value such that (X ,Y ) (X,Y ) if and only if ∑ (ϕ ,ψ )∈X ∪Y U(ϕ, ψ) > ∑ (ϕ,ψ)∈X∪Y U(ϕ, ψ).


Emiliano Lorini
email: emiliano.lorini@irit.fr

Éloan Rapion
email: eloan.rapion@ens-rennes.fr

Logical Theories of Collective Attitudes and the Belief Base Perspective

Keywords: Reasoning about beliefs, modal logic, epistemic logic

We present two logics of collective belief with a semantics exploiting the notion of belief base. The semantics distinguishes explicit from implicit belief: an agent's belief of explicit type is a piece of information contained in the agent's belief base, while a belief of implicit type corresponds to a piece of information that is derivable from the agent's belief base. The first part of the paper is devoted to the logic of implicit common belief, while the second presents the logic of explicit common belief. Implicit common belief is defined as a mutual belief of any order. This leads to the usual fixpoint construction of common belief. Explicit common belief is the collective counterpart of explicit individual belief and has a public nature. It moreover implies implicit common belief. We study axiomatic aspects of our logics as well as complexity of satisfiability checking. We show that, while the satisfiability checking problem is EXPTIME-hard for the logic of implicit common belief, it is in PSPACE for the logic of explicit common belief. This makes the latter logic a natural candidate for reasoning about collective attitudes in multi-agent scenarios and applications. We also study a dynamic extension of the logic of explicit common belief in which private and public forms of information dynamics can be modeled.

INTRODUCTION

Epistemic logic is the logic of epistemic attitudes including knowledge and belief. Since the pioneering work of Hintikka [START_REF] Hintikka | Knowledge and Belief[END_REF], it has been widely studied in artificial intelligence (AI) [START_REF] Fagin | Reasoning about Knowledge[END_REF][START_REF] Meyer | Epistemic logic for AI and computer science[END_REF] and economics [START_REF] Lismont | On the Logic of Common Belief and Common Knowledge[END_REF]. It offers a rich language for modeling not only agents' beliefs about propositional facts, but also higher-order beliefs. Standard semantics for epistemic logic languages exploit the so-called multi-agent Kripke models, namely, multi-relational structures equipped with valuation functions for the interpretation of atomic formulas. Binary relations in a multi-agent Kripke model are called epistemic accessibility relations and are used to describe the agents' epistemic states and uncertainties.

Higher-order beliefs are essential constituents of collective attitudes of agents including common knowledge and common belief [START_REF] Vanderschraaf | Common knowledge[END_REF]. According to the standard fixpoint definition, a group of agents J has the common belief that the fact φ is true if and only if the agents in J mutually believe that φ for every order k ≥ 1, that is, every agent in J believes that φ, every agent in J believes that every agent in J believes that φ, and so on ad infinitum.

The earliest analysis of common belief can be found in [START_REF] Friedell | On the Structure of Shared Awareness[END_REF][START_REF] Lewis | Convention: a philosophical study[END_REF]. The economist Robert Aumann [START_REF] Aumann | Agreeing to Disagree[END_REF] gave the first set-theoretic characterization of common knowledge. Some initial analysis of common belief and common knowledge based on epistemic logic can be found in [START_REF] Bacharach | Some extensions of a claim of Aumann in an axiomatic model of knowledge[END_REF][START_REF] Bicchieri | Self-refuting theories of strategic interaction: A paradox of common knowledge[END_REF]. The axiomatic and complexity properties of the standard approach to common belief based on the Kripke semantics were fully studied in [START_REF] Halpern | A guide to completeness and complexity for modal logics of knowledge and belief[END_REF]. 1 Weakest systems of common belief and common knowledge not satisfying, e.g., closure under logical consequence for individual beliefs or the least fixpoint principle for common belief were studied in [START_REF] Bonanno | On the Logic of Common Belief[END_REF][START_REF] Fukuda | Formalizing common belief with no underlying assumption on individual beliefs[END_REF][START_REF] Heifetz | Iterative and fixed point common belief[END_REF][START_REF] Lismont | On the Logic of Common Belief and Common Knowledge[END_REF][START_REF] Pacuit | Neighborhood Semantics for Modal Logic[END_REF]. Common belief has played a fundamental role in the analysis of shared cooperative activity of both human agents [START_REF] Bratman | Shared cooperative activity[END_REF] and artificial agents [START_REF] Grosz | Collaborative Plans for Complex Group Action[END_REF][START_REF] Levesque | On Acting Together[END_REF], intentional communication [START_REF] Colombetti | A modal logic of intentional communication[END_REF], social conventions [START_REF] Lewis | Convention: a philosophical study[END_REF] and social institutions [START_REF] List | Three kinds of collective attitudes[END_REF]. It has also be demonstrated to be an essential constituent of the concept of common ground [START_REF] Stalnaker | Common ground[END_REF], as a basis for discourse understanding and definite reference [START_REF] Clark | Definite reference and mutual knowledge[END_REF][START_REF] Schiffer | Meaning[END_REF]. Finally, it is central in epistemic game theory [START_REF] Perea | Epistemic game theory: reasoning and choice[END_REF] in which several solution concepts including iterated deletion of strongly/weakly dominated strategies (IDSDS/IDWDS) [START_REF] Bonanno | A syntactic approach to rationality in games with ordinal payoffs[END_REF][START_REF] Lorini | A minimal logic for interactive epistemology[END_REF] and backward induction [START_REF] Aumann | Backward induction and common knowledge of rationality[END_REF] are justified in the light of common belief that all players are rational.

In this paper, we present a novel approach to common belief which relies on a formal semantics exploiting the notion of belief base. The latter distinguishes explicit from implicit belief: an agent's belief of explicit type is a piece of information contained in the agent's belief base, while a belief of implicit type corresponds to a piece of information that is derivable from the agent's belief base. This semantics and its corresponding logic of explicit and implicit individual belief were introduced in [START_REF] Lorini | Rethinking epistemic logic with belief bases[END_REF] (see also [START_REF] Lorini | In Praise of Belief Bases: Doing Epistemic Logic Without Possible Worlds[END_REF][START_REF] Lorini | Decision Procedures for Epistemic Logic Exploiting Belief Bases[END_REF]). They generalize the concept of belief base from knowledge representation [START_REF] Hansson | A Textbook of Belief Dynamics: Theory Change and Database Updating[END_REF] and, more generally, the database perspective on modeling agents' mental attitudes [START_REF] Shoham | Logical Theories of Intention and the Database Perspective[END_REF] to the multi-agent case. In this paper, we extend them with collective attitudes of coalitions of agents. We study two logical systems: a logic of explicit and implicit individual belief extended by the notion of implicit common belief, and a logic of explicit and implicit individual belief extended by the notion of explicit common belief. Implicit common belief is the standard 1 The axiomatics of common knowledge and belief given in [START_REF] Halpern | A guide to completeness and complexity for modal logics of knowledge and belief[END_REF] use a fixpoint axiom and an induction (alias least fixpoint) rule. In [START_REF] Halpern | A guide to the modal logics of knowledge and belief: Preliminary draft[END_REF][START_REF] Lehmann | Knowledge, common knowledge and related puzzles (Extended Summary)[END_REF], the induction rule is replaced by an induction axiom. An alternative axiomatization of S5-based common knowledge using a more intuitive version of the induction axiom was recently given in [START_REF] Herzig | On the Axiomatisation of Common Knowledge[END_REF].

fixpoint notion of common belief we find in the literature [START_REF] Halpern | A guide to completeness and complexity for modal logics of knowledge and belief[END_REF], whereas explicit common belief is the collective counterpart of explicit individual belief and has a public nature. We stipulate that there is an explicit common belief in a coalition of agents about a certain fact α, if every agent explicitly believes that α, and every agent explicitly believes that there is an explicit common belief that α. This construction guarantees that explicit common belief implies implicit common belief, but not vice versa. The main reason for distinguishing explicit common belief from implicit common belief is that the logic of the former notion is intrinsically simpler than the logic of the latter one. In particular, we will show that, while the satisfiability checking problem is EXPTIME-hard for the logic of implicit common belief, it is in PSPACE for the logic of explicit common belief. This makes the latter logic a natural candidate for reasoning about collective attitudes of agents in multi-agent scenarios and applications.

The paper is organized as follows. In Section 2 we present the background material on the language and the semantics for explicit and implicit individual belief introduced in [START_REF] Lorini | Rethinking epistemic logic with belief bases[END_REF]. Section 3 is devoted to the logic of implicit common belief. Section 4 focuses on the logic of explicit common belief. We study the axiomatic and complexity properties of both logics. In Section 5, we illustrate the expressiveness of the logic of explicit common belief by using it to formalize an example of coordination between robotic agents. In Section 6, we present a dynamic extension of the logic of explicit common belief in which private and public forms of information dynamics can be modeled.

BACKGROUND

This section presents the language and the semantics for agents' individual beliefs of both explicit and implicit type introduced in [START_REF] Lorini | Rethinking epistemic logic with belief bases[END_REF].

Language

Assume a countably infinite set of atomic propositions Atm = {p, q, . . .} and a finite set of agents Agt = {1, . . . , n}. We define the language in two steps. First, define the language L 0 by:

L 0 def = α ::= p | ¬α | α 1 ∧ α 2 | △ i α,
where p ranges over Atm and i ranges over Agt. L 0 is the language for representing explicit beliefs. The formula △ i α is read "agent i has the explicit belief that α". The language L extends L 0 and is defined by:

L def = φ ::= α | ¬φ | φ 1 ∧ φ 2 | 2 i φ,
where α ranges over L 0 and i ranges over Agt. The other Boolean constructions ⊤, ⊥, ∨, → and ↔ are defined from α, ¬ and ∧ in the standard way. The formula 2 i φ is read "agent i implicitly believes that φ". The abbreviation 3 i φ def = ¬2 i ¬φ defines the concept of belief compatibility. The formula 3 i φ has to be read "φ is compatible with agent i's explicit beliefs".

Belief Base Semantics

The formal semantics for the language L exploit belief bases. Unlike the standard Kripke semantics in which possible worlds and epistemic alternatives are primitive, they are here defined from the primitive concept of belief base.

Definition 1 (State).

A state is a tuple B = (B i ) i ∈Agt , V where B i ⊆ L 0 is agent i's belief base, and V ⊆ Atm is the actual environment. The set of all states is noted S.

The following definition specifies truth conditions for formulas in the sublanguage L 0 . Definition 2 (Satisfaction relation).

Let B = (B i ) i ∈Agt , V ∈ S. Then, B |= p ⇐⇒ p ∈ V , B |= ¬α ⇐⇒ B ̸ |= α, B |= α 1 ∧ α 2 ⇐⇒ B |= α 1 and B |= α 2 , B |= △ i α ⇐⇒ α ∈ B i .
Observe in particular the set-theoretic interpretation of the explicit belief operators in the previous definition: agent i has the explicit belief that α if and only if α is included in her belief base.

States satisfying the property of belief correctness (BC) are of particular interest, namely, states in which agents' explicit beliefs are correct. Definition 3 (Belief correct state). Let B = (B i ) i ∈Agt , V be a state. We say it satisfies belief correctness (BC) if and only if, for every i ∈ Agt and for every α ∈ L 0 , if α ∈ B i then B |= α. The set of states satisfying property BC is noted S BC .

The following definition introduces the notion of doxastic alternative.

Definition 4 (Doxastic alternatives). Let i ∈ Agt. Then, R i is the binary relation on the set S such that, for all B = (B i ) i ∈Agt , V ,

B ′ = (B ′ i ) i ∈Agt , V ′ ∈ S: BR i B ′ if and only if ∀α ∈ B i : B ′ |= α .
BR i B ′ means that B ′ is a doxastic alternative for agent i at B, that is to say, B ′ is a state that at B agent i considers possible. The idea of the previous definition is that B ′ is a doxastic alternative for agent i at B if and only if, B ′ satisfies all facts that agent i explicitly believes at B.

A multi-agent belief model (MAB), or simply model, is defined to be a state supplemented with a set of states, called context. The context Cxt is not necessarily equal to the set of all states S, since there could be states in S incompatible with the general "laws of the domain" and, consequently, with the agents' epistemic states. For example, we might want to exclude from the context Cxt all states in which the propositions "1+1=2" and "1+1=3" are true concomitantly.

(B, Cxt) |= α ⇐⇒ B |= α, (B, Cxt) |= 2 i φ ⇐⇒ ∀B ′ ∈ Cxt : if BR i B ′ then (B ′ , Cxt) |= φ.

Axiomatics and Complexity

In [START_REF] Lorini | Rethinking epistemic logic with belief bases[END_REF]Def. 13], the logic LDA (Logic of Doxastic Attitudes) is defined as follows.

Definition 8 (LDA). LDA is the extension of classical propositional logic by the following axioms and rule of inference:

(2 i φ ∧ 2 i (φ → ψ )) → 2 i ψ (K 2 i ) △ i α → 2 i α (Int △ i ,2 i ) φ 2 i φ (Nec 2 i )
Logic LDA T 2 i extends LDA by the following additional axiom:

2 i φ → φ. (T 2 i )
K 2 i and Nec 2 i are, respectively, the K axiom and the rule of necessitation for implicit belief. Int △ i ,2 i is the "bridge" axiom between explicit and implicit belief, while T 2 i is the T axiom for correct implicit belief. In [START_REF] Lorini | Rethinking epistemic logic with belief bases[END_REF]Theorem 3], it is proved that LDA (resp. LDA T 2 i ) is sound and complete for class M (resp. M BC ). It is also proved that satisfiability checking for formulas in L relative to class M (resp. M BC ) is PSPACE-complete [START_REF] Lorini | Rethinking epistemic logic with belief bases[END_REF]Theorem 6].

IMPLICIT COMMON BELIEF

In this section, we study a novel extension of the logic of explicit and implicit individual belief by implicit common belief. The latter is the standard notion of common belief in the literature [START_REF] Fagin | Reasoning about Knowledge[END_REF].

Language and Semantics

We extend the language L by the implicit shared belief operator 2 J φ and implicit common belief operator 2 * J and name L 2 *

J the resulting language. We define it as follows:

L 2 * J def = φ ::= α | ¬φ | φ 1 ∧ φ 2 | 2 i φ | 2 J φ | 2 *
J φ, with α ranging over L 0 , i ranging over Agt and J over the set of non-empty sets of agents (alias coalitions) 2 Agt * = 2 Agt \ {∅}.

Formula 2 J φ has to be read "the agents in J share the implicit belief that φ", whereas 2 * J φ has to be read "the agents J have the implicit common belief that φ". Before giving a semantic interpretation of the implicit shared and common belief operator, we define the mutual belief operator inductively as follows:

2 0 J φ def = φ, 2 k+1 J φ def = 2 J 2 k J φ for k ≥ 0.
The implicit shared and common belief operator are interpreted relative to a multi-agent belief model (B, Cxt) of Definition 5, as follows:

(B, Cxt) |= 2 J φ ⇐⇒ ∀i ∈ J : (B, Cxt) |= 2 i φ, (B, Cxt) |= 2 * J φ ⇐⇒ ∀k ∈ N * : (B, Cxt) |= 2 k J φ.
According to the previous semantic interpretations, implicit shared belief coincides with implicit belief of all agents, while implicit common belief is the same as k-order mutual belief for every k ∈ N * .

Alternative Kripkean Semantics

In [START_REF] Lorini | Rethinking epistemic logic with belief bases[END_REF] an alternative semantics for the language L is given. It extends the standard multi-relational Kripke semantics of epistemic logic by agents' belief bases. We here use it for interpreting the language L 2 *

J and show that it has the same set of validities as the belief base semantics.

Definition 9 (Notional doxastic model

). A notional doxastic model (NDM) is a tuple M = (W , D, N, V) where: • W is a set of worlds, • D : Agt × W -→ 2 L 0 is a doxastic function, • N : Agt × W -→ 2 W is a notional function, • V : Atm -→ 2 W is a valuation function,
and such that, given the following inductive definition of the semantic interpretation of formulas L 2 *

J relative to a pair (M, w) with w ∈ W :

(M, w) |= p ⇐⇒ w ∈ V(p), (M, w) |= ¬φ ⇐⇒ (M, w) ̸ |= φ, (M, w) |= φ ∧ ψ ⇐⇒ (M, w) |= φ and (M, w) |= ψ , (M, w) |= △ i α ⇐⇒ α ∈ D(i, w), (M, w) |= 2 i φ ⇐⇒ ∀v ∈ N (i, w) : (M, v) |= φ, (M, w) |= 2 J φ ⇐⇒ ∀i ∈ J : (M, w) |= 2 i φ, (M, w) |= 2 * J φ ⇐⇒ ∀k ∈ N * : (M, w) |= 2 k J φ.
it satisfies the following condition, for all i ∈ Agt and for all w ∈ W :

(C1) N (i, w) = α ∈ D(i,w ) ||α || M , with ||α || M = {v ∈ W : (M, v) |= α }.
We say that M satisfies belief correctness (BC) if the following condition holds, for all i ∈ Agt and for all w ∈ W : (C2) w ∈ N (i, w). The class of NDMs is noted NDM, while the class of NDMs satisfying property BC is noted NDM BC .

The pair (M, w) in the previous definition is called pointed NDM. For every agent i and for every world w, D(i, w) denotes agent i's set of explicit beliefs at w. The set N (i, w) is called agent i's set of notional worlds at world w, where the term 'notional' is borrowed from [START_REF] Dennett | The Intentional Stance[END_REF][START_REF] Dennett | Précis of the intentional stance[END_REF] (see, also, [START_REF] Konolige | A deduction model of belief[END_REF]). As Condition C1 indicates, an agent's notional world is a world at which all its explicit beliefs are true. Condition C2 is the counterpart of belief correctness for NDMs.

As usual, we say that formula φ ∈ L is valid relative to the class NDM (resp. NDM BC ) if and only if, for every M = (W , D, N, V) ∈ NDM (resp. M = (W , D, N, V) ∈ NDM BC ) and for every w ∈ W , we have (M, w) |= φ. We say that φ is satisfiable for the class NDM (resp. NDM BC ) if and only if ¬φ is not valid for the class NDM (resp. NDM BC ).

Quasi-notional doxastic models (quasi-NDMs) are like notional doxastic models of Definition 9 except that Constraint C1 is replaced by the following weaker constraint:

(C1 * ) N (i, w) ⊆ α ∈ D(i,w ) ||α || M .
The class of quasi-NDMs is noted QNDM, whereas the class of quasi-NDMs satisfying property BC is noted QNDM BC .

A NDM (resp. quasi-NDM) M = (W , D, N, V) is said to be finite if and only if W , D(i, w) and V ← (w) = {p ∈ Atm : w ∈ V(p)} are finite sets for every i ∈ Agt and for every w ∈ W . The class of finite NDMs (resp. finite quasi-NDMs) is noted finite-NDM (resp. finite-QNDM). The class of finite NDMs (resp. finite quasi-NDMs) satisfying property BC is noted finite-NDM BC (resp. finite-QNDM BC ).

The following theorem highlights that the five semantics for the language L 2 * J are all equivalent. Theorem 1. Let φ ∈ L 2 * J . Then, the following five statements are equivalent.

(1) φ is satisfiable relative to class QNDM (resp. QNDM BC ), (2) φ is satisfiable relative to class finite-QNDM (resp. finite-QNDM BC ), (3) φ is satisfiable relative to class finite-NDM (resp. finite-NDM BC ), (4) φ is satisfiable relative to class NDM (resp. NDM BC ), [START_REF] Baltag | The Logic of Public Announcements, Common Knowledge and Private Suspicions[END_REF] φ is satisfiable relative to class M (resp. M BC ).

Sketch of Proof. We use a filtration method to prove that (1) implies [START_REF] Aumann | Agreeing to Disagree[END_REF]. In order to prove that (2) implies (3), we use a technique which consists in enlarging an agent i's belief base at a world w (i.e., D(i, w)) so that agent i's set of doxastic alternatives at w (i.e., N (i, w)) shrinks and perfectly coincides with the set of worlds in which all formulas in agent i's belief base at w are true, as required by Condition C1 in Definition 9. Finally, we prove that (4) and ( 5) are equivalent. The right-to-left direction is easy since from a MAB we can easily construct the corresponding NDM. The left-to-right direction is less immediate. Indeed, a NDM can be redundant, i.e., it can contain two different worlds with the same valuation of propositional atoms and the same belief bases for the agents. We have to transform a possibly redundant NDM into a non-redundant one. From a non-redundant NDM we can construct the corresponding MAB which satisfies the same formulas. ■

Axiomatics

The logic LDA-ICB (Logic of Doxastic Attitudes and Implicit Common Belief) and its variant LDA-ICB T 2 i extend the logics LDA and LDA T 2 i by principles for implicit common belief taken from [START_REF] Halpern | A guide to completeness and complexity for modal logics of knowledge and belief[END_REF]. They are defined as follows.

Definition 10 (LDA-ICB). LDA-ICB is the extension of LDA defined in Definition 8 by the following axioms and rule of inference:

2 J φ ↔ i ∈J 2 i φ (Def 2 J ) 2 * J φ → 2 J (φ ∧ 2 * J φ) (FP 2 * J ) ψ → 2 J (φ ∧ ψ ) ψ → 2 * J φ (Ind 2 * J ) Logic LDA-ICB T 2 i extends LDA-ICB by Axiom T 2 i of Definition 8.
Axiom FP 2 * J is the so-called fixpoint axiom for implicit common belief, while rule Ind 2 * J is the so-called induction rule (alias least fixpoint rule).

As usual, for every φ ∈ L 2 * J , we write ⊢ LDA-ICB φ to mean that φ is deducible in LDA-ICB, that is, there is a sequence of formulas (φ 1 , . . . , φ m ) such that:

• φ m = φ, and is an instance of some inference rule of LDA-ICB. We say that the set of formulas Γ from L

• for every 1 ≤ k ≤ m,
2 * J is LDA-ICB-consistent if there are no formulas φ 1 , . . . , φ m ∈ Γ such that ⊢ LDA-ICB (φ 1 ∧ . . . ∧ φ m ) → ⊥. Moreover, φ is LDA-ICB-consistent if {φ} is LDA-ICB-consistent.
Definitions of LDA-ICB T 2 i -deducibility and LDA-ICB T 2 i -consistency are analogous. Definitions of strong completeness and weak completeness are the usual ones from modal logic (see, e.g., [START_REF] Blackburn | Modal Logic[END_REF]): a logic Λ is said to be strongly complete with respect to a class of structures S iff every Λ-consistent set of formulas is satisfiable on some element of S. It is said to be weakly complete with respect to S iff every finite Λ-consistent set of formulas is satisfiable on some element of S.

We know for sure that the logics LDA-ICB and LDA-ICB T 2 i are not strongly complete. Indeed, they do not satisfy the compactness property, i.e., the fact that for every set of L

2 * J -formulas Γ, if Γ is LDA-ICB-consistent (resp. LDA-ICB T 2 i -consistent) then there is (B, Cxt) ∈ M (resp. (B, Cxt) ∈ M BC ) such that (B, Cxt) |= ψ , for every ψ ∈ Γ. For example, let Γ = {¬2 * J p} ∪ {2 i 1 . . . 2 i k p : k ∈ N * , i 1 , . . . , i k ∈ J }. Γ is LDA-ICB-consistent, but there is no (B, Cxt) ∈ M such that (B, Cxt) |= ψ ,
for every ψ ∈ Γ. However, LDA-ICB and LDA-ICB T 2 i are weakly complete. Theorem 2. The logic LDA-ICB is sound and weakly complete for the class M, and the logic LDA-ICB T 2 i is sound and weakly complete for the class M BC . Sketch of Proof. Soundness is a routine exercise. Thanks to Theorem 1, it is sufficient to prove completeness for the quasi-notional model semantics of Section 3.2. We prove the latter adapting the proof of Theorem 4.3 in [START_REF] Halpern | A guide to completeness and complexity for modal logics of knowledge and belief[END_REF]. Our proof uses a canonical model argument in which worlds in the canonical model are not maximally consistent sets of all formulas but rather finite maximally consistent subsets of set Sub * (φ) including all subformulas of an input formula φ, their negations and a finite "epistemic theory" capturing the interrelation between implicit individual and common belief. The latter is necessary to prove that the canonical model so constructed belongs to the class QNDM (resp. QNDM BC ). ■

In Section 4, we will replace implicit common belief by explicit common belief. We will show that the resulting logic satisfies the compactness property and is strongly complete. Moreover, it is computationally simpler than the logic of implicit common belief.

Complexity

It is easy to show that satisfiability checking for formulas in L 2 * J relative to model classes M and M BC is EXPTIME-hard. Indeed, LDA-ICB is a conservative extension of the logic of common belief with base logic K n for individual belief, while LDA-ICB T 2 i is a conservative extension of the logic of common belief with base logic KT n for individual belief. These two logics are known to be EXPTIME-hard for n > 1 [START_REF] Halpern | A guide to completeness and complexity for modal logics of knowledge and belief[END_REF]. As the following theorem indicates, EXPTIME is also a upper bound. Theorem 3. Let n > 1. Then, satisfiability checking for formulas in L 2 * J relative to the class M (resp. M BC ) is in EXPTIME. Sketch of Proof. Given a formula φ, we define a variant of its set of sub-formulas. Then, we consider the set of maximally consistent subsets of such a set, which are intended to be the worlds of a canonical model. We set an algorithm which deletes some of those states, until we can effectively obtain a quasi-NDM. Then, we can simply check if φ is in one of the remaining sets to know if φ is satisfiable. Moreover, the algorithm can be executed in exponential time in the size of φ. ■

For n = 1, logics LDA-ICB and LDA-ICB T 2 i are clearly PSPACEcomplete, since they coincide with the single-agent logics of explicit and implicit belief with base logics K and KT for implicit belief which are known to be PSPACE-complete [START_REF] Lorini | Rethinking epistemic logic with belief bases[END_REF].

EXPLICIT COMMON BELIEF

In Section 3, we have presented the logic of explicit and implicit individual belief, and implicit common belief. The aim of this section is study a new concept of collective attitude of explicit type: explicit common belief. Explicit common belief is the collective counterpart of explicit individual belief. We will use symbols of type ▽ J to represent it. We stipulate that there is an explicit common belief that α if everyone explicitly believes that α, and everyone explicitly believes that there is an explicit common belief that α. The latter highlights the public nature of explicit common belief: explicit common belief implies the agents' awareness of its existence. This is similar to the publicity condition of the concept of co-presence, as defined by Clark & Marshall [START_REF] Clark | Definite reference and mutual knowledge[END_REF]. For example, suppose Ann, Bob, Mary and Paul are sitting at a table on which there is a box. This is a situation of co-presence: each agent correctly believes that there is a box on the table and, moreover, that they are jointly seeing that there is a box on the table so that they commonly believe so.

Language and Semantics

We name L ▽ J 0 the language which results from extending L 0 with operators for explicit shared belief and explicit common belief. It is defined as follows:

L ▽ J 0 def = α ::= p | ¬α | α 1 ∧ α 2 | △ i α | △ J α | ▽ J α,
with p ranging over Atm and i ranging over Agt. Formula △ J α has to be read "the agents in J share the explicit belief that α", whereas ▽ J α has to be read "the agents in J have the explicit common belief that α". The following language L ▽ J extends language L ▽ J 0 by implicit individual belief operators:

L ▽ J def = φ ::= α | ¬φ | φ 1 ∧ φ 2 | 2 i φ,
with α ranging over L ▽ J 0 and i ranging over Agt. In order to interpret the new language L ▽ J 0 , we need to slightly redefine the notion of state of Definition 1 by assuming that an agent i's belief base is now a set of formulas from L ▽ J 0 . The explicit shared belief and explicit common belief operators are interpreted relative to a state B = (B i ) i ∈Agt , V so redefined, as follows:

B |= △ J α ⇐⇒ ∀i ∈ J : α ∈ B i , B |= ▽ J α ⇐⇒ ∀i ∈ J : α ∈ B i and ▽ J α ∈ B i .
Notice, in particular, the semantic interpretation of the explicit common belief operator: explicit common belief that α is the same as everyone having the explicit belief that α and that there is explicit common belief that α.

Clearly, implicit common belief does not necessarily imply explicit common belief. Indeed, for every J ∈ 2 Agt * , there exists (B, Cxt) ∈ M such that:

(B, Cxt) |= 2 k J p for every k ∈ N * and (B, Cxt) ̸ |= ▽ J p.
An example of such a MAB is the following:

Cxt = {B, B ′ }, B = (B i ) i ∈Agt , V and B ′ = (B i ) i ∈Agt , V ′
, where B i = {q, q → p} for every i ∈ Agt, V = {q} and V ′ = {p, q}. On the contrary, explicit common belief necessarily implies implicit common belief, as indicated by the following validity, for every J ∈ 2 Agt * :

|= ▽ J α → 2 k J α for every k ∈ N * .
Moreover, explicit common belief implies implicit common belief about explicit shared belief, as well as implicit common belief about explicit common belief. For every J ∈ 2 Agt * , we have

|= ▽ J α → 2 k J △ J α for every k ∈ N * , |= ▽ J α → 2 k J ▽ J α for every k ∈ N * .
Like implicit common belief, the explicit common belief operator can alternatively be interpreted relative to notional doxastic models (NDMs) introduced in Section 3.2. To do so, we simply need to replace the semantic interpretation for the modal operator 2 * J in Definition 9 by the following semantic interpretation for the modal operators △ J and ▽ J :

(M, w) |= △ J α ⇐⇒ ∀i ∈ J : α ∈ D(i, w), (M, w) |= ▽ J α ⇐⇒ ∀i ∈ J : α ∈ D(i, w) and ▽ J α ∈ D(i, w),
where (M, w) is a pointed NDM.

The following theorem is the counterpart of Theorem 1 for the language of explicit common belief. Theorem 4. Let φ ∈ L ▽ J . Then, the following five statements are equivalent:

(1) φ is satisfiable relative to class QNDM (resp. QNDM BC ),

(2) φ is satisfiable relative to class finite-QNDM (resp. finite-QNDM BC ), (3) φ is satisfiable relative to class finite-NDM (resp. finite-NDM BC ), (4) φ is satisfiable relative to class NDM (resp. NDM BC ), [START_REF] Baltag | The Logic of Public Announcements, Common Knowledge and Private Suspicions[END_REF] φ is satisfiable relative to class M (resp. M BC ). Sketch of Proof. The proof is similar to that of Theorem 1. ■

Axiomatics

The following definition introduces the logic LDA-ECB (Logic of Doxastic Attitudes and Explicit Common Belief) and its variant LDA-ECB T 2 i for correct beliefs.

Definition 11 (LDA-ECB). LDA-ECB is the extension of LDA defined in Definition 8 by the following axioms:

△ J α ↔ i ∈J △ i α (Def △ J ) ▽ J α ↔ (△ J α ∧ △ J ▽ J α) (Refl ▽ J ) The logic LDA-ECB T 2 i extends LDA-ECB by Axiom T 2 i of Defini- tion 8.
Axiom Def △ J defines explicit shared belief from the explicit individual belief of all agents. Axiom Refl ▽ J is the "publicity" axiom for explicit common belief. Definitions of LDA-ECB-deducibility, LDA-ECB T 2 i -deducibility, LDA-ECB-consistency, LDA-ECB T 2 iconsistency, strong and weak completeness for LDA-ECB and LDA-ECB T 2 i are analogous to the ones for logics LDA-ICB and LDA-ICB T 2 i given in Section 3.3. Unlike logics LDA-ICB and LDA-ICB T 2 i , logics LDA-ECB and LDA-ECB T 2 i satisfy the compactness property and, as the following theorem indicates, are strongly complete. Theorem 5. The logic LDA-ECB is sound and strongly complete for the class M, and the logic LDA-ECB T 2 i is sound and strongly complete for the class M BC . Sketch of Proof. Soundness is a routine exercise. Thanks to Theorem 4, it is sufficient to prove completeness for the class QNDM (resp. QNDM BC ). Unlike the proof of Theorem 5, we prove the latter by standard canonical model argument: worlds in the canonical model are (infinite) maximally consistent sets of formulas. ■

Complexity

It is easy to show that satisfiability checking for formulas in L ▽ J relative to model classes M and M BC is PSPACE-hard. Indeed, LDA-ECB is a conservative extension of the multi-modal logic K n , while LDA-ICB T 2 i is a conservative extension of the multimodal logic KT n . These two logics are known to be PSPACE-hard, even for the case n = 1 [START_REF] Halpern | A guide to completeness and complexity for modal logics of knowledge and belief[END_REF]. As the following theorem indicates, PSPACE is also a upper bound. Theorem 6. Satisfiability checking for formulas in L ▽ J relative to the class M (resp. M BC ) is in PSPACE.

Sketch of Proof. We can use the tableau method. To check the satisfiablity of a given formula φ, the goal is to construct a tableau (a concept similar to that of a quasi-NDM) which satisfies φ at its root. Then φ is satisfiable if and only if the construction can be completed. The construction algorithm can be executed with a quadratic memory in the size of the formula φ. ■

EXAMPLE

We illustrate the language L ▽ J with the help of an example of dichotomous coordination game in which agents can achieve their common goal only by making the same choice. In a coordination game, each coordination point is a Nash equilibrium and the general problem is to select one of them in order to ensure that the common goal is effectively achieved.

To this aim, we assume the set of atomic propositions Atm includes special atoms of type pl i [a] with i ∈ Agt and a ∈ Act, where Act is a finite set of action symbols. Atom pl i [a] has to be read "agent i plays (or chooses) action a". The agents in Agt are said to play a dichotomous coordination game with common goal φ G ∈ L ▽ J and action repertoire X ⊆ Act, noted Coord(φ G ,X ), if and only if (i) each agent will choose exactly one action from X , and (ii) the agents will achieve their common goal φ G if and only if they coordinate by choosing the same action from X . In formal terms:

Coord(φ G ,X ) def = φ G ↔ ( a ∈X i ∈Agt pl i [a]) ∧ i ∈Agt ( a ∈X pl i [a]) ∧ a,b ∈X :a b (pl i [a] → ¬pl i [b]) .
In our example, we suppose Agt = {1, 2} and {mr, ml} ⊆ Act. Agents 1 and 2 are two mobile robots standing in front of a narrow passage on its opposite sides, as illustrated in Figure 1. An agent or decide to move forward keeping to the left (action ml). The two agents can only coordinate by making the same choice. Indeed, if they choose different actions (e.g., agent 1 chooses mr while agent 2 chooses ml), they will miscoordinate and, consequently, collide (coll). We consider a number of hypotheses that agents 1 and 2 could share in the coordination scenario:

α 1 def = coll ↔ (pl 1 [mr] ∧ pl 2 [ml]) ∨ (pl 1 [ml] ∧ pl 2 [mr]) , α 2 def = i ∈Agt (pl i [mr] ∨ pl i [ml]), α 3 def = i ∈Agt (pl i [mr] → ¬pl i [ml]).
According to hypothesis α 1 , agents 1 and 2 will collide if and only if they choose different actions. Hypotheses α 2 and α 3 just state that an agent will choose exactly one action from {mr, ml}.

We can prove that explicit common belief of every hypothesis in {α 1 , α 2 , α 3 } implies implicit common belief of facing a coordination problem. Indeed, for every k ∈ N * , we have:

|= M h ∈ {1,2,3} ▽ Agt α h → 2 k
Agt Coord(¬coll,{mr, ml}).

In a coordination game like the one depicted in Figure 1, there are different ways to secure coordination. The bottom-up solution relies on repeated interaction: by playing the game several times the agents can learn to coordinate in a such a way that a social convention between them is established. According to Lewis' seminal theory [START_REF] Lewis | Convention: a philosophical study[END_REF], for a social convention to exist in a group of agents, the agents in the group must form a common belief that everyone in the group will conform to the convention by playing the corresponding action in the selected equilibrium. The top-down solution is by means of external norms that induce agents to play a specific equilibrium in the game. For example, in the case of the coordination game of Figure 1 the obligation to choose action mr could be enforced on agents 1 and 2 to secure coordination among them and to make the agents have a common belief of this, under the assumption that they are obedient and will comply with the obligation.

We are going to show how such a top-down mechanism can be formally represented in the language L ▽ J . The first step in the analysis consists in assuming that the set of atomic propositions Atm includes special atoms of type obed i and obl[a] for every i ∈ Agt and a ∈ Act that have to read, respectively, "agent i is norm compliant (or obedient)" and "it is obligatory to perform action a". As a second step, we define the following hypothesis which specifies the meaning of the notion of norm compliant agent:

α 4 def = i, j ∈Agt:i j obed i ↔ a ∈Act (△ i obl[a] ∧ △ i obed j ) → pl i [a] .
According to hypothesis α 4 , an agent is norm compliant (or obedient) if and only if, if it explicitly believes that the other agent is also norm compliant and that there is an obligation to perform action a, then it will choose action a. This captures a reciprocal form of obedience: an agent is willing to comply with the obligation only if it believes that the other agent is willing too.

For every k ∈ N * , we have the following two validities which highlight the conditions under which obligations determine coordination and common belief about coordination:

|= M i ∈Agt ▽ Agt obed i ∧ ▽ Agt α 4 → a ∈Act 2 k Agt △ Agt obl[a] → (pl 1 [a] ∧ pl 2 [a]) , (2)
|= M i ∈Agt ▽ Agt obed i ∧ h ∈ {1,3,4} ▽ Agt α h → a ∈Act 2 k Agt △ Agt obl[a] → ¬coll . (3)
According to validity (2) if the agents in the coordination game of Figure 1 have explicit common belief that each of them is norm compliant and have explicit common belief of what norm compliance means, as specified by hypothesis α 4 , then they have implicit common belief that if each of them is aware that it is obligatory to perform a certain action then they will perform the obligatory action. According to validity (3) if the agents in the coordination game of Figure 1 have explicit common belief that each of them is norm compliant and have explicit common belief of each hypothesis in {α 1 , α 3 , α 4 }, then they have implicit common belief that if each of them is aware that it is obligatory to perform a certain action then they will not collide.

DYNAMIC EXTENSION

In this section, we extend the language L ▽ J by belief expansion operations. Such an extension allows us to represent private and public forms of information dynamics in a multi-agent domain. We name L ▽ J ,+ J the resulting language and define it as follows:

L ▽ J ,+ J def = φ ::= α | ¬φ | φ 1 ∧ φ 2 | 2 i φ | [+ J α]φ,
where α ranges over L ▽ J 0 , i ranges over Agt and J ranges over 2 Agt * . The formula [+ J α]φ has to be read "φ holds after every agent in J has expanded her belief base with α". Events of type + J α are generically named 'informative events'.

The dynamic operator [+ J α] has the following semantic interpretation relative to MABs of Definition 5. Let B = (B i ) i ∈Agt , V ∈ S and let (B, Cxt) ∈ M. Then:

(B, Cxt) |= [+ J α]φ ⇐⇒ (B + J α , Cxt) |= φ, with V + J α = V , B + J α i = B i ∪ {α } for i ∈ J , and B + J α j = B j for j J .
Intuitively speaking, belief expansion by all agents in J with α simply consists in every agent in J adding the information α to her belief base, while all agents outside J keep their beliefs unchanged.

The following proposition provides reduction principles which allow us to transform every formula of the language L ▽ J ,+ J into an equivalent formula of the language L ▽ J . Proposition 1. The following formulas are valid for class M:

[+ J α]p ↔ p [+ J α]¬ψ ↔ ¬[+ J α]ψ [+ J α](ψ 1 ∧ ψ 2 ) ↔ ([+ J α]ψ 1 ∧ [+ J α]ψ 2 ) [+ J α]△ i β ↔ △ i β if i J or α β [+ J α]△ i α ↔ ⊤ if i ∈ J [+ J α]△ J ′ β ↔ △ J ′ β if α β [+ J α]△ J ′ α ↔ △ J ′ \J α [+ J α]▽ J ′ β ↔ (△ J ′ β ∧ △ J ′ \J ▽ J ′ β) if α = ▽ J ′ β [+ J α]▽ J ′ β ↔ (△ J ′ \J β ∧ △ J ′ ▽ J ′ β) if α = β [+ J α]▽ J ′ β ↔ ▽ J ′ β if α ▽ J ′ β and α β [+ J α]2 i φ ↔ 2 i φ if i J [+ J α]2 i φ ↔ 2 i (α → φ) if i ∈ J
It is easy to define a a mapping red which iteratively applies the valid equivalences of Proposition 1 and transforms any formula φ in L ▽ J ,+ J into an equivalent formula red(φ) in L ▽ J of polynomial size.

As a consequence, thanks to Theorem 6, the following complexity result can be proved. Theorem 7. Satisfiability checking for formulas in L ▽ J ,+ J relative to the class M is PSPACE-complete.

Let us briefly explore the modeling aspects of the language L ▽ J ,+ J . In this language, we can represent a variety of private and public information dynamics. Before defining them, we introduce the following abbreviation:

[+ J 1 α 1 ; . . . ; + J k α k ]φ def = [+ J 1 α 1 ] . . . [+ J k α k ]φ,
where [+ J 1 α 1 ; . . . ; + J k α k ]φ means "φ holds after the informative events + J 1 α 1 , . . . , + J k α k take place consecutively". The following validity captures a commutativity property for informative events:

|= M [+ J 1 α 1 ; . . . ; + J k α k ]φ ↔ [σ (+ J 1 α 1 ); . . . ; σ (+ J k α k )]φ, ( 4
)
where σ is any permutation of the set {+ J 1 α 1 , . . . , + J k α k }. This property is a consequence of the semantics of informative events based on belief expansion. Since events + J 1 α 1 , . . . , + J k α k simply expand the belief bases of the agents in J 1 , . . . , J k , the order in which they occur does not matter. This is different from public announcement logic PAL [START_REF] Plaza | Logics of public communications[END_REF] in which the order of announcements can play a role. The following are three examples of informative events of private, semi-private and public form:

priv(J , α) def = + J α, publ(J , α) def = + J α; + J ▽ J α, semiPriv(J , J ′ , α) def = + J α; + J ′ (△ J α ∨ △ J ¬α).
The event priv(J , α) consists in every agent in J privately learning that α, whereas publ(J , α) means that all agents in J publicly learn that α. Finally, semiPriv(J , J ′ , α) means that all agents in J privately learn that α, while the agents in J ′ learn that the agents in J has just learnt whether α is true. An example of the latter is the situation of Ann (A), Bob (B), Mary (M) and Paul (P) sitting at a table on which there is an empty box. In the initial situation, they do not know whether the box is empty since they cannot see what is inside it. Mary and Paul look inside the box in front of everybody. Therefore, Mary and Paul privately learn that the box is empty. Moreover, Ann, Bob, Mary and Paul learn that Mary and Paul have just learnt whether the box is empty. The latter event is represented by semiPriv({M, P }, {A, B, M, P }, boxEmpty). Note that publ(J , α) and semiPriv(J , J ′ , α) are definable from priv(J , α). Specifically, publ(J , α) is the same as priv(J , α) followed by priv(J , ▽ J α) and semiPriv(J , J ′ , α) is the same as priv(J , α) followed by priv(J ′ , △ J α∨ △ J ¬α). In other words, publicity and semi-privateness are defined from privateness. For instance, publicly learning that α corresponds to the fact that every agent in α privately learns that α and that α has become common belief. The following are interesting properties of private, semi-private and public informative events:

|= M [priv(J , α)] i ∈J 2 i α, (5)
|= M [semiPriv(J , J ′ , α)]

i ∈J, j ∈J ′

2 i α ∧ 2 j (2 i α ∨ 2 i ¬α) , (6)
|= M [publ(J , α)]2 k J α for every k ∈ N * ,

|= M [publ(J , α)]2 k J △ J α for every k ∈ N * ,

|= M [publ(J , α)]2 k J ▽ J α for every k ∈ N * .

Note in particular validities ( 7), ( 8) and ( 9): after having publicly learnt that α, the agents will have the implicit common belief of α, that they share the belief of α and that they have the explicit common belief of α. For example, going back to the example of Section 5, we have the following validity, for every k ∈ N * :

|= M i ∈Agt ▽ Agt obed i ∧ ▽ Agt α 4 → publ Agt, obl[a] 2 k Agt (pl 1 [a] ∧ pl 2 [a]). (10)
This guarantees that if the agents in the coordination game of Figure 1 have explicit common belief that each of them is norm compliant and of what norm compliance means then, by publicly learning that action a is obligatory, they form the implicit common belief that each of them will perform the obligatory action.

CONCLUSION

Let's take stock. We have studied two logics of collective attitudes: the logic of implicit common belief and the logic of explicit common belief. We have provided axiomatic and complexity results for both logics. While satisfiability checking for the former logic is EXPTIME-hard, it is in PSPACE for the latter. Our complexity result relies on a tableau method. Future work will be devoted to find a polysize reduction of satisfiability checking for the logic of explicit common belief to QBF. This will open up the possibility of exploiting existing efficient QBF solvers for automated reasoning about collective attitudes in multi-agent systems. We also plan to explore the connection between the dynamic extension we presented in Section 6 and dynamic epistemic logic (DEL), namely the extension of epistemic logic by so-called event models [START_REF] Baltag | The Logic of Public Announcements, Common Knowledge and Private Suspicions[END_REF][START_REF] Van Ditmarsch | Dynamic Epistemic Logic[END_REF]. In particular, we would like to precisely characterize the subclass of event models that are captured by our update semantics. Since full DEL is known to be NEXPTIME-hard [START_REF] Aucher | On the complexity of dynamic epistemic logic[END_REF], we know for sure that the latter is necessarily a strict subclass. In this paper, we have studied the logic of implicit common belief and the logic of explicit common belief separately. In future work, we will explore the axiomatic properties and complexity of the unified language including both implicit and explicit common belief. Our conjecture is that satisfiability checking for such rich epistemic language remains in EXPTIME.

Definition 5 (

 5 Multi-agent belief model). A multi-agent belief model (MAB) is a pair (B, Cxt), where B ∈ S and Cxt ⊆ S. The class of MABs is noted M. Note that in Definition 5 we do not require B ∈ Cxt. The following definition extends Definition 2 to the full language L. Its formulas are interpreted with respect to MABs. (We omit Boolean cases, as they are defined in the usual way.) Definition 6 (Satisfaction relation (cont.)). Let (B, Cxt) ∈ M. Then:

1 Figure 1 :

 11 Figure 1: Example of coordination game

  It is easy to verify that (B, Cxt) satisfies BC iff B ∈ Cxt and, for every i ∈ Agt, R i ∩ (Cxt × Cxt) is reflexive.Let φ ∈ L. We say that φ is valid relative to the class M (resp. M BC ), noted |= M φ (resp. |= M BC φ), if and only if, for every (B, Cxt) ∈ M (resp. (B, Cxt) ∈ M BC ) we have (B, Cxt) |= φ. We say that φ is satisfiable for the class M (resp. M BC ) if and only if ¬φ is not valid for the class M (resp. M BC ).

	Main Track	AAMAS 2022, May 9-13, 2022, Online
	According to the previous definition, agent i implicitly believes
	that φ if and only if, φ is true at all states in the context that i
	considers possible.
	The notion of belief correctness can be lifted from states to
	models, as follows.
	Definition 7 (Belief correct MAB). Let (B, Cxt) ∈ M. We say
	it satisfies belief correctness (BC) if and only if (i) B ∈ Cxt, and (ii) all
	states in Cxt satisfy property BC of Definition 3. The class of MABs
	satisfying property BC is noted M BC .

  either φ k is an instance of one of the axiom schema of LDA-ICB or there are formulas φ k 1 , . . . , φ k t such that k 1 , . . . , k t < k and

φ k 1 , ...,φ k t φ k

Proc. of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022), P. Faliszewski, V. Mascardi, C. Pelachaud, M.E. Taylor (eds.), May 9-13, 2022, Online. © 2022 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.

ACKNOWLEDGMENTS

This work is supported by the ANR project CoPains ("Cognitive Planning in Persuasive Multimodal Communication"). Support from the ANR-3IA Artificial and Natural Intelligence Toulouse Institute is also acknowledged.