  Estimation of population size using incomplete lists (also called the
capture-recapture problem) has a long history across many biological and social
sciences. For example, human rights and other groups often construct partial
and overlapping lists of victims of armed conflicts, with the hope of using
this information to estimate the total number of victims. Earlier statistical
methods for this setup either use potentially restrictive parametric
assumptions, or else rely on typically suboptimal plug-in-type nonparametric
estimators; however, both approaches can lead to substantial bias, the former
via model misspecification and the latter via smoothing. Under an identifying
assumption that two lists are conditionally independent given measured
covariate information, we make several contributions. First we derive the
nonparametric efficiency bound for estimating the capture probability, which
indicates the best possible performance of any estimator, and sheds light on
the statistical limits of capture-recapture methods. Then we present a new
estimator, and study its finite-sample properties, showing that it has a double
robustness property new to capture-recapture, and that it is near-optimal in a
non-asymptotic sense, under relatively mild nonparametric conditions. Next, we
give a method for constructing confidence intervals for total population size
from generic capture probability estimators, and prove non-asymptotic
near-validity. Finally, we study our methods in simulations, and apply them to
estimate the number of killings and disappearances attributable to different
groups in Peru during its internal armed conflict between 1980 and 2000.
