License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.71
URN: urn:nbn:de:0030-drops-145112
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14511/
Li, Fu ;
Zheng, Xiong
Maximum Votes Pareto-Efficient Allocations via Swaps on a Social Network
Abstract
In recent work, Gourv{รจ}s, Lesca, and Wilczynski (IJCAI 17) propose a variant of the classic housing markets model in which the matching between agents and objects evolves through Pareto-improving swaps between pairs of agents who are adjacent in a social network. To explore the swap dynamics of their model, they pose several basic questions concerning the set of reachable matchings, and investigate the computational complexity of these questions when the graph structure of the social network is a star, path, or tree, or is unrestricted.
We are interested in how to direct the agents to swap objects with each other in order to arrive at a reachable matching that is both efficient and most agreeable. In particular, we study the computational complexity of reaching a Pareto-efficient matching that maximizes the number of agents who prefer their match to their initial endowments. We consider various graph structures of the social network: path, star, tree, or being unrestricted. Additionally, we consider two assumptions regarding preference relations of agents: strict (ties among objects not allowed) or weak (ties among objects allowed). By designing two polynomial-time algorithms and two NP-hardness reductions, we resolve the complexity of all cases not yet known. Our main contributions include a polynomial-time algorithm for path networks with strict preferences and an NP-hardness result in a star network with weak preferences.
BibTeX - Entry
@InProceedings{li_et_al:LIPIcs.MFCS.2021.71,
author = {Li, Fu and Zheng, Xiong},
title = {{Maximum Votes Pareto-Efficient Allocations via Swaps on a Social Network}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {71:1--71:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-201-3},
ISSN = {1868-8969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14511},
URN = {urn:nbn:de:0030-drops-145112},
doi = {10.4230/LIPIcs.MFCS.2021.71},
annote = {Keywords: Housing markets, Distributed process, Algorithms, Complexity}
}
|
Keywords: |
|
Housing markets, Distributed process, Algorithms, Complexity |
|
Collection: |
|
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
18.08.2021 |
