Thomas Ågotnes

LORI Conference 2025 Conference Paper

Intentionally Anonymous Public Announcements

• Thomas Ågotnes
• Rustam Galimullin
• Ken Satoh
• Satoshi Tojo

Abstract We formalise the notion of an intentionally anonymous public announcement in the tradition of public announcement logic. An anonymous announcement can be seen as in-between a public announcement from “the outside” (an announcement of \(\varphi \) ) and a public announcement by one of the agents a (an announcement of \(K_a\varphi \) ): we get more information than just \(\varphi \), but not (necessarily) about exactly who made it. In this paper we assume that it is common knowledge that the announcer intended to be anonymous. Like in the Russian Cards puzzle, with that assumption, anonymous announcements in fact reveal more information than without. We introduce an operator for intentionally anonymous announcements, and show that in several ways it all boils down to the notion of a “safe” announcement (again, similarly to Russian Cards). We model safety via a fixed-point operator that is similar to common knowledge. Main formal results include comparisons of expressivity and axiomatic completeness for a language expressing safety.

LORI Conference 2025 Conference Paper

Next-Time Coalition Logic

• Thomas Ågotnes
• Fengkui Ju

Abstract Coalition Logic (CL) can be seen as the next-time fragment of Alternating-time Temporal Logic (ATL). Modalities in ATL are combinations of strategy quantifiers and tense modalities “glued” together. In ATL* this requirement is relaxed, and the two types of modalities can be mixed freely, resulting in more expressive logics. That comes at a cost: for example, as far as we know, no complete axiomatisation of ATL* exists. In this paper we study the next-time fragment of ATL*: CL*. Like in ATL and unlike in CL, we must now consider strategies rather than just actions, and like in ATL* but unlike in ATL, it matters whether we use full-memory or just memoryless strategies. The question of whether CL* actually is more expressive than CL hinges on that choice. We characterise the relative expressive power of the two variants of CL* compared to CL, and give a sound and complete axiomatisation of CL* with full-memory strategies.

LORI Conference 2025 Conference Paper

The Modal Logic of n-State Frames

• Xiaolong Liang
• Yì N. Wáng
• Thomas Ågotnes

Abstract Modal logics often have the finite model property. However, for many applications the state space is not only finite, but of fixed size n for a positive number n. An example is reasoning about a social network where the relations can vary but the set of agents (corresponding to states) is fixed. In this paper we investigate the modal logic of frames with n states, for any positive integer n, in the basic modal language. This defines a family of modal logics parameterized by n. We give complete axiomatizations of many of these logics, and characterize the computational complexity of the basic logic.

LORI Conference 2023 Conference Paper

A Formal Analysis of Hollis' Paradox

• Thomas Ågotnes
• Chiaki Sakama

Abstract In Hollis’ paradox, A and B each chose a positive integer and whisper their number to C. C then informs them, jointly, that they have chosen different numbers and, moreover, that neither of them are able to work out who has the greatest number. A then reasons as follows: B cannot have 1, otherwise he would know that my number is greater, and by the same reasoning B knows that I don’t have 1. But then B also cannot have 2, otherwise he would know that my number is greater (since he knows I don’t have 1). This line of reasoning can be repeated indefinitely, effectively forming an inductive proof, ruling out any number – an apparent paradox. In this paper we formalise Hollis’ paradox using public announcement logic, and argue that the root cause of the paradox is the wrongful assumption that A and B assume that C’s announcement necessarily is successful. This resolves the paradox without assuming that C can be untruthful, or that A and B are not perfect reasoners, like other solutions do. There are similarities to the surprise examination paradox. In addition to a semantic analysis in the tradition of epistemic logic, we provide a syntactic one, deriving conclusions from a set of premises describing the initial situation – more in the spirit of the literature on Hollis’ paradox. The latter allows us to pinpoint which assumptions are actually necessary for the conclusions resolving the paradox.

JAAMAS Journal 2023 Journal Article

Quantifying over information change with common knowledge

• Thomas Ågotnes
• Rustam Galimullin

