Some remarks on a Telgarsky's conjecture concerning products of paracompact spaces

R. Telgarsky conjectured that if X is a paracompact space then the product X×Y is paracompact for every paracompact space Y if and only if the first player of the G(DC,X) game, introduced by R. Telgarsky, see [R. Telgarsky, Spaces defined by topological games, Fund. Math. 88 (1975) 193-223], has a winning strategy. The paper contains some results supporting this conjecture.     

Loeb Measure from the Point of View of a Coin Flipping Game

A hyperfinitely long coin flipping game between the Gambler and the Casino, associated with a given set A, is considered. It turns out that the Gambler has a winning strategy if and only if A has Loeb measure 0. The Casino has a winning strategy if and only if A contains an internal subset of positive Loeb measure. Mathematics Subject Classification: 03H05, 03E15.     

A Strong Anti-Folk Theorem

We study the properties of finitely complex, symmetric, globally stable, and semi-perfect equilibria. We show that: (1) If a strategy satisfies these properties then players play a Nash equilibrium of the stage game in every period; (2) The set of finitely complex, symmetric, globally stable, semi-perfect equilibrium payoffs in the repeated game equals the set of Nash equilibria payoffs in the stage game; and (3) A strategy vector satisfies these properties in a Pareto optimal way if and only if players play some Pareto optimal Nash equilibrium of the stage game in every stage. Our second main result is a strong anti-Folk Theorem, since, in contrast to what is described by the Folk Theorem, the set of equilibrium payoffs does not expand when the game is repeated.This paper is a revised version of Chapter 3 of my Ph.D. thesis, which has circulated under the title “An Interpretation of Nash Equilibrium Based on the Notion of Social Institutions”.     

Theoretical analysis and numerical simulation of Parrondo’s paradox game in space

A multi-agent spatial Parrondo game model is designed according to the cooperative Parrondo’s paradox proposed by Toral. The model is composed of game A and game B. Game A is a zero-sum game between individuals, reflecting competitive interaction between an individual and its neighbors. The winning or losing probability of one individual in game B depends on its neighbors’ winning or losing states, reflecting the dependence that individuals has on microhabitat and the overall constraints that the microhabitat has on individuals. By using the analytical approach based on discrete-time Markov chain, we analyze game A, game B and the random combination of game A+B, and obtain corresponding stationary distribution probability and mathematical expectations. We have established conditions of the weak and strong forms of the Parrondo effect, and compared the computer simulation results with the analytical results so as to verify their validity. The analytical results reflect that competition results in the ratchet effect of game B, which generates Parrondo’s Paradox that the combination of the losing games can produce a winning result.     

三步矩阵对策上的无中生有计及其实例

基于一个历史实例及假定:①三步矩阵对策中赢得矩阵都不变,②每步都是局中人1先行动,③对于每步对策,局中人2观测不到对手究竟使用了何策略;但局中人1可以观测到对手所用的策略,建立了三步矩阵对策上的无中生有计(《三十六计》中的第七计)的对策模型.研究了当局中人2中计,半识破和完全识破对手的无中生有计时的赢得和所用的策略的情况.并用上述实例对模型作了说明.     

The cat and the noisy mouse

We consider a variant of a pursuit and evasion game studied independently by Britnell and Wildon as well as Haslegrave. In their game, a cat has to catch an invisible mouse that moves along the edges of some graph $G$. In our version, the cat receives partial information about its distance to the mouse, and we show that the cat has a winning strategy if and only if $G$ is a forest. Seager proposed a similar game with complete distance information whose rules cause some small yet important differences to the game we consider.     

On (strong) α-favorability of the Wijsman hyperspace

The Banach-Mazur game as well as the strong Choquet game are investigated on the Wijsman hyperspace from the nonempty player's (i.e. α's) perspective. For the strong Choquet game we show that if X is a locally separable metrizable space, then α has a (stationary) winning strategy on X iff it has a (stationary) winning strategy on the Wijsman hyperspace for each compatible metric on X. The analogous result for the Banach-Mazur game does not hold, not even if X is separable, as we show that α may have a (stationary) winning strategy on the Wijsman hyperspace for each compatible metric on X, and not have one on X. We also show that there exists a separable 1st category metric space such that α has a (stationary) winning strategy on its Wijsman hyperspace. This answers a question of Cao and Junnila (2010) [6].     

Game-perfect digraphs

In the A-coloring game, two players, Alice and Bob, color uncolored vertices of a given uncolored digraph D with colors from a given color set C, so that, at any time a vertex is colored, its color has to be different from the colors of its previously colored in-neighbors. Alice begins. The players move alternately, where a move of Bob consists in coloring a vertex, and a move of Alice in coloring a vertex or missing the turn. The game ends when Bob is unable to move. Alice wins if every vertex is colored at the end, otherwise Bob wins. This game is a variant of a graph coloring game proposed by Bodlaender (Int J Found Comput Sci 2:133?C147, 1991). The A-game chromatic number of D is the smallest cardinality of a color set C, so that Alice has a winning strategy for the game played on D with C. A digraph is A-perfect if, for any induced subdigraph H of D, the A-game chromatic number of H equals the size of the largest symmetric clique of H. We characterize some basic classes of A-perfect digraphs, in particular all A-perfect semiorientations of paths and cycles. This gives us, as corollaries, similar results for other games, in particular concerning the digraph version of the usual game chromatic number.     

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.     

连续对策之判断下的最优策略集

