A Robust Optimization Approach for Solving Two-Person Games under Interval Uncertainty

Abstract In this paper, robust optimization methodologies for solving incomplete-information two-person zero-sum and nonzero-sum games are developed that consider single or multiple interval inputs (i.e., interval-valued payoffs). Unlike complete-information games, where all parameters of the game such as individual players’ payoffs are assumed common knowledge, incomplete-information games deal with uncertain payoffs. In some cases, the payoffs may be estimated from imprecise data, such as interval data. In such situations, conventional methods that use deterministic payoffs are not appropriate. Also, in many cases, payoffs are available as multiple intervals. This paper proposes robust optimization models for non-cooperative, simultaneous-move, one-shot, two-person games with incomplete information. The proposed approaches are able to aggregate information from multiple sources and thereby result in more realistic outcomes. The robust optimization methods developed in this paper can be used to solve two-person games with interval-valued (single or multiple intervals) payoffs as well as with single-valued (i.e., deterministic) and aleatory (i.e., precise probabilistic information) payoffs or a combination of them. The proposed methodologies are illustrated with several example problems including an investment decision problem and a capacity expansion decision problem. The proposed decoupled approach is compared with some previously developed approaches and it is demonstrated that the proposed formulations generate conservative solutions in the presence of interval uncertainty.