Polynomial-Time Multi-Agent Pathfinding with Heterogeneous and Self-Interested Agents

This paper proposes a polynomial-time strategyproof mechanism that solves multi-agent pathfinding (MAPF) problems with heterogeneous and self-interested agents. In MAPF, agents need to reach their goal destinations while avoiding collisions between them. In this paper, we consider heterogeneous and self-interested MAPF. Agents are heterogeneous if the costs of traversing a given path differ between agents. In particular, we assume each agent has a private linear cost function of travel time. The proposed strategyproof mechanisms aim to make agents truthfully declare the slope of the private linear cost function.