Abstract Public announcement logic (PAL) extends multi-agent epistemic logic with dynamic operators modelling the effects of public communication. Allowing quantification over public announcements lets us reason about the existence of an announcement that reaches a certain epistemic goal. Two notable examples of logics of quantified announcements are arbitrary public announcement logic (APAL) and group announcement logic (GAL). While the notion of common knowledge plays an important role in PAL, and in particular in characterisations of epistemic states that an agent or a group of agents might make come about by performing public announcements, extensions of APAL and GAL with common knowledge still haven’t been studied in detail. That is what we do in this paper. In particular, we consider both conservative extensions, where the semantics of the quantifiers is not changed, as well as extensions where the scope of quantification also includes common knowledge formulas. We compare the expressivity of these extensions relative to each other and other connected logics, and provide sound and complete axiomatisations. Finally, we show how the completeness results can be used for other logics with quantification over information change.

LORI Conference 2021 Conference Paper

Crossing Hands in the Russian Cards Problem

• Tor Hagland
• Thomas Ågotnes

Abstract The Russian Cards Problem has been extensively studied as an example of a problem of an unconditionally secure protocol where the sender and receiver are able to transmit secret information safely over a public non-secure channel without the secret being learned by a third party with access to the channel. Epistemic logic in general and public announcement logic in particular have been very useful in this study, as it involves careful analysis of subtle properties of nested knowledge. A long standing open problem is whether or not there exist protocols of length strictly greater than two for the original problem. In this paper we finally settle this problem, answering the question in the affirmative, by presenting a new solution to the original Russian Cards Problem that involves more than two steps. It starts with an initial announcement with so-called crossing hands, after which it is not common knowledge that the protocol can terminate in one more step.

LORI Conference 2021 Conference Paper

Dynamic Coalition Logic: Granting and Revoking Dictatorial Powers

• Rustam Galimullin
• Thomas Ågotnes

Abstract One of the classic formalisms for reasoning about multi-agent coalitional ability is coalition logic (CL). In CL it is possible to express what a coalition can achieve in the next step no matter what agents outside of the coalition do at the same time. We propose an extension of CL with dynamic operators that allow us to grant dictatorial powers to agents or to revoke them. In such a way we are able to reason about the dynamics of coalitional ability. We also discuss some logical properties of the proposed formalisms and compare their relative expressive power.

AAMAS Conference 2021 Conference Paper

Quantified Announcements and Common Knowledge

• Rustam Galimullin
• Thomas Ågotnes

Public announcement logic (PAL) extends multi-agent epistemic logic with dynamic operators modelling the effects of public communication. Allowing quantification over public announcements lets us reason about the existence of an announcement to reach a certain epistemic goal. Two notable examples of logics of quantified announcements are arbitrary public announcement logic (APAL) and group announcement logic (GAL). The notion of common knowledge plays an important role in PAL, and in particular in characterisations of epistemic states that an agent or a group of agents might make come about by performing public announcements. In this paper, we study extensions of APAL and GAL with common knowledge, which has not been done before. We consider both conservative extensions where the semantics of the quantifiers is not changed, as well as extensions where the scope of quantification also includes common knowledge formulas. We compare the expressivity of these extensions relative to each other and other connected logics, and provide sound and complete axiomatisations.

KR Conference 2021 Conference Paper

Somebody Knows

• Thomas Ågotnes
• Yì N. Wáng

Several different notions of group knowledge have been extensively studied in the epistemic and doxastic logic literature, including common knowledge, general knowledge (everybody-knows) and distributed knowledge. In this paper we study a natural notion of group knowledge between general and distributed knowledge: somebody-knows. While something is general knowledge if and only if it is known by everyone, this notion holds if and only if it is known by someone. This is stronger than distributed knowledge, which is the knowledge that follows from the total knowledge in the group. We introduce a modality for somebody-knows in the style of standard group knowledge modalities, and study its properties. Unlike the other mentioned group knowledge modalities, somebody-knows is not a normal modality; in particular it lacks the conjunctive closure property. We provide an equivalent neighbourhood semantics for the language with a single somebody-knows modality, together with a completeness result: the somebody-knows modalities are completely characterised by the modal logic EMN extended with a particular weak conjunctive closure axiom. We also show that the satisfiability problem for this logic is PSPACE-complete. The neighbourhood semantics and the completeness and complexity results also carry over to logics for so-called local reasoning (Fagin et al. 1995) with bounded ``frames of mind'', correcting an existing completeness result in the literature (Allen 2005).

