A note on optimal matching with variable controls using the assignment algorithm

The assignment algorithm is an old, well-known, widely implemented, fast, c ombinatorial algorithm for optimal matching in a bipartite graph. This note proposes a method for using the assignment algorithm to solve the problem of optimal matching with a variable number of controls, in which there is a choice not only of who to select as a control for each treated subject, bu t also of how many controls to have for each treated subject. The strategy uses multiple copies of treated subjects and sinks with zero cost to absorb extra controls. Also, it is shown that an optimal matching with variable n umbers of controls cannot be obtained by starting with an optimal pair matc hing and adding the closest additional controls. An example involving morta lity after surgery in Pennsylvania hospitals is used to illustrate the meth od.