We study a fairness-based model for 2-facility location games on the real line where the social objective is to minimize the maximum envy over all agents. All the agents seek to minimize their personal costs, and the envy between any two of them is the difference in their personal costs. We consider two cases of personal costs, called min-dist and sum-dist cost. We are interested in investigating strategyproof mechanisms for 2-facility location games in both cases. In the case of min-dist personal cost, we prove that a lower bound of the additive approximation for any deterministic strategyproof mechanism is 1/4; then we propose a 1/2-additive approximate deterministic group strategyproof mechanism and a 1/4-additive approximate randomized strategyproof mechanism. In the case of sum-dist personal cost, we design an optimal and group strategyproof deterministic mechanism.
展开▼
