Invited Session Wed.1.MA 376

Wednesday, 10:30 - 12:00 h, Room: MA 376

Cluster 22: Stochastic optimization [...]

Risk aversion in stochastic combinatorial optimization


Chair: Evdokia Nikolova



Wednesday, 10:30 - 10:55 h, Room: MA 376, Talk 1

Jian Li
Maximizing expected utility for stochastic combinatorial optimization problems

Coauthor: Amol Deshpande


We study the stochastic versions of a broad class of combinatorial
problems where the weights of the elements in the input dataset are
uncertain. The class of problems that we study includes shortest
paths, minimum weight spanning trees, and minimum weight matchings
over probabilistic graphs, and other combinatorial problems like
knapsack. We observe that the expected value is inadequate in
capturing different types of risk-averse or risk-prone behaviors, and
instead we consider a more general objective which is to maximize the
expected utility of the solution for some given utility function,
rather than the expected weight (expected weight becomes a special
case). We show that we can obtain a polynomial time approximation
algorithm with additive error ε for any ε>0, and the maximum value
of the utility function is bounded by a constant. Our result
generalizes several prior results on stochastic shortest path,
stochastic spanning tree, and stochastic knapsack. Our algorithm for
utility maximization makes use of a technique to decompose a general
utility function into exponential utility functions, which may be
useful in other stochastic optimization problems.



Wednesday, 11:00 - 11:25 h, Room: MA 376, Talk 2

Chaitanya Swamy
Risk-averse stochastic optimization: Probabilistically-constrained models and algorithms for black-box distributions


We consider various stochastic models that incorporate the notion of risk-averseness into the standard 2-stage recourse model, and develop techniques for solving the algorithmic problems arising in these models. A key notable and distinguishing feature of our work is that we obtain results in the black-box setting, where one is given only sampling access to the underlying distribution. One such model is what we call the risk-averse budget model, where we impose a probabilistic constraint that restricts the probability of the second-stage cost exceeding a given budget B to at most a given input threshold ρ. We devise an approximation scheme for solving the LP-relaxations of a variety of risk-averse budgeted problems. Complementing this, we give a rounding procedure that lets us use existing LP-based approximation algorithms for the 2-stage and/or deterministic counterpart of the problem to round the fractional solution. This yields approximation algorithms for various discrete optimization problems in our risk-averse models with black-box distributions. These are the first approximation results for problems involving probabilistic constraints with black-box distributions.



Wednesday, 11:30 - 11:55 h, Room: MA 376, Talk 3

Abraham Othman
Inventory-based versus prior-based options trading agents

Coauthor: Tuomas W. Sandholm


Options are a basic, widely-traded form of financial derivative that offer payouts based on the future price of an underlying asset. The finance literature gives us option-trading algorithms that take into consideration information about how prices move over time but do not explicitly involve the trades the agent made in the past. In contrast, the prediction market literature gives us automated market-making agents (like the popular LMSR) that are event-independent and price trades based only on the inventories the agent holds. We simulate the performance of five trading agents inspired by these literatures on a large database of recent historical option prices. We find that a combination of the two approaches produced the best results in our experiments: a trading agent that keeps track of previously-made trades combined with a good prior distribution on how prices move over time. The experimental success of this synthesized trader has implications for agent design in both financial and prediction markets.


  California Payday Loans. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.