To estimate the distribution of the number of acquaintances of the members of a society, the network scale-up method asks survey respondents about the number of people they know with features for which national statistics are available. While many features have been used for this purpose, first names have been suggested to produce particularly low levels of transmission error and recall bias. For this method to be precise, a set of names needs to be selected for the survey that jointly represents the population in relevant variables such as gender or age. This article provides a solution approach to finding the optimal set of names. This can be applied to any population for which a joint distribution of first names and relevant variables is available. We show that our approach successfully provides sets of names closely mirroring the population distributions for six countries with different name statistics.