Single-suit two-person card play II. Dominance

This paper studies a two-person constant sum perfect information game, the End Play Game, arising from an abstraction of end play in bridge. This game was described by Emanuel Lasker who called it whistette. The game uses a deck of cards consisting of a single totally ordered suit of 2n cards. The deck is divided into two hands A and B of n cards each, held by players Left and Right, and one player is designated as having the lead. The player on lead chooses one of his cards, and the other player after seeing this card selects one of his own to play. The player with the higher card wins a trick and obtains the lead. The cards in the trick are removed from each hand, and play then continues until all cards are exhausted. Each player strives to maximize his trick total, and the value of the game to each player is the number of tricks he takes. The strategy of this game seems to be quite complicated, despite its simple appearance. This paper studies partial orderings on hands. One partial order recognizes regularities in the value function that persist when extra cards are added to hands. A pair of hands (A ^* , B ^* ) dominates a pair of hands (A, B) for Left, if for any set of extra cards (C ₁, C ₂) added to the deck such that A B (which equals A ^* B ^* ) is a block of consecutive cards in the expanded deck A B {C ₁ , C ₂} the value of (A C ₁, B C ₂) to Left always is at least as much as the value to Left of (A ^* C ₁, B ^* C ₂) both when Left has the lead in both games and when Right has the lead in both games. The main result is that ({4, 1}, {3, 2}) dominates ({3, 2}, {4, 1}). Note that with just four cards the hands {4, 1} and {3, 2} are of identical value — they both take one trick independent of the lead or how the hands are played. The dominance result shows that {4, 1} is preferable to {3, 2} when other cards are present. We show that the dominance relation gives a partial order that is not a total order on hands of 3 or more cards. We also study the total point count ordering, which gives a rough estimate for the value of a hand. We derive upper and lower bounds for the value of a hand with given point count.     

A Problem in Permutations: the Game of 'Mousetrap'

The game of 'Mousetrap, a problem in permutations, first introduced by Arthur Cayley in 1857 and independently addressed by Cayley and Adolph Steen in 1878, has been largely unexamined since. The game involves permutations of n cards numbered consecutively from 1 to n. The cards are laid out face up in some order and the game is played by counting on the cards, beginning the count with 1. If at any time the number of the count matches the number on the card, this is called a hit and the card is thrown out. The counting begins again with 1 on the next card and returns to the first card when the nth card is reached. Each time a card is hit, that card is removed and the counting starts over at 1. The game continues until all the cards have been hit and thrown out (the player wins) or until the counting reaches n with no cards having been hit (the cards win). The game is re-introduced here and a summary of both Cayley's and Steen's work is presented. Computer programs, written to generate the types of permutations dealt with by Steen, uncovered discrepancies in his work. Further examination of these discrepancies lead to the discovery of a combinatorial pattern of coefficients which Steen was unable to recognize because of his computational errors. Corrected versions of Steen's erroneous formulas are presented.     

三步矩阵对策上的无中生有计及其实例

基于一个历史实例及假定:①三步矩阵对策中赢得矩阵都不变,②每步都是局中人1先行动,③对于每步对策,局中人2观测不到对手究竟使用了何策略;但局中人1可以观测到对手所用的策略,建立了三步矩阵对策上的无中生有计(《三十六计》中的第七计)的对策模型.研究了当局中人2中计,半识破和完全识破对手的无中生有计时的赢得和所用的策略的情况.并用上述实例对模型作了说明.     

一类多步矩阵对策上的计策问题

以有序树为工具,研究了可以描述连环计,诱敌深入等多步矩阵对策上的一类计策模型.在不考虑信息环境的封闭对策系统中,及局中人对每一步矩阵对策的赢得矩阵,两个局中人的策略集合以及局中人的理性等的了解都是局中人的共同知识的假定下,提出了局中人的最优计策链及将计就计等概念,研究了局中人中计和识破计策的固有概率,讨论了局中人在什么情况下最好主动用计,在什么情况下最好从动用计以及求解最优计策等问题.     

An axiomatization of the disjunctive permission value for games with a permission structure

