We consider online task computing environments such as volunteer computing platforms running on BOINC (e.g., SETI@) and crowdsourcing platforms such as Amazon’s Mechanical Turk. We model the computations as an Internet-based task computing system under the master-worker paradigm. A master entity sends tasks across the Internet, to worker entities willing to perform a computational task. Workers execute the tasks, and report back the results, completing the computational round. Unfortunately, workers are untrustworthy and might report an incorrect result. Thus, the first research question we answer in this work is how to design a reliable master-worker task computing system. We capture the workers’ behavior through two realistic models:

(1) the “error probability model” which assumes the presence of altruistic workers willing to provide correct results and the presence of troll workers aiming at providing random incorrect results. Both types of workers suffer from an error probability altering their intended response.

(2) The “rationality model” which assumes the presence of altruistic workers, always reporting a correct result, the presence of malicious workers always reporting an incorrect result, and the presence of rational workers following a strategy that will maximize their utility (benefit). The rational workers can choose among two strategies: either be honest and report a correct result, or cheat and report an incorrect result. Our two modeling assumptions on the workers’ behavior are supported by an experimental evaluation we have performed on Amazon Mechanical Turk.

Given the error probability model, we evaluate two reliability techniques: (1) “voting” and (2) “auditing” in terms of task assignments required and time invested for computing correctly a set of tasks with high probability. Considering the rationality model, we take an evolutionary game theoretic approach and we design mechanisms that eventually achieve a reliable computational platform where the master receives the correct task result with probability one and with minimal auditing cost. The designed mechanisms provide incentives to the rational workers, reinforcing their strategy to a correct behavior, while they are complemented by four reputation schemes that cope with malice. Finally, we also design a mechanism that deals with unresponsive workers by keeping a reputation related to the workers’ response rate. The designed mechanism selects the most reliable and active workers in each computational round. Simulations, among other, depict the trade-off between the master’s cost and the time the system needs to reach a state where the master always receives the correct task result. The second research question we answer in this work concerns the fair and efficient distribution of workers among the masters over multiple computational rounds. Masters with similar tasks are competing for the same set of workers at each computational round. Workers must be assigned to the masters in a fair manner; when the master values a worker’s contribution the most. We consider that a master might have a strategic behavior, declaring a dishonest valuation on a worker in each round, in an attempt to increase its benefit. This strategic behavior from the side of the masters might lead to unfair and inefficient assignments

of workers. Applying renowned auction mechanisms to solve the problem at hand can be infeasible since monetary payments are required on the side of the masters. Hence, we present an alternative mechanism for fair and efficient distribution of the workers in the presence of strategic masters, without the use of monetary incentives. We show analytically that our designed mechanism guarantees fairness, is socially efficient, and is truthful. Simulations favourably compare our designed mechanism with two benchmark auction mechanisms.

About Evgenia Christoforou

I am currently a PhD Student at IMDEA Networks while pursuing my PhD in the Department of Mathematical Engineering in Universidad Carlos III. I received my BSc and MSc degree in Computer Science from the University of Cyprus (UCY), Cyprus, in June 2009 and June 2012, respectively. I have worked as a Research Assistant at the University of Cyprus investigating the foundations, principles, feasibility, and cost-reliability tradeoffs of Master-Worker Internet–based computing applications, such as SETI@.

My research is currently focusing on the applications of mechanism design in the field of Networks, Crowdsourcing and Volunteer Computing. In particular I am looking into the problem of achieving reliability in online task computing environments, such as the volunteer computing platforms and other commercial platforms (i.e., as Amazon’s Mechanical Turk). Moreover, I have been working on the problem of designing mechanisms for fair and efficient allocating of resources without the use of payments. I have been disseminating my work for the past six years in renown conferences and journals while I have taken part in national and European project calls. I am a teaching assistant at the Universidad Carlos III and I am actively involved in initiatives that promote the role of research and education in student communities.

Personal site

La defensa de tesis se realizará en inglés

Supervisor de tesis: Dr. Antonio Fernández Anta, IMDEA Networks Institute & Dr. Ángel Sánchez, Universidad Carlos III de Madrid
Universidad: Universidad Carlos III de Madrid, España
Programa de doctorado: Ingeniería Telemática