As they are conventionally formulated, Boolean games assume that players make their choices in ignorance of the choices being made by other players – they are games of simultaneous moves. For many settings, this is clearly unrealistic. In this paper, we show how Boolean games can be enriched by dependency graphs which explicitly represent the informational dependencies between variables in a game. More precisely, dependency graphs play two roles. First, when we say that variable x (...) depends on variable y, then we mean that when a strategy assigns a value to variable x, it can be informed by the value that has been assigned to y. Second, and as a consequence of the first property, they capture a richer and more plausible model of concurrency than the simultaneous-action model implicit in conventional Boolean games. Dependency graphs implicitly define a partial ordering of the run-time events in a game: if x is dependent on y, then the assignment of a value to y must precede the assignment of a value to x; if x and y are independent, however, then we can say nothing about the ordering of assignments to these variables—the assignments may occur concurrently. We refer to Boolean games with dependency graphs as partial-order Boolean games. After motivating and presenting the partial-order Boolean games model, we explore its properties. We show that while some problems associated with our new games have the same complexity as in conventional Boolean games, for others the complexity blows up dramatically. We also show that the concurrency in partial-order Boolean games can be modelled using a closure-operator semantics, and conclude by considering the relationship of our model to Independence-Friendly logic. (shrink)

Boolean games are a logical setting for representing strategic games in a succinct way, taking advantage of the expressive power and conciseness of propositional logic. A Boolean game consists of a set of players, each of which controls a set of propositional variables and has a specific goal expressed by a propositional formula. We show here that Boolean games are a very simple setting, yet sophisticated enough, for analysing the formation of coalitions. Due to (...) the fact that players have dichotomous preferences, the following notion emerges naturally: a coalition in a Boolean game is efficient if it has the power to guarantee that all goals of the members of the coalition are satisfied. We study the properties of efficient coalitions. (shrink)

A fundamental problem in game theory is the possibility of reaching equilibrium outcomes with undesirable properties, e.g., inefficiency. The economics literature abounds with models that attempt to modify games in order to avoid such undesirable properties, for example through the use of subsidies and taxation, or by allowing players to undergo a bargaining phase before their decision. In this paper, we consider the effect of such transformations in Boolean games with costs, where players control propositional variables that (...) they can set to true or false, and are primarily motivated to seek the satisfaction of some goal formula, while secondarily motivated to minimise the costs of their actions. We adopt preparation sets as our basic solution concept. A preparation set is a set of outcomes that contains for every player at least one best response to every outcome in the set. Prep sets are well-suited to the analysis of Boolean games, because we can naturally represent prep sets as propositional formulas, which in turn allows us to refer to prep formulas. The preference structure of Boolean games with costs makes it possible to distinguish between hard and soft prep sets. The hard prep sets of a game are sets of valuations that would be prep sets in that game no matter what the cost function of the game was. The properties defined by hard prep sets typically relate to goal-seeking behaviour, and as such these properties cannot be eliminated from games by, for example, taxation or subsidies. In contrast, soft prep sets can be eliminated by an appropriate system of incentives. Besides considering what can happen in a game by unrestricted manipulation of players’ cost function, we also investigate several mechanisms that allow groups of players to form coalitions and eliminate undesirable outcomes from the game, even when taxes or subsidies are not a possibility. (shrink)

The game is played on a complete Boolean algebra in ω-many moves. At the beginning White chooses a non-zero element p of and, in the nth move, White chooses a positive pn

Boolean algebra carries (...) a strictly positive Maharam submeasure or contains a countable dense subset, then Black has a winning strategy in the game played on . A Suslin algebra on which the game is undetermined is constructed and the game is compared with the well-known cut-and-choose games , and introduced by Jech. (shrink)

Recent years have seen increased interest in the question of whether it is possible to provide an evolutionary game-theoretic explanation for certain kinds of social norms. I sketch a proof of a general representation theorem for a large class of evolutionary game-theoretic models played on a social network, in hope that this will contribute to a greater understanding of the long-term evolutionary dynamics of such models, and hence the evolution of social norms.

