A Computational Investigation into the Strict Core of the 4-player Restricted Houseswapping Game
Loading...
Authors
Stewart, Owen Paul
Issue Date
2025
Type
Thesis
Language
en_US
Keywords
Birkhoff-von Neumann , game theory , houseswapping , matching games , ordinal preference
Alternative Title
Abstract
This thesis investigates the strict core in Restricted Houseswapping Games with Ordinal Preferences (RHGOPs), introduced by Quint [18]. RHGOPs generalize classical matching models with ordinal preferences, such as the houseswapping game of Shapley and Scarf [24] and the marriage game of Gale and Shapley [9], by incorporating a restricted trading structure. While prior work shows that many restricted houseswapping games have non-empty strict core if strongly balanced, and many RHGOPs in the literature have a non-empty strict core if there are strict preferences, no analogous guarantee exists for the strict core for RHGOPs in general. We conjecture that every RHGOP with strict preferences and a strongly balanced trading structure has a non-empty strict core across all preference structures. We test this with an exhaustive computational analysis of all 220 possible trading structures in 4−player RHGOPs, identify the 167,077 strongly balanced trading structures via Birkhoff-von Neumann decomposition of select doubly stochastic matrices, and confirm that each has a non-empty strict core across all preferences. This supports the conjecture and reveals a new, smallest class of doubly stochastic matrices forwhich the Birkhoff algorithm fails to find all decompositions.