The concept of an infinite game played on a finite graph is perhaps novel in the context of an rather extensive recent literature in which infinite games are generally played on an infinite game tree. We claim two advantages for our model, which is admittedly more restrictive. First, our games have a more apparent resemblance to ordinary parlor games in spite of their infinite duration. Second, by distinguishing those nodes of the graph that (...) determine the winning and losing of the game , we are able to offer a complexity analysis that is useful in computer science applications. (shrink)

We present an infinite-game characterization of the well-founded semantics for function-free logic programs with negation. Our game is a simple generalization of the standard game for negation-less logic programs introduced by van Emden [M.H. van Emden, Quantitative deduction and its fixpoint theory, Journal of Logic Programming 3 37–53] in which two players, the Believer and the Doubter, compete by trying to prove a query. The standard game is equivalent to the minimum Herbrand model semantics of logic programming in the (...) sense that a query succeeds in the minimum model semantics iff the Believer has a winning strategy for the game which begins with the Doubter doubting this query. The game for programs with negation that we propose follows the same rules as the standard one, except that the players swap roles every time the play “passes through” negation. We start our investigation by establishing the determinacy of the new game by using some classical tools from the theory of infinite-games. Our determinacy result immediately provides a novel and purely game-theoretic characterization of the semantics of negation in logic programming. We proceed to establish the connections of the game semantics to the existing semantic approaches for logic programming with negation. For this purpose, we first define a refined version of the game that uses degrees of winning and losing for the two players. We then demonstrate that this refined game corresponds exactly to the infinite-valued minimum model semantics of negation [P. Rondogiannis,W.W. Wadge, Minimum model semantics for logic programs with negation-as-failure, ACM Transactions on Computational Logic 6 441–467]. This immediately implies that the unrefined game is equivalent to the well-founded semantics. (shrink)

We show that strong measure zero sets -totally bounded metric space) can be characterized by the nonexistence of a winning strategy in a certain infinite game. We use this characterization to give a proof of the well known fact, originally conjectured by K. Prikry, that every dense \ subset of the real line contains a translate of every strong measure zero set. We also derive a related result which answers a question of J. Fickett.

It is well known that if the nonempty player of the Banach–Mazur game has a winning strategy on a space, then that space is Baire in all powers even in the box product topology. The converse of this implication may also be true: We know of no consistency result to the contrary. In this paper we establish the consistency of the converse relative to the consistency of the existence of a proper class of measurable cardinals.

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.

It is commonly assumed that Aristotle denies any real existence to infinity. Nothing is actually infinite. If, in order to resolve Zeno’s paradoxes, Aristotle must talk of infinity, it is only in the sense of a potentiality that can never be actualized. Aristotle’s solution has been both praised for its subtlety and blamed for entailing a limitation of mathematic. His understanding of the infinite as simply indefinite (the “bad infinite” that fails to reach its accomplishment), his conception (...) of the cosmos and even its prime mover as finite (in the sense of autarchic/self-contained) have been contrasted with the subsequent claim of God as ens infinitum (understood as a “positive” infinity). The goal of this essay is to reexamine the major texts (notably De caelo) and to demonstrate that (1) Aristotle’s claim according to which there is no actual infinite concerns only substances, not processes. (2) That Aristotle does not deny an actual infinite as such. (3) That when considering time and God (qua eternal) Aristotle acknowledges an actual infinite. (shrink)

We prove a number of results on the determinacy of σ-projective sets of reals, i.e., those belonging to the smallest pointclass containing the open sets and closed under complements, countable unions, and projections. We first prove the equivalence between σ-projective determinacy and the determinacy of certain classes of games of variable length <ω^2 (Theorem 2.4). We then give an elementary proof of the determinacy of σ-projective sets from optimal large-cardinal hypotheses (Theorem 4.4). Finally, we show how to generalize the (...) proof to obtain proofs of the determinacy of σ-projective games of a given countable length and of games with payoff in the smallest σ-algebra containing the projective sets, from corresponding assumptions (Theorem 5.1, Theorem 5.4). (shrink)

BioShock Infinite is a piece of fiction that lets one peer into a world where this linearity seems overridden by a multiverse where all the possibilities exist. Stories are important for video games. Its story is one of the reasons BioShock Infinite resonates with audiences all around the world. The field of philosophy that deals with art is called aesthetics. If one think that it's even worth asking the question of whether BioShock Infinite is art or (...) not, then one might want to consider this: What is it we're asking about in this case? When we ask whether Infinite is art, we're asking about the experience of playing it. BioShock Infinite is still one of the greatest video game stories and worlds of all time. In this, it represents a big step towards artful video game design. BioShock succeeds in showing that the possibilities for artful storytelling are infinite. (shrink)

