On the Convergence of Swap Dynamics to Pareto-Optimal Matchings
Authors: Felix Brandt, Anaëlle Wilczynski
JAIR 2024 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study whether Pareto-optimal stable matchings can be reached via pairwise swaps in one-to-one matching markets with initial assignments. We consider housing markets, marriage markets, and roommate markets as well as three different notions of swap rationality. Our main results are as follows. While it can be efficiently determined whether a Pareto-optimal stable matching can be reached when defining swaps via blocking pairs, checking whether this is the case for all such sequences is computationally intractable. When defining swaps such that all involved agents need to be better off, even deciding whether a Pareto-optimal stable matching can be reached via some sequence is intractable. This confirms and extends a conjecture made by Damamme, Beynier, Chevaleyre, and Maudet (2015) who have shown that convergence to a Pareto-optimal matching is guaranteed in housing markets with single-peaked preferences. We prove that in marriage and roommate markets, single-peakedness is not sufficient for this to hold, but the stronger restriction of one-dimensional Euclidean preferences is. |
| Researcher Affiliation | Academia | Felix Brandt EMAIL Technische Universit at M unchen Boltzmannstr. 3, 85748 Munich, Germany; Ana elle Wilczynski EMAIL MICS, Centrale Sup elec, Universit e Paris-Saclay 9 rue Joliot Curie, 91190 Gif-sur-Yvette, France. Both authors are affiliated with universities. |
| Pseudocode | No | The paper describes algorithms and concepts through mathematical definitions and textual explanations, but it does not contain clearly labeled pseudocode or algorithm blocks with structured formatting. |
| Open Source Code | No | The paper does not contain any statement about releasing source code, nor does it provide links to any code repositories or supplementary materials containing code. |
| Open Datasets | No | The paper is theoretical in nature and does not make use of empirical datasets for experiments. Therefore, no datasets or access information for them are provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments using datasets. Consequently, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper focuses on theoretical analysis and computational complexity. It does not describe any experimental setups or specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not detail any software dependencies with specific version numbers, as it does not involve practical implementations or experiments. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and computational complexity. It does not describe any experimental setups, hyperparameters, or training configurations. |