ﻻ يوجد ملخص باللغة العربية
We study the facility location games with candidate locations from a mechanism design perspective. Suppose there are n agents located in a metric space whose locations are their private information, and a group of candidate locations for building facilities. The authority plans to build some homogeneous facilities among these candidates to serve the agents, who bears a cost equal to the distance to the closest facility. The goal is to design mechanisms for minimizing the total/maximum cost among the agents. For the single-facility problem under the maximum-cost objective, we give a deterministic 3-approximation group strategy-proof mechanism, and prove that no deterministic (or randomized) strategy-proof mechanism can have an approximation ratio better than 3 (or 2). For the two-facility problem on a line, we give an anonymous deterministic group strategy-proof mechanism that is (2n-3)-approximation for the total-cost objective, and 3-approximation for the maximum-cost objective. We also provide (asymptotically) tight lower bounds on the approximation ratio.
This paper is devoted to the two-opposite-facility location games with a penalty whose amount depends on the distance between the two facilities to be opened by an authority. The two facilities are opposite in that one is popular and the other is obn
The study of approximate mechanism design for facility location problems has been in the center of research at the intersection of artificial intelligence and economics for the last decades, largely due to its practical importance in various domains,
We consider a new setting of facility location games with ordinal preferences. In such a setting, we have a set of agents and a set of facilities. Each agent is located on a line and has an ordinal preference over the facilities. Our goal is to desig
Recommendation systems are extremely popular tools for matching users and contents. However, when content providers are strategic, the basic principle of matching users to the closest content, where both users and contents are modeled as points in so
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 her