Gale’s top trading cycles algorithm
E612746
Gale’s top trading cycles algorithm is a mechanism in matching theory that produces efficient and strategy-proof allocations of indivisible goods, such as in housing markets, by iteratively forming and executing trading cycles among participants.
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
allocation mechanism
ⓘ
matching algorithm ⓘ mechanism in matching theory ⓘ |
| algorithmType |
graph-based algorithm
ⓘ
iterative algorithm ⓘ |
| appliesTo |
allocation of indivisible goods
ⓘ
house allocation problems ⓘ housing markets ⓘ kidney exchange models ⓘ school choice problems ⓘ |
| assumes |
agents have complete and transitive preferences
ⓘ
preferences are strict in the basic formulation ⓘ |
| contrastWith | deferred acceptance algorithm NERFINISHED ⓘ |
| field |
market design
ⓘ
matching theory ⓘ microeconomics ⓘ |
| goal |
ensure strategy-proofness for participants
ⓘ
produce efficient allocations of indivisible goods ⓘ |
| guarantees | existence of an allocation in the core of the housing market game ⓘ |
| input |
agents’ strict preference orderings over goods
ⓘ
finite set of agents ⓘ finite set of indivisible goods ⓘ initial endowment of goods to agents ⓘ |
| namedAfter | David Gale NERFINISHED ⓘ |
| output | allocation of goods to agents ⓘ |
| outputProperty |
no agent can be made better off without making another worse off
ⓘ
no coalition of agents can reassign their initial endowments to make all its members strictly better off ⓘ |
| property |
Pareto efficient
ⓘ
core-selecting in housing markets with initial endowments ⓘ individually rational given initial endowments ⓘ strategy-proof for agents ⓘ |
| relatedTo |
Gale–Shapley deferred acceptance algorithm
NERFINISHED
ⓘ
Shapley–Scarf housing market model NERFINISHED ⓘ core of a cooperative game ⓘ top trading cycles and chains mechanisms ⓘ |
| step |
agents and goods in executed cycles are removed from the market
ⓘ
all agents in a cycle are assigned the good they point to ⓘ at least one cycle of agents and goods is identified in the graph ⓘ directed graph of agents and goods is formed ⓘ each agent points to her most-preferred available good ⓘ each good points to its current owner ⓘ procedure repeats until no agents or goods remain ⓘ |
| usedIn |
design of allocation mechanisms without monetary transfers
ⓘ
public policy applications in matching markets ⓘ theoretical analysis of housing markets ⓘ |
| usesConcept |
directed cycles
ⓘ
trading cycles ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.