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)

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)

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)

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.

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)

We characterize the (κ, Λ, < μ)-distributive law in Boolean algebras in terms of cut and choose games $\scr{G}_{<\mu}^{\kappa}(\lambda)$ , when μ ≤ κ ≤ Λ and κ<κ = κ. This builds on previous work to yield game-theoretic characterizations of distributive laws for almost all triples of cardinals κ, Λ, μ with μ ≤ Λ, under GCH. In the case when μ ≤ κ ≤ Λ and κ<κ = κ, we show that it is necessary to consider whether (...) the κ-stationarity of Pκ+Λ in the ground model is preserved by B. In this vein, we develop the theory of κ-club and κ-stationary subsets of Pκ+Λ. We also construct Boolean algebras in which Player I wins $\scr{G}_{\kappa}^{\kappa}(\kappa ^{+})$ but the (κ, ∞, κ)-d.1, holds, and, assuming GCH, construct Boolean algebras in which many games are undetermined. (shrink)

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

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)

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)

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.

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

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)

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.

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)

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.

We argue that pedagogic authority relies on love, which is misunderstood if seen as a matter of actions and subjects. Love is based not on finite subjects and objects existing in Euclidean space and linear time, but, rather, on the non-finite ontology, space and time of relations. Loving authority is a matter of calling and vocation, arising from the spontaneous and simultaneous call-and-response of a lively relation. We make this argument through a reading of Buber’s I–You relation and Murdoch’ s (...) account of the responsiveness of ascetic discipline. In presenting this analysis, we draw upon a case study from a research project on Australian teachers and students. (shrink)

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)

This study examined the link between employees’ adult attachment orientations and perceptions of line managers’ interpersonal justice behaviors, and the moderating effect of national culture. Participants from countries categorized as low collectivistic and high collectivistic completed an online survey. Attachment anxiety and avoidance were negatively related to interpersonal justice perceptions. Cultural differences did not moderate the effects of avoidance. However, the relationship between attachment anxiety and interpersonal justice was non-significant in the Southern Asia cultural cluster. Our findings indicate the importance (...) of ‘fit’ between cultural relational values and individual attachment orientations in shaping interpersonal justice perceptions, and highlight the need for more non-western organizational justice research. (shrink)

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. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim).

Abstract In this article we develop a relational understanding of sociality, that is, an account of social life that takes relation as primary. This stands in contrast to the common assumption that relations arise when subjects interact, an account that gives logical priority to separation. We will develop this relational understanding through a reading of the work of Martin Buber, a social philosopher primarily interested in dialogue, meeting, relationship, and the irreducibility and incomparability of reality. In particular, the article contrasts (...) Buber’s work with that of poststructuralist theorists who take as their starting point the deconstruction of the Hegelian logic of binary oppositions. Deconstruction understands difference as the excess that undoes the binary, but Buber, we argue, shows how difference derives from the primacy and ontological undefinability of relation. Relational logic does not exclude the logic of separations and oppositions: relation is the primal ground that makes separations possible. Content Type Journal Article Pages 1-13 DOI 10.1007/s11841-011-0278-9 Authors Andrew Metcalfe, School of Social Sciences and International Studies, University of New South Wales, Sydney, NSW 2052, Australia Ann Game, School of Social Sciences and International Studies, University of New South Wales, Sydney, NSW 2052, Australia Journal Sophia Online ISSN 1873-930X Print ISSN 0038-1527. (shrink)

The mechanisms responsible for the fine tuning of development, where the wildtype phenotype is reproduced with high fidelity, are not well understood. The difficulty in approaching this problem is the identification of mutant phenotypes indicative of a defect in these fine‐tuning control mechanisms. Evolutionary biologists have used asymmetry as a measure of developmental homeostasis. The rationale for this was that, since the same genome controls the development of the left and right sides of a bilaterally symmetrical organism, departures from symmetry (...) can be used to measure genetic or environmental perturbations. This paper examines the relationship between asymmtry and resistance to organophosphorous insecticides in the Australian sheep blowfly, Lucilia cuprina. A resistance gene, Rop‐1, which encodes a carboxylesterase enzyme, also confers a significant increase in asymmetry. Continued exposure of resistant populations to insecticide has selected a dominant suppressor of the asymmetry phenotype. Genetic evidence indicates that the modifier is the L. cuprina Notch homologue. (shrink)

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)

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)

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