Determining whether a housing allocation is in the Core

Question

I have recently been thinking about the housing allocation problem where we have a set of players and a set of houses where players have strict preferences over the houses. I am aware of the Top Trading Cycle algorithm which can be used to assign houses to players in a Pareto Optimal, Strategy Proof, and Individual Rational way. Furthermore, this resulting allocation is group rational, i.e. in the (weak) core meaning that no subset of players can deviate and switch their assigned houses among themselves so that all players in this subset strictly improve. This also implies that the core is always non-empty.

However, what I was wondering is whether there exists an approach that allows us to efficiently determine whether a given allocation is in the (weak) core. I.e. given an allocation f, can we determine whether there exists a subset of players that can switch so that all of them strictly improve?

I could not find much existing content on this question. Any input would be highly appreciated!

Answer 1

I believe this might work:

Consider the directed graph G induced by the players and their preferences. An allocation f is a circulation on G. Given an allocation f, we can now consider the modified graph G' where for each node v, we remove those edges that are of lower preference than the currently assigned edge in f. Furthermore, we remove the edge that is assigned in f. The resulting graph G' now only consists of those edges that point to more desirable houses for each player. If we can find any cycle in this modified graph, f is not in the weak core. Else, it is.

Answer 2

There are two ways to interpret the question. First, is an allocation in the core for the initial assignment of houses? Second, is the allocation in the core if every agent owns their assigned house. For the second question, just run the top trading cycle algorithm starting from the allocation (that seems to be your answer, too). If nothing changes, you have a core allocation. For the first question, just run the top trading cycle algorithm from the initial assignment of houses and compare. With strict preferences, there is always a unique weak core allocation; this is part of Theorem 2 of

Roth, Alvin E., and Andrew Postlewaite. "Weak versus strong domination in a market with indivisible goods." Journal of Mathematical Economics 4.2 (1977): 131-137.