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 d with 0 ≤ d ≤ 1, and each agent i wants his private time t_i to be within the activity duration [y, y + d] or at least as close as possible. Thus his cost is the time difference between his time t_i and the activity duration [y, y + d]. The social cost is the summation of all agents’ costs. Our objective is to choose the activity starting time y 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 t_i to be far away from the activity duration [y, y + d]. 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.