|
Abstract:
|
Matching in observational studies is constrained by the computational challenges of deriving such matches. To simplify the problem, existing matching methods focus on specific study designs and use slow or heuristic algorithms. As a result, well-performing matching has not been feasible in studies with large samples or complex designs. In this paper, we introduce a matching method that admits a wide range of designs, has a proven level of optimality and can be derived quickly. The method is a generalization of full matching and inherits its optimality properties. In particular, it does not impose extraneous constraints on the matching and will, therefore, facilitate the matches that best balance covariates. However, unlike traditional full matching, the investigator can specify any desired structure of the matched groups over any number of treatment conditions. We introduce a fast approximation algorithm that derives generalized full matchings in linearithmic time on average. Despite its speed, the algorithm typically performs on par with existing optimal algorithms, and the maximum within-group dissimilarity is guaranteed to be no worse than four times the optimal solution.
|
