Facility location problems often permit facilities to be located at any position. But what if this is not the case in practice? What if facilities can only be located at particular locations like a highway exit or close to a bus stop? We consider here the impact of such constraints on the location of facilities on the performance of strategy proof mechanisms for locating facilities.We study four different performance objectives: the total distance agents must travel to their closest facility, the maximum distance any agent must travel to their closest facility, and the utilitarian and egalitarian welfare.We show that constraining facilities to a limited set of locations makes all four objectives harder to approximate in general.
翻译:设施定位问题往往允许设施位于任何位置。但如果实际情况并非如此呢?如果设施只能位于高速公路出口或公共汽车站附近等特定地点,怎么办?我们在这里考虑这种设施位置限制对设施定位战略验证机制的实施的影响。我们研究四个不同的绩效目标:总距离代理必须前往最接近的设施,任何代理必须前往最接近的设施的最大距离,以及功利和平等福利。 我们表明,将设施限制在有限的一组地点会使所有四个目标普遍难以接近。