In this paper we study different vaccination strategies that could have been implemented for the early COVID-19 pandemic. We use a demographic epidemiological mathematical model based on differential equations in order to investigate the efficacy of a variety of vaccination strategies under limited vaccine supply. We use the number of deaths as the metric to measure the efficacy of each of these strategies. Finding the optimal strategy for the vaccination programs is a complex problem due to the large number of variables that affect the outcomes. The constructed mathematical model takes into account demographic risk factors such as age, comorbidity status and social contacts of the population. We perform simulations to assess the performance of more than three million vaccination strategies which vary depending on the vaccine priority of each group. This study focuses on the scenario corresponding to the early vaccination period in the USA, but can be extended to other countries. The results of this study show the importance of designing an optimal vaccination strategy in order to save human lives. The problem is extremely complex due to the large amount of factors, high dimensionality and nonlinearities. We found that for low/moderate transmission rates the optimal strategy prioritizes high transmission groups, but for high transmission rates, the optimal strategy focuses on groups with high CFRs. The results provide valuable information for the design of optimal vaccination programs. Moreover, the results help to design scientific vaccination guidelines for future pandemics.