Optimization under uncertainty

Uncertainty exists everywhere; from the future price of a stock, to the routing time of a network packet and playing a slot machine. In presence of such uncertainty, one often has to take a decision without knowing the entire information. While one approach is to optimize for the worst possible scenario (i.e. a {\em robust} approach), this is undesirable as it leads to large scale inefficiencies. Instead, we focus on designing optimization techniques to handle such uncertainty by assuming the presence of statistical information about the input. In this regard, we study two important classes of allocation problems: (a) allocation in a general stochastic packing framework, and (b) allocation to selfish buyers in a Bayesian setting (i.e. Bayesian mechanism design). We first consider a generic stochastic packing framework where the item sizes or profits come from item-specific distributions; this framework encapsulates a wide variety of natural scenarios that include (a) deadline scheduling, (b) bandwidth allocation to bursty connections, and (c) asset allocation for a risk averse investor. We design new techniques to construct a PTAS for any stochastic packing problem in this framework, assuming a slight relaxation in the packing constraints. Our techniques can handle adaptivity, and extend to a wide variety of risk-averse objectives. Our techniques also yield a new approximation result when the packing constraints are strict. We next focus on Bayesian mechanism design. In a mechanism, buyers\u27 valuations are private and the seller has to optimize only based on his priors. This leads to a unique set of stochastic challenges; we focus on three specific aspects: As the outcome of a mechanism is random, there is risk associated with it; thus, the buyers\u27 as well as the seller\u27s risk-aversion play a strong role in the design of the mechanism. We design approximately optimal DSIC and BIC mechanisms for a risk-averse seller in presence of potentially risk-averse buyers. This uses our result on utility equivalence of correlated random variables for a concave objective function. In addition to being a private information, a buyer\u27s valuation may as well depend upon the entire allocation. In particular, we consider the positive network externality effect on a buyer\u27s valuation and design approximately optimal mechanisms for various single-parameter and multi-parameter settings. Finally, we study the problem of designing mechanisms with desirable payment properties, such as (a) quitting rights for buyers, (b) ex post individual rationality in presence of budget constraints, and (c) cost to borrow money beyond budget; we give a generic technique to design optimal mechanisms in presence of such desirable but complex payment constraints