We introduce properties of Boolean algebras which are closely related to the existence of winning strategies in the Banach-Mazur Boolean game. A σ-short Boolean algebra is a Boolean algebra that has a dense subset in which every strictly descending sequence of length ω does not have a nonzero lower bound. We give a characterization of σ-short Boolean algebras and study properties of σ-short Boolean algebras.

We address the issue of manipulating games through communication. In the specific setting we consider (a variation of Boolean games), we assume there is some set of environment variables, the values of which are not directly accessible to players; the players have their own beliefs about these variables, and make decisions about what actions to perform based on these beliefs. The communication we consider takes the form of (truthful) announcements about the values of some environment variables; the (...) effect of an announcement is the modification of the beliefs of the players who hear the announcement so that they accurately reflect the values of the announced variables. By choosing announcements appropriately, it is possible to perturb the game away from certain outcomes and towards others. We specifically focus on the issue of stabilisation: making announcements that transform a game from having no stable states to one that has stable configurations. (shrink)

We discuss the relationship between various weak distributive laws and games in Boolean algebras. In the first part we give some game characterizations for certain forms of Prikry’s “hyper-weak distributive laws”, and in the second part we construct Suslin algebras in which neither player wins a certain hyper-weak distributivity game. We conclude that in the constructible universe L, all the distributivity games considered in this paper may be undetermined.

We consider Effort Games, a game-theoretic model of cooperation in open environments, which is a variant of the principal-agent problem from economic theory. In our multiagent domain, a common project depends on various tasks; carrying out certain subsets of the tasks completes the project successfully, while carrying out other subsets does not. The probability of carrying out a task is higher when the agent in charge of it exerts effort, at a certain cost for that agent. A central authority, (...) called the principal, attempts to incentivize agents to exert effort, but can only reward agents based on the success of the entire project.We model this domain as a normal form game, where the payoffs for each strategy profile are defined based on the different probabilities of carrying out each task and on the boolean function that defines which task subsets complete the project, and which do not. We view this boolean function as a simple coalitional game, and call this game the underlying coalitional game. We suggest the Price of Myopia as a measure of the influence the model of rationality has on the minimal payments the principal has to make in order to motivate the agents in such a domain to exert effort.We consider the computational complexity of testing whether exerting effort is a dominant strategy for an agent, and of finding a reward strategy for this domain, using either a dominant strategy equilibrium or using iterated elimination of dominated strategies. We show these problems are generally #P-hard, and that they are at least as computationally hard as calculating the Banzhaf power index in the underlying coalitional game. We also show that in a certain restricted domain, where the underlying coalitional game is a weighted voting game with certain properties, it is possible to solve all of the above problems in polynomial time. We give bounds on PoM in weighted voting effort games, and provide simulation results regarding PoM in another restricted class of effort games, namely effort games played over Series-Parallel Graphs. (shrink)

It is unprovable that every complete subalgebra of a countably closed complete Boolean algebra is countably closed.

The game Gls(κ) is played on a complete Boolean algebra B, by two players. White and Black, in κ-many moves (where κ is an infinite cardinal). At the beginning White chooses a non-zero element p ∈ B. In the α-th move White chooses pα ∈ (0.p)p and Black responds choosing iα ∈ {0.1}. White wins the play iff $\bigwedge _{\beta \in \kappa}\bigvee _{\alpha \geq \beta }p_{\alpha}^{i\alpha}=0$ , where $p_{\alpha}^{0}=p_{\alpha}$ and $p_{\alpha}^{1}=p\ p_{\alpha}$ . The corresponding game theoretic properties of c.B.a.'s (...) are investigated. So. Black has a winning strategy (w.s) if κ ≥ π(B) or if B contains a κ -closed dense subset. On the other hand, if White has a w.s., then κ ∈ [h₂(B). π(B)). The existence of w.s. is characterized in a combinatorial way and in terms of forcing. In particular, if 2κ = κ ∈ Reg and forcing by B preserves the regularity of κ, then White has a w.s. iff the power 2κ is collapsed to κ in some extension. It is shown that, under the GCH, for each set S ⊆ Reg there is a c.B.a. B such that White (respectively. Black) has a w.s. for each infinite cardinal κ ∈ S (resp. κ ∉ S). Also it is shown consistent that for each κ ∈ Reg there is a c.B.a. on which the game Gls(κ) is undetermined. (shrink)

