Picking winners: Diversification through portfolio optimization

Abstract

We develop a general framework for selecting a small pool of candidate solutions to maximize the chancesthat one will be optimal to a combinatorial optimization problem, under a linear and additive random payofffunction. We formulate this problem using a two-stage distributionally robust model, with a mixed 0-1semidefinite program. This approach allows us to exploit the “diversification” effect inherent in the problem,to address how different candidate solutions can be selected to improve the chances that one will attain ahigh ex-post payoff. More interestingly, using this distributionally robust optimization approach, our modelrecovers the “evil twin” strategy, well-known in the field of football pool betting, under appropriate settings.We also address the computational challenges of scaling up our approach to construct a moderate numberof candidate solutions to increase the chances of finding one that performs well. To this end, we developa sequential optimization approach based on a compact semidefinite programming reformulation of theproblem. Extensive numerical results show the superiority of our approach over existing methods.