本文引进连续对策上的判断块、判断准确、判断下的最优策略集等概念，得到了如下几个主要结果：1.判断下的最优策略集是一个局部凸空间的非空有界闭凸集；2.两个判断下的最优策略集相等的充要条件是这两个判断位于同一判断块中；3.若局中人判断准确，则在一次性对策下不论他使用此判断下的那一个最优策略（不论是纯的还是混合的），都可无风险地取得最优赢得。     

On Erdős's Eulerian Trail Game

 Paul Erdős proposed the following graph game. Starting with the empty graph on n vertices, two players, Trailmaker and Breaker, draw edges alternatingly. Each edge drawn has to start at the endpoint of the previously drawn edge, so the sequence of edges defines a trail. The game ends when it is impossible to continue the trail, and Trailmaker wins if the trail is eulerian. For all values of n, we determine which player has a winning strategy. Received: November 6, 1996 / Revised: May 2, 1997     

The game of arboricity

Using a fixed set of colors C, Ann and Ben color the edges of a graph G so that no monochromatic cycle may appear. Ann wins if all edges of G have been colored, while Ben wins if completing a coloring is not possible. The minimum size of C for which Ann has a winning strategy is called the game arboricity of G, denoted by A_g(G). We prove that A_g(G)?3k for any graph G of arboricity k, and that there are graphs such that A_g(G)?2k-2. The upper bound is achieved by a suitable version of the activation strategy, used earlier for the vertex coloring game. We also provide two other strategies based on induction and acyclic colorings.     

Crowding games are sequentially solvable

A sequential-move version of a given normal-form game Γ is an extensive-form game of perfect information in which each player chooses his action after observing the actions of all players who precede him and the payoffs are determined according to the payoff functions in Γ. A normal-form game Γ is sequentially solvable if each of its sequential-move versions has a subgame-perfect equilibrium in pure strategies such that the players' actions on the equilibrium path constitute an equilibrium of Γ.  A crowding game is a normal-form game in which the players share a common set of actions and the payoff a particular player receives for choosing a particular action is a nonincreasing function of the total number of players choosing that action. It is shown that every crowding game is sequentially solvable. However, not every pure-strategy equilibrium of a crowding game can be obtained in the manner described above. A sufficient, but not necessary, condition for the existence of a sequential-move version of the game that yields a given equilibrium is that there is no other equilibrium that Pareto dominates it. Received July 1997/Final version May 1998     

A <Emphasis Type="Italic">q</Emphasis>-player impartial avoidance game for generating finite groups

We study a q-player variation of the impartial avoidance game introduced by Anderson and Harary, where q is a prime. The game is played by the q players taking turns selecting previously-unselected elements of a finite group. The losing player is the one who selects an element that causes the set of jointly-selected elements to be a generating set for the group, with the previous player winning. We introduce a ranking system for the other players to prevent coalitions. We describe the winning strategy for these games on cyclic, nilpotent, dihedral, and dicyclic groups.     

Strong equilibria of a repeated game with randomized strategies

A version of Aumann's (1976) model of a repeated game with randomized strategies is studied. The pure strategy set of each player is assumed to be a compact metric spacnd complexities due to the information structures are explicitly handled. It is shown that one can extend Aumann's argument to this setup and still prove the Aumann Proposition on equivalence of the β-core of a one-shot game with correlated strategies and the strong equilibrium utility allocations of the associated repeated game with randomized strategies. To this extended version of the Aumann Proposition, the author's theorem for nonemptiness of the β-core with correlated strategies is applicable, so this version is non-vacuous.     

The Banach–Mazur game and domain theory

Archiv der Mathematik - We prove that player $$\alpha $$ has a winning strategy in the Banach–Mazur game on a space X if and only if X is F-Y countably $$\pi $$-domain representable. We show...     

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.     

A note on balancedness and nonemptiness of the core in voting games

Consider a society with a finite number,n, of individuals who have to choose an alternative from a setA in them-dimensional Euclidean space IR ^m . Assuming that the preference relation overA of every individual is convex and continuous, Greenberg (1979) showed some that if the set of winning coalitions (i.e. those that have the veto power) consists of all coalitions with more thanmn/m + 1 individuals the core of the induced game is nonempty. Greenberg and Weber (1984) have strengthened this result by showing that the induced game is in fact balanced. On the other hand Le Breton (1987), Schofield (1984a) and Strnad (1985) have generalized Greenberg's theorem to arbitrary voting games. The purpose of this note is to show that however the induced game is not generally balanced.     

Infinite sequential games with perfect but incomplete information

Infinite sequential games, in which Nature chooses a Borel winning set and reveals it to one of the players, do not necessarily have a value if Nature has 3 or more choices. The value does exist if Nature has 2 choices. The value also does not necessarily exist if Nature chooses from 2 Borel payoff functions. Similarly, if Player 1 chooses the Borel winning set and does not reveal his selection to Player 2, then the game does not necessarily have a value if there are 3 or more choices; it does have a value if there are only 2 choices. If Player 1 chooses from 2 Borel payoff functions and does not reveal his choice, the game need not have a value either.     

The graph grabbing game on Km,n-trees

The graph grabbing game is a two-player game on weighted connected graphs where all weights are non-negative. Two players, Alice and Bob, alternately remove a non-cut vertex from the graph (i.e., the resulting graph is still connected) and get the weight assigned to the vertex, where the starting player is Alice. Each player’s aim is to maximize his/her outcome when all vertices have been taken, and Alice wins the game if she gathered at least half of the total weight. Seacrest and Seacrest (2017) proved that Alice has a winning strategy for every weighted tree with even order, and conjectured that the same statement holds for every weighted connected bipartite graph with even order. In this paper, we prove that Alice wins the game on a type of a connected bipartite graph with even order called a $K_{m,n}$-tree.