We consider games over a finite alphabet with Gurevich-Harrington's winning conditions and restraints as in Yakhnis-Yakhnis . The game tree, the Gurevich-Harrington's kernels of the winning condition and the restraints are defined by finite automata. We give an effective criterion to determine the winning player and an effective presentation of a class of finite automata defined winning strategies.Our approach yields an alternative solution to the games considered by Büchi and Landweber . The BL algorithm is an important tool (...) for solving effectively presented games. The differences between the BL and our algorithms are as follows. Our algorithm is uniformly applicable to winning sets that correspond to boolean combinations of BL winning conditions, while the BL algorithm requires a transformation of such boolean combinations into a single BL condition. Our algorithm directly applies to a larger class of game trees for a given game alphabet than does the BL one. We describe Büchi-Landweber's class of winning conditions in a more transparent way by using finite automata and Gurevich-Harrington's form of winning conditions. Our algorithms that determine the winner of the game and find a winning strategy, are based on a translation of the events in the game in terms of the transition table of the automaton representing the game. This automaton differs from the ones that represent BL winning conditions. Both algorithms need further investigation.The algorithm determining the winner in the game, can be used as a verifier of concurrent programs. This is because programs can be viewed as strategies in Gurevich-Harrington's games and program specifications could be regarded as winning conditions for such games. The algorithm which finds a winning strategy could be used as a basis for automated concurrent program design.The present paper is a sequel to Annals of Pure and Applied Logic 48 277–297. (shrink)

Gaifman's normal form theorem showed that every first-order sentence of quantifier rank n is equivalent to a Boolean combination of “scattered local sentences”, where the local neighborhoods have radius at most 7n−1. This bound was improved by Lifsches and Shelah to 3×4n−1. We use Ehrenfeucht–Fraïssé type games with a “shrinking horizon” to get a spectrum of normal form theorems of the Gaifman type, depending on the rate of shrinking. This spectrum includes the result of Lifsches and Shelah, with (...) a more easily understood proof and with the bound on the radius improved to 4n−1. We also obtain bounds for a normal form theorem of Schwentick and Barthelmann. (shrink)

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)

In the original Ulam-Rényi game with _m_ lies/errors, Player I chooses a secret number \({\bar{x}}\) in a finite search space _S_, and Player II must guess \({\bar{x}}\) by adaptively asking Player I a minimum number of binary questions. Up to _m_ answers may be mendacious/erroneous or may be distorted before reaching Player II. In his monograph “Fault-Tolerant Search Algorithms. Reliable Computation with Unreliable Information”, F. Cicalese provides a comprehensive account of many models of the game and their applications in error-correcting (...) coding with noiseless feedback. Since for \(m>0\) lies the game is not called off by contradictory answers, and repeated answers to the same question are more informative than single answers, the underlying logic of the game with _m_ lies is not boolean. Indeed, the logic of Rényi-Ulam games is Łukasiewicz infinite-valued logic Ł \(_\infty \). In this paper we consider Ulam-Rényi games with variable numbers of lies over infinite search spaces. We characterize the MV-algebras and the unital Specker \(\ell \) -groups given by the logic of these games. (shrink)

