Online Team Formation in Social Networks
Stefano Leonardi, Sapienza University of Rome
Increasingly, groups of people cooperate and collectively accomplish complex tasks online. The design of mechanisms to create effective teams is a key research challenge. Being part of a team requires being able to communicate effectively with other teammates and complementing each other's skills. In this paper, we study the problem of online team formation. We consider a setting in which people possess different skills and compatibility among potential team members is modeled by a social network. A sequence of tasks arrives in an online fashion, and each task requires a specific set of skills. The goal is to form a new team upon arrival of each task, so that
i) each team possesses all skills required by the task,
ii) each team has small communication overhead, and
iii) the workload of performing the tasks is balanced among people in the fairest possible way.
We propose efficient algorithms that address all these requirements: our algorithms form teams that always satisfy the required skills, provide approximation guarantees with respect to team communication overhead, and they are online-competitive with respect to load balancing. Experiments performed on collaboration networks among film actors and scientists, confirm that our algorithms are successful at balancing these conflicting requirements.
(Joint work with Aris Anagnostopoulos, Luca Becchetti, Carlos Castillo and Arisitides Gionis)