Abstrakt
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 (M) was proposed: the maximum number of satisfied agents in the market (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 (M) admits an economic equilibrium if sat(M) is equal to the total number n of agents, but sat (M) is NP-hard to compute. In this paper we give a 2-approximation algorithm for sat (M) in the case of trichotomic preferences.
On the other hand, we prove that sat (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.