Algorithms for Rationalizability and CURB Sets

Abstract

Significant work has been done on computational as-pects of solving games under various solution concepts, such as Nash equilibrium, subgame perfect Nash equi-librium, correlated equilibrium, and (iterated) domi-nance. However, the fundamental concepts of ratio-nalizability and CURB (Closed Under Rational Behav-ior sets have not, to our knowledge, been studied from a computational perspective. First, for rationalizabil-ity we describe an LP-based polynomial algorithm that finds all strategies that are rationalizable against a mix-ture over a given set of opponent strategies. Then, we describe a series of increasingly sophisticated polyno-mial algorithms for finding all minimal CURB sets, one minimal CURB set, and the smallest minimal CURB set. Finally, we give theoretical results regarding the relationships between CURB sets and Nash equilibria, showing that finding a Nash equilibrium can be expo-nential only in the size of the smallest CURB set. We show that this can lead to an arbitrarily large reduction in the complexity of finding a Nash equilibrium. On the downside, we also show that the smallest CURB set can be arbitrarily larger than the supports of the enclosed Nash equilibrium.