Optimal strategies for equal-sum dice games

In this paper, we consider a non-cooperative two-person zero-sum matrix game, called dice game. In an (n,σ) dice game, two players can independently choose a dice from a collection of hypothetical dice having n faces and with a total of σ eyes distributed over these faces. They independently roll their dice and the player showing the highest number of eyes wins (in case of a tie, none of the players wins). The problem at hand in this paper is the characterization of all optimal strategies for these games. More precisely, we determine the (n,σ) dice games for which optimal strategies exist and derive for these games the number of optimal strategies as well as their explicit form.     

The diameter game

A large class of Positional Games are defined on the complete graph on n vertices. The players, Maker and Breaker, take the edges of the graph in turns, and Maker wins iff his subgraph has a given — usually monotone — property. Here we introduce the d‐diameter game, which means that Maker wins iff the diameter of his subgraph is at most d. We investigate the biased version of the game; i.e., when the players may take more than one, and not necessarily the same number of edges, in a turn. Our main result is that we proved that the 2‐diameter game has the following surprising property: Breaker wins the game in which each player chooses one edge per turn, but Maker wins as long as he is permitted to choose 2 edges in each turn whereas Breaker can choose as many as (1/9)n^1/8/(lnn)^3/8. In addition, we investigate d‐diameter games for d ≥ 3. The diameter games are strongly related to the degree games. Thus, we also provide a generalization of the fair degree game for the biased case. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

A PGM framework for recursive modeling of players in simple sequential Bayesian games

We consider the situation where two agents try to solve each their own task in a common environment. In particular, we study simple sequential Bayesian games with unlimited time horizon where two players share a visible scene, but where the tasks (termed assignments) of the players are private information. We present an influence diagram framework for representing simple type of games, where each player holds private information. The framework is used to model the analysis depth and time horizon of the opponent and to determine an optimal policy under various assumptions on analysis depth of the opponent. Not surprisingly, the framework turns out to have severe complexity problems even in simple scenarios due to the size of the relevant past. We propose two approaches for approximation. One approach is to use Limited Memory Influence Diagrams (LIMIDs) in which we convert the influence diagram into a set of Bayesian networks and perform single policy update. The other approach is information enhancement, where it is assumed that the opponent in a few moves will know your assignment. Empirical results are presented using a simple board game.     

Multiple-elimination knockout tournaments with the fixed-win property

We classify those triples (n,l,w) for which there exists a ‘knockout’ tournament for n players in which the winner always wins exactly w games and each loser loses exactly l games.     

Combat games

We propose a mathematical formulation of a combat game between two opponents with offensive capabilities and offensive objectives. Resolution of the combat involves solving two differential games with state constraints. Depending on the game dynamics and parameters, the combat can terminate in one of four ways: (i) the first player wins, (ii) the second player wins, (iii) a draw (neither wins), or (iv) joint capture. In the first two cases, the optimal strategies of the two players are determined from suitable zero-sum games, whereas in the latter two the relevant games are nonzero-sum. Further, to avoid certain technical difficulties, the concept of a -combat game is introduced.Dedicated to G. LeitmannThe first author wishes to acknowledge the friendship and guidance of George Leitmann, beginning in the author's student days at Berkeley and continuing to the present time. All the authors thank George Leitmann for many recent fruitful discussions on differential games.on sabbatical leave from Technion, Israel Institute of Technology, Haifa, Israel.     

Efficient Winning Strategies in Random‐Turn Maker–Breaker Games

We consider random‐turn positional games, introduced by Peres, Schramm, Sheffield, and Wilson in 2007. A p‐random‐turn positional game is a two‐player game, played the same as an ordinary positional game, except that instead of alternating turns, a coin is being tossed before each turn to decide the identity of the next player to move (the probability of Player I to move is p ). We analyze the random‐turn version of several classical Maker–Breaker games such as the game Box (introduced by Chvátal and Erd?s in 1987), the Hamilton cycle game and the k‐vertex‐connectivity game (both played on the edge set of ). For each of these games we provide each of the players with a (randomized) efficient strategy that typically ensures his win in the asymptotic order of the minimum value of p for which he typically wins the game, assuming optimal strategies of both players.     

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.     

Decentralized Interaction and Co-Adaptation in the Repeated Prisoner&2018;s Dilemma

