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 CChard, 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 quasiNC².
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:123:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771337},
ISSN = {18688969},
year = {2020},
volume = {153},
editor = {Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11809},
URN = {urn:nbn:de:0030drops118090},
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 