10.4230/LIPICS.OPODIS.2019.23
Zheng, Xiong
Xiong
Zheng
Electrical and Computer Engineering Department, University of Texas at Austin, USA
Garg, Vijay K.
Vijay K.
Garg
Electrical and Computer Engineering Department, University of Texas at Austin, USA
Parallel and Distributed Algorithms for the Housing Allocation Problem
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2020
Conference Paper
Parallel Algorithm
Distributed Algorithm
Housing Allocation
Housing Markets
Pareto optimality
en
Pascal Felber
University of Neuchâtel, Switzerland
Roy Friedman
Technion, Israel
Seth Gilbert
NUS, Singapore
Avery Miller
University of Manitoba, Canada
arXiv:1905.03111
10.4230/LIPIcs.OPODIS.2019
978-3-95977-133-7
1868-8969
Unknown license
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.
LIPIcs, Vol. 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019), pages 23:1-23:16