An approximation algorithm for blocking of an experimental design

Blocked randomized designs are used to improve the precision of treatment effect estimates compared to a completely randomized design. A block is a set of units that are relatively homogeneous and consequently would tend to produce relatively similar outcomes if the treatment had no effect. The problem of finding the optimal blocking of the units into equal sized blocks of any given size larger than two is known to be a difficult problem—there is no polynomial time method guaranteed to find the optimal blocking. All available methods to solve the problem are heuristic methods. We propose methods that run in polynomial time and guarantee a blocking that is provably close to the optimal blocking. In all our simulation studies, the proposed methods perform better, create better homogeneous blocks, compared with the existing methods. Our blocking method aims to minimize the maximum of all pairwise differences of units in the same block. We show that bounding this maximum difference ensures that the error in the average treatment effect estimate is similarly bounded for all treatment assignments. In contrast, if the blocking bounds the average or sum of these differences, the error in the average treatment effect estimate can still be large in several treatment assignments.