The cops and robber game is a well-studied model for investigating pursuit-evasion phenomena, among many others. Although many variants of this game have been studied in the literature, the epistemic assumptions underlying their game designs are often left implicit. In this work, we focus on the imperfect information version of the game and re-examine it from an epistemic perspective to explore the levels of player knowledge that are essential for playing the game. To facilitate our investigations on these knowledge levels, we discuss two kinds of strategies for the players, history-based and positional, and show what matters in this context. Our study eventually sheds light on the implicit assumptions prevalent in the existing literature in terms of player knowledge while playing the game, and provides a foundation for further studies on epistemically informed game structures.

Logics for reasoning about knowledge and actions have seen many applications in various domains of multi-agent systems, including epistemic planning. Change of knowledge based on observations about the surroundings forms a key aspect in such planning scenarios. Public Observation Logic (POL) is a variant of public announcement logic for reasoning about knowledge that gets updated based on public observations. Each state in an epistemic (Kripke) model is equipped with a set of expected observations. These states evolve as the expectations get matched with the actual observations. In this work, we prove that the satisfiability problem of POL is 2EXPTIME-complete.

Abstract We discuss the notion of bisimulation in various model-changing modal logics and provide an algorithmic study of the same. We provide a general algorithm which gives an overall procedure to check whether two models are bisimilar in all these logics. Through our algorithmic analyses we provide a PSPACE upper bound of the bisimulation/model comparison problem of all these modal logics. We also provide some insight into the higher complexity of the model comparison problem for these logics compared to that for the basic modal logic.

Public observation logic (POL) reasons about agent expectations and agent observations in various real world situations. The expectations of agents take shape based on certain protocols about the world around and they remove those possible scenarios where their exceptions and observations do not match. This in turn influences the epistemic reasoning of these agents. In this work, we study the computational complexity of the satisfaction problems of various fragments of POL. In the process, we also highlight the inevitable link that these fragments have with the well-studied Public announcement logic.

Public observation logic (POL) is a variant of dynamic epistemic logic to reason about agent expectations and agent observations. Agents have certain expectations, regarding the situation at hand, that are actuated by the relevant protocols, and they eliminate possible worlds in which their expectations do not match with their observations. In this work, we investigate the computational complexity of the model checking problem for POL and prove its PSPACE-completeness. We also study various syntactic fragments of POL. We exemplify the applicability of POL model checking in verifying different characteristics and features of an interactive system with respect to the distinct expectations and (matching) observations of the system. Finally, we provide a discussion on the implementation of the model checking algorithms.

Abstract Dealing with preferences is a ubiquitous part of our daily lives, and thus, preference forms an integral part of our daily decision-making processes. If we consider preferences among groups of agents, deliberation often leads to changes in preferences of an agent, influenced by the opinions of others, depending on how reliable these agents are according to the agent under consideration. Sometimes, it also leads to changes in the opposite direction, i.e. reliability over agents gets updated depending on their preferences. There are various formal studies of preference change based on reliability and/or trust, but not the other way around—this work contributes to the formal study of the latter aspect, i.e. on reliability change based on agent preferences. In process, some policies of preference change based on agent reliabilities are also discussed. We introduce a novel formal study of the relevant changes in agent reliabilities in decision-making scenarios, which is an integral part of artificial intelligence studies in the current day. A two-dimensional hybrid language is proposed to describe such processes, and axiomatizations and decidability are discussed.

When agents know a protocol, this leads them to have expectations about future observations. Agents can update their knowledge by matching their actual observations with the expected ones. They eliminate states where they do not match. In this paper, we study how agents perceive protocols that are not commonly known, and propose a logic to reason about knowledge in such scenarios.