The paper generalizes the notion of a social law, the foundation of the theory of artificial social systems developed for coordinating Multi-Agent Systems. In an artificial social system, its constituent agents are given a common social law to obey and are free to act within the confines it legislates, which are carefully designed to avoid inter-agent conflict and deadlock. In this paper, we argue that social laws can be overly restrictive in that they indiscriminately apply to all distributions of agent behavior, even when the probability of conflicting conditions arising is acceptably small. We define the notion of a non-deterministic social law applicable to a family of probability distributions that describe the expected behaviors of a system’s agents. We demonstrate that taking these distributions into account can lead to the formulation of more efficient social laws and the algorithms that adhere to them. We illustrate our approach with a traffic domain problem and demonstrate its utility through an extensive series of simulations.