Players that participate in acooperative game with transferable utilities are assumed to be part of apermission structure being a hierarchical organization in which there are players that need permission from other players before they can cooperate. Thus a permission structure limits the possibilities of coalition formation. Various assumptions can be made about how a permission structure affects the cooperation possibilities. In this paper we consider thedisjunctive approach in which it is assumed that each player needs permission from at least one of his predecessors before he can act. We provide an axiomatic characterization of thedisjunctive permission value being theShapley value of a modified game in which we take account of the limited cooperation possibilities.     

Two-noisy-versus-one-silent duel with equal accuracy functions

This paper deals with the two-noisy-versus-one-silent duel which is still open, as pointed out by Styszyński (Ref. 1). Player I has a noisy gun with two bullets, and player II has a silent gun with one bullet. Each player fires his bullets aiming at his opponent at any time in [0, 1]. The accuracy function (the probability that one player hits his opponent if he fires at timet) isp(t)=t for each player. If player I hits player II, without being hit himself before, the payoff of the duel is +1; if player I is hit by player II, without hitting player II before, the payoff is taken to be ?1. In this paper, we determine the optimal strategies and the value of the game. The strategy for player II depends explicitly on the firing moment of player I's first shot.     

Zero-sum sequential games with incomplete information

Repeated zero-sum two-person games of incomplete information on one side are considered. If the one-shot game is played sequentially, the informed player moving first, it is proved that the value of then-shot game is constant inn and is equal to the concavification of the game in which the informed player disregards his extra information. This is a strengthening ofAumann andMaschler's results for simultaneous games. Optimal strategies for both players are constructed explicitly.     

The Advanced Australian Shuffle

The “classical” Australian under-down shuffle starts with a deck of n cards. Then one proceeds as follows: one card under the deck, one on the table, one under the deck, one on the table, etc. One continues until only one card remains. There is an explicit formula to calculate the number of the card in the original deck that survives, and this is the basis of several mathematical magic tricks.     

Bifurcation analysis of a non-cooperative differential game with one weak player

We study a bifurcation problem for a system of two differential equations in implicit form. For each value of the parameter θ, the solution yields a pair of Nash equilibrium strategies in feedback form, for a non-cooperative differential game. When θ=0, the second player has no power to influence the dynamics of the system, and his optimal strategy is myopic. The game thus reduces to an optimal control problem for the first player. By studying the bifurcation in the solutions to the corresponding system of Hamilton-Jacobi equations, one can establish existence and multiplicity of solutions to the differential game, as θ becomes strictly positive.     

A multistage game with incomplete information requiring an infinite memory

This paper describes a zero-sum, discrete, multistage, time-lag game in which, for one player, there is no integerk such that an optimal strategy, for a new move during play, can always be determined as a function of the pastk state positions; that is, the player requires an infinite memory. The game is a pursuit-evasion game with the payoff to the maximizing player being the time to capture.This paper is the result of work carried out at the University of Adelaide, Adelaide, Australia, under an Australian Commonwealth Postgraduate Award.The author should like to thank the referee for his valued suggestions.     

连续对策上的计策问题

限定一个连续对策不是平凡地无意义（例如对某个局中人绝对有利等），我们提出了连续对策上的计策的基本概念。最后得到结论，如果局中人1使用经典对策，那么他的赢得期望必不是赢得函数的最大值。如果局中人1使用计策成功（即使得局中人2中计），那么局中人1必取得赢得函数的最大值，局中人2也有对偶的结果。     

On repeated games with incomplete information played by non-Bayesian players

Unlike in the traditional theory of games of incomplete information, the players here arenot Bayesian, i.e. a player does not necessarily have any prior probability distribution as to what game is being played. The game is infinitely repeated. A player may be absolutely uninformed, i.e. he may know only how many strategies he has. However, after each play the player is informed about his payoff and, moreover, he has perfect recall. A strategy is described, that with probability unity guarantees (in the sense of the liminf of the average payoff) in any game, whatever the player could guarantee if he had complete knowledge of the game.     

On Simple MIX game

