Document Open Access Logo

Parallel and Distributed Algorithms for the Housing Allocation Problem

Authors Xiong Zheng, Vijay K. Garg

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.23.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Xiong Zheng
  • Electrical and Computer Engineering Department, University of Texas at Austin, USA
Vijay K. Garg
  • Electrical and Computer Engineering Department, University of Texas at Austin, USA

Funding

This work was partially supported by NSF CSR-1563544,CNS-1812349, and Cullen Trust Professorship.

Cite As Get BibTex

Xiong Zheng and Vijay K. Garg. Parallel and Distributed Algorithms for the Housing Allocation Problem. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.OPODIS.2019.23

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parallel algorithms
Keywords
  • Parallel Algorithm
  • Distributed Algorithm
  • Housing Allocation
  • Housing Markets
  • Pareto optimality

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Atila Abdulkadiroğlu and Tayfun Sönmez. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, 66(3):689-701, 1998. Google Scholar
  2. Atila Abdulkadiroğlu and Tayfun Sönmez. House allocation with existing tenants. Journal of Economic Theory, 88(2):233-260, 1999. Google Scholar
  3. David J Abraham, Katarína Cechlárová, David F Manlove, and Kurt Mehlhorn. Pareto optimality in house allocation problems. In International Symposium on Algorithms and Computation, pages 3-15. Springer, 2004. Google Scholar
  4. Nir Amira, Ran Giladi, and Zvi Lotker. Distributed weighted stable marriage problem. In International Colloquium on Structural Information and Communication Complexity, pages 29-40. Springer, 2010. Google Scholar
  5. Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32-53, 1986. Google Scholar
  6. Stephen A Cook, Yuval Filmus, and Dai Tri Man Le. The complexity of the comparator circuit value problem. ACM Transactions on Computation Theory (TOCT), 6(4):15, 2014. Google Scholar
  7. Manlove David. Algorithmics of matching under preferences, volume 2. World Scientific, 2013. Google Scholar
  8. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 367-376. ACM, 2014. Google Scholar
  9. Stephen Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-NC. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 754-763. ACM, 2016. Google Scholar
  10. Aanund Hylland and Richard Zeckhauser. The efficient allocation of individuals to positions. Journal of Political economy, 87(2):293-314, 1979. Google Scholar
  11. Richard M Karp and Vijaya Ramachandran. Parallel algorithms for shared-memory machines, Handbook of Theoretical Computer Science (J. van Leeuwen, ed.), 1990. Google Scholar
  12. Jinpeng Ma. Strategy-proofness and the strict core in a market with indivisibilities. International Journal of Game Theory, 23(1):75-83, 1994. Google Scholar
  13. Bruce M Maggs and Ramesh K Sitaraman. Algorithmic nuggets in content delivery. ACM SIGCOMM Computer Communication Review, 45(3):52-66, 2015. Google Scholar
  14. Ernst W Mayr and Ashok Subramanian. The complexity of circuit value and network stability. Journal of Computer and System Sciences, 44(2):302-323, 1992. Google Scholar
  15. Gary L Miller and John H Reif. Parallel Tree Contraction and Its Application. Technical report, HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB, 1985. Google Scholar
  16. Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani. Matching is as easy as matrix inversion. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 345-354. ACM, 1987. Google Scholar
  17. Alvin E Roth. Incentive compatibility in a market with indivisible goods. Economics letters, 9(2):127-132, 1982. Google Scholar
  18. Alvin E Roth and Andrew Postlewaite. Weak versus strong domination in a market with indivisible goods. Journal of Mathematical Economics, 4(2):131-137, 1977. Google Scholar
  19. Lloyd Shapley and Herbert Scarf. On cores and indivisibility. Journal of mathematical economics, 1(1):23-37, 1974. Google Scholar
  20. Uzi Vishkin. Randomized speed-ups in parallel computation. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 230-239. ACM, 1984. Google Scholar
  21. Yufei Yuan. Residence exchange wanted: a stable residence exchange problem. European Journal of Operational Research, 90(3):536-546, 1996. Google Scholar
  22. Xiong Zheng and Vijay Garg. Parallel and Distributed Algorithms for the housing allocation Problem. arXiv preprint arXiv:1905.03111, 2019. Google Scholar
  23. Lin Zhou. On a conjecture by Gale about one-sided matching problems. Journal of Economic Theory, 52(1):123-135, 1990. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact