Jose M Vidal
In this problem every node represents an agent with a house that he wants to trade. Every agent has an ordered preference of the other agents' houses he prefers (this list includes the agent's own house). The trick then is to get all agents to trade houses so that they all end up in a house that is at least as good, in their eyes, as the one they currently have.
The Top Trading Cycle Algorithm (TTCA) solves this problem using a very simple greedy method. It was first proposed in:
The algorithm is:
while there are agents in the game
--each agent points to the one it prefers most
--all agents that are in a loop drop out of the game
In this animation the blue nodes are the ones that have not traded and the green nodes have already traded. Once a trade cycle is found all the links in the cycle turn black. The edges represent an agent's most preferred house where a node with no edge prefers its own house. As the algorithm runs the nodes adjust their edges in case their most preferred node turns green.
TTCA is guaranteed to find a solution, and that solution is in the core. That is, there is no subset of agents that could deviate from this solution and everyone one of them receive a house that they like better than the one the got under TTCA.
I have extended the basic algorithm with a distributed method for identifying cycles. In this program each agent only talks to the one it prefers the most. Of course, if the one it prefers most drops out of the game then the agent talks to the his next most prefered agent that is still in the game. This implementation cheats in that the agents do know the total number of other agents that are blue.
20100623