On extensions of Hoeffding’s inequality for panel data

Hoeffding’s inequality provides a probability bound for the deviation between the average of n independent bounded random variables and its mean. This paper introduces two inequalities that extend Hoeffding’s inequality to panel data, which consists of several mutually independent sequences of dependent data with strong mixing or with a dependence structure being even more general than strong mixing. One is denoted as the Bosq’s Extension which is an extension of Bosq’s inequality (Bosq, 1993) to panel data and the other one is called the Triplex Extension, which extends the Triplex inequality (Jiang, 2009) to panel data. The Bosq’s Extension provides a tighter upper probability bound, while the Triplex Extension is more relaxed in assumption allowing unboundedness and more general dependence than strong mixing. We also apply these two inequalities to establish the convergence rate of empirical risk minimization for high dimensional panel data with variable selection.     

Embedding processes in combinatorial game theory

Berlekamp asked the question “What is the habitat of ∗2?” (See Guy, 1996 [6].) It is possible to generalize the question and ask “For a game G, what is the largest n such that ∗n is a position of G?” This leads to the concept of the nim dimension. In Santos and Silva (2008) [8] a fractal process was proposed for analyzing the previous questions. For the same purpose, in Santos and Silva (2008) [9], an algebraic process was proposed. In this paper we implement a third idea related to embedding processes. With Alan Parr’s traffic lights, we exemplify the idea of estimating the “difficulty” of the game and proving that its nim dimension is infinite.     

Parental care as a differential game: A dynamic extension of the Houston–Davies game

An interpretation of the conflict between male and female parents during the process of caring for their common offspring by means of Game Theory was given in Houston and Davies. [A.I. Houston, N.B. Davies, The evolution of cooperation and life history in the dunnock Prunella modularis, in: R.M. Sibly, R.H. Smith (Eds.), Behavioral Ecology, Blackwell Scientific Publications, 1985, pp. 471–487]. Mathematically, this model represents a static game with continuous strategy sets. Recently, this model was reconsidered in a dynamic discrete time framework which also included state dependencies [J.M. McNamara et al., A dynamic game-theoretic model of parental care, J. Theor. Biol. 205 (2000) 605–623]. In this article, we give an interpretation of the parental care conflict in continuous time by means of a differential game with state dependent strategies.     

Evolutionary dynamics of the spatial Prisoner’s Dilemma with self-inhibition

In this paper we study the influence of interventions on self-interactions in a spatial Prisoner’s Dilemma on a two-dimensional grid with periodic boundary conditions and synchronous updating of the dynamics. We investigate two different types of self-interaction modifications. The first type (FSIP) is deterministic, effecting each self-interaction of a player by a constant factor, whereas the second type (PSIP) performs a probabilistic interventions. Both types of interventions lead to a reduction of the payoff of the players and, hence, represent inhibiting effects. We find that a constant but moderate reduction of self-interactions has a very beneficial effect on the evolution of cooperators in the population, whereas probabilistic interventions on self-interactions are in general counter productive for the coexistence of the two different strategies.     

Generalized knight’s tour on 3D chessboards

In [G.L. Chia, Siew-Hui Ong, Generalized knight’s tours on rectangular chessboards, Discrete Applied Mathematics 150 (2005) 80-98], Chia and Ong proposed the notion of the generalized knight’s tour problem (GKTP). In this paper, we address the 3D GKTP, that is, the GKTP on 3D chessboards of size L×M×N, where L≤M≤N. We begin by presenting several sufficient conditions for a 3D chessboard not to admit a closed or open generalized knight’s tour (GKT) with given move patterns. Then, we turn our attention to the 3D GKTP with (1, 2, 2) move. First, we show that a chessboard of size L×M×N does not have a closed GKT if either (a) L≤2 or L=4, or (b) L=3 and M≤7. Then, we constructively prove that a chessboard of size 3×4s×4t with s≥2and t≥2 must contain a closed GKT.     

Sufficient conditions for optimality of threat strategies in a differential game

The problem of defining threat strategies in nonzero-sum games is considered, and a definition of optimal threat strategies is proposed in the static case. This definition is then extended to differential games, and sufficient conditions for optimality of threat strategies are derived. These are then applied to a simple example. The definition proposed here is then compared with the definition of threat strategies given by Nash.     

