Functional classical mechanics and rational numbers

The notion of microscopic state of the system at a given moment of time as a point in the phase space as well as a notion of trajectory is widely used in classical mechanics. However, it does not have an immediate physical meaning, since arbitrary real numbers are unobservable. This notion leads to the known paradoxes, such as the irreversibility problem. A “functional” formulation of classical mechanics is suggested. The physical meaning is attached in this formulation not to an individual trajectory but only to a “beam” of trajectories, or the distribution function on phase space. The fundamental equation of the microscopic dynamics in the functional approach is not the Newton equation but the Liouville equation for the distribution function of the single particle. The Newton equation in this approach appears as an approximate equation describing the dynamics of the average values and there are corrections to the Newton trajectories. We give a construction of probability density function starting from the directly observable quantities, i.e., the results of measurements, which are rational numbers.     

Convergence of aspirations and (partial) cooperation in the prisoner's dilemma

This paper proposes an aspiration-based dynamic model for cooperation where a large population of agents are matched afresh every period to play a Prisoner's Dilemma. At each point in time, agents hold a common aspiration level which is updated on the basis of some “population statistic”, i.e. a certain scalar summary (e.g. average payoff) associated to the current state. On the other hand, those agents who feel “dissatisfied” (relative to current aspiration) switch actions at a rate which is increasing in the magnitude of the dissatisfaction. The resulting process is shown to converge in the long run under quite general conditions. Moreover, if agents are responsive enough, the long-run social state displays some extent of cooperation, with a constant positive fraction of the population (always less than half) choosing to cooperate in every period. Received: January 1998/Revised version: October 1998     

A study of travel time prediction using universal kriging

This study describes an approach for predicting travel time by kriging. The kriging method, which is a means of spatial prediction, is used as prediction measure for car travel time in an imaginary four-dimensional space. Each point in the space represents a single journey: the coordinates of a point are the coordinates of the origin and destination on a plane. The travel time can then be viewed as a function over this four-dimensional space. The prediction relies on the feature that nearby points (in the four-dimensional space) will have almost the same travel time. In this approach, it is not necessary to break down travel times from origin to destination into link travel times. The approach will also allow us to use information from “probe vehicles” for travel time prediction in the near future. The feasibility of this approach is demonstrated through a case study in London and its environs. The case study uses 200 observations for verification. The multiple correlation coefficient of estimated travel time and the verification data is 0.9045. The results indicate that 95% prediction limits are between ±10 minutes and ±30 minutes for travel between two arbitrary points. This prediction method is effective for urban districts with links having changeable travel time owing to congestion.     

Control of multi-node mobile communications networks with time-varying channels via stability methods

Consider a communications network consisting of mobiles and random external data processes, each destined to a particular destination. Each mobile can serve as a node in the multi-hop path from source to destination. At each mobile the data is queued according to the source destination pair. The quality of the connecting channels are randomly varying. Time is divided into small scheduling intervals. At the beginning of each interval, the channels are estimated and this information is used for the decisions concerning allocation of transmission power and/or time, bandwidth, and perhaps antennas, in a queue and channel-state dependent way. Under a natural (and “almost” necessary) “average flow” condition, stochastic stability methods are used to develop scheduling policies that assure stability. The policies are readily implementable and allow a range of tradeoffs between current rates and queue lengths, under very weak conditions. Because of the non-Markovian nature of the problem, we use the perturbed Stochastic Liapunov function method. The choice of Liapunov function allows a choice of the effective performance criteria. All essential factors are incorporated into a “mean rate” function, so that the results cover many different systems. Extensions concerning acknowledgments, multicasting, non-unique routes, and others are given to illustrate the versatility of the method, and a useful method for getting the a priori routes is discussed.     

Dynamic programming—neural network real-time traffic adaptive signal control algorithm

In this paper, an “intelligent” isolated intersection control system was developed. The developed “intelligent” system makes “real time” decisions as to whether to extend (and how much) current green time. The model developed is based on the combination of the dynamic programming and neural networks. Many tests show that the outcome (the extension of the green time) of the proposed neural network is nearly equal to the best solution. Practically negligible CPU times were achieved, and were thus absolutely acceptable for the “real time” application of the developed algorithm.     

The Existence and Uniqueness of Nash Equilibrium Point in an m-player Game “Shoot Later, Shoot First!”

We consider the following “silent duel” of m players with a possible economic interpretation. Each player has one “bullet”, which she can shoot at any time during the time interval [0,1]. The probability that the i-th player hits the “target” at moment t is given by an increasing accuracy function f _i (t). The winner is the player who hits the target first. Under natural assumptions on the functions f _i (t) we prove the existence and uniqueness of a Nash equilibrium point in this game, and we provide an explicit construction of this equilibrium. This construction allows us to obtain exact solutions for many specific examples. Some of them are presented.This work was partly supported by RBRF grants 03-01-00479.     

Optimisation of linear unbiased intensity estimators for point processes

