Instantaneous self-fulfilling of long-term prophecies on the probabilistic distribution of financial asset values

Our goal here is to present various examples of situations where a “large” investor (i.e. an investor whose “size” challenges the liquidity or the depth of the market) sees his long-term guesses on some important financial parameters instantaneously confirmed by the market dynamics as a consequence of his trading strategy, itself based upon his guesses. These examples are worked out in the context of a model (i.e. a quantitative framework) which attempts to provide a rigorous basis for the qualitative intuitions of many practitioners. Our results may be viewed as some kind of reverse Black–Scholes paradigm where modifications of option prices affect today's real volatility.     

A note on “Euclidean algorithms are Gaussian” by V. Baladi and B. Vallée

The paper “Euclidean algorithms are Gaussian” [V. Baladi, B. Vallée, Euclidean algorithm are Gaussian, J. Number Theory 110 (2005) 331-386], is devoted to the distributional analysis of three variants of Euclidean algorithms. The Central Limit Theorem and the Local Limit Theorem obtained there are the first ones in the context of the “dynamical analysis” method. The techniques developed have been applied in further various works (e.g. [V. Baladi, A. Hachemi, A local limit theorem with speed of convergence for Euclidean algorithms and Diophantine costs, Ann. Inst. H. Poincaré Probab. Statist. 44 (2008) 749-770; E. Cesaratto, J. Clément, B. Daireaux, L. Lhote, V. Maume, B. Vallée, Analysis of fast versions of the Euclid algorithm, in: Proceedings of Third Workshop on Analytic Algorithmics and Combinatorics, ANALCO'08, SIAM, 2008; E. Cesaratto, A. Plagne, B. Vallée, On the non-randomness of modular arithmetic progressions, in: Fourth Colloquium on Mathematics and Computer Science. Algorithms, Trees, Combinatorics and Probabilities, in: Discrete Math. Theor. Comput. Sci. Proc., vol. AG, 2006, pp. 271-288]). These theorems are proved first for an auxiliary probabilistic model, called “the smoothed model,” and after, the estimates are transferred to the “true” probabilistic model. In this note, we remark that “the smoothed model” described in [V. Baladi, B. Vallée, Euclidean algorithm are Gaussian, J. Number Theory 110 (2005) 331-386] is not adapted to this transfer and replaces it by an adapted one. However, the results remain unchanged.     

Conservative allocation models for outbound containers in container terminals

This paper examines location assignment for outbound containers in container terminals. It is an extension to the previous modeling work of Kim et al. (2000) and Zhang et al. (2010). The previous model was an “optimistic” handling way and gave a moderate punishment for placing a lighter container onto the top of a stack already loaded with heavier containers. Considering that the original model neglected the stack height and the state-changing magnitude information when interpreting the punishment parameter and hid too much information about the specific configurations for a given stack representation, we propose two new “conservative” allocation models in this paper. One considers the stack height and the state-changing magnitude information by reinterpreting the punishment parameter and the other further considers the specific configurations for a given stack representation. Solution qualities for the “optimistic” and the two “conservative” allocation models are compared on two performance indicators. The numerical experiments indicate that both the first and second “conservative” allocation models outperform the original model in terms of the two performance indicators. In addition, to overcome computational difficulties encountered by the dynamic programming algorithm for large-scale problems, an approximate dynamic programming algorithm is presented as well.     

Error analysis of efficient evaluation algorithms for tensor product surfaces

Backward stability of the Casteljau algorithm and two more efficient algorithms for polynomial tensor product surfaces with interest in CAGD is shown. The conditioning of the corresponding bases are compared. These algorithms are also compared with the corresponding Horner algorithm and their higher accuracy is shown. A running error analysis of the algorithms is also carried out providing algorithms which calculate “a posteriori” sharp error bounds simultaneously to the evaluation of the surface without increasing significantly the computational cost.     

Heterogeneous information lags and evolutionary stability

We investigate the effect of information lags in discrete time evolutionary game dynamics on symmetric games. At the end of each period, some players obtain information about the distribution of strategies among the entire population. They update their strategies according to this information. In contrast to the previous literature (e.g., Tao and Wang (1997)) where large delays lead to instability, we show that the relationship between information lags and the stability of equilibria is not “monotonic.” In anti-coordination games under smoothed best-response dynamics, a small probability of delay can stabilize the equilibrium, while a large probability can destabilize it.     

On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids

Given A?{a¹,…,a^m}⊂R^d whose affine hull is R^d, we study the problems of computing an approximate rounding of the convex hull of A and an approximation to the minimum-volume enclosing ellipsoid of A. In the case of centrally symmetric sets, we first establish that Khachiyan's barycentric coordinate descent (BCD) method is exactly the polar of the deepest cut ellipsoid method using two-sided symmetric cuts. This observation gives further insight into the efficient implementation of the BCD method. We then propose a variant algorithm which computes an approximate rounding of the convex hull of A, and which can also be used to compute an approximation to the minimum-volume enclosing ellipsoid of A. Our algorithm is a modification of the algorithm of Kumar and Y?ld?r?m, which combines Khachiyan's BCD method with a simple initialization scheme to achieve a slightly improved polynomial complexity result, and which returns a small “core set.” We establish that our algorithm computes an approximate solution to the dual optimization formulation of the minimum-volume enclosing ellipsoid problem that satisfies a more complete set of approximate optimality conditions than either of the two previous algorithms. Furthermore, this added benefit is achieved without any increase in the improved asymptotic complexity bound of the algorithm of Kumar and Y?ld?r?m or any increase in the bound on the size of the computed core set. In addition, the “dropping idea” used in our algorithm has the potential of computing smaller core sets in practice. We also discuss several possible variants of this dropping technique.     

Directed and weighted majority games

In this paper we deal with several classes of simple games; the first class is the one of ordered simple games (i.e. they admit of a complete desirability relation). The second class consists of all zero-sum games in the first one.First of all we introduce a natural partial order on both classes respectively and prove that this order relation admits a rank function. Also the first class turns out to be a rank symmetric lattice. These order relations induce fast algorithms to generate both classes of ordered games.Next we focus on the class of weighted majority games withn persons, which can be mapped onto the class of weighted majority zero-sum games withn+1 persons.To this end, we use in addition methods of linear programming, styling them for the special structure of ordered games. Thus, finally, we obtain algorithms, by combiningLP-methods and the partial order relation structure. These fast algorithms serve to test any ordered game for the weighted majority property. They provide a (frequently minimal) representation in case the answer to the test is affirmative.     

Resource-saving infinite-horizon tracking under uncertain input

A feedback controller for approximate tracking a prescribed trajectory of an inaccurately observed dynamical system effected by uncertain non-observable input disturbances over an infinite time interval is constructed. The controller is “resource-saving” in a sense that control resources spent for approximate tracking do not exceed (with some small gaps) those needed for exact tracking in an “ideal” situation where the current values of the input disturbance are fully observable.     

Particle swarm with equilibrium strategy of selection for multi-objective optimization

A new ranking scheme based on equilibrium strategy of selection is proposed for multi-objective particle swarm optimization (MOPSO), and the preference ordering is used to identify the “best compromise” in the ranking stage. This scheme increases the selective pressure, especially when the number of objectives is very large. The proposed algorithm has been compared with other multi-objective evolutionary algorithms (MOEAs). The experimental results indicate that our algorithm produces better convergence performance.     

On the dynamic programming principle for uniformly nondegenerate stochastic differential games in domains

We prove the dynamic programming principle for uniformly nondegenerate stochastic differential games in the framework of time-homogeneous diffusion processes considered up to the first exit time from a domain. The zeroth-order “coefficient” and the “free” term are only assumed to be measurable. In contrast with previous results established for constant stopping times we allow arbitrary stopping times and randomized ones as well. The main assumption, which will be removed in a subsequent article, is that there exists a sufficiently regular solution of the Isaacs equation.     

AIR Tools — A MATLAB package of algebraic iterative reconstruction methods

We present a MATLAB package with implementations of several algebraic iterative reconstruction methods for discretizations of inverse problems. These so-called row action methods rely on semi-convergence for achieving the necessary regularization of the problem. Two classes of methods are implemented: Algebraic Reconstruction Techniques (ART) and Simultaneous Iterative Reconstruction Techniques (SIRT). In addition we provide a few simplified test problems from medical and seismic tomography. For each iterative method, a number of strategies are available for choosing the relaxation parameter and the stopping rule. The relaxation parameter can be fixed, or chosen adaptively in each iteration; in the former case we provide a new “training” algorithm that finds the optimal parameter for a given test problem. The stopping rules provided are the discrepancy principle, the monotone error rule, and the NCP criterion; for the first two methods “training” can be used to find the optimal discrepancy parameter.     

Simultaneous modelling of the Cholesky decomposition of several covariance matrices

A method for simultaneous modelling of the Cholesky decomposition of several covariance matrices is presented. We highlight the conceptual and computational advantages of the unconstrained parameterization of the Cholesky decomposition and compare the results with those obtained using the classical spectral (eigenvalue) and variance-correlation decompositions. All these methods amount to decomposing complicated covariance matrices into “dependence” and “variance” components, and then modelling them virtually separately using regression techniques. The entries of the “dependence” component of the Cholesky decomposition have the unique advantage of being unconstrained so that further reduction of the dimension of its parameter space is fairly simple. Normal theory maximum likelihood estimates for complete and incomplete data are presented using iterative methods such as the EM (Expectation-Maximization) algorithm and their improvements. These procedures are illustrated using a dataset from a growth hormone longitudinal clinical trial.     

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.     

Computation of the invariant measure for a Lévy driven SDE: Rate of convergence

We study the rate of convergence of some recursive procedures based on some “exact” or “approximate” Euler schemes which converge to the invariant measure of an ergodic SDE driven by a Lévy process. The main interest of this work is to compare the rates induced by “exact” and “approximate” Euler schemes. In our main result, we show that replacing the small jumps by a Brownian component in the approximate case preserves the rate induced by the exact Euler scheme for a large class of Lévy processes.     

Modified algorithms for the minimum volume enclosing axis-aligned ellipsoid problem

Consider the problem of computing a (1+?)-approximation to the minimum volume axis-aligned ellipsoid (MVAE) enclosing a set of m points in Rⁿ. We first provide an extension and improvement to algorithm proposed in Kumar and Y?ld?r?m (2008) [5] (the KY algorithm) for the MVAE problem. The main challenge of the MVAE problem is that there is no closed form solution in the line search step (beta). Therefore, the KY algorithm proposed a certain choice of beta that leads to their complexity and core set results in solving the MVAE problem. We further analyze the line search step to derive a new beta, relying on an analysis of up to the fourth order derivative. This choice of beta leads to the improved complexity and core set results. The second modification is given by incorporating “away steps” into the first one at each iteration, which obtains the same complexity and core set results as the first one. In addition, since the second modification uses the idea of “dropping points”, it has the potential to compute smaller core sets in practice. Some numerical results are given to show the efficiency of the modified algorithms.     

Time-marching algorithms for initial-boundary value problems based upon “approximate approximations”

New time marching algorithms for solving initial-boundary value problems for semi-linear parabolic and hyperbolic equations are described. With respect to the space variable the discretization is based upon a method of approximate approximation proposed by the second author. We use approximate approximations of the fourth order. In time the algorithms are finite-difference schemes of either first or second approximation order. At each time step the approximate solution is represented by an explicit analytic formula. The algorithms are stable under mild restrictions to the time step which come from the non-linear part of the equation. Some computational results and hints on crucial implementation issues are provided.Supported by the Center for Applied and Industrial Mathematics, Department of Mathematics, Linköping University, Sweden.     

“Cautious” utility maximization and iterated weak dominance

This paper examines the implications of assuming that rational players in a two-player noncooperative game maximize expected utility using cautious beliefs; i.e., beliefs that give positive probability to all rational strategies of the other players. The result is a solution concept that captures some of the flavor of but is not equivalent to the iterated elimination of weakly dominated strategies. The solution concept yields attractive results for some games, but suffers from nonexistence problems in other games. We interpret the nonexistence problems as showing that it is logically inconsistent to assume that rational players analyze all games on the basis of cautious expected utility maximization.We would like to thank Pierpaolo Battigalli, two anonymous referees, and an editor for helpful comments. Tilman Börgers gratefully acknowledges financial assistance from the Schweizerischer Nationalfonds.     

A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games

We suggest the first strongly subexponential and purely combinatorial algorithm for solving the mean payoff games problem. It is based on iteratively improving the longest shortest distances to a sink in a possibly cyclic directed graph.We identify a new “controlled” version of the shortest paths problem. By selecting exactly one outgoing edge in each of the controlled vertices we want to make the shortest distances from all vertices to the unique sink as long as possible. The decision version of the problem (whether the shortest distance from a given vertex can be made bigger than a given bound?) belongs to the complexity class NP∩CONP. Mean payoff games are easily reducible to this problem. We suggest an algorithm for computing longest shortest paths. Player MAX selects a strategy (one edge from each controlled vertex) and player MIN responds by evaluating shortest paths to the sink in the remaining graph. Then MAX locally changes choices in controlled vertices looking at attractive switches that seem to increase shortest paths lengths (under the current evaluation). We show that this is a monotonic strategy improvement, and every locally optimal strategy is globally optimal. This allows us to construct a randomized algorithm of complexity , which is simultaneously pseudopolynomial (W is the maximal absolute edge weight) and subexponential in the number of vertices n. All previous algorithms for mean payoff games were either exponential or pseudopolynomial (which is purely exponential for exponentially large edge weights).     

A stochastic and asymmetric-information framework for a dominant-manufacturer supply chain

Consider a dominant manufacturer wholesaling a product to a retailer, who in turn retails it to the consumers at $p/unit. The retail-market demand volume varies with p according to a given demand curve. This basic system is commonly modeled as a manufacturer-Stackelberg ([mS]) game under a “deterministic and symmetric-information” (“det-sym-i”) framework. We first explain the logical flaws of this framework, which are (i) the dominant manufacturer-leader will have a lower profit than the retailer under an iso-elastic demand curve; (ii) in some situations the system’s “correct solution” can be hyper-sensitive to minute changes in the demand curve; (iii) applying volume discounting while keeping the original [mS] profit-maximizing objective leads to an implausible degenerate solution in which the manufacturer has dictatorial power over the channel. We then present an extension of the “stochastic and asymmetric-information” (“sto-asy-i”) framework proposed in Lau and Lau [Lau, A., Lau, H.-S., 2005. Some two-echelon supply-chain games: Improving from deterministic–symmetric-information to stochastic-asymmetric-information models. European Journal of Operational Research 161 (1), 203–223], coupled with the notion that a profit-maximizing dominant manufacturer may implement not only [mS] but also “[pm]”—i.e., using a manufacturer-imposed maximum retail price. We show that this new framework resolves all the logical flaws stated above. Along the way, we also present a procedure for the dominant manufacturer to design a profit-maximizing volume-discount scheme using stochastic and asymmetric demand information.     

Interval modeling of dynamics for multibody systems

Modeling of multibody systems is an important though demanding field of application for interval arithmetic. Interval modeling of dynamics is particularly challenging, not least because of the differential equations which have to be solved in the process. Most modeling tools transform these equations into a (non-autonomous) initial value problem, interval algorithms for solving of which are known. The challenge then consists in finding interfaces between these algorithms and the modeling tools. This includes choosing between “symbolic” and “numerical” modeling environments, transforming the usually non-autonomous resulting system into an autonomous one, ensuring conformity of the new interval version to the old numerical, etc. In this paper, we focus on modeling multibody systems’ dynamics with the interval extension of the “numerical” environment MOBILE, discuss the techniques which make the uniform treatment of interval and non-interval modeling easier, comment on the wrapping effect, and give reasons for our choice of MOBILE by comparing the results achieved with its help with those obtained by analogous symbolic tools.