A Prisoner&2018;s dilemma that is repeated indefinitely has many equilibria; the problem of selecting among these is often approached using evolutionary models. The background of this paper is a number of earlier studies in which a specific type of evolutionary model, a genetic algorithm (GA), was used to investigate which behavior survives under selective pressure. However, that normative instrument searches for equilibria that may never be attainable. Furthermore, it aims for optimization and, accordingly, says what people should do to be successful in repeated prisoner&2018;s dilemma (RPD) type situations. In the current paper, I employ simulation to find out what people would do, whether this makes them successful or not. Using a replication of Miller&2018;s (1988) GA study for comparison, a model is simulated in which the population is spatially distributed across a torus. The agents only interact with their neighbors and locally adapt their strategy to what they perceive to be successful behavior among those neighbors. Although centralized GA-evolution may lead to somewhat better performance, this goes at the cost of a large increase in required computations while a population with decentralized interactions and co-adaptation is almost as successful and, additionally, endogenously learns a more efficient scheme for adaptation. Finally, when the agents&2018; perceptive capabilities are limited even further, so that they can only perceive how their neighbors are doing against themselves, rather than against all those neighbors&2018; opponents&2014;which essentially removes reputation as a source of information&2014;cooperation breaks down.     

超网络中心性度量的υ-Position值方法

利用合作博弈理论的分配规则如Shapley值、Banzhaf值等来度量政治、经济和社会网络中节点的中心性或者重要性是识别网络中关键节点的一类重要方法。考虑到在超网络中代表各类组织的超边在网络中发挥的作用不同,本文研究了超网络博弈上一类广义Position值的分配规则,被称为υ-position值。它可以作为网络中度值测度的一类推广,以此来度量网络中参与者的中心性和相对重要性。其次,证明了超网络结构上类Shapley-position值可由分支超边指数和局部平衡超边贡献两个性质所唯一刻画。最后, 举例分析了υ-position值在超网络中心性测度中的应用。     

The length of some diagonalization games

For X a separable metric space and an infinite ordinal, consider the following three games of length : In ONE chooses in inning an –cover of X; TWO responds with a . TWO wins if is an –cover of X; ONE wins otherwise. In ONE chooses in inning a subset of which has the zero function in its closure, and TWO responds with a function . TWO wins if is in the closure of ; otherwise, ONE wins. In ONE chooses in inning a dense subset of , and TWO responds with a . TWO wins if is dense in ; otherwise, ONE wins. After a brief survey we prove: 1. If is minimal such that TWO has a winning strategy in , then is additively indecomposable (Theorem 4) 2. For countable and minimal such that TWO has a winning strategy in on X, the following statements are equivalent (Theorem 9): a) TWO has a winning strategy in on . b) TWO has a winning strategy in on . 3. The Continuum Hypothesis implies that there is an uncountable set X of real numbers such that TWO has a winning strategy in on X (Theorem 10). Received: 14 February 1997     

Periodic stopping games

Stopping games (without simultaneous stopping) are sequential games in which at every stage one of the players is chosen, who decides whether to continue the interaction or stop it, whereby a terminal payoff vector is obtained. Periodic stopping games are stopping games in which both of the processes that define it, the payoff process as well as the process by which players are chosen, are periodic and do not depend on the past choices. We prove that every periodic stopping game without simultaneous stopping, has either periodic subgame perfect ϵ-equilibrium or a subgame perfect 0-equilibrium in pure strategies. This work is part of the master thesis of the author done under the supervision of Prof. Eilon Solan. I am thankful to Prof. Solan for his inspiring guidance. I also thank two anonymous referees of the International Journal of Game Theory for their comments.     

On a generalization of Kaplansky's game

In this paper, games of the following general kind are studied: Two players move alternately by selecting unselected integer coordinate points in the plane. On each move, the first player selects exactly r points and the second player selects exactly one point. The first player wins if he can select p points on a line having none of his opponent's points before his opponent selects q points on a line having none of his own. If this latter eventuality occurs first, the second player wins. It is shown that if p ? c(r)q, then the second player can always win.     

Directed Switching Games on graphs and matroids

We introduce directed versions of the Shannon Switching Game. In the Directed Shannon Switching Game two players, BLACK and WHITE, alternatively direct edges of a graph with two distinguished vertices x₀, x₁. WHITE wins if he connects x₀ to x₁ by a directed path. In the One-Way Game, WHITE is allowed to use edges directed by BLACK. Several related other games are also considered. All these games are particular cases of games played on oriented matroids. The main results of the paper yield complete classifications of directed switching games on graphic and cographic oriented matroids.     

An <Emphasis Type="Italic">m</Emphasis><Superscript>th</Superscript> Generation Model for Weak Ranking of Players in a Tournament