A general non-stationary point process whose intensity function is given up to unknown numerical factor λ is considered. As an alternative to the conventional estimator of λ based on counting the points, we consider general linear unbiased estimators of λ given by sums of weights associated with individual points. A necessary and sufficient condition for a linear, unbiased estimator for the intensity λ to have the minimum variance is determined. It is shown that there are “nearly” no other processes than Poisson and Cox for which the unweighted estimator of λ, which counts the points only, is optimal. The properties of the optimal estimator are illustrated by simulations for the Matérn cluster and the Matérn hard-core processes. This research was partially supported by Grant Agency of Czech Republic, project No. 201/03/D062.     

The Concavity Assumption on Felicities and Asymptotic Dynamics in the RSS Model

An analysis of the RSS model in mathematical economics involves the study of an infinite-horizon variational problem in discrete time. Under the assumption that the felicity function is upper semicontinuous and “supported” at the value of the maximally-sustainable level of a production good, we report a generalization of results on the equivalence, existence and asymptotic convergence of optimal trajectories in this model. We consider two parametric specifications, and under the second, identify a “symmetry” condition on the zeroes of a “discrepancy function” underlying the objective function that proves to be necessary and sufficient for the asymptotic convergence of good programs. With a concave objective function, as is standard in the antecedent literature, we show that the symmetry condition reduces to an equivalent “non-interiority” condition.     

Disagreement point axioms and the egalitarian bargaining solution

We provide new characterizations of the egalitarian bargaining solution on the class of strictly comprehensive n-person bargaining problems. The main axioms used in all of our results are Nash’s IIA and disagreement point monotonicity—an axiom which requires a player’s payoff to strictly increase in his disagreement payoff. For n = 2 these axioms, together with other standard requirements, uniquely characterize the egalitarian solution. For n > 2 we provide two extensions of our 2-person result, each of which is obtained by imposing an additional axiom on the solution. Dropping the axiom of anonymity, strengthening disagreement point monotonicity by requiring player i’s payoff to be a strictly decreasing function of the disagreement payoff of every other player j ≠ i, and adding a “weak convexity” axiom regarding changes of the disagreement point, we obtain a characterization of the class of weighted egalitarian solutions. This “weak convexity” axiom requires that a movement of the disagreement point in the direction of the solution point should not change the solution point. We also discuss the so-called “transfer paradox” and relate it to this axiom.     

The island confinement method for reducing search space in local search methods

Typically local search methods for solving constraint satisfaction problems such as GSAT, WalkSAT, DLM, and ESG treat the problem as an optimisation problem. Each constraint contributes part of a penalty function in assessing trial valuations. Local search examines the neighbours of the current valuation, using the penalty function to determine a “better” neighbour valuation to move to, until finally a solution which satisfies all the constraints is found. In this paper we investigate using some of the constraints as “hard” constraints, that are always satisfied by every trial valuation visited, rather than as part of a penalty function. In this way these constraints reduce the possible neighbours in each move and also the overall search space. The treating of some constraints as hard requires that the space of valuations that are satisfied is “connected” in order to guarantee that a solution can be found from any starting position within the region; thus the concept of islands and the name “island confinement method” arises. Treating some constraints as hard provides new difficulties for the search mechanism since the search space becomes more jagged, and there are more deep local minima. A new escape strategy is needed. To demonstrate the feasibility and generality of our approach, we show how the island confinement method can be incorporated in, and significantly improve, the search performance of two successful local search procedures, DLM and ESG, on SAT problems arising from binary CSPs. A preliminary version of this paper appeared in AAAI’2002.     

Lebesgue numbers and Atsuji spaces in subsystems of second-order arithmetic

We study Lebesgue and Atsuji spaces within subsystems of second order arithmetic. The former spaces are those such that every open covering has a Lebesgue number, while the latter are those such that every continuous function defined on them is uniformly continuous. The main results we obtain are the following: the statement “every compact space is Lebesgue” is equivalent to ; the statements “every perfect Lebesgue space is compact” and “every perfect Atsuji space is compact” are equivalent to ; the statement “every Lebesgue space is Atsuji” is provable in ; the statement “every Atsuji space is Lebesgue” is provable in . We also prove that the statement “the distance from a closed set is a continuous function” is equivalent to . Received: February 2, 1996     

Goal programming sensitivity analysis using interval penalty weights

This paper presents an application of the vector-maximum research [4–8] to the sensitivity analysis of goal programming problems as several of the criterion function penalty weights are simultaneously and independently varied. A generalized goal programming capability is presented and a six-stage analytic procedure is described. The problem is generalized in the sense that the regular goal programming penalty weights can be expanded to intervals if desired. The solution procedure is new in that it depends upon an algorithm for the vector-maximum problem, criterion cone contraction procedures, and filtering techniques. Together they are able to generate and process all extreme points on the portion of the surface of the goal programming augmented feasible region corresponding to the interval penalty weights specified. In effect, the procedure and adapted algorithm of this paper delivers to goal programming an operational power of sensitivity analysis not previously available to users. A numerical example is provided in order to illustrate the computerized application of the total goal programming procedure outlined.     

