A Stochastic Analysis of Some Two‐Person Sports

We consider two‐person sports where each rally is initiated by a server, the other player (the receiver) becoming the server when he/she wins a rally. Historically, these sports used a scoring based on the side‐out scoring system, in which points are only scored by the server. Recently, however, some federations have switched to the rally‐point scoring system in which a point is scored on every rally. As various authors before us, we study how much this change affects the game. Our approach is based on a rally‐level analysis of the process through which, besides the well‐known probability distribution of the scores, we also obtain the distribution of the number of rallies. This yields a comprehensive knowledge of the process at hand, and allows for an in‐depth comparison of both scoring systems. In particular, our results help to explain why the transition from one scoring system to the other has more important implications than those predicted from game‐winning probabilities alone. Some of our findings are quite surprising, and unattainable through Monte Carlo experiments. Our results are of high practical relevance to international federations and local tournament organizers alike, and also open the way to efficient estimation of the rally‐winning probabilities.     

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.     

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.     

The existence of serial correlation and its effect on the format of a championship playoff series

The specific home/away sequencing of games has been a point of contention in the championship series of professional sports leagues. This research analyses data from the National Basketball Association (NBA) Finals in developing a logistic-regression model to predict the outcome of games that takes into consideration several factors, including home-court advantage and game-to-game momentum. It is found that negative serial correlation exists such that the team that wins one game is more likely to lose the next game of the series. This model is then used to predict the probability of each team winning each of the games within the series, and these probabilities are combined to evaluate alternative playoff formats. It is found that different formats are appropriate depending on the nature of momentum, and that the format used by the NBA may minimize travel requirements, but other formats may perform better in extending the length of the series.     

乒乓球赛制的概率分析

乒乓球比赛的每局原先是21分制现在是11分制,单打由5局3胜制改为7局4胜制。赛制的改变增加了比赛结果的偶然性。本文用概率方法对赛制的改变进行了定量分析,给出了新赛制和旧赛制下运动员取胜的概率。     

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.     

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.     

Coalition formation in simple games with dominant players

A player, in a proper and monotonic simple game, is dominant if he holds a “strict majority” within a winning coalition. A (non-dictatorial) simple game is dominated if it contains exactly one dominant player. We investigate several possibilities of coalition formation in dominated simple games, under the assumption that the dominant player is given a mandate to form a coalition. The relationship between the various hypotheses on coalition formation in dominated games is investigated in the first seven sections. In the last section we classify real-life data on European parliaments and town councils in Israel.     

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.     

体育赛事对局结果预测

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

Theoretical analysis and numerical simulation of Parrondo’s paradox game in space

A multi-agent spatial Parrondo game model is designed according to the cooperative Parrondo’s paradox proposed by Toral. The model is composed of game A and game B. Game A is a zero-sum game between individuals, reflecting competitive interaction between an individual and its neighbors. The winning or losing probability of one individual in game B depends on its neighbors’ winning or losing states, reflecting the dependence that individuals has on microhabitat and the overall constraints that the microhabitat has on individuals. By using the analytical approach based on discrete-time Markov chain, we analyze game A, game B and the random combination of game A+B, and obtain corresponding stationary distribution probability and mathematical expectations. We have established conditions of the weak and strong forms of the Parrondo effect, and compared the computer simulation results with the analytical results so as to verify their validity. The analytical results reflect that competition results in the ratchet effect of game B, which generates Parrondo’s Paradox that the combination of the losing games can produce a winning result.     

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.     

Games with Unknown Past

We define a new type of two player game occurring on a tree. The tree may have no root and may have arbitrary degrees of nodes. These games extend the class of games considered by Gurevich-Harrington in [5]. We prove that in the game one of the players has a winning strategy which depends on finite bounded information about the past part of a play and on future of each play that is isomorphism types of tree nodes. This result extends further the Gurevich-Harrington determinacy theorem from [5].     

Atomic weights and the combinatorial game of bipass

We define an all-small ruleset, bipass, within the framework of normal play combinatorial games. A game is played on finite strips of black and white stones. Stones of different colors are swapped provided they do not bypass one of their own kind. We find a simple surjective function from the strips to integer atomic weights (Berlekamp, Conway and Guy 1982) that measures the number of units in all-small games. This result provides explicit winning strategies for many games, and in cases where it does not, it gives narrow bounds for the canonical form game values. We find game values for some parametrized families of games, including an infinite number of strips of value ?, and we prove that the game value ?2 does not appear as a disjunctive sum of bipass. Lastly, we define the notion of atomic weight tameness, and prove that optimal misére play bipass resembles optimal normal play.     

A <Emphasis Type="Italic">q</Emphasis>-player impartial avoidance game for generating finite groups

We study a q-player variation of the impartial avoidance game introduced by Anderson and Harary, where q is a prime. The game is played by the q players taking turns selecting previously-unselected elements of a finite group. The losing player is the one who selects an element that causes the set of jointly-selected elements to be a generating set for the group, with the previous player winning. We introduce a ranking system for the other players to prevent coalitions. We describe the winning strategy for these games on cyclic, nilpotent, dihedral, and dicyclic groups.     

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.     

Conference structures and fair allocation rules

To describe how the outcome of a cooperative game might depend on which groups of players hold cooperative planning conferences, we study allocation rules, which are functions mapping conference structures to payoff allocations. An allocation rule is fair if every conference always gives equal benefits to all its members. Any characteristic function game without sidepayments has a unique fair allocation rule. The fair allocation rule also satisfies a balanced contributions formula, and is closely related to Harsanyi's generalized Shapley value for games without sidepayments. If the game is superadditive, then the fair allocation rule also satisfies a stability condition.     

On the optimality of the uniform random strategy

Biased Maker‐Breaker games, introduced by Chvátal and Erd?s, are central to the field of positional games and have deep connections to the theory of random structures. The main questions are to determine the smallest bias needed by Breaker to ensure that Maker ends up with an independent set in a given hypergraph. Here we prove matching general winning criteria for Maker and Breaker when the game hypergraph satisfies certain “container‐type” regularity conditions. This will enable us to answer the main question for hypergraph generalizations of the H‐building games studied by Bednarska and ?uczak as well as a generalization of the van der Waerden games introduced by Beck. We find it remarkable that a purely game‐theoretic deterministic approach provides the right order of magnitude for such a wide variety of hypergraphs, while the analogous questions about sparse random discrete structures are usually quite challenging.     

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.     

From winning strategy to Nash equilibrium

Game theory is usually considered applied mathematics, but a few game‐theoretic results, such as Borel determinacy, were developed by mathematicians for mathematics in a broad sense. These results usually state determinacy, i.e., the existence of a winning strategy in games that involve two players and two outcomes saying who wins. In a multi‐outcome setting, the notion of winning strategy is irrelevant yet usually replaced faithfully with the notion of (pure) Nash equilibrium. This article shows that every determinacy result over an arbitrary game structure, e.g., a tree, is transferable into existence of multi‐outcome (pure) Nash equilibrium over the same game structure. The equilibrium‐transfer theorem requires cardinal or order‐theoretic conditions on the strategy sets and the preferences, respectively, whereas counter‐examples show that every requirement is relevant, albeit possibly improvable. When the outcomes are finitely many, the proof provides an algorithm computing a Nash equilibrium without significant complexity loss compared to the two‐outcome case. As examples of application, this article generalises Borel determinacy, positional determinacy of parity games, and finite‐memory determinacy of Muller games.