A general characterization of the mean field limit for stochastic differential games

The mean field limit of large-population symmetric stochastic differential games is derived in a general setting, with and without common noise, on a finite time horizon. Minimal assumptions are imposed on equilibrium strategies, which may be asymmetric and based on full information. It is shown that approximate Nash equilibria in the n-player games admit certain weak limits as n tends to infinity, and every limit is a weak solution of the mean field game (MFG). Conversely, every weak MFG solution can be obtained as the limit of a sequence of approximate Nash equilibria in the n-player games. Thus, the MFG precisely characterizes the possible limiting equilibrium behavior of the n-player games. Even in the setting without common noise, the empirical state distributions may admit stochastic limits which cannot be described by the usual notion of MFG solution.     

Linear information for approximation of the Itô integrals

We study optimal approximation of stochastic integrals in the Itô sense when linear information, consisting of certain integrals of trajectories of Brownian motion, is available. Upper bounds on the nth minimal error, where n is the fixed cardinality of information, are obtained by the Wagner–Platen algorithm and are O(n ^???3/2) or O(n ^???2), depending on considered class of integrands. We also show that Ω(n ^???2) is a lower bound which holds even for very smooth integrands.     

The construction of infinite families of any κ-tight optimal and singular κ-tight optimal directed double loop networks

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. It is an important topological structure of computer interconnection networks and has been widely used in the designing of local area networks and distributed systems. Given the number n of nodes, how to construct a DLN which has minimum diameter? This problem has attracted great attention. A related and longtime unsolved problem is for any given non-negative integer k, is there an infinite family of k-tight optimal DLN? In this paper, two main results are obtained (1) for any k ≥ 0, the infinite families of k-tight optimal DLN can be constructed, where the number n(k,e,c) of their nodes is a polynomial of degree 2 in e with integral coefficients containing a parameter c. (2) for any k ≥ 0,an infinite family of singular k-tight optimal DLN can be constructed.     

Fast heuristics for protection networks for dynamic routing

Traffic volatility and network reliability are important issues in the provision of high speed network services. We consider the construction of a second network, the protection network which can carry overload traffic due to the failure or congestion of any two links in the original network. The level of protection against such contingencies can be specified by a traffic requirement matrix. We construct a fully connected protection network, for an n node network, using an O(n²) heuristic based on the largest two traffic requirements for each node. This procedure is then modified to generate a more effective O(n⁴) heuristic, both methods facilitate fast processing for two-hop dynamic routing. We compare the performance of the heuristics with the O(n¹⁵) optimal solution.     

Probabilistic stable rules and Nash equilibrium in two-sided matching problems

We study many-to-many matching with substitutable and cardinally monotonic preferences. We analyze stochastic dominance (sd) Nash equilibria of the game induced by any probabilistic stable matching rule. We show that a unique match is obtained as the outcome of each sd-Nash equilibrium. Furthermore, individual-rationality with respect to the true preferences is a necessary and sufficient condition for an equilibrium outcome. In the many-to-one framework, the outcome of each equilibrium in which firms behave truthfully is stable for the true preferences. In the many-to-many framework, we identify an equilibrium in which firms behave truthfully and yet the equilibrium outcome is not stable for the true preferences. However, each stable match for the true preferences can be achieved as the outcome of such equilibrium.     

The complexity of depth-two information networks

The lower bound Ω(n log₂ n) for the complexity of an arbitrary depth-two information network with n inputs and n outputs is proved providing the inputs are independent, the outputs are independent, and the total information of any input and any output is n times less than the entropy of any input or output. A similar estimate for Boolean depth-two circuits of functional elements is obtained as a corollary.     

On the minimum size of binary codes with length 2<Emphasis Type="Italic">R</Emphasis> + 4 and covering radius <Emphasis Type="Italic">R</Emphasis>

The minimum size of a binary code with length n and covering radius R is denoted by K(n, R). For arbitrary R, the value of K(n, R) is known when n ≤  2R +  3, and the corresponding optimal codes have been classified up to equivalence. By combining combinatorial and computational methods, several results for the first open case, K(2R +  4, R), are here obtained, including a proof that K(10, 3) =  12 with 11481 inequivalent optimal codes and a proof that if K(2R +  4, R) <  12 for some R then this inequality cannot be established by the existence of a corresponding self-complementary code.     

A boundary Schwarz lemma on the classical domain of type <Emphasis Type="Italic">I</Emphasis>

Let R _I (m, n) be the classical domain of type I in ? ^m×n with 1 ≤ m ≤ n. We obtain the optimal estimates of the eigenvalues of the Fréchet derivative Df(\(\mathop Z\limits^ \circ \)) at a smooth boundary fixed point \(\mathop Z\limits^ \circ \)of R _I (m, n) for a holomorphic self-mapping f of R _I (m, n). We provide a necessary and sufficient condition such that the boundary points of R _I (m, n) are smooth, and give some properties of the smooth boundary points of R _I (m, n). Our results extend the classical Schwarz lemma at the boundary of the unit disk Δ to R _I (m, n), which may be applied to get some optimal estimates in several complex variables.     

