Building Collaborative Teams: A Local Navigation-based Approach - Singla, Adish; Horvitz, Eric; Kohli, Pushmeet; Krause, Andreas; White, Ryen W. (NIPS 2014 Workshop on Crowdsourcing and Machine Learning, Montreal, Quebec, Canada, 2014)
Seeking expertise from others and building teams or coalitions is an important part of collaborative problem solving. We discuss the challenges and opportunities that arise in the context of a human computation system in which individual users possess heterogeneous skills and are embedded in an underlying social network that serves as the backbone of information exchange among them. How do structures of acquaintance networks and the limitation of user’s knowledge to local connections affects her ability to form collaborations? What is the role played by a user based on her skills and network positioning in terms of her ability to contribute to the whole system? In this paper, we seek an answer to these questions, starting with a simple generative model to capture the social structures among heterogeneous population seen in reality. Then, we generalize the challenge of team formation and expertise seeking as that of maximizing a submodular function in a decentralized setting where we only have access to local network knowledge. We discuss how the degree of locality of the network knowledge, complexity of utility functions, as well as the properties of the underlying graph affects the hardness of the problem and the ability to get an approximate solution. Our methodology and findings sheds light on how collaborations form among sets of individuals, which we believe is an under-explored problem in human computation and crowdsourcing systems.