Self-organising multi-agent systems regulate their components’ behaviour voluntarily, according to a set of socially-constructed, mutually-agreed, and mutable social arrangements. In some systems, these arrangements may be applied with a frequency, at a scale and within implicit cost constraints such that performance becomes a pressing issue. In this context, this paper introduces the Megabike Scenario, which consists of a negotiated agreement on a relatively ‘large’ set of conventional rules and ‘frequent’, ‘democratic’ deliberation and decision-making according to those rules, but a resource-bounded imperative to reach a ‘correct’ decision. A formalism is defined for expressive rule representation combined with efficient and effective rule processing, which is evaluated against five interleaved socio-functional requirements. System performance is also evaluated empirically through simulation. We conclude that to self-organise their social arrangements, agents need some awareness of their own limitations and the value of compromise.