Portfolio Construction
Robust Optimization, Game Theory and Variational Inequalities
January 1, 2005
Topics - Portfolio Construction
MIT Dissertation
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.
This document is not intended to, and does not relate specifically to any investment strategy or product that AQR offers. It is being provided merely to provide a framework to assist in the implementation of an investor’s own analysis and an investor’s own view on the topic discussed herein.
This document has been provided to you solely for information purposes and does not constitute an offer or solicitation of an offer or any advice or recommendation to purchase any securities or other financial instruments and may not be construed as such. The factual information set forth herein has been obtained or derived from sources believed by the author and AQR Capital Management, LLC (“AQR”) to be reliable but it is not necessarily all-inclusive and is not guaranteed as to its accuracy and is not to be regarded as a representation or warranty, express or implied, as to the information’s accuracy or completeness, nor should the attached information serve as the basis of any investment decision. This document is not to be reproduced or redistributed to any other person. The information set forth herein has been provided to you as secondary information and should not be the primary source for any investment or allocation decision. Past performance is not a guarantee of future performance. Diversification does not eliminate the risk of experiencing investment losses.
This material is not research and should not be treated as research. This paper does not represent valuation judgments with respect to any financial instrument, issuer, security or sector that may be described or referenced herein and does not represent a formal or official view of AQR. The views expressed reflect the current views as of the date hereof and neither the author nor AQR undertakes to advise you of any changes in the views expressed herein.
The information contained herein is only as current as of the date indicated, and may be superseded by subsequent market events or for other reasons. Charts and graphs provided herein are for illustrative purposes only. The information in this presentation has been developed internally and/or obtained from sources believed to be reliable; however, neither AQR nor the author guarantees the accuracy, adequacy or completeness of such information. Nothing contained herein constitutes investment, legal, tax or other advice nor is it to be relied on in making an investment or other decision. There can be no assurance that an investment strategy will be successful. Historic market trends are not reliable indicators of actual future market behavior or future performance of any particular investment which may differ materially, and should not be relied upon as such. Diversification does not eliminate the risk of experiencing investment losses.
The information in this paper may contain projections or other forward-looking statements regarding future events, targets, forecasts or expectations regarding the strategies described herein, and is only current as of the date indicated. There is no assurance that such events or targets will be achieved, and may be significantly different from that shown here. The information in this document, including statements concerning financial market trends, is based on current market conditions, which will fluctuate and may be superseded by subsequent market events or for other reasons.