@inbook {IOPORT.05988770,
    author       = {Cechl\'arov\'a, Katar{\'\i}na and Jel{\'\i}nkov\'a, Eva},
    title        = {Approximability of economic equilibrium for housing markets with duplicate houses.},
    year         = {2011},
    booktitle    = {Graph-theoretic concepts in computer science. 37th international workshop, WG 2011, Tepl\'a Monastery, Czech Republic, June 21--24, 2011. Revised papers},
    isbn         = {978-3-642-25869-5},
    pages        = {95-106},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-642-25870-1_10},
    abstract     = {Summary: 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.},
    identifier   = {05988770},
}