How to play the one-lie Rényi-Ulam game

The one-lie Rényi-Ulam liar game is a two-player perfect information zero-sum game, lasting q rounds, on the set [n]?{1,…,n}. In each round Paul chooses a subset A⊆[n] and Carole either assigns one lie to each element of A or to each element of [n]?A. Paul wins the original (resp. pathological) game if after q rounds there is at most one (resp. at least one) element with one or fewer lies. We exhibit a simple, unified, optimal strategy for Paul to follow in both games, and use this to determine which player can win for all q,n and for both games.     

Lightness of digraphs in surfaces and directed game chromatic number

The lightness of a digraph is the minimum arc value, where the value of an arc is the maximum of the in-degrees of its terminal vertices. We determine upper bounds for the lightness of simple digraphs with minimum in-degree at least 1 (resp., graphs with minimum degree at least 2) and a given girth k, and without 4-cycles, which can be embedded in a surface S. (Graphs are considered as digraphs each arc having a parallel arc of opposite direction.) In case k≥5, these bounds are tight for surfaces of nonnegative Euler characteristics. This generalizes results of He et al. [W. He, X. Hou, K.-W. Lih, J. Shao, W. Wang, X. Zhu, Edge-partitions of planar graphs and their game coloring numbers, J. Graph Theory 41 (2002) 307-317] concerning the lightness of planar graphs. From these bounds we obtain directly new bounds for the game colouring number, and thus for the game chromatic number of (di)graphs with girth k and without 4-cycles embeddable in S. The game chromatic resp. game colouring number were introduced by Bodlaender [H.L. Bodlaender, On the complexity of some coloring games, Int. J. Found. Comput. Sci. 2 (1991) 133-147] resp. Zhu [X. Zhu, The game coloring number of planar graphs, J. Combin. Theory B 75 (1999) 245-258] for graphs. We generalize these notions to arbitrary digraphs. We prove that the game colouring number of a directed simple forest is at most 3.     

Nash-solvable two-person symmetric cycle game forms

A two-person positional game form g (with perfect information and without moves of chance) is modeled by a finite directed graph (digraph) whose vertices and arcs are interpreted as positions and moves, respectively. All simple directed cycles of this digraph together with its terminal positions form the set A of the outcomes. Each non-terminal position j is controlled by one of two players i∈I={1,2}. A strategy x_i of a player i∈I involves selecting a move (j,j^′) in each position j controlled by i. We restrict both players to their pure positional strategies; in other words, a move (j,j^′) in a position j is deterministic (not random) and it can depend only on j (not on preceding positions or moves or on their numbers). For every pair of strategies (x₁,x₂), the selected moves uniquely define a play, that is, a directed path form a given initial position j₀ to an outcome (a directed cycle or terminal vertex). This outcome a∈A is the result of the game corresponding to the chosen strategies, a=a(x₁,x₂). Furthermore, each player i∈I={1,2} has a real-valued utility function u_i over A. Standardly, a game form g is called Nash-solvable if for every u=(u₁,u₂) the obtained game (g,u) has a Nash equilibrium (in pure positional strategies).A digraph (and the corresponding game form) is called symmetric if (j,j^′) is its arc whenever (j^′,j) is. In this paper we obtain necessary and sufficient conditions for Nash-solvability of symmetric cycle two-person game forms and show that these conditions can be verified in linear time in the size of the digraph.     

Singularity, Wielandt’s lemma and singular values

In this study, some upper and lower bounds for singular values of a general complex matrix are investigated, according to singularity and Wielandt’s lemma of matrices. Especially, some relationships between the singular values of the matrix A and its block norm matrix are established. Based on these relationships, one may obtain the effective estimates for the singular values of large matrices by using the lower dimension norm matrices. In addition, a small error in Piazza (2002) [G. Piazza, T. Politi, An upper bound for the condition number of a matrix in spectral norm, J. Comput. Appl. Math. 143 (1) (2002) 141-144] is also corrected. Some numerical experiments on saddle point problems show that these results are simple and sharp under suitable conditions.     

Simple games and weighted games: A theoretical and computational viewpoint

It is a well-known result in the theory of simple games that a game is weighted if and only if it is trade robust. In this paper we propose a variant of trade robustness, that we call invariant-trade robustness, which is enough to determine whether a simple game is weighted. To test whether a simple game is invariant-trade robust we do not need to consider all winning coalitions; a reduced subset of minimal winning coalitions is enough.We make a comparison between the two methods (trade robustness and invariant-trade robustness) to check whether a simple game is weighted. We also provide by means of algorithms a full classification using both methods, for simple games with less than 8 voters according to the maximum level of (invariant-)trade robustness they achieve.     

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.     