Parity games are combinatorial representations of closed Boolean μ-terms. By adding to them draw positions, they have been organized by Arnold and Santocanale [3] and [27] into a μ-calculus whose standard interpretation is over the class of all complete lattices. As done by Berwanger et al. [8] and [9] for the propositional modal μ-calculus, it is possible to classify parity games into levels of a hierarchy according to the number of fixed-point variables. We ask whether this hierarchy (...) collapses w.r.t. the standard interpretation. We answer this question negatively by providing, for each n≥1, a parity game Gn with these properties: it unravels to a μ-term built up with n fixed-point variables, it is not semantically equivalent to any game with strictly less than n−2 fixed-point variables. (shrink)

On a very natural conception of sets, every set has an absolute complement. The ordinary cumulative hierarchy dismisses this idea outright. But we can rectify this, whilst retaining classical logic. Indeed, we can develop a boolean algebra of sets arranged in well-ordered levels. I show this by presenting Boolean Level Theory, which fuses ordinary Level Theory (from Part 1) with ideas due to Thomas Forster, Alonzo Church, and Urs Oswald. BLT neatly implement Conway’s games and surreal numbers; (...) and a natural extension of BLT is definitionally equivalent with ZF. (shrink)

We study the gameGfin related to weak distributivity of a given Boolean algebraB. Consider the following implication: ifBis weakly -distributive then player I does not have a winning strategy in the gameGfin. We show that this implication is true for properBbut it is not true in general.

We prove (in ZFC Set Theory) that all infinite games whose winning sets are of the following forms are determined: (1) (A - S) ∪ B, where A is $\Pi^0_2, \bar\bar{S}, 2^{\aleph_0}$ , and the games whose winning set is B is "strongly determined" (meaning that all of its subgames are determined). (2) A Boolean combination of Σ 0 2 sets and sets smaller than the continuum. This also enables us to show that strong determinateness is not (...) preserved under complementation, improving a result of Morton Davis which required the continuum hypothesis to prove this fact. Various open questions related to the above results are discussed. Our main conjecture is that (2) above remains true when "Σ 0 2 " is replaced by "Borel". (shrink)

Some cardinal invariants from Cichon's diagram can be characterized using the notion of cut-and-choose games on cardinals. In this paper we give another way to characterize those cardinals in terms of infinite games. We also show that some properties for forcing, such as the Sacks Property, the Laver Property and ω ω -boundingness, are characterized by cut-and-choose games on complete Boolean algebras.

The cut and choose game is one of the infinitary games on a complete Boolean algebra B introduced by Jech. We prove that existence of a winning strategy for II in implies semiproperness of B. If the existence of a supercompact cardinal is consistent then so is “for every 1-distributive algebra B II has a winning strategy in ”.

In this paper, we initiate the study of Ehrenfeucht–Fraïssé games for some standard finite structures. Examples of such standard structures are equivalence relations, trees, unary relation structures, Boolean algebras, and some of their natural expansions. The paper concerns the following question that we call the Ehrenfeucht–Fraïssé problem. Given nω as a parameter, and two relational structures and from one of the classes of structures mentioned above, how efficient is it to decide if Duplicator wins the n-round EF game (...) ? We provide algorithms for solving the Ehrenfeucht–Fraïssé problem for the mentioned classes of structures. The running times of all the algorithms are bounded by constants. We obtain the values of these constants as functions of n. (shrink)

We characterize the -distributive law in Boolean algebras in terms of cut and choose games.

Coalitional games raise a number of important questions from the point of view of computer science, key among them being how to represent such games compactly, and how to efficiently compute solution concepts assuming such representations. Marginal contribution nets , introduced by Ieong and Shoham, are one of the simplest and most influential representation schemes for coalitional games. MC-nets are a rulebased formalism, in which rules take the form pattern → value, where “pattern ” is a (...) class='Hi'>Boolean condition over agents, and “value ” is a numeric value. Ieong and Shoham showed that, for a class of what we will call “basic” MC-nets, where patterns are constrained to be a conjunction of literals, marginal contribution nets permit the easy computation of solution concepts such as the Shapley value. However, there are very natural classes of coalitional games that require an exponential number of such basic MC-net rules. We present read-once MC-nets, a new class of MC-nets that is provably more compact than basic MC-nets, while retaining the attractive computational properties of basic MC-nets. We show how the techniques we develop for read-once MC-nets can be applied to other domains, in particular, computing solution concepts in network flow games on series-parallel networks. (shrink)

