Computational complexity of winning strategies in two-person polynomial games

One considers two-person games, with players called I and II below. In order, they choose natural numbers, for example, for length 4, I chooses x₁, II chooses x₂. I chooses x₃, II chooses x₄. Then I wins if P(x₁,x₂,x₃,x₄)=0.Here P is a polynomial with integer coefficients. An old theorem of von Neumann and Zermelo shows that such a game is determined, i.e., there exists a winning strategy for one player or the other but not necessarily a computable winning strategy or one computable in polynomial time. It will be shown that there exists a game of polynomial type of length 4 for which there do not exist winning strategies for either player which are computable in polynomial time.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 192, pp. 69–73, 1991.     

Weak acyclic coloring and asymmetric coloring games

We introduce the notion of weak acyclic coloring of a graph. This is a relaxation of the usual notion of acyclic coloring which is often sufficient for applications. We then use this concept to analyze the (a,b)-coloring game. This game is played on a finite graph G, using a set of colors X, by two players Alice and Bob with Alice playing first. On each turn Alice (Bob) chooses a (b) uncolored vertices and properly colors them with colors from X. Alice wins if the players eventually create a proper coloring of G; otherwise Bob wins when one of the players has no legal move. The (a,b)-game chromatic number of G, denoted (a,b)-χ_g(G), is the least integer t such that Alice has a winning strategy when the game is played on G using t colors. We show that if the weak acyclic chromatic number of G is at most k then (2,1)-.     

Cc （X） Spaces with X Locally Compact

In this paper, we show, among other results, that if X is a [separable] locally compact space X [satisfying the first countability axiom] then the space Cc （X） has countable tightness [if and only if it has bounding tightness] if and only if it is Frechet-Urysohn, if and only if Cc （X） contains a dense （LM） subspace and if and only if X is a-compact.     

Two point-picking games derived from a property of function spaces

We present a study of two versions of the point-picking game defined by Berner and Juhasz. Given a space X there are two rivals O and P who take turns playing on X. In the n-th round Player O takes a non-empty open subset U_n of the space X and P responds by choosing a point x_n ∈ U_n. After ω-many moves are completed, the family is called the play of the game. In the CD-game CD(X) Player P wins if the set is closed and discrete. Otherwise O is the winner. In the CL-game CL(X, p), where the point p ∈ X is fixed, Player O wins if contains p in its closure. If , then P is declared to be the winner. We show that in spaces C_p(X) both CD-game and CL-game are equivalent to Gruenhage’s W-game for Player O. If , then Player O has a winning strategy in CL(X, p). The converse is not always true. However, if X is separable or compact of π-weight ≤ ω₁, then existence of a winning strategy for O in CL(X, p) is equivalent to .     

Tightness games with bounded finite selections

For a topological space X and a point x ∈ X, consider the following game—related to the property of X being countably tight at x. In each inning n ∈ ω, the first player chooses a set A _n that clusters at x, and then the second player picks a point a _n ∈ A _n ; the second player is the winner if and only if \(x \in \overline {\left\{ {{a_n}:n \in \omega } \right\}} \).In this work, we study variations of this game in which the second player is allowed to choose finitely many points per inning rather than one, but in which the number of points they are allowed to choose in each inning has been fixed in advance. Surprisingly, if the number of points allowed per inning is the same throughout the play, then all of the games obtained in this fashion are distinct. We also show that a new game is obtained if the number of points the second player is allowed to pick increases at each inning.     

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.     

On the Density of Positive Proper Efficient Points in a Normed Space

In the context of vector optimization and generalizing cones with bounded bases, we introduce and study quasi-Bishop-Phelps cones in a normed space X. A dual concept is also presented for the dual space X*. Given a convex subset A of a normed space X partially ordered by a closed convex cone S with a base, we show that, if A is weakly compact, then positive proper efficient points are sequentially weak dense in the set E(A, S) of efficient points of A; in particular, the connotation weak dense in the above can be replaced by the connotation norm dense if S is a quasi-Bishop-Phelps cone. Dually, for a convex subset of X* partially ordered by the dual cone S ⁺, we establish some density results of positive weak* efficient elements of A in E(A, S ⁺).     

Spaces in which every dense subset is a Gδ

A topological space X is called a DG_δ-space if every subset of X is a G_δ-set in its closure. In this paper we study DG_δ-spaces that contains subspaces in which every dense subset is open and spaces in which every subset is a G_δ . We give some new results in these classes of topological spaces.     

Game chromatic index of k‐degenerate graphs

We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001     

Remote points and the like in pointfree topology

A point p of β, where X is a Tychonoff space, is called a remote point if for any nowhere dense D ⊆, X, p ∉ cl_βx D. A subset S of X is called round if whenever the closure in βX of a zero-set of X contains S, then it is a neighborhood of S. The purpose of this paper is to study these notions in the pointfree context. In the process, we introduce N-homomorphisms and show how the Stone extension of an N-homomorphism transfers remote points back and forth.      

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

Rothberger bounded groups and Ramsey theory

We show that:

(1)

Rothberger bounded subgroups of σ-compact groups are characterized by Ramseyan partition relations (Corollary 4).

(2)

For each uncountable cardinal κ there is a T₀ topological group of cardinality κ such that ONE has a winning strategy in the point-open game on the group and the group is not a closed subspace of any σ-compact space (Theorem 8).

(3)

