  We provide a series of algorithms demonstrating that solutions according to
the fundamental game-theoretic solution concept of closed under rational
behavior (CURB) sets in two-player, normal-form games can be computed in
polynomial time (we also discuss extensions to n-player games). First, we
describe an algorithm that identifies all of a player's best responses
conditioned on the belief that the other player will play from within a given
subset of its strategy space. This algorithm serves as a subroutine in a series
of polynomial-time algorithms for finding all minimal CURB sets, one minimal
CURB set, and the smallest minimal CURB set in a game. We then show that the
complexity of finding a Nash equilibrium can be exponential only in the size of
a game's smallest CURB set. Related to this, we show that the smallest CURB set
can be an arbitrarily small portion of the game, but it can also be arbitrarily
larger than the supports of its only enclosed Nash equilibrium. We test our
algorithms empirically and find that most commonly studied academic games tend
to have either very large or very small minimal CURB sets.
