On the solitaire cone and its relationship to multi-commodity flows

The classical game of Peg Solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. The modern mathematical study of the game dates to the 1960s, when the solitaire cone was first described by Boardman and Conway. Valid inequalities over this cone, known as pagoda functions, were used to show the infeasibility of various peg games. In this paper we study the extremal structure of solitaire cones for a variety of boards, and relate their structure to the well studied metric cone. In particular we give:?1. an equivalence between the multicommodity flow problem with associated dual metric cone and a generalized peg game with associated solitaire cone;?2. a related NP-completeness result;?3. a method of generating large classes of facets;?4. a complete characterization of 0-1 facets;?5. exponential upper and lower bounds (in the dimension) on the number of facets;?6. results on the number of facets, incidence and adjacency relationships and diameter for small rectangular, toric and triangular boards;?7. a complete characterization of the adjacency of extreme rays, diameter, number of 2-faces and edge connectivity for rectangular toric boards. Received: July 1996 / Accepted: February 2000?Published online February 22, 2001     

Three person baccarat

Baccarat and the closely related game Chemin-de-Fer are played for high stakes in casinos around the world. Optimal strategies for the player and the banker in the two person game have been developed by Kemeny and Snell. Similar strategies are now the rules of play in Nevada. Thorp and Walden developed card counting strategies to make certain side bets profitable but these bets are no longer allowed. Hence, the game is essentially a Bernoulli trial with a banker edge of 1.24%. For the three person game we determine the banker's strategy that optimally counters the two players fixed rules of play. It is optimal for the players to collude and place indentical bets in which case the game becomes a Bernoulli trial with banker's edge of 0.82%.     

乒乓球赛制的概率分析

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

Analysis of a game of graph solitaire

Let G be a simple undirected graph. To each vertex assign one of two colours say red or blue. A solitaire game is played on G as follows. A move consists of selecting a blue vertex, inverting the colours of its neighbours and then deleting the chosen vertex and all edges incident upon it. The goal is to delete all the vertices. The question of finding a winning strategy in the case when G is a simple cycle was proposed in the problems section of the American Mathematical Monthly. In this article some general results on winning colour configurations are derived and the game is analysed for certain other graph classes.     

Peg solitaire on graphs

There have been several papers on the subject of traditional peg solitaire on different boards. However, in this paper we consider a generalization of the game to arbitrary boards. These boards are treated as graphs in the combinatorial sense. We present necessary and sufficient conditions for the solvability of several well-known families of graphs. In the major result of this paper, we show that the cartesian product of two solvable graphs is likewise solvable. Several related results are also presented. Finally, several open problems related to this study are given.     

Two Approaches to the Problem of Sharing Delay Costs in Joint Projects

This paper concentrates on cost sharing situations which arise when delayed joint projects involve joint delay costs. The problem here is to determine fair shares for each of the agents who contribute to the delay of the project such that the total delay cost is cleared. We focus on the evaluation of the responsibility of each agent in delaying the project based on the activity graph representation of the project and then on solving the important problem of the delay cost sharing among the agents involved. Two approaches, both rooted in cooperative game theory methods are presented as possible solutions. In the first approach delay cost sharing rules are introduced which are based on the delay of the project and on the individual delays of the agents who perform activities. This approach is inspired by the bankruptcy and taxation literature and leads to five rules: the (truncated) proportional rule, the (truncated) constrained equal reduction rule and the constrained equal contribution rule. By introducing two coalitional games related to delay cost sharing problems, which we call the pessimistic delay game and the optimistic delay game, also game theoretical solutions as the Shapley value, the nucleolus and the -value generate delay cost sharing rules. In the second approach the delays of the relevant paths in the activity graph together with the delay of the project play a role. A two-stage solution is proposed. The first stage can be seen as a game between paths, where the delay cost of the project has to be allocated to the paths. Here serial cost sharing methods play a role. In the second stage the allocated costs of each path are divided proportionally to the individual delays among the activities in the path.     

A solitaire game played on 2-colored graphs

We introduce a solitaire game played on a graph. Initially one disk is placed at each vertex, one face green and the other red, oriented with either color facing up. Each move of the game consists of selecting a vertex whose disk shows green, flipping over the disks at neighboring vertices, and deleting the selected vertex. The game is won if all vertices are eliminated. We derive a simple parity-based necessary condition for winnability of a given game instance. By studying graph operations that construct new graphs from old ones, we obtain broad classes of graphs where this condition also suffices, thus characterizing the winnable games on such graphs. Concerning two familiar (but narrow) classes of graphs, we show that for trees a game is winnable if and only if the number of green vertices is odd, and for n-cubes a game is winnable if and only if the number of green vertices is even and not all vertices have the same color. We provide a linear-time algorithm for deciding winnability for games on maximal outerplanar graphs. We reduce the decision problem for winnability of a game on an arbitrary graph G to winnability of games on its blocks, and to winnability on homeomorphic images of G obtained by contracting edges at 2-valent vertices.     

Social norms and choice: a weak folk theorem for repeated matching games

A folk theorem which holds for all repeated matching games is established. The folk theorem holds any time the stage game payoffs of any two players are not affinely equivalent. The result is independent of population size and matching rule—including rules that depend on players choices or the history of play.      

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.     

Selfish Square Packing

