Decision under uncertainty: problems in control theory, robust optimization and game theory
Creators: name: Hadjiyiannis, Michael Jason
Publisher: name: Imperial College London
Year: 2013

description: Decision making under uncertainty is a widely-studied area spanning a number of fields such as computational optimization, control theory, utility theory and game theory. A typical problem of decision making under uncertainty requires the design of an optimal decision rule, control policy, or behavioural function, that takes into account all available information regarding the uncertain parameters and returns the decision that is most suitable for the given objective. A popular requirement is to determine robust decisions that maintain certain desired characteristics despite the presence of uncertainty. In this thesis, we study three distinct problems that involve the design of robust decisions under different types of uncertainty. We investigate a dynamic multi-stage control problem with stochastic exogenous uncertainty, a dynamic two-stage robust optimization problem with epistemic exogenous uncertainty, and finally a game theoretic problem with both stochastic endogenous and epistemic exogenous uncertainty. Specifically, a) we develop an efficient algorithm that bounds the performance loss of affine policies operating in discrete-time, finite-horizon, stochastic systems with expected quadratic costs and mixed linear state and input constraints. Finding the optimal control policy for such problems is generally computationally intractable, but suboptimal policies can be computed by restricting the class of admissible policies to be affine on the observation. Our algorithm provides an estimate of the loss of optimality due to the use of such affine policies, and it is based on a novel dualization technique, where the dual variables are restricted to have an affine structure; b) we develop an efficient algorithm to bound the suboptimality of linear decision rules in two-stage dynamic linear robust optimization problems, where they have been shown to suffer a worst-case performance loss of the order $\Omega(\sqrt{m})$ for problems with $m$ linear constraints. Our algorithm is based on a scenario selection technique, where the original problem is evaluated only over a finite subset of the possible uncertain parameters. This set is constructed from the Lagrange multipliers associated with the computation of the linear adaptive decision rules. The resulting instance-wise bounds outperform known bounds, including the aforementioned worst-case bound, in the vast majority of problem instances; c) we develop an algorithm that enumerates all behavioural functions that are at equilibrium in a game where players face epistemic uncertainty regarding their opponent's utility functions. Traditionally, these games are solved as complete-information games where players are assumed to be risk-neutral, with a utility function that is positively affine in the monetary payoffs. We demonstrate that this assumption imposes severe limitations on the problem structure, and we propose that these games should be formulated as incomplete private information games where each player may have any increasing or increasing concave utility function. If the players are ambiguity-averse, then under these assumptions, they play either a pure strategy, a max-min strategy, or a convex combination of the two. By utilizing this result, we develop an algorithm that can enumerate all equilibria of the game.