Despite advances in deep learning and facial recognition techniques, the problem of fault-intolerant facial recognition remains challenging. With the current state of progress in the field of automatic face recognition and the in-feasibility of fully manual recognition, the situation calls for human-machine collaborative methods. We design a system that uses machine predictions for a given face to generate queries that are answered by human experts to provide the system with the information required to predict the identity of the face correctly. We use a Markov Decision Process for which we devise an appropriate query structure and a reward structure to generate these queries in a budget or accuracy-constrained setting. Finally, as we do not know the capabilities of the human experts involved, we model each human as a bandit and adopt a multi-armed bandit approach with consensus queries to efficiently estimate their individual accuracies, enabling us to maximize the accuracy of our system. Through careful analysis and experimentation on real-world data-sets using humans, we show that our system outperforms methods that exploit only machine intelligence, simultaneously being highly cost-efficient as compared to fully manual methods. In summary, our system uses human-machine collaboration for face recognition problem more intelligently and efficiently. © 2020 Association for Computing Machinery.