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.     

On acyclicity of games with cycles

We study restricted improvement cycles (ri-cycles) in finite positional n-person games with perfect information modeled by directed graphs (di-graphs) that may contain directed cycles (di-cycles). We assume that all these di-cycles form one outcome c, for example, a draw. We obtain criteria of restricted improvement acyclicity (ri-acyclicity) in two cases: for n=2 and for acyclic di-graphs. We provide several examples that outline the limits of these criteria and show that, essentially, there are no other ri-acyclic cases.We also discuss connections between ri-acyclicity and some open problems related to Nash-solvability.     

Finitely additive stochastic games with Borel measurable payoffs

We prove that a two-person, zero-sum stochastic game with arbitrary state and action spaces, a finitely additive law of motion and a bounded Borel measurable payoff has a value. Received December 1996/Final version November 1997     

Infinite dimensional differential games with hybrid controls

A two-person zero-sum infinite dimensional differential game of infinite duration with discounted payoff involving hybrid controls is studied. The minimizing player is allowed to take continuous, switching and impulse controls whereas the maximizing player is allowed to take continuous and switching controls. By taking strategies in the sense of Elliott-Kalton, we prove the existence of value and characterize it as the unique viscosity solution of the associated system of quasi-variational inequalities.     

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.     

Characterization of optimal strategies in matrix games with convexity properties

This paper gives a full characterization of matrices with rows and columns having properties closely related to the (quasi-) convexity-concavity of functions. The matrix games described by such payoff matrices well approximate continuous games on the unit square with payoff functions F (x, y) concave in x for each y, and convex in y for each x. It is shown that the optimal strategies in such matrix games have a very simple structure and a search-procedure is given. The results have a very close relationship with the known theorem of Debreu and Glicksberg about the existence of a pure Nash equilibrium in n-person games. Received: May 1997/Final version: August 1999     

Finding a Nash equilibrium in noncooperativeN-person games by solving a sequence of linear stationary point problems

In this paper we present an algorithm for finding a Nash equilibrium in a noncooperative normal formN-person game. More generally, the algorithm can be applied for solving a nonlinear stationary point problem on a simplotope, being the Cartesian product of several simplices. The algorithm solves the problem by solving a sequence of linear stationary point problems. Each problem in the sequence is solved in a finite number of iterations. Although the overall convergence cannot be proved, the method performs rather well. Computational results suggest that this algorithm performs at least as good as simplicial algorithms do.For the special case of a bi-matrix game (N=2), the algorithm has an appealing game-theoretic interpretation. In that case, the problem is linear and the algorithm always finds a solution. Furthermore, the equilibrium found in a bi-matrix game is perfect whenever the algorithm starts from a strategy vector at which all actions are played with positive probability.This research is part of the VF-program Co-operation and Competition, which has been approved by the Netherlands Ministery of Education and Sciences.     

The Structure of Hypergroup on the Cyclical Group

ＴｈｅＳｔｒｕｃｔｕｒｅｏｆＨｙｐｅｒｇｒｏｕｐｏｎｔｈｅＣｙｃｌｉｃａｌＧｒｏｕｐ￥ＺｈｏｎｇＹｕｂｉｎ（Ｄｅｐａｒｔｍｅｎｔｏｆｍａｔｈｅｍａｔｉｃｓ，ＧｕａｎｇｚｈｏｕＴｅａｃｈｅｒｓＣｏｌｌｅｇｅ）Ａｂｓｔｒａｃｔ：Ｓｉｎｃｅｔｈｅｈｙｐｅｒ...     

On Sullivan��s conjecture on cycles in 4-free and 5-free digraphs

For a simple digraph G, let β(G) be the size of the smallest subset X■E(G) such that G-X has no directed cycles, and let γ(G) be the number of unordered pairs of nonadjacent vertices in G. A digraph G is called k-free if G has no directed cycles of length at most k. This paper proves that β(G) ≤ 0.3819γ(G) if G is a 4-free digraph, and β(G) ≤ 0.2679γ(G) if G is a 5-free digraph. These improve the results of Sullivan in 2008.     

Existence of value in pursuit-evasion games with restricted phase coordinates

Almost all results referring to the problem of the existence of a value in differential games concern games without restricted phase coordinates. In this paper, we introduce a concept of value for differential games of pursuit and evasion and prove, under some general assumption, the existence of it. The players are required to satisfy some general phase constraints. The arguments employed in this paper are based on some extent on Krasovskii's method of extremal construction. We also show that the lower value in the Friedman sense is a generalization of our value. In a special linear case, the equivalence between pursuit differential games and time-optimal control problems is established.     

Learning of winning strategies for terminal games with linear-size memory

We prove that if one or more players in a locally finite positional game have winning strategies, then they can find it by themselves, not losing more than a bounded number of plays and not using more than a linear-size memory, independently of the strategies applied by the other players. We design two algorithms for learning how to win. One of them can also be modified to determine a strategy that achieves a draw, provided that no winning strategy exists for the player in question but with properly chosen moves a draw can be ensured from the starting position. If a drawing- or winning strategy exists, then it is learnt after no more than a linear number of plays lost (linear in the number of edges of the game graph). Z. Tuza’s research has been supported in part by the grant OTKA T-049613.     

