Games played by Boole and Galois

We define an infinite class of 2-pile subtraction games, where the amount that can be subtracted from both piles simultaneously is an extended Boolean function f of the size of the piles, or a function over GF(2). Wythoff's game is a special case. For each game, the second player winning positions are a pair of complementary sequences. Sample games are presented, strategy complexity questions are discussed, and possible further studies are indicated. The motivation stems from the major contributions of Professor Peter Hammer to the theory and applications of Boolean functions.     

Lattice games without rational strategies

We show that the lattice games of Guo and Miller support universal computation, disproving their conjecture that all lattice games have rational strategies. We also state an explicit counterexample to that conjecture: a three dimensional lattice game whose set of winning positions does not have a rational generating function.     

On Dedekind’s problem for complete simple games

We state an integer linear programming formulation for the unique characterization of complete simple games, i.e. a special subclass of monotone Boolean functions. In order to apply the parametric Barvinok algorithm to obtain enumeration formulas for these discrete objects we provide a tailored decomposition of the integer programming formulation into a finite list of suitably chosen sub-cases. As for the original enumeration problem of Dedekind on Boolean functions we have to introduce some parameters to be able to derive exact formulas for small parameters. Recently, Freixas et al. have proven an enumeration formula for complete simple games with two types of voters. We will provide a shorter proof and a new enumeration formula for complete simple games with two minimal winning vectors.     

Irregular gaming areas

This work deals with those discrete games, the corresponding payoff matrices of which might be changed according to some unknown law within a given period of time. Such games are often seen in irregular gaming areas where some existing situations can act upon the elements of the payoff matrix. A computational algorithm is proposed, and a new management game under catastrophe conditions pertaining to payoff matrix is given. Graph theory, theory of Games, simulation and Boolean algebra are used.     

体育赛事对局结果预测

甲乙双方展开系列赛,每局必分胜负,那么,若要分出输赢,平均需要比赛多少局？通过实例对这一问题进行研究：将胜负概率的乘积作为一个整体,由此可获得一个一般性公式,并以斯诺克比赛为例,介绍其应用.     

On the use of binary decision diagrams for solving problems on simple games

Simple games are yes/no cooperative games which arise in many practical applications. Recently, we have used reduced ordered binary decision diagrams and quasi-reduced ordered binary decision diagrams (abbreviated as Robdds and Qobdds, respectively) for the representation of simple games and for the computation of some power indices. In the present paper, we continue this work. We show how further important computational problems on simple games can be solved using Qobdds, viz. the identification of some key players, the computation of the desirability relation on individuals, the test whether a simple game is proper and strong, respectively, and the computation of Qobdd-representations for the sets of all minimal winning coalitions, all shift-minimal winning coalitions and all blocking coalitions, respectively. Applications of these solutions include the computation of recent power indices based on shift-minimal winning coalitions and the test for linear separability of a directed simple game.     

Enumeration by kernel positions

We introduce a class of two-player games on posets with a rank function, in which each move of the winning strategy is unique. This allows one to enumerate the kernel positions by rank. The main example is a simple game on words in which the number of kernel positions of rank n is a signed factorial multiple of the nth Bernoulli number of the second kind. Generalizations to the degenerate Bernoulli numbers and to negative integer substitutions into the Bernoulli polynomials are developed. Using an appropriate scoring system for each function with an appropriate Newton expansion we construct a game in which the expected gain of a player equals the definite integral of the function on the interval [0,1].     

σ‐short Boolean algebras

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)     

Some undecidable determined games

Computing machines using algorithms play games and even learn to play games. However, the inherent finiteness properties of algorithms impose limitations on the game playing abilities of machines. M. Rabin illustrated this limitation in 1957 by constructing a two-person win-lose game with decidable rules but no computable winning strategies. Rabin's game was of the type where two players take turns choosing integers to satisfy some decidable but very complicated winning condition. In the present paper we obtain similar theorems of this type but the winning conditions are extremely simple relations (polynomial equations). Specific examples are given.     

Regular simple games

