  Multi-Agent Path Finding (MAPF) involves determining paths for multiple
agents to travel simultaneously and collision-free through a shared area toward
given goal locations. This problem is computationally complex, especially when
dealing with large numbers of agents, as is common in realistic applications
like autonomous vehicle coordination. Finding an optimal solution is often
computationally infeasible, making the use of approximate, suboptimal
algorithms essential. Adding to the complexity, agents might act in a
self-interested and strategic way, possibly misrepresenting their goals to the
MAPF algorithm if it benefits them. Although the field of mechanism design
offers tools to align incentives, using these tools without careful
consideration can fail when only having access to approximately optimal
outcomes. In this work, we introduce the problem of scalable mechanism design
for MAPF and propose three strategyproof mechanisms, two of which even use
approximate MAPF algorithms. We test our mechanisms on realistic MAPF domains
with problem sizes ranging from dozens to hundreds of agents. We find that they
improve welfare beyond a simple baseline.
