A Computationally Tractable Theory of Performance Analysis in Stochastic Systems
Probability theory, while providing an insightful approach to model uncertainty, does not allow computationally tractable performance analysis for many systems, especially multi-dimensional systems. Queueing networks, network information theory, pricing multi-dimensional financial contracts, auction design in multi-item, multi-bidder auctions are some examples.
We propose a new approach to analyze stochastic systems based on robust optimization. The key idea is to replace the Kolmogorov axioms as primitives of probability theory, with some of the asymptotic implications of probability theory: the central limit theorem and law of large numbers and to define appropriate robust optimization problems to perform performance analysis. In this way, the performance analysis questions become highly structured optimization problems (linear, conic, mixed integer) for which there exist efficient, practical algorithms that are capable of solving truly large scale systems.
We demonstrate that the proposed approach achieves a computationally tractable methods for (a) analyzing multiclass queueing networks, and (b) pricing multi-dimensional financial contracts generalizing the work of Black, Scholes and Merton.
