Abstract: Two new algorithms for bipartite matching with respect to a scalar index (e.g., propensity score) are proposed [Ruzankin P.S. (2020) A Fast Algorithm for Maximal Propensity Score Matching. Methodol Comp Appl]. The first algorithm detects the maximal possible number of matched disjoint pairs satisfying a given caliper and constructs a corresponding matching. The second algorithm is nearest neighbor matching (NNM) without replacement under a caliper, followed by optimal rematching. The both algorithms have linearithmic time complexity. In simulations and real-life examples, the first algorithm produced better maximal within-pair score distance compared to NNM, while the second algorithm produced better average within-pair score distance compared to NNM. qmatch R package was developed (github.com/a-tarasenko/qmatch). In our simulations, it took < 0.5 seconds to match 500000 observations for the both implemented algorithms, while for MatchIt R package v. 4.2.0 with NNM, it took 96 minutes on average. The work was supported by Mathematical Center in Akademgorodok under agreement No. 075-15-2019-1675 with the Ministry of Science and Higher Education of the Russian Federation.

Cite: Rusankin P. , Tarasenko A.S.
Fast Algorithms for Propensity Score Matching
Joint Statistical Meetings 2021 08-12 Aug 2021