Graham’s pebbling conjecture on product of thorn graphs of complete graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p₁,p₂,…,p_n be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p₁,p₂,…,p_n, is obtained by attaching p_i new vertices of degree 1 to the vertex u_i of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every .     

Devaney’s chaos implies distributional chaos in a sequence

Let X be a complete metric space without isolated points, and let f:X→X be a continuous map. In this paper we prove that if f is transitive and has a periodic point of period p, then f is distributionally chaotic in a sequence. Particularly, chaos in the sense of Devaney is stronger than distributional chaos in a sequence.     

Set-valued cooperative games with fuzzy payoffs. The fuzzy assignment game

In this paper we study cooperative games with fuzzy payoffs. The main advantage of the approach presented is the incorporation into the analysis of the problem of ambiguity inherent in many real-world collective decision situations. We propose extensions of core concepts which maintain the fuzzy nature of allocations, and lead to a more satisfactory study of the problem within the fuzzy context. Finally, we illustrate the extended core concepts and the approach to obtain the corresponding allocations through the analysis of assignment games with uncertain profits.     

Properties of game options

A game option is an American option with the added feature that not only the option holder, but also the option writer, can exercise the option at any time. We characterize the value of a perpetual game option in terms of excessive functions, and we use the connection between excessive functions and concave functions to explicitly determine the value in some examples. Moreover, a condition on the two contract functions is provided under which the value is convex in the underlying diffusion value in the continuation region and increasing in the diffusion coefficient.Mathematics Subject Classification (2000) Primary 91A15, Secondary 60G40, 91B28     

Sharing costs in highways: A game theoretic approach

This paper introduces a new class of games, highway games, which arise from situations where there is a common resource that agents will jointly use. That resource is an ordered set of several indivisible sections, where each section has an associated fixed cost and each agent requires some consecutive sections. We present an easy formula to calculate the Shapley value, and we present an efficient procedure to calculate the nucleolus for this class of games.     

A combinatorial proof of the Dense Hindman’s Theorem

The Dense Hindman’s Theorem states that, in any finite coloring of the natural numbers, one may find a single color and a “dense” set B₁, for each b₁∈B₁ a “dense” set (depending on b₁), for each a “dense” set (depending on b₁,b₂), and so on, such that for any such sequence of b_i, all finite sums belong to the chosen color. (Here density is often taken to be “piecewise syndetic”, but the proof is unchanged for any notion of density satisfying certain properties.) This theorem is an example of a combinatorial statement for which the only known proof requires the use of ultrafilters or a similar infinitary formalism. Here we give a direct combinatorial proof of the theorem.     

Generalized genus sequences for misère octal games

Two approaches have been used to solve impartial games with misère play; genus theory, which has resulted in a number of results summarized in [2], and Sibert-Conway decomposition [9], which has been used to solve the octal game 0.77 (known as Kayles). The main aim of this paper is to publish (for the first time) the results archived in [1], extending genus theory beyond the applications to which it has previously been applied. In addition, we extend a result from [6] to misère play by adapting it to use the extended genus theory. The resulting theorems require extensive calculations to verify that their preconditions hold for any particular games. These calculations have been carried out by computer for all two-digit octal games. For many of these games, this has resulted in complete solutions. Complete solutions are presented for four games listed in [8] as unsolved. Received: September 2001     

A cooperative location game based on the 1-center location problem

In this paper we introduce and analyze new classes of cooperative games related to facility location models defined on general metric spaces. The players are the customers (demand points) in the location problem and the characteristic value of a coalition is the cost of serving its members. Specifically, the cost in our games is the service radius of the coalition. We call these games the Minimum Radius Location Games (MRLG).We study the existence of core allocations and the existence of polynomial representations of the cores of these games, focusing on network spaces, i.e., finite metric spaces induced by undirected graphs and positive edge lengths, and on the ?_p metric spaces defined over R^d.     

A differential game with two pursuers and one evader

This paper is concerned with a coplanar pursuit-evasion problem in which a faster evaderE with constant speedw>1 must pass between two pursuersP ₁,P ₂ having unit speed, the payoff being the distance of closest approach to either one of the pursuers. The control variables are the directions of the velocities ofP ₁,P ₂, andE. The path equations are integrated, and a closed-form solution is obtained in terms of elliptic functions of the first and second kind. A closed-loop solution is given graphically in several diagrams, for different values ofw.     

An extension of Rosenthal’s inequality

An extension of Rosenthal’s inequality is established.