Playing off-line games with bounded rationality

We study a two-person zero-sum game where players simultaneously choose sequences of actions, and the overall payoff is the average of a one-shot payoff over the joint sequence. We consider the maxmin value of the game played in pure strategies by boundedly rational players and model bounded rationality by introducing complexity limitations. First we define the complexity of a sequence by its smallest period (a nonperiodic sequence being of infinite complexity) and study the maxmin of the game where player 1 is restricted to strategies with complexity at most n and player 2 is restricted to strategies with complexity at most m. We study the asymptotics of this value and a complete characterization in the matching pennies case. We extend the analysis of matching pennies to strategies with bounded recall.     

A Game Related to the Number of Hides Game

In this paper, we study a discrete search game on an array of N ordered cells, with two players having opposite goals: player I (searcher) and player II (hider). Player II has to hide q objects at consecutive cells and player I can search p consecutive cells. The payoff to player I is the number of objects found by him. In some situations, the players need to adopt sophisticated strategies if they are to act optimally.     

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.     

One class of simultaneous pursuit games

Let A and B be given convex closed bounded nonempty subsets in a Hilbert space H; let the first player choose points in the set A and let the second one do those in the set B. We understand the payoff function as the mean value of the distance between these points. The goal of the first player is to minimize the mean value, while that of the second player is to maximize it. We study the structure of optimal mixed strategies and calculate the game value.     

Cooperation in spatial prisoner’s dilemma game with delayed decisions

Phenomena that time delays of information lead to delayed decisions are extensive in reality. The effect of delayed decisions on the evolution of cooperation in the spatial prisoner’s dilemma game is explored in this work. Players with memory are located on a two dimensional square lattice, and they can keep the payoff information of his neighbors and his own in every historic generation in memory. Every player uses the payoff information in some generation from his memory and the strategy information in current generation to determine which strategy to choose in next generation. The time interval between two generations is set by the parameter m. For the payoff information is used to determine the role model for the focal player when changing strategies, the focal player’s decision to learn from which neighbor is delayed by m generations. Simulations show that cooperation can be enhanced with the increase of m. In addition, just like the original evolutionary game model (m = 0), pretty dynamic fractal patterns featuring symmetry can be obtained when m > 0 if we simulate the invasion of a single defector in world of cooperators on square lattice.     

Nonlinear dynamics in a heterogeneous duopoly game with adjusting players and diseconomies of scale

A repeated, discrete time, heterogeneous Cournot duopoly game with bounded rational and adaptive players adjusting the quantities of production is subject of investigation. Linear inverse demand function and quadratic cost functions reflecting decreasing returns to scale are assumed. The game is modeled with a system of two difference equations. Evolution of outputs over time is obtained by iteration of a two dimensional nonlinear map. Existing equilibria and their stability are analyzed. In face of diseconomies of scale, bounded rational and adaptive duopolists are shown to experience a decrease in the latitude of their output adjustment decisions with respect to the market stability compared to constant returns to scale and ceteris paribus. Chaotic dynamics is confirmed to depend mainly on the adjustment behavior of the bounded rational player, who if overshoots leaves the adaptive player with limited opportunities to stabilize the market again, hence industries facing diseconomies of scale are found to be less stable than those with constant marginal costs. Complexity of the dynamical system is examined by means of numerical simulations, where the paper extends the results of other authors who considered analogous games assuming linear cost functions. Intermittent transition to chaos and attractor merging crisis are shown among others.     

On a duel with time lag and equal accuracy functions

This paper deals with a duel with time lag that has 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 this opponent. The gun of player I is silent and the gun of player II is noisy with time lagt (i.e., if player II fires at timex, then player I knows it at timex+t). They both have equal accuracy functions. Furthermore, if player I hits player II without being hit himself before, the payoff is +1; if player I is hit by player II without hitting player 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 the optimal strategy for each player, the game value, and some examples.     

公路客运监管的进化博弈分析

运用进化博弈理论研究公路客运监管问题,建立了公路客运监管问题的博弈模型,分析了公路客运车主和公路客运管理者之间的行为选择,得到了博弈方的复制动态方程,研究了博弈模型的进化稳定策略。探讨了影响进化稳定策略的因素。研究结果表明公路客运车主和公路客运管理者在有限理性基础上得到的进化稳定策略与博弈双方的收益、系统所处的初始状态有关,并根据所提出的博弈模型,提出了合理性建议。     

The Value of Information Structures in Zero-sum Games with Lack of Information on One Side

Two players are engaged in a zero-sum game with lack of information on one side, in which player 1 (the informed player) receives some stochastic signal about the state of nature. I consider the value of the game as a function of player 1’s information structure, and study the properties of this function. It turns out that these properties reflect the fact that in zero sum situation the value of information for each player is positive.     

