About: Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://dx.doi.org/10.1007/978-3-642-25870-1_10
Description	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. 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. (en)
Title	Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses (en)
skos:prefLabel	Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses (en)
skos:notation	RIV/00216208:11320/11:10126049!RIV13-MSM-11320___
http://linked.open...avai/predkladatel	Matematicko-fyzikální fakulta
http://linked.open...avai/riv/aktivita	Z
http://linked.open...avai/riv/aktivity	Z(MSM0021620838)
http://linked.open...vai/riv/dodaniDat	2013
http://linked.open...aciTvurceVysledku	Jelínková, Eva
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	186943
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/11:10126049
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	hardness of approximation; approximation algorithms; economic equilibrium; housing markets (en)
http://linked.open.../riv/klicoveSlovo	approximation algorithms economic equilibrium hardness of approximation housing markets
http://linked.open...ontrolniKodProRIV	[748F7A29D253]
http://linked.open...v/mistoKonaniAkce	Teplá Monastery, Czech Republic
http://linked.open...i/riv/mistoVydani	Heidelberg
http://linked.open...i/riv/nazevZdroje	Graph-Theoretic Concepts in Computer Science
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...UplatneniVysledku	2011
http://linked.open...iv/tvurceVysledku	Cechlárová, Katarína Jelínková, Eva
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open...ain/vavai/riv/wos	000307088100010
http://linked.open.../riv/zahajeniAkce	2011-06-21 (xsd:date)
http://linked.open...n/vavai/riv/zamer	Moderní metody, struktury a systémy informatiky
issn	0302-9743
number of pages	12 (xsd:int)
http://bibframe.org/vocab/doi	10.1007/978-3-642-25870-1_10
http://purl.org/ne...btex#hasPublisher	Springer-Verlag. (Berlin; Heidelberg)
https://schema.org/isbn	978-3-642-25869-5
http://localhost/t...ganizacniJednotka	11320
is http://linked.open...avai/riv/vysledek of	Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 112 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software