Improvements in the upward social mobility of a group or society can paradoxically lead to more frustration (relative deprivation) among its members. At present, there is little understanding of the conditions under which this paradox occurs. Boudon created a game-theoretic model of relative deprivation that can be used to derive predictions for these conditions. We extend his model, and through computer simulations provide predictions for the relationship between societal mobility and relative deprivation, of which a subset is tested within a laboratory experiment. Among other things, we predict and find that if social mobility moves from a low to medium level, and the costs of investing in a better position are low, relative deprivation increases.