Estimation Problems for Periodically Correlated Isotropic Random Fields

Spectral theory of isotropic random fields in Euclidean space developed by M. I. Yadrenko is exploited to find a solution to the problem of optimal linear estimation of the functional

$$ A\zeta ={\sum\limits_{t=0}^{\infty}}\,\,\,{\int_{S_n}} \,\,a(t,x)\zeta (t,x)\,m_n(dx) $$

which depends on unknown values of a periodically correlated (cyclostationary with period T) with respect to time isotropic on the sphere S _n in Euclidean space E ⁿ random field ζ(t, x), t?∈?Z, x?∈?S _n . Estimates are based on observations of the field ζ(t, x)?+?θ(t, x) at points (t, x), t?=???1,???2, ..., x?∈?S _n , where θ(t, x) is an uncorrelated with ζ(t, x) periodically correlated with respect to time isotropic on the sphere S _n random field. Formulas for computing the value of the mean-square error and the spectral characteristic of the optimal linear estimate of the functional Aζ are obtained. The least favourable spectral densities and the minimax (robust) spectral characteristics of the optimal estimates of the functional Aζ are determined for some special classes of spectral densities.

     

Multi-period empty container repositioning with stochastic demand and lost sales

This paper considers repositioning empty containers between multi-ports over multi-periods with stochastic demand and lost sales. The objective is to minimize the total operating cost including container-holding cost, stockout cost, importing cost and exporting cost. First, we formulate the single-port case as an inventory problem over a finite horizon with stochastic import and export of empty containers. The optimal policy for period n is characterized by a pair of critical points (A _n , S _n ), that is, importing empty containers up to A _n when the number of empty containers in the port is fewer than A _n ; exporting empty containers down to S _n when the number of empty containers in the port is more than S _n ; and doing nothing, otherwise. A polynomial-time algorithm is developed to determine the two thresholds, that is, A _n and S _n , for each period. Next, we formulate the multi-port problem and determine a tight lower bound on the cost function. On the basis of the two-threshold optimal policy for a single port, a polynomial-time algorithm is developed to find an approximate repositioning policy for multi-ports. Simulation results show that the proposed approximate repositioning algorithm performs very effectively and efficiently.     

An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d?1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.     