Assignment games with stable core

We prove that the core of an assignment game (a two-sided matching game with transferable utility as introduced by Shapley and Shubik, 1972) is stable (i.e., it is the unique von Neumann-Morgenstern solution) if and only if there is a matching between the two types of players such that the corresponding entries in the underlying matrix are all row and column maximums. We identify other easily verifiable matrix properties and show their equivalence to various known sufficient conditions for core-stability. By these matrix characterizations we found that on the class of assignment games, largeness of the core, extendability and exactness of the game are all equivalent conditions, and strictly imply the stability of the core. In turn, convexity and subconvexity are equivalent, and strictly imply all aformentioned conditions. Final version: April 1, 2001     

关于循环环的理想、素理想和极大理想

研究了循环环R=的理想、素理想和极大理想的个数和结构,得到了如下结论:1)理想:(1)若|R|=∞,则R共有无穷多个理想:;(2)若|R|=n,设n的正因数个数为T(n),则R共有T(n)个理想:.2)素理想:(1)若|R|=∞,设a^2=ka(k≥0),①当k=0时,R的素理想只有R;②当k>0时,R的素理想共有无穷多个,它们是:{0}、R及;(2)若|R|=n>1,设a^2=ka,0≤k.3)极大理想:(1)若|R|=∞,则R有无限多个极大理想,它们是;(2)若|R|=n>1,设n的互不相同的素因数个数为ψ(n),则R共有ψ(n)个极大理想:(pa|p是n的素因数).     

Closedness under reduced games

We will introduce the notation of the generalized reduced game to unify the representations for maximal subclasses of the classes of essential games (superadditive games and convex games) that are closed under reduction in the sense of Sobolev (1975), Hart and Mas-Colell (1989), and Moulin (1985), respectively.     

带策略约束的区间数双矩阵博弈的双线性规划求解方法

传统区间数双矩阵博弈理论研究局中人支付值为区间数的策略选择问题,但没有考虑局中人策略选择可能受到各种约束.创建一种求解局中人策略选择受约束且支付值为区间数的双矩阵博弈（简称带策略约束的区间数双矩阵博弈）的简单、有效的双线性规划求解方法.首先,将局中人的博弈支付看作支付值区间中数值的函数.通过证明这种函数具有单调性,据此利用支付值区间的上、下界,构造了一对辅助双线性规划模型,可分别用于显式地计算任意带策略约束的区间数双矩阵博弈中局中人区间数博弈支付的上、下界及其相应的最优策略.最后,利用考虑策略约束条件下企业和政府针对发展低碳经济策略问题的算例,通过比较其与不考虑策略约束情形下的结果,说明了提出的模型和方法的有效性、优越性及可应用性.     

Multi-player stopping games with redistribution of payoffs and BSDEs with oblique reflection

We examine the connections between a novel class of multi-person stopping games with redistribution of payoffs and multi-dimensional reflected BSDEs in discrete- and continuous-time frameworks. Our goal is to provide an essential extension of classic results for two-player stopping games (Dynkin games) to the multi-player framework. We show the link between certain multi-period m$m$-player stopping games and a new kind of m$m$-dimensional reflected BSDEs. The existence and uniqueness of a solution to continuous-time reflected BSDEs are established. Continuous-time redistribution games are constructed with the help of reflected BSDEs and a characterization of the value of such stopping games is provided.     

On existence of undominated pure strategy Nash equilibria in anonymous nonatomic games: a generalization

In this paper, we generalize the exitence result for pure strategy Nash equilibria in anonymous nonatomic games. By working directly on integrals of pure strategies, we also generalize, for the same class of games, the existence result for undominated pure strategy Nash equilibria even though, in general, the set of pure strategy Nash equilibria may fail to be weakly compact. Received August 2001     

Various characterizations of convex fuzzy games

This note enlarges the literature on convex fuzzy games with new characterizing properties of such games besides the increasing average marginal return property, namely: the monotonicity of the first partial derivatives, the directional convexity and forC ²-functions the non-negativity of the second order partial derivatives.     

Asymmetric graph coloring games

We introduce the (a,b)‐coloring game, an asymmetric version of the coloring game played by two players Alice and Bob on a finite graph, which differs from the standard version in that, in each turn, Alice colors a vertices and Bob colors b vertices. We also introduce a related game, the (a,b)‐marking game. We analyze these games and determine the (a,b)‐chromatic numbers and (a,b)‐coloring numbers for the class of forests and all values of a and b. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 169–185, 2005     

Pure equilibria in a simple dynamic model of strategic market game

We present a discrete model of two-person constant-sum dynamic strategic market game. We show that for every value of discount factor the game with discounted rewards possesses a pure stationary strategy equilibrium. Optimal strategies have some useful properties, such as Lipschitz property and symmetry. We also show value of the game to be nondecreasing both in state and discount factor. Further, for some values of discount factor, exact form of optimal strategies is found. For β less than , there is an equilibrium such that players make large bids. For β close to 1, there is an equilibrium with small bids. Similar result is obtained for the long run average reward game.