This paper refines the game theoretic analysis of conversations in Asher et al. by adding epistemic concepts to make explicit the intuitive idea that conversationalists typically conceive of conversational strategies in a situation of imperfect information. This ‘epistemic’ turn has important ramifications for linguistic analysis, and we illustrate our approach with a detailed treatment of linguistic examples.

numbers as in the following example ♦1,1♦1,2 2,3 5,4p We denote the set of formulas of this modal language by M L(k). For each modality type i, there will be an accessibility relation Ri. That is, an k-ary modal structure for the modal propositional language L will have the form..

I will show that the semantic structure of a new imperfect-information propositional logic can be described in terms of extensive forms of semantic games. I will discuss some ensuing properties of these games such as imperfect recall, informational consistency, and team playing. Finally, I will suggest a couple of applications that arise in physics, and most notably in quantum theory and quantum logics.

In this article we investigate the family of independence-friendly (IF) logics in the equality-free setting, concentrating on questions related to expressive power. Various natural equality-free fragments of logics in this family translate into existential second-order logic with prenex quantification of function symbols only and with the first-order parts of formulae equality-free. We study this fragment of existential second-order logic. Our principal technical result is that over finite models with a vocabulary consisting of unary relation symbols only, this fragment of second-order (...) logic is weaker in expressive power than first-order logic (with equality). Results about the fragment could turn out useful for example in the study of independence-friendly modal logics. In addition to proving results of a technical nature, we address issues related to a perspective from which IF logic is regarded as a specification framework for games, and also discuss the general significance of understanding fragments of second-order logic in investigations related to non-classical logics. (shrink)

In this paper, we present a prenex form theorem for a version of Independence Friendly logic, a logic with imperfect information. Lifting classical results to such logics turns out not to be straightforward, because independence conditions make the formulas sensitive to signalling phenomena. In particular, nested quantification over the same variable is shown to cause problems. For instance, renaming of bound variables may change the interpretations of a formula, there are only restricted quantifier extraction theorems, and slashed connectives (...) cannot be so easily removed. Thus we correct some claims from Hintikka [8], Caicedo & Krynicki [3] and Hodges [11]. We refine definitions, in particular the notion of equivalence, and sharpen preconditions, allowing us to restore those claims, including the prenex form theorem of Caicedo & Krynicki [3], and, as a side result, we obtain an application to Skolem forms of classical formulas. It is a known fact that a complete calculus for IF-logic is impossible, but with our results we establish several quantifier rules that form a partial calculus of equivalence for a general version of IF-logic reflecting general properties of information flow in games. (shrink)

We present a compositional semantics for first-order logic with imperfect information that is equivalent to Sevenster and Sandu’s equilibrium semantics (under which the truth value of a sentence in a finite model is equal to the minimax value of its semantic game). Our semantics is a generalization of an earlier semantics developed by the first author that was based on behavioral strategies, rather than mixed strategies.

In this paper, we introduce a new approach to independent quantifiers, as originally introduced in Informational independence as a semantic phenomenon by Hintikka and Sandu [9] under the header of independence-friendly languages. Unlike other approaches, which rely heavily on compositional methods, we shall analyze independent quantifiers via equilibriums in strategic games. In this approach, coined equilibrium semantics, the value of an IF sentence on a particular structure is determined by the expected utility of the existential player in any of (...) the game’s equilibriums. This approach was suggested in Henkin quantifiers and complete problems by Blass and Gurevich [2] but has not been taken up before. We prove that each rational number can be realized by an IF sentence. We also give a lower and upper bound on the expressive power of IF logic under equilibrium semantics. (shrink)

When seeking to coordinate in a game with imperfect information, it is often relevant for a player to know what other players know. Keeping track of the information acquired in a play of infinite duration may, however, lead to infinite hierarchies of higher-order knowledge. We present a construction that makes explicit which higher-order knowledge is relevant in a game and allows us to describe a class of games that admit coordinated winning strategies with finite memory.

We discuss games of both perfect and imperfect information at two levels of structural detail: players’ local actions, and their global powers for determining outcomes of the game. We propose matching logical languages for both. In particular, at the ‘action level’, imperfect information games naturally model a combined ‘dynamic-epistemic language’ – and we find correspondences between special axioms and particular modes of playing games with their information dynamics. At the ‘outcome level’, we (...) present suitable notions of game equivalence, plus some simple representation results. (shrink)

