On a combinatorial game

A drawing strategy is explained which applies to a wide class of combinatorial and positional games. In some settings the strategy is best possible. When applied to n-dimensional Tic-Tac-Toe, it improves a result of Hales and Jewett [5].     

Economical tight examples for the biased Erd?s-Selfridge theorem

A positional game is essentially a generalization of tic-tac-toe played on a hypergraph (V,F). A pivotal result in the study of positional games is the Erd?s-Selfridge theorem, which gives simple criteria for the existence of a Breaker's winning strategy on a hypergraph F. It has been shown that the Erd?s-Selfridge theorem can be tight and that numerous extremal systems exist for that theorem. We focus on a generalization of the Erd?s-Selfridge theorem proven by Beck for biased (p:q) games, which we call the (p:q)-Erd?s-Selfridge theorem. We show that for pn-uniform hypergraphs there is a unique extremal system for the (p:q)-Erd?s-Selfridge theorem (q?2) when Maker must win in exactly n turns (i.e., as quickly as possible).     

Guaranteed control in differential games with ellipsoidal payoff

A class of antagonistic linear differential games (DGs) in a fixed time interval with ellipsoidal payoff functional is considered. This class of DGs includes problems which assume both rigid constraints on the players' controls and requirements to minimize control expenses. Other known classes of differential games, such as linear DGs with a quadratic performance index and linear DGs with ellipsoidal terminal sets and admissible sets of controls for the players, considered in Kurzhanskii's ellipsoidal technique, are limiting cases of DGs of this class. The concept of a u-strategic function, which expresses the property of u-stability for ellipsoidal functions, is introduced. An effective algorithm is presented for computing a u-strategic function, based on Kurzhanskii's ellipsoidal technique. The main result of this paper is that a guaranteed positional strategy for player u is defined by a certain explicit formula in terms of a u-strategic function. The proof of this result is based on a viability theorem for differential equations.     

Algorithms and the calculation of Nash equilibria for multi-objective control of time-discrete systems and polynomial-time algorithms for dynamic c-games on networks

We consider a multi-objective control problem of time-discrete systems with given starting and final states. The dynamics of the system are controlled by p actors (players). Each of the players intends to minimize his own integral-time cost of the system’s transitions using a certain admissible trajectory. Nash Equilibria conditions are derived and algorithms for solving dynamic games in positional form are proposed in this paper. The existence theorem for Nash equilibria is related to the introduction of an auxiliary dynamic c-game. Stationary and non-stationary cases are described. The paper concludes with a complexity analysis for that decision process.     

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.     

Stationary strategies in topological games

