We present a method to find the maximum magnitude of any supply-shortfall service that an aggregator of energy storage devices is able to sell to a grid operator. This is first demonstrated in deterministic settings, then applied to scenarios in which device availabilities are stochastic. In this case we implement chance constraints on the inability to deliver as promised. We show a significant computational improvement in using our method in place of straightforward scenario simulation. As an extension, we present an approximation to this method which allows the determined fleet capability to be applied to any chosen service, rather than having to re-solve the chance-constrained optimisation each time.