The paper presents an application of game-theoretical ideas to the semantics of natural language, especially the analysis of quantifiers and anaphora. The paper also introduces the idea of games of imperfect information and connects to partial logics.

We present a new notion of game equivalence that captures basic powers of interacting players. We provide a representation theorem, a complete logic, and a new game algebra for basic powers. In doing so, we establish connections with imperfect information games and epistemic logic. We also identify some new open problems concerning logic and games.

We study partiality in propositional logics containing formulas with either undefined or over-defined truth-values. Undefined values are created by adding a four-place connective W termed transjunction to complete models which, together with the usual Boolean connectives is shown to be functionally complete for all partial functions. Transjunction is seen to be motivated from a game-theoretic perspective, emerging from a two-stage extensive form semantic game of imperfect information between two players. This game-theoretic approach yields an interpretation where partiality is (...) generated as a property of non-determinacy of games. Over-defined values are produced by adding a weak, contradictory negation or, alternatively, by relaxing the assumption that games are strictly competitive. In general, particular forms of extensive imperfect information games give rise to a generalised propositional logic where various forms of informational dependencies and independencies of connectives can be studied. (shrink)

We present a new notion of game equivalence that captures basic powers of interacting players. We provide a representation theorem, a complete logic, and a new game algebra for basic powers. In doing so, we establish connections with imperfect information games and epistemic logic. We also identify some new open problems concerning logic and games.

Dynamic epistemic logic describes the possible information-changing actions available to individual agents, and their knowledge pre-and post conditions. For example, public announcement logic describes actions in the form of public, truthful announcements. However, little research so far has considered describing and analysing rational choice between such actions, i.e., predicting what rational self-interested agents actually will or should do. Since the outcome of information exchange ultimately depends on the actions chosen by all the agents in the system, and assuming (...) that agents have preferences over such outcomes, this is a game theoretic scenario. This is, in our opinion, an interesting general research direction, combining logic and game theory in the study of rational information exchange. In this article we take some first steps in this direction: we consider the case where available actions are public announcements, and where each agent has a (typically epistemic) goal formula that she would like to become true. What will each agent announce? The truth of the goal formula also depends on the announcements made by other agents. We analyse such public announcement games. (shrink)

We associate the semantic game with chance moves conceived by Blinov with Blamey’s partial logic. We give some equivalent alternatives to the semantic game, some of which are with a third player, borrowing the idea of introducing the pseudo-player called Nature in game theory. We observe that IF propositional logic proposed by Sandu and Pietarinen can be equivalently translated to partial logic, which implies that imperfect information may not be necessary for IF propositional logic. We also indicate that (...) some independent quantifiers can be regarded as dependent quantifiers of indeterminate sequence, using the interjunction connective in partial logic. We conclude our paper by indicating some further research in a more general setting. (shrink)

This is a two-volume set that provides an introduction to non-cooperative Game Theory. Volume 1 covers the basic concepts, while Volume 2 is devoted to advanced topics. The book is richly illustrated with approximately 400 figures. It is suitable for both self-study and as the basis for an undergraduate course in game theory as well as a first-year graduate-level class. It is written to be accessible to anybody with high-school level knowledge of mathematics. At the end of each chapter there (...) is a collection of exercises accompanied by detailed answers. The book contains approximately 180 exercises. (shrink)

Over the past two decades, academic economics has undergone a mild revolution in methodology. The language, concepts and techniques of noncooperative game theory have become central to the discipline. This book provides the reader with some basic concepts from noncooperative theory, and then goes on to explore the strengths, weaknesses, and future of the theory as a tool of economic modelling and analysis. The central theses are that noncooperative game theory has been a remarkably popular tool in economics over the (...) past decade because it allows analysts to capture essential features of dynamic competition and competition where some parties have proprietary information. The theory is weakest in providing a sense of when it - and equilibrium analysis in particular - can be applied and what to do when equilibrium analysis is inappropriate. Many of these weaknesses can be addressed by the consideration of individuals who are boundedly rational and learn imperfectly from the past. Written in a non-technical style and working by analogy, the book, first given as part of the Clarendon Lectures in Economics, is readily accessible to a broad audience and will be of interest to economists and students alike. Knowledge of game theory is not required as the concepts are developed as the book progresses. (shrink)

This paper is based on tutorials on 'Logic and Games' at the 7th Asian Logic Conference in Hsi-Tou, Taiwan, 1999, and until 2002 in Siena, Stuttgart, Trento, Udine, and Utrecht. We present logic games as a topic per se, giving models for dynamic interaction between agents. First, we survey some basic logic games. Then we show how their common properties raise general issues of game structure and 'game logics'. Next, we review logic games in the light (...) of general game logic. Finally, we discuss more 'realistic' influences from game theory into logic games, including players' preferences, and imperfect information. (shrink)