LORI Conference 2019 Conference Paper

Analyzing Echo Chambers: A Logic of Strong and Weak Ties

• Mina Young Pedersen
• Sonja Smets
• Thomas Ågotnes

Abstract Echo chamber is a widely used term describing a situation where certain information is reinforced within a closed network. To reason about echo chambers, we introduce a two-sorted hybrid logic of strong and weak ties based on a logic of positive and negative relations known from the literature. We show that some classical property definitions can be formalized and that a known claim from social network analysis is a validity. We also prove that the logic is axiomatizable, sound and strongly complete. We combine our results with research on homophily and social group formation to represent relations between similar agents. Lastly, we add a knowledge modality and dynamic operators to analyze change in these networks.

LORI Conference 2019 Conference Paper

Group Announcement Logic with Distributed Knowledge

• Rustam Galimullin
• Thomas Ågotnes
• Natasha Alechina

Abstract Public announcement logic (PAL) is an extension of epistemic logic with dynamic operators that model the effects of all agents simultaneously and publicly acquiring the same piece of information. One of the extensions of PAL, group announcement logic (GAL), allows quantification over (possibly joint) announcements made by agents. In GAL, it is possible to reason about what groups can achieve by making such announcements. It seems intuitive that this notion of coalitional ability should be closely related to the notion of distributed knowledge, the implicit knowledge of a group. Thus, we study the extension of GAL with distributed knowledge, and in particular possible interaction properties between GAL operators and distributed knowledge. The perhaps surprising result is that there in fact are no interaction properties, contrary to intuition. We make this claim precise by providing a sound and complete axiomatisation of GAL with distributed knowledge.

AIJ Journal 2017 Journal Article

Resolving distributed knowledge

• Thomas Ågotnes
• Yì N. Wáng

LORI Conference 2017 Conference Paper

Towards a Logic of Tweeting

• Zuojun Xiong
• Thomas Ågotnes
• Jeremy Seligman
• Rui Zhu

Abstract In this paper we study the logical principles of a common type of network communication events that haven’t been studied from a logical perspective before, namely network announcements, or tweeting, i. e. , simultaneously sending a message to all your friends in a social network. In particular, we develop and study a minimal modal logic for reasoning about propositional network announcements. The logical formalisation helps elucidate core logical principles of network announcements, as well as a number of assumptions that must be made in such reasoning. The main results are sound and complete axiomatisations.

TARK Conference 2015 Conference Paper

Resolving Distributed Knowledge

• Thomas Ågotnes
• Yì N. Wáng

Distributed knowledge is the sum of the knowledge in a group; what someone who is able to discern between two possible worlds whenever any member of the group can discern between them, would know. Sometimes distributed knowledge is referred to as the potential knowledge of a group, or the joint knowledge they could obtain if they had unlimited means of communication. In epistemic logic, the formula D_G{\phi} is intended to express the fact that group G has distributed knowledge of {\phi}, that there is enough information in the group to infer {\phi}. But this is not the same as reasoning about what happens if the members of the group share their information. In this paper we introduce an operator R_G, such that R_G{\phi} means that {\phi} is true after G have shared all their information with each other - after G's distributed knowledge has been resolved. The R_G operators are called resolution operators. Semantically, we say that an expression R_G{\phi} is true iff {\phi} is true in what van Benthem [11, p. 249] calls (G's) communication core; the model update obtained by removing links to states for members of G that are not linked by all members of G. We study logics with different combinations of resolution operators and operators for common and distributed knowledge. Of particular interest is the relationship between distributed and common knowledge. The main results are sound and complete axiomatizations.

JELIA Conference 2014 Conference Paper

Measuring Dissimilarity between Judgment Sets

• Marija Slavkovik 0001
• Thomas Ågotnes

Abstract Distances and scores are widely used to measure (dis)similarity between objects of information such as preferences, belief sets, judgment sets, etc. Typically, measures are directly imported from information theory or topology, with little consideration for adequacy in the context of comparing logically related information. We propose a set of desirable properties for measures used to aggregate (logically related) judgments, and show which of the measures used for this purpose satisfy them.

LORI Conference 2013 Conference Paper

Boolean Games with Epistemic Goals

• Thomas Ågotnes
• Paul Harrenstein
• Wiebe van der Hoek
• Michael J. Wooldridge