We give a simple game-theoretic proof of Silver's theorem that every analytic set is Ramsey. A set P of subsets of ω is called Ramsey if there exists an infinite set H such that either all infinite subsets of H are in P or all out of P. Our proof clarifies a strong connection between the Ramsey property of partitions and the determinacy of infinite games.

Inspired by Scarf, Zhao, Sandholm and Yang and Zhang, we introduce the model of coalitional population games with infinitely many pure strategies, and define the notions of NTU core and TU core for coalitional population games. We next prove the existence results for NTU cores and TU cores. Furthermore, as an extension of the NTU core, we introduce the notion of strong equilibria and prove the existence theorem of strong equilibria.

Let Mn♯ denote the minimal active iterable extender model which has n Woodin cardinals and contains all reals, if it exists, in which case we denote by Mn the class-sized model obtained by iterating the topmost measure of Mn class-many times. We characterize the sets of reals which are Σ1-definable from R over Mn, under the assumption that projective games on reals are determined:1. for even n, Σ1Mn=⅁RΠn+11;2. for odd n, Σ1Mn=⅁RΣn+11.This generalizes a theorem of Martin and Steel for (...) L, that is, the case n=0. As consequences of the proof, we see that determinacy of all projective games with moves in R is equivalent to the statement that Mn♯ exists for all n∈N, and that determinacy of all projective games of length ω2 with moves in N is equivalent to the statement that Mn♯ exists and satisfies AD for all n∈N. (shrink)

Turn taking is observed in many field and laboratory settings captured by various widely studied 2 × 2 games. This article develops a repeated game model that allows us to systematically investigate turn-taking behavior in many 2 × 2 games, including the battle of the sexes, the game of chicken, the game of common-pool-resources assignment, and a particular version of the prisoners’ dilemma. We consider the “turn taking with independent randomizations” (TTIR) strategy that achieves three objectives: (a) helping (...) the players reach the turn-taking path, (b) resolving the question of who takes the good turn first, and (c) deterring defection. We determine conditions under which there exists a unique TTIR strategy profile that can be supported as a subgame-perfect equilibrium. We also show that there exist conditions under which an increase in the “degree of conflict” of the stage game leads to a decrease in the expected number of periods in reaching the turn-taking path. (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 represent truth sets for a variety of the well known semantic theories of truth as those sets consisting of all sentences for which a player has a winning strategy in an infinite two person game. The classifications of the games considered here are simple, those over the natural model of arithmetic being all within the arithmetical class of $\Sum_{3}^{0}$.

Almost more than any other sport, baseball has long attracted the interest of writers and intellectuals. Relatively few of them have been philosophers however. Alva Noe, a celebrated philosopher, here proposes to collect and rework his short articles and blog posts (many of which first appeared on npr.org) on baseball into a cohesive and accessible book that tries to tease out its deeper meanings - and to advance a view of what baseball ultimately is all about. A basic theme will (...) run through the book, which is that fundamentally baseball is concerned with questions of responsibility and liability - i.e. who gets credit or blame for a play. It is starting from this fundamental insight that Noe then ranges over diverse topics like the slowness of baseball and the virtues of boredom, why fans write down box scores, the meaning of the no-hitter, television replays, the aesthetics of ballparks, how we learn to 'see' baseball like we learn to look at art, the ethics of performance enhancing drugs, the nature of fandom, and reflections on rules and umpires. Noe's writing voice is informal and personal, and always puts the details of the sport before the ideas. Ultimately, his essays are part of a larger view of baseball as fundamentally a game about values - and not simply, as some would have it, a numbers game. (shrink)

We consider a real-valued function f defined on the set of infinite branches X of a countably branching pruned tree T. The function f is said to be a limsup function if there is a function $u \colon T \to \mathbb {R}$ such that $f(x) = \limsup _{t \to \infty } u(x_{0},\dots,x_{t})$ for each $x \in X$. We study a game characterization of limsup functions, as well as a novel game characterization of functions of Baire class 1.

The general aim of this paper is to introduce some ideas of the theory of infinite topological games into the philosophical debate on supertasks. First, we discuss the elementary aspects of some infinite topological games, among them the Banach-Mazur game.Then it is shown that the Banach-Mazur game may be conceived as a Newtonian supertask.In section 4 we propose to conceive physical experiments as infinite games. This leads to the distinction between determined and undetermined experiments (...) and the problem of how it is related to that between determinism and indeter-minism. Finally the role of the Axiom of Choice as a source of indetermi-nacy of supertasks is discussed. (shrink)

Motivated by aspects of reasoning in theories of physics, Robin Giles defined a characterization of infinite valued Łukasiewicz logic in terms of a game that combines Lorenzen-style dialogue rules for logical connectives with a scheme for betting on results of dispersive experiments for evaluating atomic propositions. We analyze this game and provide conditions on payoff functions that allow us to extract many-valued truth functions from dialogue rules of a quite general form. Besides finite and infinite valued Łukasiewicz logics, (...) also Meyer and Slaney’s Abelian logic and Cancellative Hoop Logic turn out to be characterizable in this manner. (shrink)

Banach introduced the following two-person, perfect information, infinite game on the real numbers and asked the question: For which sets $A \subseteq \mathbf{R}$ is the game determined????? Rules: The two players alternate moves starting with player I. Each move a n is legal iff it is a real number and $0 , and for $n > 1, a_n . The first player to make an illegal move loses. Otherwise all moves are legal and I wins iff ∑ a n (...) exists and ∑ a n ∈ A. We will look at this game and some variations of it, called Banach games. In each case we attempt to find the relationship between Banach determinancy and the determinancy of other well-known and much-studied games. (shrink)

This paper criticizes non-constructive uses of set theory in formal economics. The main focus is on results on preference aggregation and Arrow’s theorem for infinite electorates, but the present analysis would apply as well, e.g., to analogous results in intergenerational social choice. To separate justified and unjustified uses of infinite populations in social choice, I suggest a principle which may be called the Hildenbrand criterion and argue that results based on unrestricted axiom of choice do not meet this (...) criterion. The technically novel part of this paper is a proposal to use a set-theoretic principle known as the axiom of determinacy ), not as a replacement for Choice, but simply to eliminate applications of set theory violating the Hildenbrand criterion. A particularly appealing aspect of \ from the point of view of the research area in question is its game-theoretic character. (shrink)