For each uncountable cardinal κ there is a T₀ topological group of cardinality κ such that ONE has a winning strategy in the point-open game on the group and the group is σ-compact (Corollary 17).

     

Positional Games and the Second Moment Method

Dedicated to the memory of Paul Erdős We study the fair Maker–Breaker graph Ramsey game MB(n;q). The board is , the players alternately occupy one edge a move, and Maker wants a clique of his own. We show that Maker has a winning strategy in MB(n;q) if , which is exactly the clique number of the random graph on n vertices with edge-probability 1/2. Due to an old theorem of Erdős and Selfridge this is best possible apart from an additive constant. Received March 28, 2000     

Probabilistic Extensions of the Erdős–Ko–Rado Property

The classical Erdős–Ko–Rado (EKR) Theorem states that if we choose a family of subsets, each of size k, from a fixed set of size , then the largest possible pairwise intersecting family has size . We consider the probability that a randomly selected family of size t=t _n has the EKR property (pairwise nonempty intersection) as n and k=k _n tend to infinity, the latter at a specific rate. As t gets large, the EKR property is less likely to occur, while as t gets smaller, the EKR property is satisfied with high probability. We derive the threshold value for t using Janson’s inequality. Using the Stein–Chen method we show that the distribution of X ₀, defined as the number of disjoint pairs of subsets in our family, can be approximated by a Poisson distribution. We extend our results to yield similar conclusions for X _i , the number of pairs of subsets that overlap in exactly i elements. Finally, we show that the joint distribution (X ₀, X ₁, ..., X _b ) can be approximated by a multidimensional Poisson vector with independent components.      

Homomorphisms on Lipschitz Spaces

 Denote by the family of all real valued functions on a metric space which satisfy a Lipschitz condition on the compact (bounded) subsets of X. We prove that every homomorphism on is the evaluation at some point of X if and only if X is realcompact (every closed bounded subset of X is compact). (Received 4 November 1998; in revised form 31 May 1999)     

Avoider-Enforcer: The rules of the game

An Avoider-Enforcer game is played by two players, called Avoider and Enforcer, on a hypergraph F⊆X². The players claim previously unoccupied elements of the board X in turns. Enforcer wins if Avoider claims all vertices of some element of F, otherwise Avoider wins. In a more general version of the game a bias b is introduced to level up the players' chances of winning; Avoider claims one element of the board in each of his moves, while Enforcer responds by claiming b elements. This traditional set of rules for Avoider-Enforcer games is known to have a shortcoming: it is not bias monotone.We relax the traditional rules in a rather natural way to obtain bias monotonicity. We analyze this new set of rules and compare it with the traditional ones to conclude some surprising results. In particular, we show that under the new rules the threshold bias for both the connectivity and Hamiltonicity games, played on the edge set of the complete graph Kn, is asymptotically equal to n/logn. This coincides with the asymptotic threshold bias of the same game played by two “random” players.     

On (strong) α-favorability of the Vietoris hyperspace

For a normal space X, α (i.e. the nonempty player) having a winning strategy (resp. winning tactic) in the strong Choquet game Ch(X) played on X is equivalent to α having a winning strategy (resp. winning tactic) in the strong Choquet game played on the hyperspace CL(X) of nonempty closed subsets endowed with the Vietoris topology τ _V . It is shown that for a non-normal X where α has a winning strategy (resp. winning tactic) in Ch(X), α may or may not have a winning strategy (resp. winning tactic) in the strong Choquet game played on the Vietoris hyperspace. If X is quasi-regular, then having a winning strategy (resp. winning tactic) for α in the Banach-Mazur game BM(X) played on X is sufficient for α having a winning strategy (resp. winning tactic) in BM(CL(X), τ _V ), but not necessary, not even for a separable metric X. In the absence of quasi-regularity of a space X where α has a winning strategy in BM(X), α may or may not have a winning strategy in the Banach-Mazur game played on the Vietoris hyperspace.     

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.     

Testing for Tail Independence in Extreme Value models

Let (X,Y) be a random vector which follows in its upper tail a bivariate extreme value distribution with reverse exponentialmargins. We show that the conditional distribution function (df) of X + Y, given that X + Y>c, converges to the df F (t) = t ², , as if and only if X,Y are tail independent. Otherwise, the limit is F (t) = t. This is utilized to test for the tail independence of X, Y via various tests, including the one suggested by the Neyman–Pearson lemma. Simulations show that the Neyman–Pearson test performs best if the threshold c is close to 0, whereas otherwise it is the Kolmogorov–Smirnov test that performs best. The mathematical conditions are studied under which the Neyman–Pearson approach actually controls the type I error. Our considerations are extended to extreme value distributions in arbitrary dimensions as well as to distributions which are in a differentiable spectral neighborhood of an extreme value distribution.     

On spaces in which countably compact sets are closed, and hereditary properties

A space X is called C-closed if every countably compact subset of X is closed in X. We study the properties of C-closed spaces. Among other results, it is shown that countably compact C-closed spaces have countable tightness and under Martin's Axiom or 2^ω0<2^ω1, C-closed is equivalent to sequential for compact Hausdorff spaces. Furthermore, every hereditarily quasi-k Hausdorff space is Fréchet-Urysohn, which generalizes a theorem of Arhangel'sk in [4]. Also every hereditarily q-space is hereditarily of pointwise countable type and contains an open dense first countable subspace.