Abstract
In a modification of the classical model of housing market which includes duplicate houses, economic equilibrium might not exist. As a measure of approximation the value sat \(\mathcal(M)\) was proposed: the maximum number of satisfied agents in the market \(\mathcal(M)\), where an agent is said to be satisfied if, given a set of prices, he gets a most preferred house in his budget set. Clearly, market \(\mathcal(M)\) admits an economic equilibrium if sat(M) is equal to the total number n of agents, but sat\(\mathcal(M)\) is NP-hard to compute.
In this paper we give a 2-approximation algorithm for sat\(\mathcal(M)\) in the case of trichotomic preferences. On the other hand, we prove that sat\(\mathcal(M)\) is hard to approximate within a factor smaller than 21/19, even if each house type is used for at most two houses. If the preferences are not required to be trichotomic, the problem is hard to approximate within a factor smaller than 1.2. We also prove that, provided the Unique Games Conjecture is true, approximation is hard within a factor 1.25 for trichotomic preferences, and within a factor 1.5 in the case of general preferences.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abraham, D., Blum, A., Sandholm, T.: Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. In: EC 2007, San Diego, California (2007)
Abraham, D.J., Cechlárová, K., Manlove, D.F., Mehlhorn, K.: Pareto Optimality in House Allocation Problems. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 3–15. Springer, Heidelberg (2004)
Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. In: CCC 2009: Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, pp. 74–80. IEEE Computer Society, Washington, DC, USA (2009)
Cechlárová, K., Fleiner, T.: Housing markets through graphs. Algorithmica 58(1), 19–33 (2010)
Cechlárová, K., Jelínková, E.: An efficient implementation of the equilibrium algorithm for housing markets with duplicate houses. Information Processing Letters 111(13), 667–670 (2011)
Cechlárová, K., Schlotter, I.: Computing the Deficiency of Housing Markets with Duplicate Houses. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 72–83. Springer, Heidelberg (2010)
Deng, X., Papadimitriou, C., Safra, S.: On the complexity of price equilibria. J. Computer and System Sciences 67, 311–324 (2003)
Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of Mathematics 162, 439–485 (2005)
Fekete, S., Skutella, M., Woeginger, G.: The complexity of economic equilibria for house allocation markets. Information Processing Letters 88(5), 219–223 (2003)
Halldórsson, M.M., Iwama, K., Miyazaki, S., Yanagisawa, H.: Improved approximation results for the stable marriage problem. ACM Trans. Algorithms 3(3), 30 (2007)
Khot, S.: On the power of unique 2-prover 1-round games. In: Proc. 34th ACM Symp. on Theory of Computing, STOC 2002, pp. 767–775 (2002)
Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2 − ε. Journal of Computer and System Sciences 74(3), 335–349 (2008); Computational Complexity 2003
Shapley, L., Scarf, H.: On cores and indivisibility. J. Math. Econ. 1, 23–37 (1974)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cechlárová, K., Jelínková, E. (2011). Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses. In: Kolman, P., Kratochvíl, J. (eds) Graph-Theoretic Concepts in Computer Science. WG 2011. Lecture Notes in Computer Science, vol 6986. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25870-1_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-25870-1_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25869-5
Online ISBN: 978-3-642-25870-1
eBook Packages: Computer ScienceComputer Science (R0)