Fix 2 < n < ω. Let CA n denote the class of cylindric algebras of dimension n, and let RCA n denote the variety of representable CA n ’s. Let L n denote first-order logic restricted to the first n variables. Roughly, CA n, an instance of Boolean algebras with operators, is the algebraic counterpart of the syntax of L n, namely, its proof theory, while RCA n algebraically and geometrically represents the Tarskian semantics of L n. Unlike (...) Boolean algebras having a Stone representation theorem, RCA n ⊊ CA n. Using combinatorial game theory, we show that the existence of certain finite relation algebras RA, which are algebras whose domain consists of binary relations, implies that the celebrated Henkin omitting types theorem fails in a very strong sense for L n. Using special cases of such finite RA ’s, we recover the classical nonfinite axiomatizability results of Monk, Maddux, and Biro on RCA n and we re-prove Hirsch and Hodkinson’s result that the class of completely representable CA n ’s is not first-order definable. We show that if T is an L n countable theory that admits elimination of quantifiers, λ is a cardinal < 2 ℵ 0, and F = 〈 Γ i : i < λ 〉 is a family of complete nonprincipal types, then F can be omitted in an ordinary countable model of T. (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)

The canonical pair of a proof system P is the pair of disjoint NP sets where one set is the set of all satisfiable CNF formulas and the other is the set of CNF formulas that have P-proofs bounded by some polynomial. We give a combinatorial characterization of the canonical pairs of depth d Frege systems. Our characterization is based on certain games, introduced in this article, that are parametrized by a number k, also called the depth. We show (...) that the canonical pair of a depth d Frege system is polynomially equivalent to the pair (Ad+2,Bd+2) where Ad+2 (respectively, Bd+1) are depth d+1 games in which Player I (Player II) has a positional winning strategy. Although this characterization is stated in terms of games, we will show that these combinatorial structures can be viewed as generalizations of monotone Boolean circuits. In particular, depth 1 games are essentially monotone Boolean circuits. Thus we get a generalization of the monotone feasible interpolation for Resolution, which is a property that enables one to reduce the task of proving lower bounds on the size of refutations to lower bounds on the size of monotone Boolean circuits. However, we do not have a method yet for proving lower bounds on the size of depth d games for d>1. (shrink)

We prove a local normal form theorem of the Gaifman type for the infinitary logic L∞ωω whose formulas involve arbitrary unary quantifiers but finite quantifier rank. We use a local Ehrenfeucht-Fraïssé type game similar to the one in [9]. A consequence is that every sentence of L∞ωω of quantifier rank n is equivalent to an infinite Boolean combination of sentences of the form ψ, where ψ has counting quantifiers restricted to the -neighborhood of y.

The class forcing theorem, which asserts that every class forcing notion ${\mathbb {P}}$ admits a forcing relation $\Vdash _{\mathbb {P}}$, that is, a relation satisfying the forcing relation recursion—it follows that statements true in the corresponding forcing extensions are forced and forced statements are true—is equivalent over Gödel–Bernays set theory $\text {GBC}$ to the principle of elementary transfinite recursion $\text {ETR}_{\text {Ord}}$ for class recursions of length $\text {Ord}$. It is also equivalent to the existence of truth predicates for the (...) infinitary languages $\mathcal {L}_{\text {Ord},\omega }$, allowing any class parameter A; to the existence of truth predicates for the language $\mathcal {L}_{\text {Ord},\text {Ord}}$ ; to the existence of $\text {Ord}$ -iterated truth predicates for first-order set theory $\mathcal {L}_{\omega,\omega }$ ; to the assertion that every separative class partial order ${\mathbb {P}}$ has a set-complete class Boolean completion; to a class-join separation principle; and to the principle of determinacy for clopen class games of rank at most $\text {Ord}+1$. Unlike set forcing, if every class forcing notion ${\mathbb {P}}$ has a forcing relation merely for atomic formulas, then every such ${\mathbb {P}}$ has a uniform forcing relation applicable simultaneously to all formulas. Our results situate the class forcing theorem in the rich hierarchy of theories between $\text {GBC}$ and Kelley–Morse set theory $\text {KM}$. (shrink)

