In this chapter an approach to ensure safe and deadlock-free navigation for decentralized multi-robot systems operating in constrained environments, including doorways and intersections, is presented. Although many solutions have been proposed that ensure safety and resolve deadlocks, optimally preventing deadlocks in a minimally invasive and decentralized fashion remains an open problem. The objective is first formalized as a noncooperative, noncommunicative, partially observable multi-robot navigation problem in constrained spaces with multiple conflicting agents, which are termed as social mini-games. Formally, a discrete-time optimal receding horizon control problem leveraging control barrier functions for safe long-horizon planning is solved. The approach used in this chapter to ensuring liveness rests on the insight that there exist barrier certificates that allow each robot to preemptively perturb their state in a minimally invasive fashion onto liveness sets, i.e., states where robots are deadlock-free. This approach in simulation as well on physical robots using F1∕10 robots, a Clearpath Jackal, and a Boston Dynamics Spot in a doorway, hallway, and corridor intersection scenario is evaluated. Compared to both fully decentralized and centralized approaches with and without deadlock resolution capabilities, it is demonstrated that the approach used here results in safer, more efficient, and smoother navigation, based on a comprehensive set of metrics including success rate, collision rate, stop time, change in velocity, path deviation, time to goal, and flow rate.