EPJ Data Sci. (2016) 5: 20
https://doi.org/10.1140/epjds/s13688-016-0082-4

Regular article

Bandit strategies in social search: the case of the DARPA red balloon challenge

¹ Data61 Unit, Commonwealth Scientific and Industrial Research Organization, Melbourne, Victoria, Australia
² Faculty of Information Technology, Monash University, Caulfield, Victoria, Australia
³ The Media Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA

^* e-mail: CaronHaohui.Chen@data61.csiro.au

Received: 16 December 2015
Accepted: 26 May 2016
Published online: 6 June 2016

Abstract

Collective search for people and information has tremendously benefited from emerging communication technologies that leverage the wisdom of the crowds, and has been increasingly influential in solving time-critical tasks such as the DARPA Network Challenge (DNC, also known as the Red Balloon Challenge). However, while collective search often invests significant resources in encouraging the crowd to contribute new information, the effort invested in verifying this information is comparable, yet often neglected in crowdsourcing models. This paper studies how the exploration-verification trade-off displayed by the teams modulated their success in the DNC, as teams had limited human resources that they had to divide between recruitment (exploration) and verification (exploitation). Our analysis suggests that team performance in the DNC can be modelled as a modified multi-armed bandit (MAB) problem, where information arrives to the team originating from sources of different levels of veracity that need to be assessed in real time. We use these insights to build a data-driven agent-based model, based on the DNC’s data, to simulate team performance. The simulation results match the observed teams’ behavior and demonstrate how to achieve the best balance between exploration and exploitation for general time-critical collective search tasks.