The interpretation of propositions in Lukasiewicz's infinite-valued calculus as answers in Ulam's game with lies--the Boolean case corresponding to the traditional Twenty Questions game--gives added interest to the completeness theorem. The literature contains several different proofs, but they invariably require technical prerequisites from such areas as model-theory, algebraic geometry, or the theory of ordered groups. The aim of this paper is to provide a self-contained proof, only requiring the rudiments of algebra and convexity in finite-dimensional vector spaces.

The formal language studied in this paper contains two categories of expressions, terms and formulas. Terms express events, formulas propositions. There are infinitely many atomic terms and complex terms are made up by Boolean operations. Where and are terms the atomic formulas have the form = ( is the same as ), Forb ( is forbidden) and Perm ( is permitted). The formulae are truth functional combinations of these. An algebraic and a model theoretic account of validity are given (...) and an axiomatic system is provided for which they are characteristic.The closure principle, that what is not forbidden is permitted is shown to hold at the level of outcomes but not at the level of events. In the two final sections some other operators are considered and a semantics in terms of action games. (shrink)

In this article, Savage’s theory of decision-making under uncertainty is extended from a classical environment into a non-classical one. The Boolean lattice of events is replaced by an arbitrary ortho-complemented poset. We formulate the corresponding axioms and provide representation theorems for qualitative measures and expected utility. Then, we discuss the issue of beliefs updating and investigate a transition probability model. An application to a simple game context is proposed.

We study a generalization of the standard syntax and game-theoretic semantics of logic, which is based on a duality between two players, to a multiplayer setting. We define propositional and modal languages of multiplayer formulas, and provide them with a semantics involving a multiplayer game. Our focus is on the notion of equivalence between two formulas, which is defined by saying that two formulas are equivalent if under each valuation, the set of players with a winning strategy is the same (...) in the two respective associated games. We provide a derivation system which enumerates the pairs of equivalent formulas, both in the propositional case and in the modal case. Our approach is algebraic: We introduce multiplayer algebras as the analogue of Boolean algebras, and show, as the corresponding analog to Stone’s theorem, that these abstract multiplayer algebras can be represented as concrete ones which capture the game-theoretic semantics. For the modal case we prove a similar result. We also address the computational complexity of the problem whether two given multiplayer formulas are equivalent. In the propositional case, we show that this problem is co-NP-complete, whereas in the modal case, it is PSPACE-hard. (shrink)

The two concepts of probability used in physics are analyzed from the formal and the material points of view. The standard theory corresponds toprob 1 (probability of the coexistence of two properties). A general logicomathematical theory ofprob 2 (probability of transition between states) is presented in axiomatic form. The underlying state algebra is neither Boolean nor Birkhoff-von Neumann but partial Boolean. In the Boolean subalgebras,prob 1 theory holds. The theory presented contains the logicomathematical foundations of quantum mechanics (...) and, as degenerate cases, the theories of stochastic games and of Markov chains. (shrink)

