Open Research Index

Gale's Top Trading Cycles (Shapley-Scarf Housing Market)

Arthur Freitas Ramos, David Barros Hulak, Ruy Jose Guerra Barretto de Queiroz

Palomar Registrypalomar/PALOMAR-2026-10-01-000015Oct 1, 2026cs.GTscore 0

A Lean formalization of Gale's top trading cycles algorithm (1974) for the Shapley-Scarf housing market. Finitely many agents (Fin n) each own exactly one house (the endowment is a bijection endow : Fin n ≃ Fin n) and have strict preferences over houses, given most-preferred-first as per-agent permutations rank i : Fin n ≃ Fin n; agent i strictly prefers house a over house b iff (rank i).symm a < (rank i).symm b. The comparator-checked results are TTC.Palomar.ttcTerminates: the TTC procedure (each remaining agent points to the owner of their favourite remaining house, each house points to…

SourceRepositoryJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/palomar/PALOMAR-2026-10-01-000015
curl -X POST /api/v1/records/palomar/PALOMAR-2026-10-01-000015/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-10-01-000015/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'