A symbolic finite-state approach for automated proving of theorems in combinatorial game theory

We develop a finite-state automata approach, implemented in a Maple package Toads and Frogs available from our websites, for conjecturing, and then rigorously proving, values for large families of positions in Richard Guy's combinatorial game ‘Toads and Frogs’. In particular, we prove a conjecture of Jeff Erickson.     

A Relationship Among Gentzen's Proof-Reduction,Kirby-Paris' Hydra Game and Buchholz's Hydra Game

We first note that Gentzen's proof-reduction for his consistency proof of PA can be directly interpreted as moves of Kirby-Paris' Hydra Game, which implies a direct independence proof of the game (Section 1 and Appendix). Buchholz's Hydra Game for labeled hydras is known to be much stronger than PA. However, we show that the one-dimensional version of Buchholz's Game can be exactly identified to Kirby-Paris' Game (which is two-dimensional but without labels), by a simple and natural interpretation (Section 2). Jervell proposed another type of a combinatorial game, by abstracting Gentzen's proof-reductions and showed that his game is independent of PA. We show (Section 3) that this Jervell's game is actually much stronger than PA, by showing that the critical ordinal of Jervell's game is φ_ω (0) (while that of PA or of Kirby-Paris' Game is φ₁ (0) = ?₀) in the Veblen hierarchy of ordinals.     

Cutting lemma and union lemma for the domination game

Two new techniques are introduced into the theory of the domination game. The cutting lemma bounds the game domination number of a partially dominated graph with the game domination number of a suitably modified partially dominated graph. The union lemma bounds the S-game domination number of a disjoint union of paths using appropriate weighting functions. Using these tools a conjecture asserting that the so-called three legged spiders are game domination critical graphs is proved. An extended cutting lemma is also derived and all game domination critical trees on 18, 19, and 20 vertices are listed.     

A threshold for the Maker‐Breaker clique game

We study the Maker‐Breaker k‐clique game played on the edge set of the random graph G(n, p). In this game, two players, Maker and Breaker, alternately claim unclaimed edges of G(n, p), until all the edges are claimed. Maker wins if he claims all the edges of a k‐clique; Breaker wins otherwise. We determine that the threshold for the graph property that Maker can win this game is at , for all k > 3, thus proving a conjecture from Ref. [Stojakovi? and Szabó, Random Struct Algor 26 (2005), 204–223]. More precisely, we conclude that there exist constants such that when the game is Maker's win a.a.s., and when it is Breaker's win a.a.s. For the triangle game, when k = 3, we give a more precise result, describing the hitting time of Maker's win in the random graph process. We show that, with high probability, Maker can win the triangle game exactly at the time when a copy of K₅ with one edge removed appears in the random graph process. As a consequence, we are able to give an expression for the limiting probability of Maker's win in the triangle game played on the edge set of G(n, p). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 318–341, 2014     

The infinite duration lying oracle game

In the lying oracle game, a Player places bets on the outcomes of a sequence of coin flips. A second player, the Oracle, informs the Player what the outcome of each coin flip is, but may at times lie. We analyse this game when the duration of the game is infinite, where the Oracle's ability to lie or be truthful is specified by a set of lie patterns X, known to both players. By equipping X with Lebesgue measure, we prove that for any ε?>?0, the Player has a strategy that yields an expected fortune of at least 1/λ⁺(X)???ε, and that the Oracle has a strategy that limits the Player's expected fortune to at most 1/λ^?(X), where λ⁺(X) and λ^?(X) are the outer and inner Lebesgue measure of X, respectively.     

Hedging of game options in discrete markets with transaction costs

Game options introduced in [10] in 2000 were studied, by now, mostly in frictionless both complete and incomplete markets. In complete markets the fair price of a game option coincides with the value of an appropriate Dynkin's game, whereas in markets with friction and in incomplete ones there is a range of arbitrage free prices and superhedging comes into the picture. Here we consider game options in general discrete time markets with transaction costs and construct backward and forward induction algorithms for the computation of their prices and superhedging strategies from both seller's (upper arbitrage free price) and buyer's (lower arbitrage free price) points of view extending to the game options case most of the results from [12].     

Optimal strategic reasoning with McNaughton functions

The aim of the paper is to explore strategic reasoning in strategic games of two players with an uncountably infinite space of strategies the payoff of which is given by McNaughton functions—functions on the unit interval which are piecewise linear with integer coefficients. McNaughton functions are of a special interest for approximate reasoning as they correspond to formulas of infinitely valued Lukasiewicz logic. The paper is focused on existence and structure of Nash equilibria and algorithms for their computation. Although the existence of mixed strategy equilibria follows from a general theorem (Glicksberg, 1952) [5], nothing is known about their structure neither the theorem provides any method for computing them. The central problem of the article is to characterize the class of strategic games with McNaughton payoffs which have a finitely supported Nash equilibrium. We give a sufficient condition for finite equilibria and we propose an algorithm for recovering the corresponding equilibrium strategies. Our result easily generalizes to n-player strategic games which don't need to be strictly competitive with a payoff functions represented by piecewise linear functions with real coefficients. Our conjecture is that every game with McNaughton payoff allows for finitely supported equilibrium strategies, however we leave proving/disproving of this conjecture for future investigations.     

The Arc‐Weighted Version of the Second Neighborhood Conjecture

Seymour conjectured that every oriented simple graph contains a vertex whose second neighborhood is at least as large as its first. Seymour's conjecture has been verified in several special cases, most notably for tournaments by Fisher  6 . One extension of the conjecture that has been used by several researchers is to consider vertex‐weighted digraphs. In this article we introduce a version of the conjecture for arc‐weighted digraphs. We prove the conjecture in the special case of arc‐weighted tournaments, strengthening Fisher's theorem. Our proof does not rely on Fisher's result, and thus can be seen as an alternate proof of said theorem.     

HOW RAPID SHOULD EMISSION REDUCTION BE? A GAME‐THEORETIC APPROACH

Abstract In this paper, we search for multistage realization of international environmental agreements. To analyze countries' incentives and the results of their interactions, we mathematically represent players' strategic preferences and apply a game‐theoretic approach to make predictions about their outcomes. The initial decision on emissions reduction is determined by the Stackelberg equilibrium concept. We generalize Barrett's static “emission” model to a dynamic framework and answer the question “how rapid should the emission reduction be?” It appears that sharper abatement is desirable in the early term, which is similar to the conclusion of the Stern review. Numerical example demonstrates that abatement dynamics of the coalition and the free‐rider differ when discounting of the future payoffs increases. We show that without incentives from external organizations or governments, such pollution reduction path can actually lead to a decline in the agreement's membership size.     

Two Game Models for Cooperation with Implicit Noncooperation

We propose two flexible game models to represent and analyze cases that cannot be modeled by current game models. One is called sharing creditability game (SCG) and the other is called bottomline game (BLG). The new models transform cooperative games into new games that incorporate auxiliary information (noncooperative in nature) usually neglected in previous theories. The new games will be solved only by traditional noncooperative game theory. When the new solutions are applied to the original games, the solutions can reflect the auxiliary information in addition to the original objectives of the decision makers or players. Generally, the new solutions are different from the cooperative and the noncooperative solutions of the original games. Existing transferable utility (TU) games and noncooperative games will coincide with special cases of the two new game models. Using SCG and BLG, the prisoner’s dilemma can be reformulated and a richer set of decisions can be considered for the players. The two new game models have potential applications in military and socioeconomic situations.This research was partly funded by the College Engineering, Ohio State University.     

Avoiding non-optimal management decisions by applying a three-person inspection game

An inspection game models a conflict situation between an inspector and an inspectee. The mathematical analysis aims to generate optimal behavior of the inspectee under the assumption that an undesirable action of the inspectee could otherwise be carried out strategically. In this paper the controller’s (inspector’s) particular job is to audit a manager’s (inspectee’s) decision and to submit a report to the company’s top managers for examination. Thus, a conflict as regards the choice of behavioral actions of the manager, the controller and the top management impends. Based on Fandel and Trockel (2011a) this modified inspection game is discussed here for the first time as a three-person game in the context of a manager’s faulty decision that will unnecessarily add to the company’s costs and that the top management understandably wishes to minimize. We will first examine the conditions under which a Nash equilibrium occurs in this three-person game in which poor management, poor monitoring and poor revision coincide. We will then examine the effects that the penalties and bonuses exert on the Nash equilibrium solution. We will find that penalties and bonuses can neutralize each other in their effects on the improved decision making by the manager and the controller.     

Meyniel's conjecture holds for random d‐regular graphs

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most . In a separate paper, we showed that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph. The result was obtained by showing that the conjecture holds for a general class of graphs with some specific expansion‐type properties. In this paper, this deterministic result is used to show that the conjecture holds asymptotically almost surely for random d‐regular graphs when d = d(n) ≥ 3.     

The switching game on unions of oriented matroids

In 1986, Hamidoune and Las Vergnas [3] introduced an oriented matroid version of the so-called Shannon’s switching game. They conjectured that the classification of the directed switching game on oriented matroids is identical to the classification of the non-oriented version. In this note, we support this conjecture by showing its validity for an infinite class of oriented matroids obtained as unions of rank-1 and/or rank-2 uniform oriented matroids.     

Characterizations ofk-Convex Games

The paper deals with the class of k-convex n-person transferable utility games which has clear affinities to the well-known class of convex n-person TU-games. Five new characterizations of a k-convex n-person game are presented in terms of the following key notions:(1) the unanimity coordinates, as determined by the algebraic representation of the game with respect to the particular basis consisting of all n-person unanimity games; (2) the second order partial derivatives of Owen's multilinear extension of the game; (3) the coremembership of the adjusted marginal worth vectors of the game (taking into account even or odd orderings of players); (4) a min-modular decomposition of an appropriately chosen cover-game (the decomposition of which is based on the adjusted marginal worth vectors of the initial game); (5) the concavity of the Lovász extension of the associated cover-game     

基于参与主体异质性条件下囚徒困境合作演化博弈模型研究

利用演化博弈理论,对参与主体异质性条件下的囚徒困境模型进行了探讨,求出了满足不同条件下的演化稳定策略,并对种群中个体异质性对演化稳定策略的影响进行了分析,得出种群中选择相同策略的个体异质性差异越大,参与个体选择合作行为作为演化稳定策略的可能性就越大.极端地,当个体的异质性趋向于无穷大时,合作成为唯一的演化稳定占优策略,为现实大多数合作系统中能保持长期的一种合作稳定状态提供了合理地解释.     

Saddle-point equilibrium sequence in one class of singular infinite horizon zero-sum linear-quadratic differential games with state delays

ABSTRACT

We consider an infinite horizon zero-sum linear-quadratic differential game with state delays in the dynamics. The cost functional of this game does not contain a control cost of the minimizing player (the minimizer), meaning that the considered game is singular. For this game, definitions of the saddle-point equilibrium and the game value are proposed. These saddle-point equilibrium and game value are obtained by a regularization of the singular game. Namely, we associate this game with a new differential game for the same equation of dynamics. The cost functional in the new game is the sum of the original cost functional and an infinite horizon integral of the square of the minimizer's control with a small positive weight coefficient. This new game is regular, and it is a cheap control game. An asymptotic analysis of this cheap control game is carried out. Using this asymptotic analysis, the existence of the saddle-point equilibrium and the value of the original game is established, and their expressions are derived. Illustrative example is presented.     

Fair reception and Vizing's conjecture

In this paper we introduce the concept of fair reception of a graph which is related to its domination number. We prove that all graphs G with a fair reception of size γ(G) satisfy Vizing's conjecture on the domination number of Cartesian product graphs, by which we extend the well‐known result of Barcalkin and German concerning decomposable graphs. Combining our concept with a result of Aharoni, Berger and Ziv, we obtain an alternative proof of the theorem of Aharoni and Szabó that chordal graphs satisfy Vizing's conjecture. A new infinite family of graphs that satisfy Vizing's conjecture is also presented. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 45‐54, 2009     

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.     

图的中间图2-pebbling性质和Graham猜想

本文研究了图的2-pebbling性质和Graham猜想.利用图的pebbling数的一些结果,我们研究了路和圈的中间图具有2-pebbling性质,从而也证明了路的中间图满足Graham猜想.     

Irreducible values of polynomials

Schinzel's Hypothesis H is a general conjecture in number theory on prime values of polynomials that generalizes, e.g., the twin prime conjecture and Dirichlet's theorem on primes in arithmetic progression. We prove a quantitative arithmetic analog of this conjecture for polynomial rings over pseudo algebraically closed fields. This implies results over large finite fields via model theory. A main tool in the proof is an irreducibility theorem à la Hilbert.