The papers collected in this volume exemplify some of the trends in current approaches to logic, language and computation. Written by authors with varied academic backgrounds, the contributions are intended for an interdisciplinary audience. The first part of this volume addresses issues relevant for multi-agent systems: reasoning with incomplete information, reasoning about knowledge and beliefs, and reasoning about games. Proofs as formal objects form the subject of Part II. Topics covered include: contributions on logical frameworks, linear logic, and (...) different approaches to formalized reasoning. Part III focuses on representations and formal methods in linguistic theory, addressing the areas of comparative and temporal expressions, modal subordination, and compositionality. (shrink)

Game-theoretic reasoning pervades economic theory and is used widely in other social and behavioural sciences. An Introduction to Game Theory International Edition, by Martin J. Osborne, presents the main principles of game theory and shows how they can be used to understand economics, social, political, and biological phenomena. The book introduces in an accessible manner the main ideas behind the theory rather than their mathematical expression. All concepts are defined precisely, and logical reasoning is used throughout. The book requires an (...) understanding of basic mathematics but assumes no specific knowledge of economics, political science, or other social or behavioural sciences. Coverage includes the fundamental concepts of strategic games, extensive games with perfect information, and coalitional games; the more advanced subjects of Bayesian games and extensive games with imperfect information; and the topics of repeated games, bargaining theory, evolutionary equilibrium, rationalizability, and maxminimization. The book offers a wide variety of illustrations from the social and behavioural sciences. Each topic features examples that highlight theoretical points and illustrations that demonstrate how the theory may be used. (shrink)

In the literature on logics of imperfect information it is often stated, incorrectly, that the Game-Theoretical Semantics of Independence-Friendly quantifiers captures the idea that the players of semantical games are forced to make some moves without knowledge of the moves of other players. We survey here the alternative semantics for IF logic that have been suggested in order to enforce this “epistemic reading” of sentences. We introduce some new proposals, and a more general logical language which distinguishes (...) between “independence from actions” and “independence from strategies”. New semantics for IF logic can be obtained by choosing embeddings of the set of IF sentences into this larger language. We compare all the semantics proposed and their purported game-theoretical justifications, and disprove a few claims that have been made in the literature. (shrink)

We formulate a formal framework in which we combine the theory of dynamic epistemic logic and the theory of games. In particular, we show how we can use tools of dynamic epistemic logic to reason about information change ? and in particular, the effect of communication acts ? in such a game of imperfect information. We show how this framework allows for the formulation of specific assumptions in pragmatics of communication, as well as the formulation of (...) general results about the value of information. (shrink)

Understanding the flow of knowledge in multi-agent protocols is essential when proving the correctness or security of such protocols. Current logical approaches, often based on model checking, are well suited for modeling knowledge in systems where agents do not act strategically. Things become more complicated in strategic settings. In this paper we show that such situations can be understood as a special type of game – a knowledge condition game – in which a coalition “wins” if it is able to (...) bring about some epistemic condition. This paper summarizes some results relating to these games. Two proofs are presented for the computational complexity of deciding whether a coalition can win a knowledge condition game with and without opponents (Σ2P-complete and NP-complete respectively). We also consider a variant of knowledge condition games in which agents do not know which strategies are played, and prove that under this assumption, the presence of opponents does not affect the complexity. The decision problem without opponents is still NP-complete, but requires a different proof. (shrink)

As an efficient approach, the trust policy is implemented to defend against insider attacks in complex networks. However, the imperfection of trust relationships directly hinders the effort to quantitatively calculate trust value, especially in choosing a cooperative partner. Fortunately, the game theory is gradually concerned with addressing the above issue to further enhance security. In this paper, the game theory and the trust policy are reviewed briefly. Then, the research roadmap on game-based trust in complex networks is discussed and analysed (...) deeply. Furthermore, some research directions in the near future are given. It is worth mentioning that our contributions not only describe the evolution of the game-based trust clearly but also suggest the trust mechanism based on the bounded rational game more suitable to uncertain information. (shrink)