An overview of different versions and applications of Lorenzen’s dialogue game approach to the foundations of logic, here largely restricted to the realm of manyvalued logics, is presented. Among the reviewed concepts and results are Giles’s characterization of Łukasiewicz logic and some of its generalizations to other fuzzy logics, including interval based logics, a parallel version of Lorenzen’s game for intuitionistic logic that is adequate for finite- and infinite-valued Gödel logics, and a truth comparison game for infinite-valued Gödel (...) logic. (shrink)

We consider the infinite game where player ONE chooses terms of a strictly increasing sequence of first category subsets of a space and TWO chooses nowhere dense sets. If after ω innings TWO's nowhere dense sets cover ONE's first category sets, then TWO wins. We prove a theorem which implies for the real line: If TWO has a winning strategy which depends on the most recent n moves of ONE only, then TWO has a winning strategy depending on the (...) most recent 3 moves of ONE (Corollary 3). Our results give some new information concerning Problem 1 of [S1] and clarifies some of the results in [B-J-S] and in [S1]. (shrink)

I consider the natural infinitary variations of the games Wordle and Mastermind, as well as their game‐theoretic variations Absurdle and Madstermind, considering these games with infinitely long words and infinite color sequences and allowing transfinite game play. For each game, a secret codeword is hidden, which the codebreaker attempts to discover by making a series of guesses and receiving feedback as to their accuracy. In Wordle with words of any size from a finite alphabet of n letters, (...) including infinite words or even uncountable words, the codebreaker can nevertheless always win in n steps. Meanwhile, the mastermind number, defined as the smallest winning set of guesses in infinite Mastermind for sequences of length ω over a countable set of colors without duplication, is uncountable, but the exact value turns out to be independent of, for it is provably equal to the eventually different number, which is the same as the covering number of the meager ideal. I thus place all the various mastermind numbers, defined for the natural variations of the game, into the hierarchy of cardinal characteristics of the continuum. (shrink)