Homogeneous games as anti step functions

In this paper the class of homogeneousn-person games “without dummies and steps” is characterized by two algebraic axioms. Each of these games induces a natural vector of lengthn, called incidence vector of the game, and vice versa. A geometrical interpretation of incidence vectors allows to construct all of these games and to enumerate them recursively with respect to the number of persons. In addition an algorithm is defined, which maps each directed game to a minimal representation of a homogeneous game. Moreover both games coincide, if the initial game is homogeneous.     

Stationary,completely mixed and symmetric optimal and equilibrium strategies in stochastic games

In this paper, we address various types of two-person stochastic games—both zero-sum and nonzero-sum, discounted and undiscounted. In particular, we address different aspects of stochastic games, namely: (1) When is a two-person stochastic game completely mixed? (2) Can we identify classes of undiscounted zero-sum stochastic games that have stationary optimal strategies? (3) When does a two-person stochastic game possess symmetric optimal/equilibrium strategies? Firstly, we provide some necessary and some sufficient conditions under which certain classes of discounted and undiscounted stochastic games are completely mixed. In particular, we show that, if a discounted zero-sum switching control stochastic game with symmetric payoff matrices has a completely mixed stationary optimal strategy, then the stochastic game is completely mixed if and only if the matrix games restricted to states are all completely mixed. Secondly, we identify certain classes of undiscounted zero-sum stochastic games that have stationary optima under specific conditions for individual payoff matrices and transition probabilities. Thirdly, we provide sufficient conditions for discounted as well as certain classes of undiscounted stochastic games to have symmetric optimal/equilibrium strategies—namely, transitions are symmetric and the payoff matrices of one player are the transpose of those of the other. We also provide a sufficient condition for the stochastic game to have a symmetric pure strategy equilibrium. We also provide examples to show the sharpness of our results.     

Some thoughts on saddle-point conditions and information structures in zero-sum differential games

For a very simple two-stage, linear-quadratic, zero-sum difference game with dynamic information structure, we show that (i) there exist nonlinear saddle-point strategies which require the same existence conditions as the well-known linear, closed-loop, no-memory solution and (ii) there exist both linear and nonlinear saddle-point strategies which require more stringent conditions than the unique open-loop solution. We then discuss the implication of this result with respect to the existence of saddle points in zero-sum differential games for different information patterns.     

Static search games played over graphs and general metric spaces

We define a general game which forms a basis for modelling situations of static search and concealment over regions with spatial structure. The game involves two players, the searching player and the concealing player, and is played over a metric space. Each player simultaneously chooses to deploy at a point in the space; the searching player receiving a payoff of 1 if his opponent lies within a predetermined radius r of his position, the concealing player receiving a payoff of 1 otherwise. The concepts of dominance and equivalence of strategies are examined in the context of this game, before focusing on the more specific case of the game played over a graph. Methods are presented to simplify the analysis of such games, both by means of the iterated elimination of dominated strategies and through consideration of automorphisms of the graph. Lower and upper bounds on the value of the game are presented and optimal mixed strategies are calculated for games played over a particular family of graphs.     

Correlation through bounded recall strategies

Two agents independently choose mixed m-recall strategies that take actions in finite action spaces A ₁ and A ₂. The strategies induce a random play, a ₁, a ₂, . . ., where a _t assumes values in A ₁ × A ₂. An M-recall observer observes the play. The goal of the agents is to make the observer believe that the play is similar to a sequence of i.i.d. random actions whose distribution is ${Q\in\Delta(A_1\times A_2)}$ . For nearly every t, the following event should occur with probability close to one: “the distribution of a _t+M given a _t , . . . , a _t+M-1 is close to Q.” We provide a sufficient and necessary condition on m, M, and Q under which this goal can be achieved (for large m). This work is a step in the direction of establishing a folk theorem for repeated games with bounded recall. It tries to tackle the difficulty in computing the individually rational levels (IRL) in the bounded recall setting. Our result implies, for example, that in some games the IRL in the bounded recall game is bounded away below the IRL in the stage game, even when all the players have the same recall capacity.     

Solution concepts in two-person multicriteria games

In this paper, we propose new solution concepts for multicriteria games and compare them with existing ones. The general setting is that of two-person finite games in normal form (matrix games) with pure and mixed strategy sets for the players. The notions of efficiency (Pareto optimality), security levels, and response strategies have all been used in defining solutions ranging from equilibrium points to Pareto saddle points. Methods for obtaining strategies that yield Pareto security levels to the players or Pareto saddle points to the game, when they exist, are presented. Finally, we study games with more than two qualitative outcomes such as combat games. Using the notion of guaranteed outcomes, we obtain saddle-point solutions in mixed strategies for a number of cases. Examples illustrating the concepts, methods, and solutions are included.     

