Strategyproof Mechanisms for Activity Scheduling

Recent years have seen various designs of strategyproof mechanisms in the facility location game and the obnoxious facility game, by considering the facility as a point. In this paper, we extend that point to be an interval and study a novel activity scheduling game to schedule an activity in the time domain [0, 1] based on all agents' time reports. The activity lasts for a time period of 𝑑 with 0 ≤ 𝑑 ≤ 1, and each agent 𝑖 wants his private time 𝑡𝑖 to be within the activity duration [𝑦, 𝑦 + 𝑑] or at least as close as possible. Thus his cost is the time difference between his time 𝑡𝑖 and the activity duration [𝑦, 𝑦 + 𝑑]. The social cost is the summation of all agents' costs. Our objective is to choose the activity starting time 𝑦 so that the mechanisms are strategyproof (truthful) and efficient. We design a mechanism outputting an optimal solution and prove it is group strategyproof. For minimizing the maximum cost, we also design a strategyproof mechanism with approximation ratio 2. In the obnoxious activity scheduling game, each agent prefers his conflict time 𝑡𝑖 to be far away from the activity duration [𝑦, 𝑦 + 𝑑]. We respectively design deterministic and randomized group strategyproof mechanisms with provable approximation ratios and also show the lower bounds. Besides, for extension, we consider the cost/utility as the characteristic function and find group strategyproof mechanisms for minimizing the social cost and maximizing the social utility.