Abstract We introduce and formally study games in which the goals of players relate to the epistemic states of players in the game. For example, one player might have a goal that another player knows a certain proposition, while another player might have as a goal that a certain player does not know some proposition. The formal model we use to study epistemic games is a variation of the increasingly popular Boolean games model in which each player controls a number of Boolean variables, but has limited ability to see the truth values of the overall set of formulae that hold in the game. Each player in an epistemic Boolean game has a goal, defined as a formula of modal epistemic logic. Using such a language for goals allows us to explicitly and compactly represent desirable epistemic states. After motivating and formally defining epistemic Boolean games as a concise representation of epistemic Kripke structures, we investigate their complexity and study their properties.

IJCAI Conference 2013 Conference Paper

Multi-Agent Subset Space Logic

• Yì N. Wáng
• Thomas Ågotnes

Subset space logics have been introduced and studied as a framework for reasoning about a notion of effort in epistemic logic. The seminal Subset Space Logic (SSL) by Moss and Parikh modeled a single agent, and most work in this area has focused on different extensions of the language, or different model classes resulting from restrictions on subset spaces, while still keeping the single-agent assumption. In this paper we argue that the few existing attempts at multi-agent versions of SSL are unsatisfactory, and propose a new multi-agent subset space logic which is a natural extension of single-agent SSL. The main results are a sound and complete axiomatization of this logic, as well as an alternative and equivalent relational semantics.

LORI Conference 2013 Conference Paper

Public Announcements, Private Actions and Common Knowledge in S5 Structures

• Yì N. Wáng
• Thomas Ågotnes

Abstract In this paper we take the S5 definition of knowledge, and have a new look at logics combining modalities for public announcements, action models, common knowledge and relativized common knowledge. In particular, we prove two expressivity results which previously have only been shown for the case where knowledge is represented using arbitrary Kripke models but have remained open for the case of S5 models: public announcement logic with relativized common knowledge is strictly more expressive than public announcement logic with common knowledge, and action model logic with common knowledge is strictly more expressive than public announcement logic with common knowledge. We also propose and study a definition of relativized common knowledge for action model logic.

IJCAI Conference 2013 Conference Paper

Verifiable Equilibria in Boolean Games

• Thomas Ågotnes
• Paul Harrenstein
• Wiebe van der Hoek
• Michael Wooldridge

This work is motivated by the following concern. Suppose we have a game exhibiting multiple Nash equilibria, with little to distinguish them except that one of them can be verified while the others cannot. That is, one of these equilibria carries sufficient information that, if this is the outcome, then the players can tell that an equilibrium has been played. This provides an argument for this equilibrium being played, instead of the alternatives. Verifiability can thus serve to make an equilibrium a focal point in the game. We formalise and investigate this concept using a model of Boolean games with incomplete information. We define and investigate three increasingly strong types of verifiable equilibria, characterise the complexity of checking these, and show how checking their existence can be captured in a variant of modal epistemic logic.

ECAI Conference 2012 Conference Paper

Conservative Social Laws

• Thomas Ågotnes
• Wiebe van der Hoek
• Michael J. Wooldridge

Social laws - sets of constraints imposed on the behaviour of agents within a multi-agent system with the goal of some desirable overall behaviour resulting - are an important mechanism for coordinating multi-agent behaviour. When considering social laws in human environments, the inspiration for social laws in multiagent systems, we argue that a key design principle is least change. That is, social laws are more likely to be accepted and adopted, and hence successful, if they are conservative, in the sense that they represent the smallest change possible from the pre-existing status quo that is required to effect the desired objective. Our aim in the present paper is to introduce, formalise, and investigate the notion of a conservative social law for multi-agent systems. To make the idea of a conservative social law precise, we formalise the notion of a distance metric for social laws, and discuss a range of possible properties for such metrics. We then formulate the conservative social law problem, (i. e. , the problem of constructing an effective social law that requires the least change according to this metric), discuss some possible interpretations of distance in this context, and discuss some issues surrounding conservative social laws.

LORI Conference 2011 Conference Paper

Public Announcement Logic with Distributed Knowledge

• Yì N. Wáng
• Thomas Ågotnes