Asymmetric directed graph coloring games

This note generalizes the (a,b)-coloring game and the (a,b)-marking game which were introduced by Kierstead [H.A. Kierstead, Asymmetric graph coloring games, J. Graph Theory 48 (2005) 169-185] for undirected graphs to directed graphs. We prove that the (a,b)-chromatic and (a,b)-coloring number for the class of orientations of forests is b+2 if b≤a, and infinity otherwise. From these results we deduce upper bounds for the (a,b)-coloring number of oriented outerplanar graphs and of orientations of graphs embeddable in a surface with bounded girth.     

On the reduced game property for and the axiomatization of theT-value of TU-games

Summary The τ-value is a one-point solution concept for transferable utility (TU-) games. The paper introduces a particular type of a reduced game. It is established that the τ-value possesses the reduced game property with respect to the reduced game presented. That is, there is no inconsistency in what the players of the reduced game receive-either in the original game or in the reduced game-according to the τ-value concept. In addition, the paper provides an axiomatic characterization of the τ-value in terms of the relevant reduced game property and standardness for two-person games.     

Fodor-type Reflection Principle and reflection of metrizability and meta-Lindelöfness

We introduce a new reflection principle which we call “Fodor-type Reflection Principle” (FRP). This principle follows from but is strictly weaker than Fleissner's Axiom R. For instance, FRP does not impose any restriction on the size of the continuum, while Axiom R implies that the continuum has size ?ℵ₂.We show that FRP implies that every locally separable countably tight topological space X is meta-Lindelöf if all of its subspaces of cardinality ?ℵ₁ are (Theorem 4.3). It follows that, under FRP, every locally (countably) compact space is metrizable if all of its subspaces of cardinality ?ℵ₁ are (Corollary 4.4). This improves a result of Balogh who proved the same assertion under Axiom R.We also give several other results in this vein, some in ZFC, others in some further extension of ZFC. For example, we prove in ZFC that if X is a locally (countably) compact space of singular cardinality in which every subspace of smaller size is metrizable then X itself is also metrizable (Corollary 5.2).     

On the restricted cores and the bounded core of games on distributive lattices

A game with precedence constraints is a TU game with restricted cooperation, where the set of feasible coalitions is a distributive lattice, hence generated by a partial order on the set of players. Its core may be unbounded, and the bounded core, which is the union of all bounded faces of the core, proves to be a useful solution concept in the framework of games with precedence constraints. Replacing the inequalities that define the core by equations for a collection of coalitions results in a face of the core. A collection of coalitions is called normal if its resulting face is bounded. The bounded core is the union of all faces corresponding to minimal normal collections. We show that two faces corresponding to distinct normal collections may be distinct. Moreover, we prove that for superadditive games and convex games only intersecting and nested minimal collection, respectively, are necessary. Finally, it is shown that the faces corresponding to pairwise distinct nested normal collections may be pairwise distinct, and we provide a means to generate all such collections.     

On some problems in geometric game theory

Several problems of dynamic systems control can be reduced to geometric games. The problem of stabilization is an example. In this paper, the criteria of a saddle point in a geometric game is proved under more general conditions than earlier. Algorithms for finding a saddle point are given in cases where the strategy set of one of the players is (1) a ball in ℝ ⁿ , (2) a closed interval, (3) a polyhedral, and the strategy set of the other player is an arbitrary convex set. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 11, No. 8, pp. 131–137, 2005.     

Quadratically normal matrices of type 1 and unitary similarities between them

Verification of the unitary similarity between matrices having quadratic minimal polynomials is known to be much cheaper than the use of the general Specht-Pearcy criterion. Such an economy is possible due to the following fact: n × n matrices A and B with quadratic minimal polynomials are unitarily similar if and only if A and B have the same eigenvalues and the same singular values. It is shown that this fact is also valid for a subclass of matrices with cubic minimal polynomials, namely, quadratically normal matrices of type 1.     

Complete inflation and perfect recall in extensive games

This paper considers the relation between complete inflation and perfect recall of information partitions in extensive games. It is proved that an information partition with perfect recall is completely inflated. This result, combined with Dalkey's theorem, shows that in the class of games (without chance moves) with perfect recall, a game is determinate if and only if every player has perfect information. A necessary and sufficient condition is provided for information partitions whose complete inflations have perfect recall.