The problem of ranking players in a tournament has been studied by a number of authors. The methods developed for ranking players fall under two general headings—direct methods and rating methods. The present paper extends the tournament ranking problem in two directions. First, the usual definition of a tournament is broadened to include ties or draws. Thus, our model determines the best weak ranking of the players. Second, the ranking method presented takes account of player strength in that wins over strong players are valued higher than wins over weak players. To account for player strength, we evaluate both direct or first-order wins of players over opponents (i defeats j) and indirect or higher-order wins (i defeats k, who defeats j). A model which derives a composite score for each player, combining both direct and indirect wins, is used to obtain an overall ranking of the competitors.     

Congestion games revisited

Strategic games are considered where the players derive their utilities from participation in certain “processes”. Two subclasses consisting exclusively of potential games are singled out. In the first, players choose where to participate, but there is a unique way of participation, the same for all players. In the second, the participation structure is fixed, but each player may have an arbitrary set of strategies. In both cases, the players sum up the intermediate utilities; thus the first class essentially coincides with that of congestion games. The necessity of additivity in each case is proven. Financial support from Presidential Grants for the State Support of the Leading Scientific Schools (NSh-1843.2003.01 and NSh-5379.2006.1), the Russian Foundation for Basic Research (grant 05-01-00942), the Spanish Ministry of Education (project SEJ2004-00968), and the Lady Davis Foundation (a fellowship at the Technion, Haifa) is acknowledged. I thank Francisco Marhuenda and Dov Monderer, respectively, for procuring the last two grants. My deepest gratitude and apology are due to an anonymous referee, who carefully read two versions of the paper, suggested several improvements, and uncovered several errors, including a wrong formulation of Theorem 1. Finally, I apologize to Mikhail Gorelov, who had warned me that something was wrong with the theorem (unfortunately, I failed to pay proper attention).     

Impartial achievement and avoidance games for generating finite groups

We study two impartial games introduced by Anderson and Harary and further developed by Barnes. Both games are played by two players who alternately select previously unselected elements of a finite group. The first player who builds a generating set from the jointly selected elements wins the first game. The first player who cannot select an element without building a generating set loses the second game. After the development of some general results, we determine the nim-numbers of these games for abelian and dihedral groups. We also present some conjectures based on computer calculations. Our main computational and theoretical tool is the structure diagram of a game, which is a type of identification digraph of the game digraph that is compatible with the nim-numbers of the positions. Structure diagrams also provide simple yet intuitive visualizations of these games that capture the complexity of the positions.     

The Compromise Value for Cooperative Games with Random Payoffs

This paper introduces and studies the compromise value for cooperative games with random payoffs, that is, for cooperative games where the payoff to a coalition of players is a random variable. This value is a compromise between utopia payoffs and minimal rights and its definition is based on the compromise value for NTU games and the τ-value for TU games. It is shown that the nonempty core of a cooperative game with random payoffs is bounded by the utopia payoffs and the minimal rights. Consequently, for such games the compromise value exists. Further, we show that the compromise value of a cooperative game with random payoffs coincides with the τ-value of a related TU game if the players have a certain type of preferences. Finally, the compromise value and the marginal value, which is defined as the average of the marginal vectors, coincide on the class of two-person games. This results in a characterization of the compromise value for two-person games.I thank Peter Borm, Ruud Hendrickx and two anonymous referees for their valuable comments.     

Non-cooperative implementation of the nucleolus: The 3-player case

I present a non-cooperative bargaining game, in which responders may exit at any time and have endogenous outside options. When the order of proposers corresponds to the power that players have in the underlying coalitional function, the unique Markov perfect equilibrium outcome of the game is the prenucleolus. The result holds for 3-player superadditive games. An example shows that it cannot be extented to the same class of games forn players. The mechanism is inspired by the consistency property of the prenucleolus.I am grateful to Vijay Krishna, Andreu Mas-Colell, Eric Maskin, Amy Salsbury, and an anonymous referee for helpful comments and suggestions.     

Values on regular games under Kirchhoff’s laws

The Shapley value is a central notion defining a rational way to share the total worth of a cooperative game among players. We address a general framework leading to applications to games with communication graphs, where the feasible coalitions form a poset whose all maximal chains have the same length. Considering a new way to define the symmetry among players, we propose an axiomatization of the Shapley value of these games. Borrowing ideas from electric networks theory, we show that our symmetry axiom and the efficiency axiom correspond to the two Kirchhoff’s laws in the circuit associated to the Hasse diagram of feasible coalitions.     

On a conjecture of Brualdi and Shen on block transitive tournaments

The following conjecture of Brualdi and Shen is proven in this paper: let n be partitioned into natural numbers no one of which is greater than (n + 1) / 2. Then, given any sequence of wins for the players of some tournament among n players, there is a partition of the players into blocks with cardinalities given by those numbers, and a tournament with the given sequence of wins, that is transitive on the players within each block. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 215–230, 2003