The Online Team Formation Problem

The design of mechanisms to create effective teams able to accomplish complex tasks is a key research challenge in online collaborative systems and online labor marketplaces. In the online team formation problem a sequence of tasks arrives in an online fashion, and each task requires a specific set of skills. The goal is to schedule a new team upon arrival of each task, so that each team possesses all skills required by the task. We consider two main aspects of this problem. We first study a model in which compatibility among potential team members is modelled by a social network. The goal is to schedule teams which have small communication overhead and the workload of performing the tasks is balanced among people in the fairest possible way. Next, we consider the problem of assessing the practical benefits of outsourcing tasks versus the formation of teams of experts. At any point in time, there is a core team of hired workers. This team is dynamic: new members can be hired and existing members can be fired. Additionally, some parts of the arriving jobs can be outsourced and thus completed by non-team members. In considering these problems, we focus on the design of efficient online competitive cost-minimizing algorithms and the primal-dual method. The quality of the proposed solutions is evaluated both theoretically and on experiments performed on several examples of collaboration networks and data from large online labor marketplaces. (Joint work with Aris Anagnostopoulos, Carlos Castillo, Adriano Fazzone, Aris Gionis, and Evimaria Terzi.)