License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2019.23
URN: urn:nbn:de:0030-drops-118090
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11809/
Zheng, Xiong ;
Garg, Vijay K.
Parallel and Distributed Algorithms for the Housing Allocation Problem
Abstract
We propose parallel and distributed algorithms for the housing allocation problem. In this problem, there is a set of agents and a set of houses. Each agent has a strict preference list for a subset of houses. We need to find a matching for agents to houses such that some criterion is optimized. One such criterion which has attracted much attention is Pareto optimality. A matching is Pareto optimal if no coalition of agents can be strictly better off by exchanging houses among themselves. We also study the housing market problem, a variant of the housing allocation problem, where each agent initially owns a house. In addition to Pareto optimality, we are also interested in finding the a matching in the core of a housing market. A matching is in the core if there is no coalition of agents that can be better off by breaking away from other agents and switching houses only among themselves in the initial allocation.
In the first part of this work, we show that computing a Pareto optimal matching of a house allocation is in CC and computing a matching in the core of a housing market is CC-hard, where CC is the class of problems logspace reducible to the comparator circuit value problem. Given a matching of agents to houses, we show that verifying whether it is Pareto optimal is in NC. We also show that verifying whether it is in the core can be done in NC. We then give an algorithm to show that computing a maximum cardinality Pareto optimal matching for the housing allocation problem is in RNC² and quasi-NC².
In the second part of this work, we present a distributed version of the top trading cycle algorithm for finding a matching in the core of a housing market. To that end, we first present two algorithms for finding all the disjoint cycles in a functional graph. The first algorithm is a Las Vegas algorithm which terminates in O(log l) rounds with high probability, where l is the length of the longest cycle. The second algorithm is a deterministic algorithm which terminates in O(log* n log l) rounds, where n is the number of nodes in the graph. Both algorithms work in the synchronous distributed model and use messages of size O(log n). By applying these two algorithms for finding cycles in a functional graph, we give the distributed top trading cycle algorithm which terminates in O(n) rounds and requires O(n²) messages.
BibTeX - Entry
@InProceedings{zheng_et_al:LIPIcs:2020:11809,
author = {Xiong Zheng and Vijay K. Garg},
title = {{Parallel and Distributed Algorithms for the Housing Allocation Problem}},
booktitle = {23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
pages = {23:1--23:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-133-7},
ISSN = {1868-8969},
year = {2020},
volume = {153},
editor = {Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11809},
URN = {urn:nbn:de:0030-drops-118090},
doi = {10.4230/LIPIcs.OPODIS.2019.23},
annote = {Keywords: Parallel Algorithm, Distributed Algorithm, Housing Allocation, Housing Markets, Pareto optimality}
}
|
Keywords: |
|
Parallel Algorithm, Distributed Algorithm, Housing Allocation, Housing Markets, Pareto optimality |
|
Collection: |
|
23rd International Conference on Principles of Distributed Systems (OPODIS 2019) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
11.02.2020 |
