Stable exchange
A directed preference system is given by a directed graph D=(V,E) and for every node [math]v \in V[/math] a linear order [math]\lt_v[/math] on the out-arcs of v. The digraph may include loops and parallel edges. If e and f are out-arcs of v and [math]e \lt_v f[/math], then we say that v prefers e to f. An exchange in D is a subgraph that is the union of node-disjoint directed cycles (maybe including loops). It is called a k-way exchange if every cycle has length at most k.
- An exchange F is weakly l-way stable if there is no cycle C of length at most l in D such that each node of C who has an out-arc in F prefers its out-arc in C to its out-arc in F.
- An exchange F is strongly l-way stable if every cycle C of length at most l that is not in F has a node that prefers its out-arc in F to its out-arc in C.
"Weakly l-way stable" is usually referred to simply as "l-way stable". If l is omitted, then stability holds for any l. For a survey of related results and questions, see [1].
Top Trading Cycle (TTC) algorithm
A strongly stable exchange can always be found using the Top Trading Cycle algorithm of Gale, as shown by Shapley and Scarf [2]. The algorithm works as follows.
- We remove the nodes with out-degree 0, and for every node, we choose the best outgoing arc. Let F be the set of chosen arcs.
- As [math]|F|=|V|[/math], there is at least one directed cycle in the subgraph formed by F. The directed cycles are node-disjoint because every out-degree is 1 in F. Mark the arcs in the directed cycles as exchange arcs. Remove the nodes in the cycles.
- Repeat until [math]V=\emptyset[/math].
References
- ↑ P. Biró, Stable exchange of indivisible goods with restrictions, author link
- ↑ L. Shapley, H.E. Scarf, On cores and indivisibility, DOI link, pdf link
