## 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**

**Abstract:**

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

**Abstract:**

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**

**Abstract:**

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.