Summer School of DeCAn. Day 4

Speaker: Katarína Cechlárová (Professor, P. J. Šafárik University Košice, Faculty of Science, Slovakia)
Title: Housing markets – various topics

Abstract
Housing market is the basic model in the theory of exchange of indivisible goods. Its simplest form that dates back to the seminal paper of Shapley and Scarf exhibits several favourable properties and is ‘computationally friendly’ with the Top Trading Cycles algorithm being at its core. In this talk we deal with several modifications and optimality notions for the basic housing market. First, we revise the difficulties brought about by indifferences. Then we deal with the housing market with divorcing and engaged pairs and show a strong intractability result for its maximization variant. In the second part we concentrate on the Walrasian equilibrium in the case of duplicate houses. We explore the computational complexity of this case, propose a polynomial algorithm for the strictpreferences case and prove NP-hardness for the case with dichotomous preferences. Then we define an approximate equilibrium and explore this notion from the perspectives of parameterized complexity and approximation.

Part 2