Fast Winning Strategies in Avoider-Enforcer Games

In numerous positional games the identity of the winner is easily determined. In this case one of the more interesting questions is not who wins but rather how fast can one win. These types of problems were studied earlier for Maker-Breaker games; here we initiate their study for unbiased Avoider-Enforcer games played on the edge set of the complete graph K _n on n vertices. For several games that are known to be an Enforcer’s win, we estimate quite precisely the minimum number of moves Enforcer has to play in order to win. We consider the non-planarity game, the connectivity game and the non-bipartite game.     

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.     

Winning Sets, Quasiconformal Maps and Diophantine Approximation

This paper describes two new types of winning sets in mathbbRⁿ{mathbb{R}^n}, defined using variants of Schmidt’s game. These strong and absolute winning sets include many Diophantine sets of measure zero and first category, and have good behavior under countable intersections. Most notably, they are invariant under quasiconformal maps, while classical winning sets are not.     

Credibility of Incentive Equilibrium Strategies in Linear-State Differential Games

We characterize in this paper the credibility of incentive equilibrium strategies for the class of linear-state differential games. We derive a general condition for credibility and illustrate its use on two differential games taken from the literature of environmental economics and knowledge accumulation. We show that the proposed linear incentive strategies are not always credible. Further, we provide alternative nonlinear credible strategies which suggest that we should not stick only to linear incentive strategies, even in a simple class of differential games such as the linear-state one.This research was completed when the first author was visiting professor at GERAD, HEC, Montréal. The first author’s research was partially supported by MCYT under project BEC2002-02361 and by JCYL under project VA051/03, confinanced by FEDER funds. The second author’s research was supported by NSERC, Canada.     

连续区间策略下二人零和对策问题研究

考虑连续区间策略下的二人零和对策问题,研究其均衡策略的存在性。首先分析了完全信息下的二人零和对策问题,证明了该问题均衡策略的存在性并给出求解方法。然后进一步研究了收益函数不确定的不完全信息二人零和对策问题,在各局中人都认为对方是风险厌恶型的假设下,分析该类对策纯策略均衡的存在性,并通过研究纯策略均衡存在的充要条件给出判断并寻找纯策略均衡解的方法。最后给出一个数值算例,验证本文所提出方法的可行性。     

Total Reward Stochastic Games and Sensitive Average Reward Strategies

In this paper, total reward stochastic games are surveyed. Total reward games are motivated as a refinement of average reward games. The total reward is defined as the limiting average of the partial sums of the stream of payoffs. It is shown that total reward games with finite state space are strategically equivalent to a class of average reward games with an infinite countable state space. The role of stationary strategies in total reward games is investigated in detail. Further, it is outlined that, for total reward games with average reward value 0 and where additionally both players possess average reward optimal stationary strategies, it holds that the total reward value exists.     

Construction of Approximate Saddle-Point Strategies for Differential Games in a Hilbert Space

Two-person zero-sum infinite-dimensional differential games with strategies and payoff as in Berkovitz (SIAM J. Control Optim. 23: 173–196, 1985) are studied. Using Yosida type approximations of the infinitesimal generator (of the unbounded dynamics) by bounded linear operators, we prove convergence theorems for the approximate value functions. This is used to construct approximate saddle-point strategies in feedback form. A.J. Shaiju: NBHM Postdoctoral Fellow and the financial support from NBHM is gratefully acknowledged.     

Cell Complexities in Hyperplane Arrangements

We derive improved bounds on the complexity, i.e., the total number of faces of all dimensions, of many cells in arrangements of hyperplanes in higher dimensions, and use these bounds to obtain a very simple proof of an earlier bound, due to Aronov, Matousek, and Sharir, on the sum of squares of cell complexities in such an arrangement.     

Diophantine approximation in characteristiep

We study diophantine approximations to algebraic functions in characteristicp. We improve a theorem of Osgood, and give two classes of examples showing that this result is nearly sharp. One of these classes exhibits a new phenomenon.     

Biased Positional Games for Which Random Strategies are Nearly Optimal

For a graph G and natural numbers n and q let G(G; n, q) be the game on the complete graph K_nK_n in which two players, Maker and Breaker, alternately claim 1 and q edges respectively. Maker's aim is to build a copy of G while Breaker tries to prevent it. Let $m(G)=\mathop {\rm max}{\hbox {$m(G)=\mathop {\rm max}{\hbox {\lcub \vbox to8.5pt{\vss}.$}}{e(H)-1\over v(H)-2}:\;H\subseteq G,\,v(H)\ge 3{\hbox{$}}{e(H)-1\over v(H)-2}:\;H\subseteq G,\,v(H)\ge 3{\hbox{\rcub \vbox to8.5pt{\vss}.< /FORMULA > . It is shown that there exist constants < FORMULA FORM=ÏNLINE». It is shown that there exist constants c_0< /FORMULA > and < FORMULA FORM=ÏNLINE» and C_0< /FORMULA > such that Maker has a winning strategy in G( < SMALL > G; n, q < /SMALL > ) if < FORMULA FORM=ÏNLINE» such that Maker has a winning strategy in G(G; n, q) if q\le c_0 n^{1/m(G)}< /FORMULA > , while for < FORMULA FORM=ÏNLINE», while for q\ge C_0 n^{1/m(G)}$ the game can be won by Breaker.     

一般化两人零和模糊对策

定义一般化两人零和模糊对策,分别对具有纯策略和混合策略的一般化两人零和模糊对策进行研究,得到相应的最小最大值定理,以及一些与经典矩阵对策相类似的结果。     

On a Characterization of Evasion Strategies for Pursuit-Evasion Games on Graphs

We give a characterization of robber-win strategies for general pursuit-evasion games with one evader and any finite number of pursuers on a finite graph. We also give an algorithm that solves robber-win games.     

Solving Matrix Games with I-fuzzy Payoffs: Pareto-optimal Security Strategies Approach

A recent research work of Clemente et al. [12] on Pareto-optimal security strategies (POSS) in matrix games with fuzzy payoffs is extended to I-fuzzy scenario. Besides, the membership and the non-membership functions of the I-fuzzy values for both players are obtained by employing the technique of multiobjective optimization. The presented approach provides an efficient solution to a class of I-fuzzy matrix games with piecewise linear membership and non-membership functions. This class also includes I-fuzzy matrix games with triangular and trapezoidal I-fuzzy numbers as special cases. Further, POSS approach also provides an approximate solution to I-fuzzy matrix games with payoffs as general I-fuzzy numbers.