Optimization under uncertainty [electronic resource].

Bhalgat, Anand.
197 p.
Computer science
Local subjects:
Penn dissertations -- Computer and Information Science.
Computer and Information Science -- Penn dissertations.
System Details:
Mode of access: World Wide Web.
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' 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' as well as the seller's 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's valuation may as well depend upon the entire allocation. In particular, we consider the positive network externality effect on a buyer's 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.
Thesis (Ph.D. in Computer and Information Science) -- University of Pennsylvania, 2013.
Source: Dissertation Abstracts International, Volume: 74-10(E), Section: B.
Adviser: Sanjeev Khanna.
Local notes:
School code: 0175.
Roth, Aaron, committee member
Kearns, Michael committee member
Kannan, Sampath committee member
Goel, Ashish committee member
Khanna, Sanjeev, advisor
University of Pennsylvania. Computer and Information Science.
Contained In:
Dissertation Abstracts International 74-10B(E).
Access Restriction:
Restricted for use by site license.
Location Notes Your Loan Policy
Description Status Barcode Your Loan Policy