  We propose a decentralized collision-avoidance mechanism for a group of
independently controlled robots moving on a shared workspace. Existing
algorithms achieve multi-robot collision avoidance either (a) in a centralized
setting, or (b) in a decentralized setting with collaborative robots. We focus
on the setting with competitive robots in a decentralized environment, where
robots may strategically reveal their information to get prioritized. We
propose the mechanism SPARCAS in this setting that, using principles of
mechanism design, ensures truthful revelation of the robots' private
information and provides locally efficient movement of the robots. It is free
from collisions and deadlocks, and handles a dynamic arrival of robots. In
practice, this mechanism scales well for a large number of robots where the
optimal collision-avoiding path-finding algorithm (M*) does not scale. Yet,
SPARCAS does not compromise the path optimality too much. Our mechanism
prioritizes the robots in the order of their `true' higher needs, but for a
higher payment. It uses monetary transfers which is small enough compared to
the value received by the robots.
