We propose a robust optimization approach to analyzing three distinct classes of problems related to the notion of equilibrium: the nominal variational inequality (VI) problem over a polyhedron, the finite game under payoff uncertainty, and the network design problem under demand uncertainty.
We begin by demonstrating that the nominal VI problem is in fact a special instance of a robust constraint. Using this insight and duality-based proof techniques from robust optimization, we reformulate the VI problem over a polyhedron as a single-level (and many-times continuously differentiable) optimization problem.
Next, we propose a distribution-free model of incomplete-information games, in which the players use a robust optimization approach to contend with payoff uncertainty. Our “robust game” model relaxes the assumptions of Harsanyi’s Bayesian game model, and provides an alternative, distribution-free equilibrium concept, for which, in contrast to ex post equilibria, existence is guaranteed.
Finally, we consider uncertainty on the part of a mechanism designer. Specifically, we present a novel, robust optimization model of the network design problem (NDP) under demand uncertainty and congestion effects, and under either system- optimal or user-optimal routing. We propose a corresponding branch and bound algorithm that comprises the first constructive use of the price of anarchy concept.
In addition, we characterize conditions under which the robust NDP reduces to a less computationally demanding problem, either a nominal counterpart or a single-level quadratic optimization problem. Finally, we present a novel traffic “paradox,” illustrating counterintuitive behavior of changes in cost relative to changes in demand.