Author name cluster

Yì N. Wáng

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers

2 author rows

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.

Details

GandALF Workshop 2024 Workshop Paper

Epistemic Skills: Logical Dynamics of Knowing and Forgetting

Xiaolong Liang
Yì N. Wáng

We present a type of epistemic logics that encapsulates both the dynamics of acquiring knowledge (knowing) and losing information (forgetting), alongside the integration of group knowledge concepts. Our approach is underpinned by a system of weighted models, which introduces an "epistemic skills" metric to effectively represent the epistemic abilities associated with knowledge update. In this framework, the acquisition of knowledge is modeled as a result of upskilling, whereas forgetting is by downskilling. Additionally, our framework allows us to explore the concept of "knowability, " which can be defined as the potential to acquire knowledge through upskilling, and facilitates a nuanced understanding of the distinctions between epistemic de re and de dicto expressions. We study the computational complexity of model checking problems for these logics, providing insights into both the theoretical underpinnings and practical implications of our approach.

PDF Details DOI

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).

PDF Details DOI

LORI Conference 2021 Conference Paper

Weighted Modal Logic in Epistemic and Deontic Contexts

Huimin Dong
Xu Li 0037
Yì N. Wáng

Abstract We introduce a type of weighted modal logic with explicit weights both in the language and in the models. The framework has its applications in epistemic logic for reasoning about agents’ knowledge based on their capability, and in deontic logic for agents’ choices based on their deontic capability or utilities. We make use of weighted Kripke models with the weights understood epistemically as a similarity measure between states and deontically as a measure of expected utilities. We present sound and complete axiomatizations for the logics, and discuss variants and possible extensions.

Details

LORI Conference 2019 Conference Paper

Who Should Be My Friends? - Social Balance from the Perspective of Game Theory

Wiebe van der Hoek
Louwe B. Kuijer
Yì N. Wáng

Abstract We define balance games, which describe the formation of friendships and enmity in social networks. We show that if the agents give high priority to future profits over short term gains, all Pareto optimal strategies will eventually result in a balanced network. If, on the other hand, agents prioritize short term gains over the long term, every Nash equilibrium eventually results in a network that is stable but that might not be balanced.

Details

AIJ Journal 2018 Journal Article

Implicit, explicit and speculative knowledge

Hans van Ditmarsch
Tim French
Fernando R. Velázquez-Quesada
Yì N. Wáng

We compare different epistemic notions in the presence of awareness of propositional variables: the logic of implicit knowledge (in which explicit knowledge is definable), the logic of explicit knowledge, and the logic of speculative knowledge. Speculative knowledge is a novel epistemic notion that permits reasoning about unawareness. These logics are interpreted on epistemic awareness models: these are multi-agent Kripke structures for propositional awareness (in each state an agent may only be aware of formulas containing occurrences of a subset of all propositional variables). Different notions of bisimulation are suitable for these logics. We provide correspondence between bisimulation and modal equivalence on image-finite models for these logics. Expressivity and axiomatizations are investigated for models without restrictions, and for models with equivalence relations for all agents (modeling knowledge) and awareness introspection (agents know what they are aware of). We show that the logic of speculative knowledge is as expressive as the logic of explicit knowledge, and the logic of implicit knowledge is more expressive than the two other logics. We also present expressivity results for more restricted languages. We then provide and compare axiomatizations for the three logics; the axiomatizations for speculative knowledge are novel. We compare our results to those for awareness achieved in artificial intelligence, computer science, philosophy, and economics.

Details DOI

AIJ Journal 2017 Journal Article

Resolving distributed knowledge

Thomas Ågotnes
Yì N. Wáng

In epistemic logic, a key formal theory for reasoning about knowledge in AI and other fields, different notions of group knowledge describe different ways in which knowledge can be associated with a group of agents. Distributed knowledge can be seen as the sum of the knowledge in a group; it is sometimes 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, a formula of the form D G φ is intended to express the fact that group G has distributed knowledge of φ, that the total information in the group can be used to infer φ. In this paper we show that this is not the same as φ necessarily being true after the members of the group actually share all their information with each other – perhaps contrary to intuitive ideas about what distributed knowledge is. We furthermore introduce a new operator R G, such that R G φ means that φ 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. 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 characterizations of expressive power, and sound and complete axiomatizations. We also study the relationship to public announcement logic.

Details DOI

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.

Details DOI

TARK Conference 2013 Conference Paper

Knowledge, awareness, and bisimulation

Hans van Ditmarsch
Tim French 0002
Fernando R. Velázquez-Quesada
Yì N. Wáng

intuitive situations. Consider the following models. We compare different epistemic notions in the presence of awareness of propositional variables: the logics of implicit knowledge (in which explicit knowledge is definable), explicit knowledge, and speculative knowledge. Different notions of bisimulation are suitable for these logics. We provide correspondence between bisimulation and modal equivalence on image-finite models for these logics. The logic of speculative knowledge is equally expressive as the logic of explicit knowledge, and the logic of implicit knowledge is more expressive than both. We also provide axiomatizations for the three logics — only the one for speculative knowledge is novel. Then we move to the study of dynamics by recalling action models incorporating awareness. We show that any conceivable change of knowledge or awareness can be modelled in this setting, we give a complete axiomatization for the dynamic logic of implicit knowledge. The dynamic versions of all three logics are, surprising, equally expressive. ◦ s ◦ t ◦ u M0: ◦ s ◦ t • u Model M has a domain {s, t, u}, a single agent i with accessibility relation R = {(s, t), (t, u)}, atom p true in all states, and the agent is aware of p only in state s. Awareness is not depicted. Model M 0 is like M, except that p is now false in u (the black dot). As mentioned, the agent knows explicitly a given ϕ at a given state iff she is aware of the formula in that state and ϕ is true in all accessible states. Let us apply this to the depicted structures. In both, the agent is unaware of p at state t, and therefore of the value of p in u: she should see (M, t) and (M 0, t) as identical, and therefore (M, s) and (M 0, s) as well. We propose a notion of bisimilarity for which (M, s) and (M 0, s) are bisimilar. Now here is the surprise: in the language with awareness and modal box, states (M, s) and (M 0, s) are not modally equivalent. Given explicit knowledge KiE ϕ as 2i ϕ ∧ Ai ϕ, consider KiE 2i p. This is true in (M, s) but false in (M 0, s). In logics of awareness [4] it is common only to consider models for knowledge (equivalence relations) and belief. However, as always in multi-agent logics, it is elementary to transform a single-agent model with directed (asymmetric) accessibility into a multi-agent model where intersecting equivalence classes for agents force such asymmetry. For example, consider the following.

Details

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.

PDF Details DOI

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.

Details

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.

Details