On an approach to constructing a characteristic function in cooperative differential games

We propose a novel approach to constructing characteristic functions in cooperative differential games. A characteristic function of a coalition S is computed in two stages: first, optimal control strategies maximizing the total payoff of the players are found, and next, these strategies are used by the players from the coalition S, while the other players, those from N S, use strategies minimizing the total payoff of the players from S. The characteristic function obtained in this way is superadditive. In addition, it possesses a number of other useful properties. As an example, we compute values of a characteristic function for a specific differential game of pollution control.     

The bounded core for games with restricted cooperation

A game with restricted (incomplete) cooperation is a triple (N, v, Ω), where N represents a finite set of players, Ω ? 2^N is a set of feasible coalitions such that N ∈ Ω, and v: Ω → R denotes a characteristic function. Unlike the classical TU games, the core of a game with restricted cooperation can be unbounded. Recently Grabisch and Sudhölter [9] proposed a new solution concept—the bounded core—that associates a game (N, v,Ω) with the union of all bounded faces of the core. The bounded core can be empty even if the core is nonempty. This paper gives two axiomatizations of the bounded core. The first axiomatization characterizes the bounded core for the class G^r of all games with restricted cooperation, whereas the second one for the subclass G_bc^r ? G^r of the games with nonempty bounded cores.     

On the real complexity of a complex DFT

We present a method to construct a theoretically fast algorithm for computing the discrete Fourier transform (DFT) of order N = 2 ⁿ . We show that the DFT of a complex vector of length N is performed with complexity of 3.76875N log₂ N real operations of addition, subtraction, and scalar multiplication.     

Polar Codes with Higher-Order Memory

We introduce a construction of a set of code sequences {C_n^(m) : n ≥ 1, m ≥ 1} with memory order m and code length N(n). {C_n^(m)} is a generalization of polar codes presented by Ar?kan in [1], where the encoder mapping with length N(n) is obtained recursively from the encoder mappings with lengths N(n ? 1) and N(n ? m), and {C_n^(m)} coincides with the original polar codes when m = 1. We show that {C_n^(m)} achieves the symmetric capacity I(W) of an arbitrary binary-input, discrete-output memoryless channel W for any fixed m. We also obtain an upper bound on the probability of block-decoding error P_e of {C_n^(m)} and show that \({P_e} = O({2^{ - {N^\beta }}})\) is achievable for β < 1/[1+m(? ? 1)], where ? ∈ (1, 2] is the largest real root of the polynomial F(m, ρ) = ρ^m ? ρ^{m ? 1} ? 1. The encoding and decoding complexities of {C_n^(m)} decrease with increasing m, which proves the existence of new polar coding schemes that have lower complexity than Ar?kan’s construction.     

Observational constraints on a hyperbolic potential in brane-world inflation

