Algorithms for Organizing Human Experts

Day - Time: 12 December 2017, h.14:30
Place: Area della Ricerca CNR di Pisa - Room: C-29
  • Adriano Fazzone (Sapienza University, Rome)

Nicola Tonellotto


Despite the improvement of AI in the last decades, there are still tasks very hard for machines, but easy for humans. Crowdsourcing is a computational paradigm that is successfully used to address problems that require the solution of these types of tasks, by involving human workers in the key steps of the computation. An important characteristic of human workers is their uniqueness: different workers have different profiles and different abilities in solving tasks. In the two contributions collected in this talk, we developed new algorithmic solutions, in the field of Crowdsourcing, that exploit the different level of expertise of workers.
In the first contribution, we address the problem of finding the maximum among a set of elements in a Crowdsourcing scenario. We present a computational model for crowdsourcing that envisions two distinct classes of workers with different expertise levels: nai¨ve and expert workers. We use our model to develop and analyze an algorithm for the Max-Finding problem, that is able to exploit the distinctive characteristics of nai¨ve and expert workers. We also evaluate our algorithm on real and synthetic datasets using a real crowdsourcing platform, showing that our approach is also effective in practice.
The second contribution concerns the problem of creating a team of workers for solving tasks that arrive in an online fashion. Due to the online nature of the model, the number and the composition of the tasks is not known a-priori. Moreover, to solve all tasks in input, the structure of the team has to change in time: new members can be hired and existing members can be fired. Additionally, some parts of the arriving tasks can be outsourced and thus completed by non-team members. We developed online algorithms for the problem of finding the cost-minimizing strategy for hiring, firing and outsourcing workers for solving all tasks in the input stream, by taking into account the skills of each available worker. Using a primal-dual scheme, we prove that the developed algorithms have logarithmic competitive-approximation ratios. Finally, we performed experiments with data from three large online labor marketplaces, demonstrating the efficiency and the efficacy of our algorithms in practice.

Bio: Adriano Fazzone recently got a Ph.D. in "Engineering in Computer Science" at DIAG-Sapienza-University-of-Rome, where he got also both his B.S. and M.S. Adriano's research interests have been focussed on the design of algorithms for Data-Crowdsourcing problems. He has also interest in Data-Mining and Information-Retrieval.