Online team formation in social networks

We study the problem of online team formation. We con- sider 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 re- quirements: 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. Experi- ments performed on collaboration networks among film ac- tors and scientists, confirm that our algorithms are success- ful at balancing these conflicting requirements. This is the first paper that simultaneously addresses all these aspects. Previous work has either focused on minimiz- ing coordination for a single task or balancing the workload neglecting coordination costs.