The feasible interpolation theorem for semantic derivations from [J. Krajíček, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, J. Symbolic Logic 62 457–486] allows to derive from some short semantic derivations of the disjointness of two [Formula: see text] sets [Formula: see text] and [Formula: see text] a small communication protocol computing the Karchmer–Wigderson multi-function [Formula: see text] associated with the sets, and such a protocol further yields a small circuit separating [Formula: see text] from (...) [Formula: see text]. When [Formula: see text] is closed upwards, the protocol computes the monotone Karchmer–Wigderson multi-function [Formula: see text] and the resulting circuit is monotone. Krajíček [Interpolation by a game, Math. Logic Quart. 44 450–458] extended the feasible interpolation theorem to a larger class of semantic derivations using the notion of a real communication complexity. In this paper, we generalize the method to a still larger class of semantic derivations by allowing randomized protocols. We also introduce an extension of the monotone circuit model, monotone circuits with a local oracle, that does correspond to communication protocols for [Formula: see text] making errors. The new randomized feasible interpolation thus shows that a short semantic derivation of the disjointness of [Formula: see text], [Formula: see text] closed upwards, yields a small randomized protocol for [Formula: see text] and hence a small monotone CLO separating the two sets. This research is motivated by the open problem to establish a lower bound for proof system [Formula: see text] operating with clauses formed by linear Boolean functions over [Formula: see text]. The new randomized feasible interpolation applies to this proof system and also to cutting planes CP, to small width resolution over CP of Krajíček [Discretely ordered modules as a first-order extension of the cutting planes proof system, J. Symbolic Logic 63 1582–1596] ) and to random resolution RR of Buss, Kolodziejczyk and Thapen [Fragments of approximate counting, J. Symbolic Logic 79 496–525]. The method does not yield yet lengths-of-proofs lower bounds; for this it is necessary to establish lower bounds for randomized protocols or for monotone CLOs. (shrink)

This paper introduces a logic game which can be used to demonstrate the working of Boolean connectives. The simplicity of the system turns out to lead to some interesting meta-theoretical properties, which themselves carry a philosophical import. After introducing the system, we demonstrate an interesting feature of it—that it, while being an accurate model of propositional logic Booleans, does not contain any tautologies nor contradictions. This result allows us to make explicit a limitation of application of propositional logic to (...) those sentences with relatively stable truth values. (shrink)

We prove a local normal form theorem of the Gaifman type for the infinitary logic L∞ωω whose formulas involve arbitrary unary quantifiers but finite quantifier rank. We use a local Ehrenfeucht-Fraïssé type game similar to the one in [9]. A consequence is that every sentence of L∞ωω of quantifier rank n is equivalent to an infinite Boolean combination of sentences of the form ψ, where ψ has counting quantifiers restricted to the -neighborhood of y.

A comprehensive introduction to modal logic is long overdue and this one has many virtues. It is clearly written and should be accessible to any student who has at least one semester of basic logic and is willing to read carefully and think abstractly. The first part, on modal propositional logic, begins with a summary account of classical propositional logic, the axiomatization of Principia Mathematica being the basis for the development of modal logics throughout the book. The transition to modal (...) logic is nicely motivated by a clear presentation of intuitive notions of modality and the requirements to be included in a modal logic. Thereafter three standard systems of modal propositional logic are developed axiomatically, Feys' system T and Lewis' systems S4 and S5. The semantics for these systems is then developed in the manner of Kripke with some terminological modifications. The explanation of accessibility relations between possible worlds is made especially clear through a helpful analogy with certain sorts of games. Decision procedures and completeness proofs are then developed. A similar pattern of exposition is given to modal predicate logic in Part II, the difference being that Henkin-type methods are used in the completeness proofs. Because of the many philosophical problems raised by modal predicate logic, Part II contains more philosophical discussion than Part I. A discussion of identity and descriptions in modal predicate logic is also included. The third and final part is a survey of modal systems beginning with the Lewis' systems S1-S5 and going on to systems weaker and stronger than the Lewis' systems and others which are independent of them. Systems with alternative primitives and axiomatic bases are also discussed. A final chapter discusses the relation of Boolean algebras to modal logics and brief appendices deal with natural deduction systems of modal logic, systems of entailment, alternative notations and the semantics of Kripke and Hintikka among other topics. There are exercises at the end of each chapter. This summary suggests the merits of this introduction, its clear exposition and the enormous amount of material it brings together and summarizes.--R. H. K. (shrink)