Abstract While dynamic epistemic logics with common knowledge have been extensively studied, dynamic epistemic logics with distributed knowledge have so far received far less attention. In this paper we study extensions of public announcement logic ( \({\cal PAL}\) ) with distributed knowledge, in particular their expressivity and axiomatisations. \(\cal PAL\) extended only with distributed knowledge is not more expressive than standard epistemic logic with distributed knowledge. Our focus is therefore on \(\cal PACD\), the result of adding both common and distributed knowledge to \(\cal PAL\), which is more expressive than each of its component logics. Our main result is a completeness result for \(\cal PACD\). The axiomatisation is not surprising: it is the combination of well-known axioms. The completeness proof, however, is not trivial, and requires novel combinations and extensions of techniques for dealing with S 5 knowledge, distributed knowledge, common knowledge and public announcements at the same time.

JAAMAS Journal 2009 Journal Article

On the logic of preference and judgment aggregation

• Thomas Ågotnes
• Wiebe van der Hoek
• Michael Wooldridge

Abstract Agents that must reach agreements with other agents need to reason about how their preferences, judgments, and beliefs might be aggregated with those of others by the social choice mechanisms that govern their interactions. The emerging field of judgment aggregation studies aggregation from a logical perspective, and considers how multiple sets of logical formulae can be aggregated to a single consistent set. As a special case, judgment aggregation can be seen to subsume classical preference aggregation. We present a modal logic that is intended to support reasoning about judgment aggregation scenarios (and hence, as a special case, about preference aggregation): the logical language is interpreted directly in judgment aggregation rules. We present a sound and complete axiomatisation. We show that the logic can express aggregation rules such as majority voting; rule properties such as independence; and results such as the discursive paradox, Arrow’s theorem and Condorcet’s paradox—which are derivable as formal theorems of the logic. The logic is parameterised in such a way that it can be used as a general framework for comparing the logical properties of different types of aggregation—including classical preference aggregation. As a case study we present a logical study of, including a formal proof of, the neutrality lemma, the main ingredient in a well-known proof of Arrow’s theorem.

AAMAS Conference 2009 Conference Paper

Power in Normative Systems

• Thomas Ågotnes
• Wiebe van der Hoek
• Moshe Tennenholtz
• Michael Wooldridge

Power indices such as the Banzhaf index were originally developed within voting theory in an attempt to rigorously characterise the influence that a voter is able to wield in a particular voting game. In this paper, we show how such power indices can be applied to understanding the relative importance of agents when we attempt to devise a coordination mechanism using the paradigm of social laws, or normative systems. Understanding how pivotal an agent is with respect to the success of a particular social law is of benefit when designing such social laws: we might typically aim to ensure that power is distributed evenly amongst the agents in a system, to avoid bottlenecks or single points of failure. After formally defining the framework and illustrating the role of power indices in it, we investigate the complexity of computing these indices, showing that the characteristic complexity result is #P-completeness. We then investigate cases where computing indices is computationally easy.

AIJ Journal 2009 Journal Article

Reasoning about coalitional games

• Thomas Ågotnes
• Wiebe van der Hoek
• Michael Wooldridge

TARK Conference 2007 Conference Paper

Alternating-time temporal logics with irrevocable strategies

• Thomas Ågotnes
• Valentin Goranko
• Wojciech Jamroga

In Alternating-time Temporal Logic (atl), one can express statements about the strategic ability of an agent (or a coalition of agents) to achieve a goal φ such as: “agent i can choose a strategy such that, if i follows this strategy then, no matter what other agents do, φ will always be true”. However, strategies in atl are revocable in the sense that in the evaluation of the goal φ the agent i is no longer restricted by the strategy she has chosen in order to reach the state where the goal is evaluated. In this paper we consider alternative variants of atl where strategies, on the contrary, are irrevocable. The difference between revocable and irrevocable strategies shows up when we consider the ability to achieve a goal which, again, involves (nested) strategic ability. Furthermore, unlike in the standard semantics of atl, memory plays an essential role in the semantics based on irrevocable strategies.

TARK Conference 2007 Conference Paper

Full and relative awareness: a decidable logic for reasoning about knowledge of unawareness

• Thomas Ågotnes
• Natasha Alechina