Using Kelley's intersection number (and a variant of it) we define two classes of simple games, the regular and the strongly regular games. We show that the strongly regular games are those in which the set of winning coalitions and the set of losing coalitions can be strictly separated by a finitely additive probability measure. This, in particular, provides a combinatorial characterization for the class of finite weighted majority games within the finite simple games. We also prove that regular games have some nice properties and show that the finite regular games are exactly those simple games which are uniquely determined by their counting vector. This, in particular, generalizes a result of Chow and Lapidot.     

A complete analysis of Von Neumann's hackendot

In this note we are going to present a winning strategy for a game on trees (reminiscent of the games of Hackenbush type) which, it seems, has been invented by J. Von Neumann in order to demonstrate the inadequacy of a mere existential solution in some tasks. A complete analysis of the game is presented. The strategy itself consists of a reduction step (reducing to half the size of the game), subsequent using this until one obtains a trivial game, and a rule for how to choose a correct move in the unreduced case from that in the reduced one. The nim-function for the positions of the game can be calculated using this procedure.     

Simple games and weighted games: A theoretical and computational viewpoint

It is a well-known result in the theory of simple games that a game is weighted if and only if it is trade robust. In this paper we propose a variant of trade robustness, that we call invariant-trade robustness, which is enough to determine whether a simple game is weighted. To test whether a simple game is invariant-trade robust we do not need to consider all winning coalitions; a reduced subset of minimal winning coalitions is enough.We make a comparison between the two methods (trade robustness and invariant-trade robustness) to check whether a simple game is weighted. We also provide by means of algorithms a full classification using both methods, for simple games with less than 8 voters according to the maximum level of (invariant-)trade robustness they achieve.     

布尔矩阵的可实现问题及其与色数问题的关系

讨论了布尔矩阵的可实现问题及其与色数问题的关系.首先给出布尔矩阵可实现的一些充要条件,讨论可实现布尔矩阵的性质,其次证明可实现布尔矩阵的容度等于该矩阵所生成的图的色数;简单图的邻接矩阵的对偶阵是可实现的,且其容度就是简单图的色数的一个上界.     

Tarski's Fixpoint Lemma and combinatorial games

Using Tarski's Fixpoint Lemma for order preserving maps of a complete lattice into itself, a new, lattice theoretic proof is given for the existence of persistent strategies for combinatorial games as well as for games with a topological tolerance and games on lattices. Further, the existence of winning strategies is obtained for games on superalgebraic lattices, which includes the case of ordinary combinatorial games. Finally, a basic representation theorem is presented for those lattices.     

A mathematical analysis of badminton scoring systems

The International Badminton Federation recently introduced rule changes to make the game faster and more entertaining, by influencing how players score points and win games. We assess the fairness of both systems by applying combinatorics, probability theory and simulation to extrapolate known probabilities of winning individual rallies into probabilities of winning games and matches. We also measure how effective the rule changes are by comparing the numbers of rallies per game and the scoring patterns within each game, using data from the 2006 Commonwealth Games to demonstrate our results. We then develop subjective Bayesian methods for specifying the probabilities of winning. Finally, we describe how to propagate this information with observed data to determine posterior predictive distributions that enable us to predict match outcomes before and during play.     

Modified Schmidt games and Diophantine approximation with weights

We show that the sets of weighted badly approximable vectors in Rn are winning sets of certain games, which are modifications of (α,β)-games introduced by W.M. Schmidt in 1966. The latter winning property is stable with respect to countable intersections, and is shown to imply full Hausdorff dimension.     

Lion and man—can both win?

This paper is concerned with continuous-time pursuit and evasion games. Typically, we have a lion and a man in a metric space: they have the same speed, and the lion wishes to catch the man while the man tries to evade capture. We are interested in questions of the following form: is it the case that exactly one of the man and the lion has a winning strategy?As we shall see, in a compact metric space at least one of the players has a winning strategy. We show that, perhaps surprisingly, there are examples in which both players have winning strategies. We also construct a metric space in which, for the game with two lions versus one man, neither player has a winning strategy. We prove various other (positive and negative) related results, and pose some open problems.     

Switching induced complex dynamics in an extended logistic map

Switching strategies have been related to the so-called Parrondian games, where the alternation of two losing games yields a winning game. We can consider two dynamics that, by themselves, yield different simple dynamical behaviors, but when alternated, yield complex trajectories. In the analysis of the alternate-extended logistic map, we observe a plethora of complex dynamic behaviors, which coexist with a super stable extinction solution.