Crowd work is a term often adopted to identify networked systems that can be used for the solution of a wide range of complex problems by integrating a large number of human and/or computer efforts. Among several different types of crowd work systems that are already operational in the Internet, a large research effort has been devoted to characterize the performance of microtask-based crowd work systems. The key characteristic of these systems is that a requester structures his problem in a set of tasks, and then assigns tasks to workers, whose answers are then used to determine the correct task solution through a decision rule. A well-known example of such systems is Amazon Mechanical Turk, which allows the employment of large numbers of low-wage workers for tasks requiring human intelligence. Some believe that microtask-based crowd work systems will provide a significant new type of work organization paradigm, and will employ ever increasing numbers of workers in the future, provided that the main challenges in this new type of organizations are correctly solved.
Since task execution is typically tedious, and the economic reward for workers is pretty small, workers are not 100% reliable, in the sense that they may provide incorrect answers. Hence, in most practical cases, the same task is replicated to several workers, and then a majority decision rule is applied to their answers. A natural trade-off between reliability of the decision and cost arises; indeed, by increasing the replication factor of every task, we generally increase the reliability degree of the final decision about the task solution, but we necessarily incur higher costs. To minimize the costs, the allocation of tasks to workers (or, equivalently, of workers to tasks) is of key relevance to the system performance. As a consequence, a reliable form of worker reputation plays an essential role in the optimization of microtask-based crowd work systems.
The goal of our work is to provide the first systematic analysis of the potential benefits deriving from some form of a-priori knowledge about the reputation of workers. With this goal in mind, first we define and analyze the task assignment problem when workers' reputation estimates are available. In particular, we suppose that available workers are divided into classes, each of which represents a different reliability level. Under this hypothesis, we show that in some conditions, a greedy task assignment algorithm with performance guarantees can be devised. In addition, we propose two different decision rules. The first (MAP decision rule) is optimal if the workers' reputation estimates are perfect. The second (message-passing decision algorithm) is an iterative algorithm that is able not only to encompass imperfect workers' reputation estimates, but also to refine such estimates based on the provided answers.
Our main findings are:
o even largely inaccurate estimates of workers' reputation can be effectively exploited in the task assignment to greatly improve system performance;
o the performance of the MAP decision rule quickly degrades as worker reputation estimates become inaccurate;
o when workers' reputation estimates are significantly inaccurate, the best performance can be obtained by combining our proposed task assignment algorithm with the message-passing decision algorithm;
o there is no need for a large number of refined classes, i.e., a coarse quantization of individual reputations already achieves most of the related gain.
More details in: A. Tarable, A. Nordio, E. Leonardi, M. Ajmone Marsan, "The Importance of Worker Reputation Information in Microtask-Based Crowd Work Systems", IEEE Transactions on Parallel and Distributed Systems, vol. 28, no. 2, pp. 558-571, February 2017.
ITALIANO
"L'importanza della reputazione dei lavoratori nei sistemi di crowd-work"
"Crowd-work" è un termine spesso adottato per identificare sistemi di rete che possono essere utilizzati per la soluzione di una vasta gamma di problemi complessi grazie all'integrazione di un gran numero di sforzi umani e/o informatici. Tra i diversi tipi di sistemi di crowd-work che sono già operativi in Internet, un grande sforzo di ricerca è stato dedicato a caratterizzare le prestazioni dei sistemi di crowd-work basati su microtask. La caratteristica principale di questi sistemi è che un richiedente struttura il suo problema in una serie di compiti, e quindi assegna tali compiti ai lavoratori, le cui risposte vengono poi utilizzate per determinare la soluzione corretta del problema attraverso una regola di decisione. Un esempio ben noto di tali sistemi è Amazon Mechanical Turk, che consente l'impiego di un gran numero di lavoratori a basso salario per compiti che richiedono intelligenza umana. Taluni credono che i sistemi di crowd-work basati su microtask forniranno un significativo nuovo paradigma di organizzazione del lavoro, e impiegheranno in futuro un sempre crescente numero di lavoratori, a condizione che le principali sfide legate a questo nuovo tipo di organizzazione siano correttamente affrontate.
Dal momento che l'esecuzione dei compiti è tipicamente noiosa, e la ricompensa economica per i lavoratori è piuttosto esigua, i lavoratori non sono affidabili al 100%, nel senso che essi possono fornire risposte errate. Pertanto, in gran parte dei casi pratici, lo stesso compito viene assegnato a diversi lavoratori, e poi una regola di decisione a maggioranza viene applicato alle loro risposte. Un naturale compromesso tra l'affidabilità della decisione e il costo si pone; anzi, aumentando il fattore di replicazione di ogni compito, in genere aumenta il grado di affidabilità della decisione finale circa la soluzione del problema, ma necessariamente si sostengono costi più elevati. Per ridurre al minimo i costi, l'assegnazione dei compiti ai lavoratori (o, equivalentemente, dei lavoratori ai compiti) è di importanza fondamentale per le prestazioni del sistema. Di conseguenza, una forma affidabile di reputazione del lavoratore svolge un ruolo essenziale nella ottimizzazione dei sistemi di crowd-work basati su microtask.
L'obiettivo del nostro lavoro è quello di fornire la prima analisi sistematica dei potenziali benefici derivanti da una qualche forma di conoscenza a-priori circa la reputazione dei lavoratori. Con questo obiettivo in mente, per prima cosa si è provveduto a definire e analizzare il problema dell'assegnazione dei compiti quando le stime di reputazione dei lavoratori siano disponibili. In particolare, si suppone che i lavoratori disponibili siano suddivisi in classi, ciascuna delle quali rappresenta un livello di affidabilità differente. In base a tale ipotesi, si dimostra che in alcune condizioni, si può definire un algoritmo di assegnazione dei compiti greedy con garanzie formali di prestazione. Inoltre, proponiamo due regole di decisione diverse. La prima (regola di decisione MAP) è ottimale se le stime di reputazione dei lavoratori sono perfette. La seconda (algoritmo di message-passing) è un algoritmo iterativo che è in grado non solo di utilizzare stime imperfette di reputazione dei lavoratori, ma anche di affinare tali stime sulla base delle risposte fornite.
I nostri risultati principali sono:
o anche stime largamente imprecise della reputazione dei lavoratori possono essere efficacemente utilizzate nell'assegnazione dei compiti per migliorare notevolmente le prestazioni del sistema;
o le prestazioni della regola di decisione MAP degradano rapidamente se le stime della reputazione dei lavoratori diventano imprecise;
o quando la reputazione stimata dei lavoratori è significativamente inesatta, le migliori prestazioni si possono ottenere combinando il nostro algoritmo di assegnazione dei compiti con l'algoritmo di message-passing;
o non vi è alcuna necessità di un gran numero di classi di affidabilità, dal momento che una quantizzazione grossolana delle reputazioni individuali garantisce già gran parte del relativo guadagno.
Per maggiori dettagli: A. Tarable, A. Nordio, E. Leonardi, M. Ajmone Marsan, "The Importance of Worker Reputation Information in Microtask-Based Crowd Work Systems", IEEE Transactions on Parallel and Distributed Systems, vol. 28, no. 2, pp. 558-571, February 2017.
Focus