We consider zero-sum game which is called Simple MIX game. Each of two players (I and II) draws a number (x andy respectively) according to a uniform distribution on [0, 1]. After observing his number each player can then choose to offer or not offer to exchange his number for the other player's number. Conditions for an exchange are the following: 1) both players must offer for a trade to occur with certainty; 2) if only one player offers, a trade occurs with probabilityp. A player's payoff is equal to 1, 0 or — 1 if the value of the number which he finally gets is greater, equal or less than the number of his opponent. In the present paper we shall investigate Simple MIX game in which both of the players can obtain additional information about the opponent's number. Besides, we consider two-stage variant of this game.     

Staircase rook polynomials and Cayley’s game of Mousetrap

First introduced by Arthur Cayley in the 1850’s, the game of Mousetrap involves removing cards from a deck according to a certain rule. In this paper we find the rook polynomial for the number of Mousetrap decks in which at least two specified cards are removed. We also find a new expression for the rook polynomial for the number of decks in which exactly one specified card is removed and give expressions for counts of two kinds of Mousetrap decks in terms of other known combinatorial numbers.     

How to play the one-lie Rényi-Ulam game

The one-lie Rényi-Ulam liar game is a two-player perfect information zero-sum game, lasting q rounds, on the set [n]?{1,…,n}. In each round Paul chooses a subset A⊆[n] and Carole either assigns one lie to each element of A or to each element of [n]?A. Paul wins the original (resp. pathological) game if after q rounds there is at most one (resp. at least one) element with one or fewer lies. We exhibit a simple, unified, optimal strategy for Paul to follow in both games, and use this to determine which player can win for all q,n and for both games.     

Cycle games and cycle cut games

Two players play a game on a connected graphG. Each player in his turn occupies an edge ofG. The player who occupies a set of edges that contains a cycle, before the other does it, wins. This game may end in a draw. We call this game the normal cycle game. We define furthermore three similar games, which are called the misère cycle game, the normal cycle cut game and the misère cycle cut game. We characterize the above four games.     

Non-cooperative n-person game with a stopped set

A continuous time non-cooperative n-person Markov game with a stopped set is studied in this paper. We prove that, in the game process with or without discount factor, there exists an optimal stationary point of strategies, called the equilibrium point, and each player has his equilibrium stationary strategy, such that the total expected discounted or non-discounted gain are maximums.     

Some exploration of the game SET®

Since the game SET® was first introduced to the public in 1993, it has stimulated some interesting studies. While the game itself is rather straightforward, a plethora of decent mathematical questions lies beneath the surface. It is perhaps because the game ties in so closely with such an underlying mathematical term that its implications can be seen in many major fields of mathematics. This note introduces a generalized version of the game SET® in which there are n ^m cards, m???4,?n???3,?m???n. Each card has m features and each feature has n options. A precise formula is presented for calculating the total number of SETs in a general deck.     

Static search games played over graphs and general metric spaces

We define a general game which forms a basis for modelling situations of static search and concealment over regions with spatial structure. The game involves two players, the searching player and the concealing player, and is played over a metric space. Each player simultaneously chooses to deploy at a point in the space; the searching player receiving a payoff of 1 if his opponent lies within a predetermined radius r of his position, the concealing player receiving a payoff of 1 otherwise. The concepts of dominance and equivalence of strategies are examined in the context of this game, before focusing on the more specific case of the game played over a graph. Methods are presented to simplify the analysis of such games, both by means of the iterated elimination of dominated strategies and through consideration of automorphisms of the graph. Lower and upper bounds on the value of the game are presented and optimal mixed strategies are calculated for games played over a particular family of graphs.     

On a duel with time lag and arbitrary accuracy functions

This paper deals with a two-person zero-sum game called duel with the following structure: Each of two players I and II has a gun with one bullet and he can fire his bullet at any time in [0, 1], aiming at his opponent. If I or II fires at timex, he hits his opponent with probabilityp (x) orq(x), respectively. The gun of I is silent, and hence, II does not know whether his opponent has fired or not, and the gun of II is noisy with time lagt, wheret is a positive constant,i.e., if II fires at timex then I knows it at timex +t. Further, if I hits II without being hit himself before, the payoff is 1; if I is hit by II without hitting II before, the payoff is ?1; if they hit each other at the same time or both survive, the payoff is 0. This paper gives optimal strategy for each player and the value of the game.