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.     

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

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.     

Discrete time dynamic Stackelberg games with the leaders in turn

In many dynamic Stackelberg games, the leader changes at each stage. A new type of dynamic Stackelberg game is initially put forward in this paper and is called dynamic Stackelberg games with the leaders in turn, in which players act as the leaders in turn. There exist extremely comprehensive applications for dynamic Stackelberg games with the leaders in turn. On the one hand, in this work we aim to establish models for a new type of game, dynamic Stackelberg games of multiple players with leaders in turn, which are induced from some economic and political phenomena, which play exceedingly important roles in many fields. On the other hand, we hope to extend dynamic programming algorithms to the new model under feedback information structure.     

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.     

Analyzing n-player impartial games

Combinatorial game theory is the study of two player perfect information games. While work has been done in the past on expanding this field to include n-player games we present a unique method which guarantees a single winner. Specifically our goal is to derive a function which, given an n-player game, is able to determine the winning player (assuming all n players play optimally). Once this is accomplished we use this function in analyzing a certain family of three player subtraction games along with a complete analysis of three player, three row Chomp. Furthermore we make use of our new function in producing alternative proofs to various well known two player Chomp games. Finally the paper presents a possible method of analyzing a two player game where one of the players plays a completely random game. As it turns out this slight twist to the rules of combinatorial game theory produces rather interesting results and is certainly worth the time to study further.     

乒乓球赛制的概率分析

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

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.     

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.     

Dynamic programming approach to discrete time dynamic feedback Stackelberg games with independent and dependent followers

Stackelberg games play an extremely important role in such fields as economics, management, politics and behavioral sciences. Stackelberg game can be modelled as a bilevel optimization problem. There exists extensive literature about static bilevel optimization problems. However, the studies on dynamic bilevel optimization problems are relatively scarce in spite of the importance in explaining and predicting some phenomena rationally. In this paper, we consider discrete time dynamic Stackelberg games with feedback information. Dynamic programming algorithms are presented for the solution of discrete time dynamic feedback Stackelberg games with multiple players both for independent followers and for dependent followers. When the followers act dependently, the game in this paper is a combination of Stackelberg game and Nash game.     

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.     

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.     

Discrete time dynamic multi-leader–follower games with stage-depending leaders under feedback information

Discrete time dynamic Stackelberg games with alternating leaders are recently brought forward by and dynamic programming algorithms are extended to discrete time dynamic Stackelberg games of two players with alternating leaders under feedback information structure. In many practical problems, there are multiple leaders and multiple followers. Moreover, the positions of leaders and followers may change at some stages. We aim to extend the results of discrete time dynamic Stackelberg games with alternating leaders to multi-leader–follower games and to obtain a new type of game, dynamic multi-leader–follower game with stage-depending leaders. To simplify the problem, all players in the model are divided into two groups. At each stage, players in one group act as leaders and the players in other group are followers. In the subsequent stage, the positions may go to the contrary. Actually, whether the players in some group act as leaders or not at some stage, depends on the information at the previous stage(s). Furthermore, dynamic programming algorithms are extended to dynamic multi-leader–follower game with stage-depending leaders under feedback information structure in this paper.     

Dynamic feedback Stackelberg games with alternating leaders

In all past researches on dynamic Stackelberg games, the leader(s) and the followers are always assumed to be fixed. In practice, the roles of the players in a game may change from time to time. Some player in contract bridge, for example, acts as a leader at some stage but as a follower at the subsequent stage, which motivates the Stackelberg games with unfixed leaders. We aim to analyze the dynamic Stackelberg games with two players under such circumstances and call them dynamic Stackelberg games with alternating leaders. There are two goals in this paper. One goal is to establish models for a new type of games, dynamic Stackelberg games of alternating leaders with two players. The other goal is to extend dynamic programming algorithms to discrete time dynamic Stackelberg games with alternating leaders under feedback information structure.     

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.     

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.     

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.     

Random Perturbation in Games of Chance

In this article, we consider a problem in games of chance. Our result shows that two losing games ( A and B , in the sense of a negative expectation) can become a winning game (in the sense of a positive expectation), when the two are played in a suitable alternating order; for example, ABBABB ....... By using a regrouping technique in Automata and the concept of Markov chain embedding, we give proof of this gambling result. A signal-to-noise ratio is also presented to explain this counterintuitive phenomenon.     

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.