We revisit the classical object reallocation problem under strict preferences. When attention is constrained to the set of Pareto-efficient rules, it is known that top trading cycles (TTC) is the only rule that is strategyproof and individually-rational. We relax this constraint and consider pair-efficiency. A rule is pair-efficient if it never induces an allocation at which a pair of agents gain from trading their assigned objects. Remarkably, even in the larger set of pair-efficient rules, we find that TTC is still the only rule that is strategyproof and individually-rational.

Abstract In a strategic-form game, a strategy profile is an equilibrium if no viable coalition of agents (or players) benefits (in the Pareto sense) from jointly changing their strategies. Weaker or stronger equilibrium notions can be defined by considering various restrictions on coalition formation. For instance, in a Nash equilibrium, it is assumed that viable coalitions are singletons, and in a super strong equilibrium, it is assumed that every coalition is viable. Restrictions on coalition formation can be justified by communication limitations, coordination problems, or institutional constraints. In this paper, inspired by social structures in various real-life scenarios, we introduce certain restrictions on coalition formation, and on their basis, we introduce a number of equilibrium notions. As an application, we study our equilibrium notions in resource selection games (RSGs), and we present a complete set of existence and nonexistence results for general RSGs and their important special cases.