This volume brings together a group of logic-minded philosophers and philosophically oriented logicians, mainly from Asia, to address a variety of logical and philosophical topics of current interest, offering a representative cross-section of the philosophical logic landscape in early 21st-century Asia. It surveys a variety of fields, including modal logic, epistemic logic, formal semantics, decidability and mereology. The book proposes new approaches and constructs more powerful frameworks, such as cover theory, an algebraic approach to cut-elimination, and a Boolean approach (...) to causal discovery, to name but a few. Readers may find a wide range of applications of these original works in current research of philosophical logic, especially in the structural and conceptual analysis of some significant semantic properties and formal systems. The variety of topics and issues discussed here will appeal to readers from a broad spectrum of disciplines, ranging from mathematical/philosophical logic, computing science, cognitive science and artificial intelligence, to linguistics, game theory and beyond. (shrink)

We propose a model of unawareness that remains close to the paradigm of Aumann’s model for knowledge [R. J. Aumann, International Journal of Game Theory 28 (1999) 263-300]: just as Aumann uses a correspondence on a state space to define an agent’s knowledge operator on events, we use a correspondence on a state space to define an agent’s awareness operator on events. This is made possible by three ideas. First, like the model of [A. Heifetz, M. Meier, and B. Schipper, (...) Journal of Economic Theory 130 (2006) 78-94], ours is based on a space of partial specifications of the world, partially ordered by a relation of further specification or refinement, and the idea that agents may be aware of some coarser-grained specifications while unaware of some finer-grained specifications; however, our model is based on a different implementation of this idea, related to forcing in set theory. Second, we depart from a tradition in the literature, initiated by [S. Modica and A. Rustichini, Theory and Decision 37 (1994) 107- 124] and adopted by Heifetz et al. and [J. Li, Journal of Economic Theory 144 (2009) 977-993], of taking awareness to be definable in terms of knowledge. Third, we show that the negative conclusion of a well- known impossibility theorem concerning unawareness in [Dekel, Lipman, and Rustichini, Econometrica 66 (1998) 159-173] can be escaped by a slight weakening of a key axiom. Together these points demonstrate that a correspondence on a partial-state space is sufficient to model unawareness of events. Indeed, we prove a representation theorem showing that any abstract Boolean algebra equipped with awareness, knowledge, and belief operators satisfying some plausible axioms is representable as the algebra of events arising from a partial-state space with awareness, knowledge, and belief correspondences. (shrink)

Strong reasoning skills are an important aspect to cultivate in life, as they directly impact decision making on a daily basis. By examining the different ways the world views logic and order, new methods and techniques can be employed to help expand on this skill further in the future. -/- Philosophical Perceptions on Logic and Order is a pivotal scholarly resource that discusses the evolution of logical reasoning and future applications for these types of processes. Highlighting relevant topics including logic (...) patterns, deductive logic, and inductive logic, this publication is an ideal reference source for academicians, students, and researchers that would like to expand their understanding of how society currently employs the use of logical reasoning techniques. (shrink)

Through a phenomenological study of horse-human relations, this article explores the ways in which, as embodied beings, we live relationally, rather than as separate human identities. Conceptually this challenges oppositional logic and humanist assumptions, but where poststructuralist treatments of these issues tend to remain abstract, this article is concerned with an embodied demonstration of the ways in which we experience a relational or in-between logic in our everyday lives.

Prior research suggests brokers do not always act in the best interests of clients, although morally obligated to do so. We empirically investigated this issue focusing on trades executed at best execution price, before and after the introduction of electronic limit-order trading, on the London Stock Exchange. As a result of limit-order trading, the proportion of trades executed at the best execution price for the customer significantly increased. We attribute this to a sustained increase in the liquidity of stocks as (...) a result of limit-order trading, regardless of market capitalisation. We discuss the ethical implications of our findings and conclude that market structures that enhance market competitiveness may help reconcile broker and client interests. (shrink)