As regimes move from illiberal to liberal, post-transition justice methodology has been employed to engender truth and reconciliation. These normative concepts have evolved into a policy of creating truth and reconciliation commissions that trade civil and criminal amnesty with applicants in ex change for information. This bargained-for exchange can be analyzed as an imperfect information game, where the commission attempts to maximize information while the applicant seeks amnesty for the lowest possible price. Using game-theoretic analysis, the (...) authors model the truth-amnesty game and predict the optimal commission strategy. The analysis leads to the recommendation that future transitional justice commissions employ various specific lexicographic ordering strategies to minimize dead weight loss in the transaction. (shrink)

As regimes move from illiberal to liberal, post-transition justice methodology has been employed to engender truth and reconciliation. These normative concepts have evolved into a policy of creating truth and reconciliation commissions that trade civil and criminal amnesty with applicants in exchange for information. This bargained-for exchange can be analyzed as an imperfect information game, where the commission attempts to maximize information while the applicant seeks amnesty for the lowest possible price. Using game-theoretic analysis, the authors (...) model the truth-amnesty game and predict the optimal commission strategy. The analysis leads to the recommendation that future transitional justice commissions employ various specific lexicographic ordering strategies to minimize dead weight loss in the transaction. (shrink)

In this paper we relax the assumption that the logical constants of ordinary first-order logic be linearly ordered. As a consequence, we shall have formulas involving not only partially ordered quantifiers, but also partially ordered connectives. The resulting language, called the language of informational independence will be given an interpretation in terms of games of imperfect information. The II-logic will be seen to have some interesting properties: It is very natural to define in this logic two negations, (...) weak negation as failure to verify a sentence, and strong negation as the existence of a falsifying strategy: One can express in this logic complete problems of finite structures, like the non-connectedness and 3-colorability of finite graphs, the satisfiability problem for Boolean circuits built up from NAND-gates, etc. (shrink)

We shall introduce in this paper a language whose formulas will be interpreted by games of imperfect information. Such games will be defined in the same way as the games for first-order formulas except that the players do not have complete information of the earlier course of the game. Some simple logical properties of these games will be stated together with the relation of such games of imperfect information to higher-order (...) logic. Finally, a set of applications will be outlined. (shrink)

The semantics of the independence friendly logic of Hintikka and Sandu is usually defined via a game of imperfect information. We give a definition in terms of a game of perfect information. We also give an Ehrenfeucht-Fraïssé game adequate for this logic and use it to define a Distributive Normal Form for independence friendly logic.

We argue that in extensive decision problems (extensive games with a single player) with imperfect recall care must be taken in interpreting information sets and strategies. Alternative interpretations allow for different kinds of analysis. We address the following issues: 1. randomization at information sets; 2. consistent beliefs; 3. time consistency of optimal plans; 4. the multiselves approach to decision making. We illustrate our discussion through an example that we call the ‘‘paradox of the absentminded driver.’’ Journal (...) of Economic Literature Classification Numbers: C7, D0. 1997 Academic Press. (shrink)

© Springer-Verlag Berlin Heidelberg 2015. When reasoning about knowledge of procedures under imperfect information, the explicit representation of epistemic possibilities blows up the S5like models of standard epistemic logic. To overcome this drawback, in this paper, we propose a new logical framework based on compact models without epistemic accessibility relations for reasoning about knowledge of procedures. Inspired by the 3-valued abstraction method in model checking, we introduce hyper models which encode the imperfect procedural information. We give (...) a highly non-trivial 2-valued semantics of epistemic dynamic logic on such models while validating all the usual S5 axioms. Our approach is suitable for applications where procedural information is ‘learned’ incrementally, as demonstrated by various examples. (shrink)

Hume is rightly credited with giving a brilliant, and perhaps the best, account of justice as convention. Hume's importance as a forerunner of modern economics has also long been recognized. However, most of Hume's readers have not fully appreciated how closely Hume's analysis of convention foreshadows a particular branch of economic theory, namely, game theory. Starting with the work of Barry, Runciman and Sen and Lewis, there has been a flowering of literature on the informal game-theoretic insights to be found (...) in classics of political philosophy such as Hobbes, Locke, Hume and Rousseau. A number of authors in this tradition, including Lewis, Gauthier, Mackie, and Postema, have identified passages in Hume which they interpret as giving informal examples of specific games. Yet, unlike his predecessors, Hobbes and Locke, Hume does much more than present examples which have a game-theoretic structure. In his account of convention, Hume gives general conditions which characterize the resolution of social interaction problems, and in the examples he uses to illustrate this account, Hume outlines several different methods by which agents can arrive at such a resolution. Hume's general account of convention and his explanations of the origins of particular conventions together constitute a theory of strategic interaction, which is precisely what game theory aspires to be. (shrink)