Study on “double dawn”

The ancient record, “During the first year of King Yi, the day dawned twice at Zheng”, has provided important clues to early Chinese chronicles. The astronomical conditions and visible area distributions related to such a “double dawn” event are discussed, and the precision and current problems in the calculations of ancient astronomical phenomena are shown. On such a basis, all the solar eclipses from 1000 BC to 840 BC are calculated and their associated “double dawn” features investigated. The conclusion that the “double dawn” was a solar eclipse occurring on April 21st, 899 BC is corfirmed to be the most reasonable. Project supported by the Xia-Shang-Zhou Chronology Project and Director Foundation of the Chinese Academy of Sciences.     

Nevanlinna theory, diophantine approximation, and numerical analysis

This article treats the problem of the approximation of an analytic function f on the unit disk by rational functions having integral coefficients, with the goodness of each approximation being judged in terms of the maximum of the absolute values of the coefficients of the rational function. This relates to the more usual approximation by a rational function in that it could imply how many decimal places are needed when applying a particularly good rational function approximation having non-integrad coefficients. It is shown how to obtain “good” approximations of this type and it is also shown how under certain circumstances “very good” bounds are not possible. As in diophantine approximation this means that many merely “good” approximations do exist, which may be the preferable case. The existence or nonexistence of “very good” approximations is closely related to the diophantine approximation of the first nonzero power series coefficient of at z=0. Nevanlinna theory methods are used in the proofs.     

Heavy traffic analysis of controlled multiplexing systems

The paper develops the mathematics of the heavy traffic approach to the control and optimal control problem for multiplexing systems, where there are many mutually independent sources which feed into a single channel via a multiplexer (or of networks composed of such subsystems). Due to the widely varying bit rates over all sources, control over admission, bandwidth, etc., is needed to assure good performance. Optimal control and heavy traffic analysis has been shown to yield systems with greatly improved performance. Indeed, the heavy traffic approach covers many cases of great current interest, and provides a useful and practical approach to problems of analysis and control arising in modern high speed telecommunications. Past works on the heavy traffic approach to the multiplexing problem concentrated on the uncontrolled system or on the use of the heavy traffic limit control problem for applications, and did not provide details of the proofs. This is done in the current paper. The basic control problem for the physical system is hard, and the heavy traffic approach provides much simplification. Owing to the presence of the control, as well as to the fact that the cost function of main interest is “ergodic”, the problem cannot be fully treated with “classical” methods of heavy traffic analysis for queueing networks. A basic result is that the optimal average costs per unit time for the physical problem converge to the optimal cost per unit time for the limit stationary process as the number of sources and the time interval goes to infinity. This convergence is both in the mean and pathwise senses. Furthermore, a “nice” nearly optimal control for the limit system provides nearly optimal values for the physical system, under heavy traffic, in both a mean and pathwise sense. This revised version was published online in June 2006 with corrections to the Cover Date.     

Generalized correlated equilibrium for two-person games in extensive form with perfect information

A correlation scheme (leading to a special equilibrium called “soft” correlated equilibrium) is applied for two-person finite games in extensive form with perfect information. Randomization by an umpire takes place over the leaves of the game tree. At every decision point players have the choice either to follow the recommendation of the umpire blindly or freely choose any other action except the one suggested. This scheme can lead to Pareto-improved outcomes of other correlated equilibria. Computational issues of maximizing a linear function over the set of soft correlated equilibria are considered and a linear-time algorithm in terms of the number of edges in the game tree is given for a special procedure called “subgame perfect optimization”.     

On the concept of decision aiding process: an operational perspective

The paper presents the concept of decision aiding process as an extension of the decision process. The aim of the paper is to analyse the type of activities occurring between a “client” and an “analyst” both engaged in a decision process. The decision aiding process is analysed both under a cognitive point of view and an operational point of view: i.e. considering the “products”, or cognitive artifacts the process will deliver at the end. Finally the decision aiding process is considered as a reasoning process for which the update and revision problems hold.     

A filter inexact-restoration method for nonlinear programming

A new iterative algorithm based on the inexact-restoration (IR) approach combined with the filter strategy to solve nonlinear constrained optimization problems is presented. The high level algorithm is suggested by Gonzaga et al. (SIAM J. Optim. 14:646–669, 2003) but not yet implement—the internal algorithms are not proposed. The filter, a new concept introduced by Fletcher and Leyffer (Math. Program. Ser. A 91:239–269, 2002), replaces the merit function avoiding the penalty parameter estimation and the difficulties related to the nondifferentiability. In the IR approach two independent phases are performed in each iteration, the feasibility and the optimality phases. The line search filter is combined with the first one phase to generate a “more feasible” point, and then it is used in the optimality phase to reach an “optimal” point. Numerical experiences with a collection of AMPL problems and a performance comparison with IPOPT are provided.