Priority-augmented House Allocation

We consider the standard indivisible object allocation problem without monetary transfer and allow each object to have a weak priority over agents. It is well known that generally in such a problem stability (or no justified-envy) is not compatible with efficiency. We characterize the priority structures for which a stable and efficient assignment always exists, as well as the priority structures which admit a stable, efficient and (group) strategy-proof rule. While house allocation and housing market are two classical allocation problems that admit a stable, efficient and group strategy-proof rule, any priority-augmented allocation problem with more than three objects admits such a rule if and only if it is decomposable into a sequence of subproblems, each of which has the house allocation or the housing market structure.