Multi-robot systems have the potential to improve performance through parallelism. Unfortunately, interference often diminishes those returns. Starting from the earliest multi-robot research, a variety of arbitration mechanisms have been proposed to maximize speed-up. Vaughan and his collaborators demonstrated the effectiveness of an arbitration mechanism inspired by biological signalling where the level of aggression displayed by each agent effectively prioritizes the limited resources. But most often these arbitration mechanisms did not do any principled consideration of environmental constraints or task structure, signalling cost and precision of the outcome. These factors have been taken into consideration in this research and a taxonomy of the arbitration mechanisms have been presented. The taxonomy organizes prior techniques and newly introduced novel techniques. The latter include theoretical and practical mechanisms (from minimalist to especially efficient). Practicable mechanisms were evaluated on physical robots for which both data and models are presented. The arbitration mechanisms described span a whole gamut from implicit (in case of robotics, entirely without representation) to deliberately coordinated (via an established Biological model, reformulated from a Bayesian perspective). Another significant result of this thesis is a systematic characterization of system performance across parameters that describe the task structure: patterns of interference are related to a set of strings that can be expressed exactly. This analysis of the domain has the important (and rare) property of completeness, i.e., all possible abstract variations of the task are understood. This research presents efficiency results showing that a characterization for any given instance can be obtained in sub-linear time. It has been shown, by construction, that: (1) Even an ideal arbitration mechanism can perform arbitrarily poorly; (2) Agents may manipulate task-structure for individual and collective good; (3) Task variations affect the influence that initial conditions have on long-term behaviour; (4) The most complex interference dynamics possible for the scenario is a limit cycle behaviour.