In this paper it is argued that Hintikka's game theoreticalsemantics for Independence Friendly logic does not formalize theintuitions about independent choices; it rather is aformalization of imperfect information. Furthermore it is shownthat the logic has several remarkable properties (e.g.,renaming of bound variables is not allowed). An alternativesemantics is proposed which formalizes intuitions aboutindependence.

Objective The study evaluated patient informed consent for the Quad screen and examined differences in IC between test acceptors and test refusers. A multidimensional model of IC was used. Methods Women seeking prenatal care at nine obstetrics clinics in a large Midwestern city completed surveys between February and December 2006. Surveys contained measures for three dimensions of IC: intention, understanding and controlling influence. Results 56.2% of women did not meet criteria for all three of our dimensions of IC and therefore (...) failed to give it. The failure rate was higher among women who choose to screen than women who choose not screen. Women who met all criteria for IC were over three times less likley to choose to screen ) than women who did not meet criteria for IC. Conclusion The decision to screen for fetal anomalies is less of a deliberated action than the decision not to screen. Women who lack a fundamental understanding of the purpose and nature of the screen may be operating on the belief that the screen is part of standard care and presents no need to deliberate. (shrink)

We examine the relationship between dependence logic and game logics. A variant of dynamic game logic, called Transition Logic, is developed, and we show that its relationship with dependence logic is comparable to the one between first-order logic and dynamic game logic discussed by van Benthem. This suggests a new perspective on the interpretation of dependence logic formulas, in terms of assertions about reachability in games of imperfect information against Nature. We then capitalize on this intuition by (...) developing expressively equivalent variants of dependence logic in which this interpretation is taken to the foreground. (shrink)

This paper is a short survey of different languageswith imperfect information introduced in (Hintikka and Sandu 1989).The imperfect information concerns both quantifiers and connectives.At the end, I will sketch a connection between these languages and linearlogic.

We introduce and study a PDL-style logic for reasoning about protocols, or plans, under imperfect information. Our paper touches on a number of issues surrounding the relationship between an agent’s abilities, available choices, and information in an interactive situation. The main question we address is under what circumstances can the agent commit to a protocol or plan, and what can she achieve by doing so?

The logical foundations of game-theoretic solution concepts have so far been explored within the con¯nes of epistemic logic. In this paper we turn to a di®erent branch of modal logic, namely temporal logic, and propose to view the solution of a game as a complete prediction about future play. The branching time framework is extended by adding agents and by de¯ning the notion of prediction. A syntactic characterization of backward induction in terms of the property of internal consistency of prediction (...) is given. (shrink)

I first became aware of bioethics in the spring of 1980. I had spent a thirty‐six‐hour shift shadowing a medical resident, and I was struck that many of the resident's decisions had ethical dimensions. The next day, I came across the Hastings Center Report, and I realized I wanted to explore ethical issues I found implicit in clinical care, even though I still wanted to become a pediatrician. In September 2019, when I attended my first meeting of the U.S. Food (...) and Drug Administration's Pediatric Advisory Committee, as a pediatric pulmonologist, I had the same sense of awe and curiosity that I had forty years ago. What had appeared initially as somewhat technical decisions about the regulation of drug labeling was suffused with ethical questions. The committee was asked to discuss possible changes to the labeling of two previously approved drugs. (shrink)

We describe a logic which is the same as first-order logic except that it allows control over the information that passes down from formulas to subformulas. For example the logic is adequate to express branching quantifiers. We describe a compositional semantics for this logic; in particular this gives a compositional meaning to formulas of the 'information-friendly' language of Hintikka and Sandu. For first-order formulas the semantics reduces to Tarski's semantics for first-order logic. We prove that two formulas have (...) the same interpretation in all structures if and only if replacing an occurrence of one by an occurrence of the other in a sentence never alters the truth-value of the sentence in any structure. (shrink)

We propose a non-standard interpretation of Alternating-time Temporal Logic with imperfect information, for which no commonly accepted semantics has been proposed yet. Rather than changing the semantic structures, we generalize the usual interpretation of formulae in single states to sets of states. We also propose a new epistemic operator for ?practical? or ?constructive? knowledge, and we show that the new logic (which we call Constructive Strategic Logic) is strictly more expressive than most existing solutions, while it retains the (...) same model checking complexity. Finally, we study properties of constructive knowledge and other operators in this non-standard semantics. (shrink)