We study the equilibrium behavior of informed traders interacting with market scoring rule (MSR) market makers. One attractive feature of MSR is that it is myopically incentive compatible: it is optimal for traders to report their true beliefs about the likelihood of an event outcome provided that they ignore the impact of their reports on the profit they might garner from future trades. In this paper, we analyze non-myopic strategies and examine what information structures lead to truthful betting by traders. (...) Specifically, we analyze the behavior of risk-neutral traders with incomplete information playing in a dynamic game. We consider finite-stage and infinite-stage game models. For each model, we study the logarithmic market scoring rule (LMSR) with two different information structures: conditionally independent signals and (unconditionally) independent signals. In the finite-stage model, when signals of traders are independent conditional on the state of the world, truthful betting is a Perfect Bayesian Equilibrium (PBE). Moreover, it is the unique Weak Perfect Bayesian Equilibrium (WPBE) of the game. In contrast, when signals of traders are unconditionally independent, truthful betting is not a WPBE. In the infinite-stage model with unconditionally independent signals, there does not exist an equilibrium in which all information is revealed in a finite amount of time. We propose a simple discounted market scoring rule that reduces the opportunity for bluffing strategies. We show that in any WPBE for.. (shrink)

For X a separable metric space and $\alpha$ an infinite ordinal, consider the following three games of length $\alpha$ : In $G^{\alpha}_1$ ONE chooses in inning $\gamma$ an $\omega$ –cover $O_{\gamma}$ of X; TWO responds with a $T_{\gamma}\in O_{\gamma}$ . TWO wins if $\{T_{\gamma}:\gamma<\alpha\}$ is an $\omega$ –cover of X; ONE wins otherwise. In $G^{\alpha}_2$ ONE chooses in inning $\gamma$ a subset $O_{\gamma}$ of ${\sf C}_p(X)$ which has the zero function $\underline{0}$ in its closure, and TWO responds with (...) a function $T_{\gamma}\in O_{\gamma}$ . TWO wins if $\underline{0}$ is in the closure of $\{T_{\gamma}:\gamma<\alpha\}$ ; otherwise, ONE wins. In $G^{\alpha}_3$ ONE chooses in inning $\gamma$ a dense subset $O_{\gamma}$ of ${\sf C}_p(X)$ , and TWO responds with a $T_{\gamma}\in O_{\gamma}$ . TWO wins if $\{T_{\gamma}:\gamma<\alpha\}$ is dense in ${\sf C}_p(X)$ ; otherwise, ONE wins. After a brief survey we prove: 1. If $\alpha$ is minimal such that TWO has a winning strategy in $G^{\alpha}_1$ , then $\alpha$ is additively indecomposable (Theorem 4) 2. For $\alpha$ countable and minimal such that TWO has a winning strategy in $G^{\alpha}_1$ on X, the following statements are equivalent (Theorem 9): a) TWO has a winning strategy in $G^{\alpha}_2$ on ${\sf C}_p(X)$ . b) TWO has a winning strategy in $G^{\alpha}_3$ on ${\sf C}_p(X)$ . 3. The Continuum Hypothesis implies that there is an uncountable set X of real numbers such that TWO has a winning strategy in $G^{\omega^2}_1$ on X (Theorem 10). (shrink)

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 solve a longstanding problem by providing a denotational model for nondeterministic programs that identifies two programs iff they have the same range of possible behaviours. We discuss the difficulties with traditional approaches, where divergence is bottom or where a term denotes a function from a set of environments. We see that making forcing explicit, in the manner of game semantics, allows us to avoid these problems.We begin by modelling a first-order language with sequential I/O and unbounded nondeterminism. Then we (...) extend the model to a calculus with higher-order and recursive types, by adapting standard game semantics. Traditional adequacy proofs using logical relations are not applicable, so we use instead a novel hiding and unhiding argument. (shrink)

In the second part of the study the Chiliastic Soul concept is discussed as the goal of unity. This is done by focusing on the Castalian "game" and the death of Joseph Knecht. In addition, evidence is presented for certain fundamental conceptual similarities in the thought of Hesse and Hegel and Hesse and Jung, respectively. The author argues not only for the relevance of dialectics as key to a full understanding of Hesse but for the proposition that Hegel, Jung, and (...) Hesse share a primary intuition of ultimate unity or non-duality which shows striking parallels to the metaphysical foundations of the I Ching, Lao-Tze's tao, and the Vedantic atman-brahman identity. Finally, the death of Joseph Knecht is interpreted as affirmation of transformation in the light of Jungian alchemical symbolism. (shrink)