Combinatorial constructions of optimal (<Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">n</Emphasis>, 4, 2) optical orthogonal signature pattern codes

Optical orthogonal signature pattern codes (OOSPCs) play an important role in a novel type of optical code division multiple access (OCDMA) network for 2-dimensional image transmission. There is a one-to-one correspondence between an \((m, n, w, \lambda )\)-OOSPC and a \((\lambda +1)\)-(mn, w, 1) packing design admitting a point-regular automorphism group isomorphic to \({\mathbb {Z}}_m\times {\mathbb {Z}}_n\). In 2010, Sawa gave the first infinite class of (m, n, 4, 2)-OOSPCs by using S-cyclic Steiner quadruple systems. In this paper, we use various combinatorial designs such as strictly \({\mathbb {Z}}_m\times {\mathbb {Z}}_n\)-invariant s-fan designs, strictly \({\mathbb {Z}}_m\times {\mathbb {Z}}_n\)-invariant G-designs and rotational Steiner quadruple systems to present some constructions for (m, n, 4, 2)-OOSPCs. As a consequence, our new constructions yield more infinite families of optimal (m, n, 4, 2)-OOSPCs. Especially, we see that in some cases an optimal (m, n, 4, 2)-OOSPC can not achieve the Johnson bound. We also use Witt’s inversive planes to obtain optimal \((p, p, p+1, 2)\)-OOSPCs for all primes \(p\ge 3\).     

The Transient Behaviour of a Cyclic Queue

This paper studies a cyclic queueing problem arising in civil engineering earthmoving projects. There are m excavators and n trucks which queue to be loaded by the excavators. The problem is therefore equivalent to a machine interference problem with m operators and n machines. The size of the haul fleet must be optimized, so as to minimize the cost per unit volume of earth moved. Graphs which show regions of optimal n in the parameter space are presented for the steady-state D/D/1, M/D/1 and E _k /M/1 models. The effect of operating the M/M/m system in short work shifts, so that the initial conditions and transient behaviour are important, is then analysed and quantified as a correction to the optimal number of trucks in the haul fleet from the steady-state solution.     

On the optimal robust solution of IVPs with noisy information

We investigate the optimal solution of systems of initial-value problems with smooth right-hand side functions f from a Hölder class \(F^{r,\varrho }_{\text {reg}}\), where r ≥ 0 is the number of continuous derivatives of f, and ? ∈ (0, 1] is the Hölder exponent of rth partial derivatives. We consider algorithms that use n evaluations of f, the ith evaluation being corrupted by a noise δ_i of deterministic or random nature. For δ ≥ 0, in the deterministic case the noise δ_i is a bounded vector, ∥δ_i∥≤δ. In the random case, it is a vector-valued random variable bounded in average, (E(∥δ_i∥^q))^1/q ≤ δ, q ∈ [1, + ∞). We point out an algorithm whose L_p error (p ∈ [0, + ∞]) is O(n ^{? (r + ?)} + δ), independently of the noise distribution. We observe that the level n ^{? (r + ?)} + δ cannot be improved in a class of information evaluations and algorithms. For ε > 0, and a certain model of δ-dependent cost, we establish optimal values of n(ε) and δ(ε) that should be used in order to get the error at most ε with minimal cost.     

Adaptive age replacement strategies based on nonparametric predictive inference

We consider an age replacement problem using nonparametric predictive inference (NPI) for the lifetime of a future unit. Based on n observed failure times, NPI provides lower and upper bounds for the survival function for a future lifetime X_n+1, which are lower and upper survival functions in the theory of interval probability, and which lead to upper and lower cost functions, respectively, for age replacement based on the renewal reward theorem. Optimal age replacement times for X_n+1 follow by minimizing these cost functions. Although the renewal reward theorem implicitly assumes that the corresponding optimal strategy will be used for a long period, we study the effect on this strategy when the observed value for X_n+1, which is either an observed failure time or a right-censored observation, becomes available. This is possible due to the fully adaptive nature of our nonparametric approach, and the next optimal strategy will be for X_n+2. We compare the optimal strategies for X_n+1 and X_n+2 both analytically and via simulation studies. Our NPI-based approach is fully adaptive to the data, to which it adds only few structural assumptions. We discuss the possible use of this approach, and indeed the wider importance of the conclusions of this study to situations where one wishes to combine the statistical aspects of estimating a lifetime distribution with the more traditional operational research approach of determining optimal replacement strategies for lifetime distributions that are assumed to be known.     

On collineation groups of finite projective spaces containing a Singer cycle

By a result of Kantor, any subgroup of GL(n, q) containing a Singer cycle normalizes a field extension subgroup. This result has as a consequence a projective analogue, and this paper gives the details of this deduction, showing that any subgroup of PΓL(n, q) containing a projective Singer cycle normalizes the image of a field extension subgroup GL(n/s, q^s) under the canonical homomorphism GL(n, q) → PGL(n, q), for some divisor s of n, and so is contained in the image of ΓL(n/s, q^s) under the canonical homomorphism ΓL(n, q) → PΓL(n, q). The actions of field extension subgroups on V (n, q) are also investigated. In particular, we prove that any field extension subgroup GL(n/s, q^s) of GL(n, q) has a unique orbit on s-dimensional subspaces of V (n, q) of length coprime to q. This orbit is a Desarguesian s-partition of V (n, q).     

An Optimal Algorithm for the <Emphasis Type="Italic">k</Emphasis>-Fixed-Endpoint Path Cover on Proper Interval Graphs

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.     

On Nash and Carlson’s Inequalities for Symmetric <Emphasis Type="Italic">q</Emphasis>-Integral Transforms

The aim of this paper is to prove an \(\mathcal {L}_q^1 \cap \mathcal {L}_q^2\) versions of Nash and Carlson’s inequalities for a class of q-integral operator \(\mathcal {T}_q\) with a bounded kernel. As applications, we give q-analogues of Nash and Carlson’s inequalities for the q-Fourier-cosine, q-Fourier-sine, q-Dunkl and q-Bessel Fourier transforms.     

Optimal Embeddings of Bessel-Potential-Type Spaces into Generalized Hölder Spaces Involving <Emphasis Type="Italic">k</Emphasis>-Modulus of Smoothness

We establish necessary and sufficient conditions for embeddings of Bessel potential spaces H ^σ X(IR ⁿ ) with order of smoothness σ?∈?(0, n), modelled upon rearrangement invariant Banach function spaces X(IR ⁿ ), into generalized Hölder spaces (involving k-modulus of smoothness). We apply our results to the case when X(IR ⁿ ) is the Lorentz-Karamata space \(L_{p,q;b}({{\rm I\kern-.17em R}}^n)\). In particular, we are able to characterize optimal embeddings of Bessel potential spaces \(H^{\sigma}L_{p,q;b}({{\rm I\kern-.17em R}}^n)\) into generalized Hölder spaces. Applications cover both superlimiting and limiting cases. We also show that our results yield new and sharp embeddings of Sobolev-Orlicz spaces W ^k?+?1 L ^n/k(logL) ^α (IR ⁿ ) and W ^k L ^n/k(logL) ^α (IR ⁿ ) into generalized Hölder spaces.     

Lower bounds for the largest eigenvalue of the gcd matrix on {1, 2,..., n}

Consider the n×n matrix with (i, j)’th entry gcd (i, j). Its largest eigenvalue λ_n and sum of entries s_n satisfy λ_n > s_n/n. Because s_n cannot be expressed algebraically as a function of n, we underestimate it in several ways. In examples, we compare the bounds so obtained with one another and with a bound from S.Hong, R.Loewy (2004). We also conjecture that λ_n > 6π^?2nlogn for all n. If n is large enough, this follows from F.Balatoni (1969).