We focus on the large field of a hyperbolic potential form, which is characterized by a parameter f, in the framework of the brane-world inflation in Randall-Sundrum-II model. From the observed form of the power spectrum P _R (k), the parameter f should be of order 0.1m _p to 0.001m _p , the brane tension must be in the range λ ~ (1?10)×10⁵⁷ GeV⁴, and the energy scale is around V₀ ^1/4 ~ 10¹⁵ GeV. We find that the inflationary parameters (n _s , r, and dn _s /d(ln k) depend only on the number of e-folds N. The compatibility of these parameters with the last Planck measurements is realized with large values of N.     

Stochastic coalitional better-response dynamics and stable equilibrium

We consider coalition formation among players in an n-player finite strategic game over infinite horizon. At each time a randomly formed coalition makes a joint deviation from a current action profile such that at new action profile all the players from the coalition are strictly benefited. Such deviations define a coalitional better-response (CBR) dynamics that is in general stochastic. The CBR dynamics either converges to a K-stable equilibrium or becomes stuck in a closed cycle. We also assume that at each time a selected coalition makes mistake in deviation with small probability that add mutations (perturbations) into CBR dynamics. We prove that all K-stable equilibria and all action profiles from closed cycles, that have minimum stochastic potential, are stochastically stable. Similar statement holds for strict K-stable equilibrium. We apply the CBR dynamics to study the dynamic formation of the networks in the presence of mutations. Under the CBR dynamics all strongly stable networks and closed cycles of networks are stochastically stable.     

An efficient protocol for secure multicast key distribution in the presence of adaptive adversaries

In this paper, an efficient construction of multicast key distribution schemes based on semantically secure symmetric-key encryption schemes and cryptographically strong pseudo-random number generators is presented and analyzed. The proposed scheme is provably secure against adaptive adversaries leveraging the security amplification technique defined over the logical key hierarchy structures. Our protocol tolerates any coalition of revoked users; in particular, we do not assume any limit on the size or structure of the coalition. The proposed scheme is efficient as a performance of Join or Leave procedure requires 2 log(N) multicast activities defined over a sibling ancestor node set, 2 log(N) internal state updates of the underlying pseudo-random number generator and 2 log(N) symmetric-key encryption activities for N users in a session.     

A model of best choice under incomplete information

This paper suggests two approaches to the construction of a two-player game of best choice under incomplete information with the choice priority of one player and the equal weights of both players. We consider a sequence of independent identically distributed random variables (x _i , y _i ), i = 1..., n, which represent the quality of incoming objects. The first component is announced to the players and the second component is hidden. Each player chooses an object based on the information available. The winner is the player whose object has a greater sum of the quality components than the opponent’s object. We derive the optimal threshold strategies and compare them for both approaches.     

A Polynomial-Time Approximation Algorithm for One Problem Simulating the Search in a Time Series for the Largest Subsequence of Similar Elements

We analyze the mathematical aspects of the data analysis problem consisting in the search (selection) for a subset of similar elements in a group of objects. The problem arises, in particular, in connection with the analysis of data in the form of time series (discrete signals). One of the problems in modeling this challenge is considered, namely, the problem of searching in a finite sequence of points from the Euclidean space for the subsequence with the greatest number of terms such that the quadratic spread of the elements of this subsequence with respect to its unknown centroid does not exceed a given percentage of the quadratic spread of elements of the input sequence with respect to its centroid. It is shown that the problem is strongly NP-hard. A polynomial-time approximation algorithm is proposed. This algorithm either establishes that the problem has no solution or finds a 1/2-approximate solution if the length M^* of the optimal subsequence is even, or it yields a \(\frac{1}{2}\left(\begin{array}{c}1-\frac{1}{M^*}\\ \end{array}\right)\)-approximate solution if M* is odd. The time complexity of the algorithm is O(N³(N²+q)), where N is the number of points in the input sequence and q is the space dimension. The results of numerical simulation that demonstrate the effectiveness of the algorithm are presented.     

On the <Emphasis Type="Italic">k</Emphasis>-accessibility of cores of <Emphasis Type="Italic">TU</Emphasis>-cooperative games

This paper proposes a strengthening of the author’s core-accessibility theorem for balanced TU-cooperative games. The obtained strengthening relaxes the influence of the nontransitivity of classical domination αv on the quality of the sequential improvement of dominated imputations in a game v. More specifically, we establish the k-accessibility of the core C(α _v ) of any balanced TU-cooperative game v for all natural numbers k: for each dominated imputation x, there exists a converging sequence of imputations x₀, x₁,..., such that x₀ = x, lim x _r ∈ C(α _v ) and x_r?m is dominated by any successive imputation x _r with m ∈ [1, k] and r ≥ m. For showing that the TU-property is essential to provide the k-accessibility of the core, we give an example of an NTU-cooperative game G with a ”black hole” representing a nonempty closed subset B ? G(N) of dominated imputations that contains all the α _G -monotonic sequential improvement trajectories originating at any point x ∈ B.     

Cooperation in Games and Epistemic Readings of Independence-Friendly Sentences

In the literature on logics of imperfect information it is often stated, incorrectly, that the Game-Theoretical Semantics of Independence-Friendly (IF) quantifiers captures the idea that the players of semantical games are forced to make some moves without knowledge of the moves of other players. We survey here the alternative semantics for IF logic that have been suggested in order to enforce this “epistemic reading” of sentences. We introduce some new proposals, and a more general logical language which distinguishes between “independence from actions” and “independence from strategies”. New semantics for IF logic can be obtained by choosing embeddings of the set of IF sentences into this larger language. We compare all the semantics proposed and their purported game-theoretical justifications, and disprove a few claims that have been made in the literature.     

The formula of the solution for some classes of initial boundary value problems for the hyperbolic equation with two independent variables

A new representation is proved of the solutions of initial boundary value problems for the equation of the form u _xx (x, t) + r(x)u _x (x, t) ? q(x)u(x, t) = u _tt (x, t) + μ(x)u _t (x, t) in the section (under boundary conditions of the 1st, 2nd, or 3rd type in any combination). This representation has the form of the Riemann integral dependent on the x and t over the given section.     

A novel constant degree and constant congestion DHT scheme for peer-to-peer networks

1 Introduction and related work In recent years, peer-to-peer computing has attracted significant attention from both industry field and academic field[1-3]. The core component of many proposed peer-to- peer systems is the distributed hash table (DHT) schemes[4,5] that use a hash table-like interface to publish and look up data objects. Many proposed DHT schemes[6-15] are based on some traditional interconnection to- pology: Chord[6], Tapestry[7,8], Pastry[9] are based on hypercube topolog…     

The pursuit-evasion game on the 1-skeleton graph of a regular polyhedron. I

We consider a game between a group of n pursuers and one evader moving with the same maximum velocity along the 1-skeleton graph of a regular polyhedron. The goal of the paper is finding, for each regular polyhedron M, a number N(M) with the following properties: if n ≥ N(M), the group of pursuers wins, while if n < N(M), the evader wins. Part I of the paper is devoted to the case of polyhedra in ?³; Part II will be devoted to the case of ? ^d , d ≥ 5; and Part III, to the case of ?⁴.     

Interactive Restless Multi-armed Bandit Game and Swarm Intelligence Effect

We obtain the conditions for the emergence of the swarm intelligence effect in an interactive game of restless multi-armed bandit (rMAB). A player competes with multiple agents. Each bandit has a payoff that changes with a probability p _c per round. The agents and player choose one of three options: (1) Exploit (a good bandit), (2) Innovate (asocial learning for a good bandit among n _I randomly chosen bandits), and (3) Observe (social learning for a good bandit). Each agent has two parameters (c, p _obs ) to specify the decision: (i) c, the threshold value for Exploit, and (ii) p _obs , the probability for Observe in learning. The parameters (c, p _obs ) are uniformly distributed. We determine the optimal strategies for the player using complete knowledge about the rMAB. We show whether or not social or asocial learning is more optimal in the (p _c , n _I ) space and define the swarm intelligence effect. We conduct a laboratory experiment (67 subjects) and observe the swarm intelligence effect only if (p _c , n _I ) are chosen so that social learning is far more optimal than asocial learning.     

On Supersymmetric M-brane configurations with an R<Stack><Subscript>*</Subscript><Superscript>1,1</Superscript></Stack> /Z<Subscript>2</Subscript> submanifold

We obtain new examples of partly supersymmetric M-brane solutions defined on products of Ricci-flat manifolds, which contain a two-dimensional Lorentzian submanifold R _* ^1,1 /Z ₂ with one parallel spinor. The examples belong to the following configurations: M2, M5, M2 ∩M5 and M5 ∩M5. Among them, an M2 solution with N = 1/32 fractional number of preserved supersymmetries is presented.     

Mean field games based on stable-like processes

We investigate the mean field games of N agents based on the nonlinear stable-like processes. The main result of the paper is that any solution of the limiting mean field consistency equation generates a 1/N-Nash equilibrium for the approximating game of N agents.     

On the Smallest Size of an Almost Complete Subset of a Conic in PG(2, <Emphasis Type="Italic">q</Emphasis>) and Extendability of Reed–Solomon Codes

Abstract—In the projective plane PG(2, q), a subset S of a conic C is said to be almost complete if it can be extended to a larger arc in PG(2, q) only by the points of C \ S and by the nucleus of C when q is even. We obtain new upper bounds on the smallest size t(q) of an almost complete subset of a conic, in particular,

$$t(q) < \sqrt {q(3lnq + lnlnq + ln3)} + \sqrt {\frac{q}{{3\ln q}}} + 4 \sim \sqrt {3q\ln q} ,t(q) < 1.835\sqrt {q\ln q.} $$

The new bounds are used to extend the set of pairs (N, q) for which it is proved that every normal rational curve in the projective space PG(N, q) is a complete (q+1)-arc, or equivalently, that no [q+1,N+1, q?N+1]_q generalized doubly-extended Reed–Solomon code can be extended to a [q + 2,N + 1, q ? N + 2]_q maximum distance separable code.

     

Period analysis of the Logistic map for the finite field

Usually, the security of traditional cryptography which works on integer numbers and chaotic cryptosystem which works on real numbers is worthy of study. But the classical chaotic map over the real domain has a disadvantage that the calculation accuracy of the floating point number can be doubled when the map is implemented by computer. This is a serious drawback for practical application. The Logistic map is a classical chaotic system and it has been used as a chaotic cipher in the real number field. This inevitably leads to the degradation of finite precision under computer environment, and it is also very difficult to guarantee security. To solve these drawbacks, we extend the Logistic map to the finite field. In this paper, we consider the Logistic map for the finite field N = 3ⁿ, and analyze the period property of sequences generated by the Logistic map over Z_N. Moreover, we discuss the control parameters which may influence the behavior of the mapping, and show that the Logistic map over Z_N may be suitable for application by performance analysis. Ultimately, we find that there exists an automorphic map between two Logistic maps with the different control parameters, which makes them suitable for sequence generator in cryptosystem. The automorphic sequence generated algorithm based on the Logistic map over Z_N is designed and analyzed in detail. These sequences can be used in the pseudorandom number generator, the chaotic stream cipher, and the chaotic block cipher, etc.     

Expansion of Self-Similar Functions in the Faber–Schauder System

Let Ω = A^N be a space of right-sided infinite sequences drawn from a finite alphabet A = {0,1}, N = {1,2,…}. Let ρ(x, y)Σ_k=1^∞|x _k ? y _k |2^?k be a metric on Ω = AN, and μ the Bernoulli measure on Ω with probabilities p₀, p₁ > 0, p₀ + p₁ = 1. Denote by B(x,ω) an open ball of radius r centered at ω. The main result of this paper \(\mu (B(\omega ,r))r + \sum\nolimits_{n = 0}^\infty {\sum\nolimits_{j = 0}^{{2^n} - 1} {{\mu _{n,j}}} } (\omega )\tau ({2^n}r - j)\), where τ(x) = 2min {x,1 ? x}, 0 ≤ x ≤ 1, (τ(x) = 0, if x < 0 or x > 1 ), \({\mu _{n,j}}(\omega ) = (1 - {p_{{\omega _{n + 1}}}})\prod _{k = 1}^n{p_{{\omega _k}}} \oplus {j_k}\), \(j = {j_1}{2^{n - 1}} + {j_2}{2^{n - 2}} + ... + {j_n}\). The family of functions 1, x, τ(2 ⁿ r ? j), j = 0,1,…, 2 ⁿ ? 1, n = 0,1,…, is the Faber–Schauder system for the space C([0,1]) of continuous functions on [0, 1]. We also obtain the Faber–Schauder expansion for Lebesgue’s singular function, Cezaro curves, and Koch–Peano curves. Article is published in the author’s wording.