On Monday morning, three auto-piloted jetliners are flying on a collision course. How should the air traffic controller reroute them to avoid collisions and minimize delays? Meanwhile, a fleet of automated heavy-duty delivery trucks is completing tasks across a congested road network. Which route should they take to minimize traffic impact and fuel consumption? As transportation systems evolve towards autonomy on a larger scale, coordinating them safely and efficiently becomes unprecedentedly complicated. To fight the inherent complexity that grows factorially with the number of interacting robots, we introduce Branch and Play (B&P), an efficient and scalable game-theoretic algorithm that rapidly computes the socially optimal coordination plan and the associated order of play, i.e., the sequence in which the robots commit to their decisions. We showcase the versatility and efficiency of B&P through an extensive experiment campaign on simulated air traffic control, quadrotor swarm formation, and hardware demonstration of coordinating an autonomous delivery truck fleet in a mini-city. We show that B&P consistently outperforms state-of-the-art multi-robot planning baselines, significantly improving coordination efficiency and robustness.