We consider a game-theoretical bin packing problem. The 1D (one dimensional) case has been treated in the literature as the ʼselfish bin packing problemʼ. We investigate a 2D version, in which the items to be packed are squares and the bins are unit squares. In this game, a set of items is packed into bins. Each player controls exactly one item and is charged with a cost defined as the ratio between the area of the item and the occupied area of the respective bin. One at a time, players selfishly move their items from one bin to another, in order to minimize the costs they are charged. At a Nash equilibrium, no player can reduce the cost he is charged by moving his item to a different bin. In the 2D case, to decide whether an item can be placed in another bin with other items is NP-complete, so we consider that players use a packing algorithm to make this decision. We show that this game converges to a Nash equilibrium, independently of the packing algorithm used. We prove that the price of anarchy is at least 2.27. We also prove that, using the NFDH packing algorithm, the asymptotic price of anarchy is at most 2.6875.     

Complexity of winning strategies

Rabin has given an example of a game with recursive rules but no recursive winning strategy. We show that such a game always has a hyperarithmetical winning strategy, but arbitrarily high levels of the hyperarithmetical hierarchy may be needed. We also exhibit a recursively enumerable game which has no hyperarithmetical winning strategy.     

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.     

Binary games in constitutional form and collective choice

In this paper, we define the notion of binary game in constitutional form. For this game, we define a core and give a necessary and sufficient condition for a game to be stable.We define a representation of a collective choice rule by a binary game in constitutional form and characterize those collective choice rules which are representable.We finally introduce the notion of c-social decision function and characterize, as an application of our theorem on stability of binary constitutional games, the collective choice rules which are c-social decision functions.Our representation of a collective choice rule by a binary game in constitutional form is an obvious improvement of the classical representation by a simple game.     

Expandability radius versus density of a lattice packing

In the present paper lattice packings of open unit discs are considered in the Euclidean plane. Usually, efficiency of a packing is measured by its density, which in case of lattice packings is the quotient of the area of the discs and the area of the fundamental domain of the packing. In this paper another measure, the expandability radius is introduced and its relation to the density is studied. The expandability radius is the radius of the largest disc which can be used to substitute a disc of the packing without overlapping the rest of the packing. Lower and upper bounds are given for the density of a lattice packing of given expandability radius for any feasible value. The bounds are sharp and the extremal configurations are also presented. This packing problem is related to a covering problem studied by Bezdek and Kuperberg [BK97]. This revised version was published online in June 2006 with corrections to the Cover Date.     

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 differential games with Markov perfect triggering

This paper is an attempt to throw some light on the issue of whether defining history-dependent state variables in a differential game does allow for a dynamic play of precommitment equilibria. We suggest the application of trigger strategies in a state-feedback context. Based on a punishment mode in Markov perfect strategies and being able to detect even past deviations followed by histories returning to equilibrium, these subgame-perfect strategies lead to the enforcement of certain outcomes by means of dynamic rules of strategic interaction. The last part of our exposition is devoted to specific game structures under which a trigger equilibrium can be used as well as a punishment mode.     

Fictitious play with incomplete learning

In this paper, we consider a case that a game is played repeatedly in an incomplete learning process where each player updates his belief only in the learning periods rather than all the stages. For fictitious play process with incomplete learning, we discuss the absorbability of Nash equilibriums and the consistency of utilities in a finite game and discuss the convergence in a 2×2 game with an identical learning-period set. The main results for incomplete learning models are that, if it is uniformly played, a strict Nash equilibrium is absorbing in a fictitious play process; a fictitious play has the property of utility consistency if it exhibits infrequent switches and players learn frequently enough; a 2×2 game with an identical learning-period set has fictitious play property that any fictitious process for the game converges to equilibrium provided that players learn frequently enough.     

Bounds for Local Density of Sphere Packings and the Kepler Conjecture

This paper formalizes the local density inequality approach to getting upper bounds for sphere packing densities in R ⁿ . This approach was first suggested by L. Fejes Tóth in 1953 as a method to prove the Kepler conjecture that the densest packing of unit spheres in R ³ has density π/\sqrt 18 , which is attained by the ``cannonball packing.' Local density inequalities give upper bounds for the sphere packing density formulated as an optimization problem of a nonlinear function over a compact set in a finite-dimensional Euclidean space. The approaches of Fejes Tóth, of Hsiang, and of Hales to the Kepler conjecture are each based on (different) local density inequalities. Recently Hales, together with Ferguson, has presented extensive details carrying out a modified version of the Hales approach to prove the Kepler conjecture. We describe the particular local density inequality underlying the Hales and Ferguson approach to prove Kepler's conjecture and sketch some features of their proof. Received November 19, 1999, and in revised form April 17, 2001. Online publication December 17, 2001.     

The Sequential Truel

The Sequential Truel is a three-person game which generalizes the simple duel. The players' positions are fixed at the vertices of an equilateral triangle, and they fire, in sequence, until there is only one survivor or until each survivor has fired a pre-specified number of times. The rules of the particular game may or may not permit the tactic of abstention, i.e. firing into the air. Several versions of Sequential Truel (with and without abstention) are examined here. It is found that, often, there is a single equilibrium point which can be called the solution of the truel for rational players. Quite frequently, the poorest marksman of the three has the greatest payoff at this equilibrium point.