We prove general theorems on the existence of stationery strategies (i.e., strategies depending only on the opponent's last move) in certain infinite positional games of perfect information and we derive some consequences for various topological games.     

On acyclicity of games with cycles

We study restricted improvement cycles (ri-cycles) in finite positional n-person games with perfect information modeled by directed graphs (di-graphs) that may contain directed cycles (di-cycles). We assume that all these di-cycles form one outcome c, for example, a draw. We obtain criteria of restricted improvement acyclicity (ri-acyclicity) in two cases: for n=2 and for acyclic di-graphs. We provide several examples that outline the limits of these criteria and show that, essentially, there are no other ri-acyclic cases.We also discuss connections between ri-acyclicity and some open problems related to Nash-solvability.     

The τ-value,The core and semiconvex games

Theτ-value for cooperativen-person games is central in this paper. Conditions are given which guarantee that theτ-value lies in the core of the game. A full-dimensional cone of semiconvex games is introduced. This cone contains the cones of convex and exact games and there is a simple formula for theτ-value for such games. The subclass of semiconvex games with constant gap function is characterized in several ways. It turns out to be an (n+1)-dimensional cone and for all games in this cone the Shapley value, the nucleolus and theτ-value coincide.     

Generalizedk-quota solutions for (N,k) games

A generalization of quota solutions presented byShapley [1953] andKalisch [1959] is investigated for some classes ofn-person games. A new type of solution is obtained for symmetric games as a consequence.     

Nonlinear positional differential game in the class of mixed strategies

The feedback control problem is considered for a nonlinear dynamic system under lack of information on disturbances. The problem on minmax-maxmin of the guaranteed result for a given positional quality index is formalized as an antagonistic two-player differential game in the framework of the concept developed in the Sverdlovsk (now Yekaterinburg) school on the theory of differential games. The problem is solved in the class of mixed strategies. The existence of the value of the game and a saddle point is established. The solution to the problem is based on the application of appropriate leader models, the method of extremal shift to the accompanying points and the method of upper convex hulls. The results of the study are applied to a realistic control model. The simulation outputs are presented.     

Assignment games,chromatic number,and exchange theory

The exchange networks that social psychologists have studied can usefully be represented as game theoretic 2‐sided assignment games. Conceiving of these networks as 2‐sided assignment games opens up the possibility of studying N‐sided assignment games and games without cores. 2‐sided assignment games are special in that they always have cores, stable solutions in which every individual and subgroup behave rationally.

The implicit assignment of positions to categories of an N‐sided assignment game is related to coloring a graph. The color classes form sets of positions with potentially related interests. Color equivalence is compared to structural, regular, automorphic, and ecological positional equivalence.     

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.     

Values of games without side payments

A value forn-person games without side payments is given which coincides with theShapley value for games with side payments, and with theNash value for two-person games.     

Oddness of the number of equilibrium points: A new proof

A new proof is offered for the theorem that, in “almost all” finite games, the number of equilibrium points isfinite andodd. The proof is based on constructing a one-parameter family of games with logarithmic payoff functions, and studying the topological properties of the graph of a certain algebraic function, related to the graph of the set of equilibrium points for the games belonging to this family. In the last section of the paper, it is shown that, in the space of all games of a given size, those “exceptional” games which fail to satisfy the theorem (by having an even number or an infinity of equilibrium points) is a closed set of measure zero.     

Dimension of complete simple games with minimum

Weighted majority games have the property that players are totally ordered by the desirability relation (introduced by Isbell in [J.R. Isbell, A class of majority games, Quarterly Journal of Mathematics, 7 (1956) 183–187]) because weights induce it. Games for which this relation is total are called complete simple games. Taylor and Zwicker proved in [A.D. Taylor, W.S. Zwicker, Weighted voting, multicameral representation, and power, Games and Economic Behavior 5 (1993) 170–181] that every simple game (or monotonic finite hypergraph) can be represented by an intersection of weighted majority games and consider the dimension of a game as the needed minimum number of them to get it. They provide the existence of non-complete simple games of every dimension and left open the problem for complete simple games.     

Multi-stage sequencing situations

This paper introduces the idea of dynamics in cooperative games. The concrete case of multi-stage sequencing situations and the difficulties involved in defining stable cost savings allocations for the games arising from these situations is studied. The MEGS-rule is defined and proven to yield stable allocations. A characterization for the MEGS-rule is given.     

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.     

Reduction of Silverman-like games to games on bounded sets

A two person zero sum game is regarded as Silverman-like if the strategy sets are sets of real numbers bounded below, the payoff function is bounded, the maximum payoff is achieved whenever the second player's numbery exceeds the first player's numberx by “too much”, and the minimum is achieved wheneverx exceedsy by “too much”. Explicit upper bounds are obtained for pure strategies to be included in an optimal mixed strategy in such games. In particular, if the strategy sets are discrete, the games may be reduced to games on specified finite sets.     

Cores of partitioning games

A generalization of assignment games, called partitioning games, is introduced. Given a finite set N of players, there is an a priori given set π of coalitions of N and only coalitions in π play an essential role. Necessary and sufficient conditions for the nonemptiness of the cores of all games with essential coalitions π are developed. These conditions appear extremely restrictive. However when N is ‘large’, there are relatively few ‘types’ of players, and members of π are ‘small’ and defined in terms of numbers of players of each type contained in subsets, then approximate cores are nonempty.     

On the optimality of the uniform random strategy

Biased Maker‐Breaker games, introduced by Chvátal and Erd?s, are central to the field of positional games and have deep connections to the theory of random structures. The main questions are to determine the smallest bias needed by Breaker to ensure that Maker ends up with an independent set in a given hypergraph. Here we prove matching general winning criteria for Maker and Breaker when the game hypergraph satisfies certain “container‐type” regularity conditions. This will enable us to answer the main question for hypergraph generalizations of the H‐building games studied by Bednarska and ?uczak as well as a generalization of the van der Waerden games introduced by Beck. We find it remarkable that a purely game‐theoretic deterministic approach provides the right order of magnitude for such a wide variety of hypergraphs, while the analogous questions about sparse random discrete structures are usually quite challenging.