Randomized Strategyproof Mechanisms for Multi-Stage Facility Location Problem with Capacity Constraints

We consider the multi-stage facility location problem with capacity constraints. In the problem, we seek to locate at most one capacity constrained facility in each stage to serve a subset of agents, who arrive over different stages and are located on a line. Our goal is to design randomized strategyproof mechanisms to elicit agents’ true information and locate facilities that minimize the social cost and maximum cost, which are defined to be the sum and the maximum of the agents’ costs, respectively. Because of the stages, an agent’s cost depends on the agent’s distance to their assigned facility and the agent’s waiting cost. For different facility capacity settings with waiting cost, we provide randomized strategyproof mechanisms for the considered cost objectives. We also establish lower bounds for the approximation ratios given by any randomized strategyproof mechanisms.