In the most popular logics combining knowledge and awareness, it is not possible to express statements about knowledge of unawareness such as “Ann knows that Bill is aware of something Ann is not aware of” – without using a stronger statement such as “Ann knows that Bill is aware of p and Ann is not aware of p”, for some particular p. Recently, however, Halpern and Rêgo (2006) introduced a logic in which such statements about knowledge of unawareness can be expressed. The logic extends the traditional framework with quantification over formulae, and is thus very expressive. As a consequence, it is not decidable. In this paper we introduce a decidable logic which can be used to reason about certain types of unawareness. The logic extends the traditional framework with an operator expressing full awareness, i. e. , the fact that an agent is aware of everything, and another operator expressing relative awareness, the fact that one agent is aware of everything another agent is aware of. The logic is less expressive than Halpern’s and Rêgo’s logic. It is, however, expressive enough to express all of Halpern’s and Rêgo’s motivating examples. In addition to proving that the logic is decidable and that its satisfiability problem is PSPACE-complete, we present an axiomatisation which we show is sound and complete.

AAMAS Conference 2007 Conference Paper

Modular Interpreted Systems

• Wojciech Jamroga
• Thomas Ågotnes

We propose a new class of representations that can be used for modeling (and model checking) temporal, strategic and epistemic properties of agents and their teams. Our representations borrow the main ideas from interpreted systems of Halpern, Fagin et al. ; however, they are also modular and compact in the way concurrent programs are. We also mention preliminary results on model checking alternating-time temporal logic for this natural class of models.

AAMAS Conference 2007 Conference Paper

Normative System Games

• Thomas Ågotnes
• Wiebe van der Hoek
• Michael Wooldridge

We develop a model of normative systems in which agents are assumed to have multiple goals of increasing priority, and investigate the computational complexity and game theoretic properties of this model. In the underlying model of normative systems, we use Kripke structures to represent the possible transitions of a multiagent system. A normative system is then simply a subset of the Kripke structure, which contains the arcs that are forbidden by the normative system. We specify an agent's goals as a hierarchy of formulae of Computation Tree Logic (CTL), a widely used logic for representing the properties of Kripke structures: the intuition is that goals further up the hierarchy are preferred by the agent over those that appear further down the hierarchy. Using this scheme, we define a model of ordinal utility, which in turn allows us to interpret our Kripke-based normative systems as games, in which agents must determine whether to comply with the normative system or not. We then characterise the computational complexity of a number of decision problems associated with these Kripke-based normative system games; for example, we show that the complexity of checking whether there exists a normative system which has the property of being a Nash implementation is NP-complete.

AAMAS Conference 2007 Conference Paper

Reasoning about Judgment and Preference Aggregation

• Thomas Ågotnes
• Wiebe van der Hoek
• Michael Wooldridge

Agents that must reach agreements with other agents need to reason about how their preferences, judgments, and beliefs might be aggregated with those of others by the social choice mechanisms that govern their interactions. The recently emerging field of judgment aggregation studies aggregation from a logical perspective, and considers how multiple sets of logical formulae can be aggregated to a single consistent set. As a special case, judgment aggregation can be seen to subsume classical preference aggregation. We present a modal logic that is intended to support reasoning about judgment aggregation scenarios (and hence, as a special case, about preference aggregation): the logical language is interpreted directly in judgment aggregation rules. We present a sound and complete axiomatisation of such rules. We show that the logic can express aggregation rules such as majority voting; rule properties such as independence; and results such as the discursive paradox, Arrow's theorem and Condorcet's paradox – which are derivable as formal theorems of the logic. The logic is parameterised in such a way that it can be used as a general framework for comparing the logical properties of different types of aggregation-including classical preference aggregation.

ECAI Conference 2006 Conference Paper

Knowing Minimum/Maximum n Formulae

• Thomas Ågotnes
• Natasha Alechina

We introduce a logical language with nullary operators min(n), for each non-negative integer n, which mean ‘the reasoner has at least n different beliefs’. The resulting language allows us to express interesting properties of non-monotonic and resource-bounded reasoners. Other operators, such as 'the reasoner has at most n different beliefs' and the operator introduced in [1, 4]: 'the reasoner knows at most the formulae φ 1, …, φ n ′, are definable using min(n). We introduce several syntactic epistemic logics with min(n) operators, and prove completeness and decidability results for those logics.