Truthful and Welfare-maximizing Resource Scheduling with Application to Electric Vehicles

We consider the problem of scheduling resources with monetary transfers among agents in a setting where multiple outlets can dispense these resources at different rates within fixed time-slots. This problem is motivated by applications such as electric vehicle (EV) charging where energy is the resource and EVs are available within a convenient time window of its owners. The agents' valuations depend on the contiguous time slots at a given outlet that dispense the resource to them. We show that for monotone and its sub-class of dichotomous valuations, computing the social welfare-maximizing allocation is NP-hard, even if there is only one outlet. For monotone and dichotomous valuations, we provide a randomized 2-approximation mechanism that is truthful in dominant strategies and individually rational for a single outlet and a randomized 𝑂 (√︁ |𝑆 |)-approximation algorithm with the same properties for multiple outlets (𝑆 is the set of time-slots). However, for single-minded valuations, the welfare maximization problem for multiple outlets is in P. This allows us to use standard mechanisms like VCG to ensure truthfulness and individual rationality.