We study deterministic mechanism design without money for fc-facility location games with envy ratio on a real line segment, where a set of strategic agents report their locations and a social planner locates fc facilities for minimizing the envy ratio. The objective of envy ratio, which is defined as the maximum over the ratios between any two agents' utilities, is derived from fair division to measure the fairness with respect to a certain facility location profile. The problem is studied in two settings. In the homogeneous fc-facility location game where k facilities serve the same purpose, we propose a 2k/(2k-1) -approximate deterministic group strategyproof mechanism which is also the best deterministic strategyproof mechanism. In the heterogeneous fc-facility location game where each facility serves a different purpose, when k is even, we devise the optimal and group strategyproof mechanism; when k is odd, we provide a (k+1)/(k-1)-approximate deterministic group strategyproof mechanism.
展开▼