First-order logic is known to have a severely limited expressive power on finite structures. As a result, several different extensions have been investigated, including fragments of second-order logic, fixpoint logic, and the infinitary logic L∞ωω in which every formula has only a finite number of variables. In this paper, we study generalized quantifiers in the realm of finite structures and combine them with the infinitary logic L∞ωω to obtain the logics L∞ωω, where Q = {Qi: iε I} is a family (...) of generalized quantifiers on finite structures. Using the logics L∞ωω, we can express polynomial-time properties that are not definable in L∞ωω, such as “there is an even number of x” and “there exists at least n/2 x” , without going to second-order logic. We show that equivalence of finite structures relative to L∞ωω can be characterized in terms of certain pebble games that are a variant of the Ehrenfeucht—Fraïssé games. We combine this game-theoretic characterization with sophisticated combinatorial tools from Ramsey theory, such as van der Waerden's Theorem and Folkman's Theorem, in order to investigate the scope and limits of generalized quantifiers in finite model theory. We obtain sharp lower bounds for expressibility in the logics L∞ωω and discover an intrinsic difference between adding finitely many simple unary generalized quantifiers to L∞ωω adding infinitely many. In particular, we show that if Qis a finite sequence of simple unary generalized quantifiers, then the equicardinality, or Härtig, quantifier is not definable in L∞ωω. We also show that the query “does the equivalence relation E have an even number of equivalence classes” is not definable in the extension L∞ωω of L∞ωω by the Härtig quantifier I and any finite sequence Q of simple unary generalized quantifiers. (shrink)

In this paper we develop an Ehrenfeucht‐Fraïssé game for. Unlike the standard Ehrenfeucht‐Fraïssé games which are modeled solely after the behavior of quantifiers, this new game also takes into account the behavior of connectives in logic. We prove the adequacy theorem for this game. We also apply the new game to prove complexity results about infinite binary strings.

The representations of deep convolutional neural networks (CNNs) are formed from generalizing similarities and abstracting from differences in the manner of the empiricist theory of abstraction (Buckner, Synthese 195:5339–5372, 2018). The empiricist theory of abstraction is well understood to entail infinite regress and circularity in content constitution (Husserl, Logical Investigations. Routledge, 2001). This paper argues these entailments hold a fortiori for deep CNNs. Two theses result: deep CNNs require supplementation by Quine’s “apparatus of identity and quantification” in order to (...) (1) achieve concepts, and (2) represent objects, as opposed to “half-entities” corresponding to similarity amalgams (Quine, Quintessence, Cambridge, 2004, p. 107). Similarity amalgams are also called “approximate meaning[s]” (Marcus & Davis, Rebooting AI, Pantheon, 2019, p. 132). Although Husserl inferred the “complete abandonment of the empiricist theory of abstraction” (a fortiori deep CNNs) due to the infinite regress and circularity arguments examined in this paper, I argue that the statistical learning of deep CNNs may be incorporated into a Fodorian hybrid account that supports Quine’s “sortal predicates, negation, plurals, identity, pronouns, and quantifiers” which are representationally necessary to overcome the regress/circularity in content constitution and achieve objective (as opposed to similarity-subjective) representation (Burge, Origins of Objectivity. Oxford, 2010, p. 238). I base myself initially on Yoshimi’s (New Frontiers in Psychology, 2011) attempt to explain Husserlian phenomenology with neural networks but depart from him due to the arguments and consequently propose a two-system view which converges with Weiskopf’s proposal (“Observational Concepts.” The Conceptual Mind. MIT, 2015. 223–248). (shrink)

We consider an infinite two-person game. The second player has a winning perfect information strategy; we show that this player has a winning strategy which depends on substantially less information. The game studied here is a variation on a game of Gale.

This collection of papers in epistemic logic is oriented towards applications to game theory and individual decision theory. Most of these papers were presented at the inaugural conference of the LOFT (Logic for the Theory and Games and Decisions) conference series, which took place in 1994 in Marseille. Among the notions dealt with are those of common knowledge and common belief, infinite hierarchies of beliefs and belief spaces, logical omniscience, positive and negative introspection, backward induction and rationalizable equilibria (...) in game theory. (shrink)

Several results about the game of cops and robbers on infinite graphs are analyzed from the perspective of computability theory. Computable robber-win graphs are constructed with the property that no computable robber strategy is a winning strategy, and such that for an arbitrary computable ordinal \, any winning strategy has complexity at least \}\). Symmetrically, computable cop-win graphs are constructed with the property that no computable cop strategy is a winning strategy. Locally finite infinite trees and graphs are (...) explored. The Turing computability of a binary relation used to classify cop-win graphs is studied, and the computational difficulty of determining the winner for locally finite computable graphs is discussed. (shrink)