Prophet inequalities for parallel processes

Generalizations of prophet inequalities for single sequences are obtained for optimal stopping of several parallel sequences of independent random variables. For example, if {X_{i, j}, 1 ≤ i ≤ n, 1 ≤ j < ∞} are independent non-negative random variables, then

Full-size image

and this bound is best possible. Applications are made to comparisons of the optimal expected returns of various alternative methods of stopping of parallel processes.     

Recursive solution of linear-quadratic Nash games for weakly interconnected systems

A recursive method is developed for the solution of coupled algebraic Riccati equations and corresponding linear Nash strategies of weakly interconnected systems. It is shown that the given algorithm converges to the exact solution with the rate of convergence ofO(²), where is a small coupling parameter. In addition, only low-order systems are involved in algebrdic computations; the amount of computations required does not grow per iteration and no analyticity assumption is imposed on the system coefficients.This work was supported by Rutgers University Research Council under Grant No. 2-02188.     

Geometric critical exponent inequalities for general random cluster models

A set of new critical exponent inequalities,d(1 –1 /)2 –, dv(1 – 1/), andd> 1, is proved for a general class of random cluster models, which includes (independent or dependent) percolations, lattice animals (with any interactions), and various stochastic cluster growth models. The inequalities imply that the critical phenomena in the models are inevitably not mean-field-like in the dimensions one, two, and three.The present work was reported at the 56th Statistical Mechanics Meeting (Rutgers, December 1986).     

Consistency of a linear system of inequalities

We show that a consistency check of a linear system of inequalitiesAxb reduces to check whetherQb0 for a certain matrixQ. It is a direct consequence of the Farkas-Minkowski theorem. Thus, when one has to check consistency for different values ofb, one need not run a numerical algorithm for eachb.On leave at the Electronics Research Laboratory of the University of California at Berkeley in a CNRS/NSF Exchange Program.     

Classification of connected commutative locally Nash groups

In this article, we classify connected commutative (locally) Nash groups, which is a continuation of our previous work on the classification of abelian Nash manifolds. Our results generalize the classification of the one-dimensional case by Madden-Stanton and the two-dimensional case by Baro-Vicente-Otero. Moreover, we determine the affineness and toroidal affineness of a connected commutative Nash group.     

A two-population game in observable double-ended queuing systems

In this study, the existing game theoretical framework is extended to strategic queuing in search of solutions for a two-population game in observable double-ended queuing systems with zero matching times. We show that multiple Nash equilibria and one unique subgame perfect Nash equilibrium exist in this game.     

A capacity reservation game for suppliers with multiple blocks of capacity

This paper studies a supplier competition model in which a buyer reserves capacity from a number of suppliers that each have multiple blocks of capacity (e.g., production or power plants). The suppliers each submit a bid that specifies a reservation price and an execution price for every block, and the buyer determines what blocks to reserve. This game involves both external competition between suppliers and internal competition between blocks from each supplier. We characterize the properties of pure-strategy Nash equilibria for the game. Such equilibria may not always exist, and we provide the conditions under which they do.     

考虑订单取件时间和柔性时间窗的取送货车辆路径问题

研究了同城配送中考虑订单取货时间和柔性时间窗的取送货车辆路径问题,考虑同城配送中订单起终点,订单取货时间和订单配送的柔性时间窗,车容量限制等因素。首先构建以配送成本与超时惩罚成本之和最小化为目标的混合整数线性模型。其次,设计了含多种有效不等式及其对应分离算法的改进分支切割算法对该模型进行精确求解。最后通过实验测试分析了不等式的性能,验证了算法的有效性,实验表明适当的减少车辆数和增大装载能力能够有效的减少成本。     

两台自私型机器上自私工件排序的PoA紧界

本文研究了两台自私型机器上有自私型工件的关于二元均衡的排序问题。对任意工件序列$L$, 证明了二元均衡排序的PoA的紧界为$\frac{8}{7}$。如果工件尺寸在区间$[1, r](r\ge1)$内, 得到了二元均衡排序的PoA的紧界为关于$r$的分段线性函数。     

Smoothing methods for convex inequalities and linear complementarity problems

A smooth approximationp (x, ) to the plus function max{x, 0} is obtained by integrating the sigmoid function 1/(1 + e^–x ), commonly used in neural networks. By means of this approximation, linear and convex inequalities are converted into smooth, convex unconstrained minimization problems, the solution of which approximates the solution of the original problem to a high degree of accuracy for sufficiently large. In the special case when a Slater constraint qualification is satisfied, an exact solution can be obtained for finite. Speedup over MINOS 5.4 was as high as 1142 times for linear inequalities of size 2000 × 1000, and 580 times for convex inequalities with 400 variables. Linear complementarity problems are converted into a system of smooth nonlinear equations and are solved by a quadratically convergent Newton method. For monotone LCPs with as many as 10 000 variables, the proposed approach was as much as 63 times faster than Lemke's method.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grants CCR-9101801 and CCR-9322479.