Complexité dynamique des réseaux de HopfieldDynamical complexity of the Hopfield networks

One considers the Hopfield networks. It is shown that this system can generate any structurally stable inertial dynamics, with a bounded memory. To cite this article: S. Vakulenko, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 639–642.     

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.     

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

Directed defective asymmetric graph coloring games

We consider the following 2-person game which is played with an (initially uncolored) digraph D, a finite color set C, and nonnegative integers a, b, and d. Alternately, player I colors a vertices and player II colors b vertices with colors from C. Whenever a player colors a vertex v, all in-arcs (w,v) that do not come from a vertex w previously colored with the same color as v are deleted. For each color i the defect digraphD_i is the digraph induced by the vertices of color i at a certain state of the game. The main rule the players have to respect is that at every time for any color i the digraph D_i has maximum total degree of at most d. The game ends if no vertex can be colored any more according to this rule. Player I wins if D is completely colored at the end of the game, otherwise player II wins. The smallest cardinality of a color set C with which player I has a winning strategy for the game is called . This parameter generalizes several variants of Bodlaender’s game chromatic number. We determine the tight (resp., nearly tight) upper bound (resp., ) for the d-relaxed (a,b)-game chromatic number of orientations of forests (resp., undirected forests) for any d and a≥b≥1. Furthermore we prove that these numbers cannot be bounded in case a<b.     

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.     

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.     

Mixed complementarity problems for robust optimization equilibrium in bimatrix game

In this paper, we investigate the bimatrix game using the robust optimization approach, in which each player may neither exactly estimate his opponent’s strategies nor evaluate his own cost matrix accurately while he may estimate a bounded uncertain set. We obtain computationally tractable robust formulations which turn to be linear programming problems and then solving a robust optimization equilibrium can be converted to solving a mixed complementarity problem under the l ₁ ∩ l _∞-norm. Some numerical results are presented to illustrate the behavior of the robust optimization equilibrium.     

Some remarks on a game of Telgársky

In [3] R. Telgársky (1975) asked: does the first player have a winning strategy in the game G(F,X×X) if the first player has a winning strategy in the game G(F,X)? I give a positive answer to this question and prove that this result is also true for spaces where the first player has a winning strategy in game G(K,X) where K=1, F, C, for σC if X is P-space and for DC if X is collectionwise-normal space. The last result is related to the Telgársky's (1983) conjecture discussed in [1]. These results are not true for infinite product of spaces.     

How fast can Maker win in fair biased games?

We study $(a:a)$ Maker–Breaker games played on the edge set of the complete graph on $n$ vertices. In the following four games — perfect matching game, Hamilton cycle game, star factor game and path factor game, our goal is to determine the least number of moves which Maker needs in order to win these games. Moreover, for all games except for the star factor game, we show how first player can win in the strong version of these games.     

The bounded core for games with precedence constraints

An element of the possibly unbounded core of a cooperative game with precedence constraints belongs to its bounded core if any transfer to a player from any of her subordinates results in payoffs outside the core. The bounded core is the union of all bounded faces of the core, it is nonempty if the core is nonempty, and it is a continuous correspondence on games with coinciding precedence constraints. If the precedence constraints generate a connected hierarchy, then the core is always nonempty. It is shown that the bounded core is axiomatized similarly to the core for classical cooperative games, namely by boundedness (BOUND), nonemptiness for zero-inessential two-person games (ZIG), anonymity, covariance under strategic equivalence (COV), and certain variants of the reduced game property (RGP), the converse reduced game property (CRGP), and the reconfirmation property. The core is the maximum solution that satisfies a suitably weakened version of BOUND together with the remaining axioms. For games with connected hierarchies, the bounded core is axiomatized by BOUND, ZIG, COV, and some variants of RGP and CRGP, whereas the core is the maximum solution that satisfies the weakened version of BOUND, COV, and the variants of RGP and CRGP.     

On the noisy-silent versus silent-noisy duel with equal accuracy functions

This paper deals with the noisy-silent versus silent-noisy duel with equal accuracy functions. Each of player I and player II has a gun with two bullets and he can fire his bullets at any time in [0, 1] aiming at his opponent. The first bullet of player I and the second bullet of player II are noisy, and the second bullet of player I and the first bullet of player II are silent. It is assumed that both players have equal accuracy functions. If player I hits player II, not being hit himself before, the payoff of the duel is +1; if player I is hit by player II, not hitting player II before, the payoff is ?1. The value of the game and the optimal strategies are obtained. We find that the firing time of the silent bullet by player II's optimal strategy depends directly on the firing time of player I's noisy bullet.