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.     

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.     

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.     

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.     

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.     

Diophantine equations in separated variables

We study Diophantine equations of type \(f(x)=g(y)\), where both f and g have at least two distinct critical points (roots of the derivative) and equal critical values at at most two distinct critical points. Various classical families of polynomials \((f_n)_n\) are such that \(f_n\) satisfies these assumptions for all n. Our results cover and generalize several results in the literature on the finiteness of integral solutions to such equations. In doing so, we analyse the properties of the monodromy groups of such polynomials. We show that if f has coefficients in a field K of characteristic zero, and at least two distinct critical points and all distinct critical values, then the monodromy group of f is a doubly transitive permutation group. In particular, f cannot be represented as a composition of lower degree polynomials. Several authors have studied monodromy groups of polynomials with some similar properties. We further show that if f has at least two distinct critical points and equal critical values at at most two of them, and if \(f(x)=g(h(x))\) with \(g, h\in K[x]\) and \(\deg g>1\), then either \(\deg h\le 2\), or f is of special type. In the latter case, in particular, f has no three simple critical points, nor five distinct critical points.