Crowdsourcing : relaunching mechanism and parameters optimization

(1)

S

CHOOL OF

I

NDUSTRIAL AND

I

NFORMATION

E

NGINEERING

Master of Science in Computer Science and Engineering

Communication and Society Engineering

C

ROWDSOURCING

:

RELAUNCHING

MECHANISM AND PARAMETERS OPTIMIZATION

Author:

Maria Cristina F

RIGERIO

ID 835991

Supervisor:

Eng. Nicola G

ATTI

Co-supervisor:

Eng. Florian D

ANIEL

(2)

(3)

III

Abstract

Crowdsourcing is an economic model that exploits crowd knowledge and abil-ity to develop and sponsor new ideas, to collect opinions or to complete tasks. Paid crowdsourcing focuses on the latter topic and being a relatively new field, it still requires detailed study to enhance its features.

This thesis deals with (i) the time minimization issue and tries to perform

(ii)parameters’ optimization to cut costs, improve outcomes timing and their quality. To achieve these objectives, this work proposes a relaunching mech-anism based on time deadlines in synergy with a MAB algorithm choosing the best parameter-value combination. Finally, it collects the results of this ap-proach showing that relaunches are a valid tool for reducing task’s execution time, but the fine-tuning of parameters needs a more deeper study, together with the input data of the MAB algorithm.

(4)

(5)

V

Sommario

Crowdsourcing è un modello economico che sfrutta le conoscenze e le abilità delle persone per sviluppare e sponsorizzare nuove idee, per raccogliere opi-nioni e completare degli incarichi. Il crowdsourcing a pagamento si concentra sull’ultimo argomento e, essendo una disciplina relativamente nuova, richiede ancora uno studio approfondito per affinare le sue caratteristiche.

Questa tesi affronta (i) il problema di minimizzazione del tempo e cerca di

(ii)ottimizzare i parametri chiave individuati per contenere i costi, migliorare il tempismo delle risposte e la loro qualità. Per raggiungere questi obiettivi, questo lavoro propone un meccanismo di rilanci basato su dei limiti di tempo in collaborazione con un algoritmo MAB che sceglie la migliore combinazione parametro-valore. Infine, si raccolgono i risultati dell’approccio di cui sopra che da un lato mostrano la validità dei rilanci come strumento per ridurre il tempo di esecuzione degli incarichi, dall’altro mostrano la necessità di un ul-teriore approfondimento sui parametri e i dati di ingresso dell’algoritmo MAB per essere in grado di regolarli meglio.

(6)

(7)

VII

List of Figures

Modeling the problem 17

3.1 Tree representation example with timeline . . . 24

3.2 Parallelism on timeline . . . 25

Identifying parameters’ value 27 4.1 Requester’s payoff . . . 28

4.2 Serious workers/Active cheaters equilibrium . . . 29

4.3 Lazy cheaters equilibrium . . . 30

4.4 No relaunch timeline . . . 34

4.5 One relaunch timeline . . . 35

4.6 Parallel relaunch representation . . . 37

4.7 Iterative relaunch representation . . . 39

4.8 Parallel and iterative representation . . . 40

4.9 Tree representation . . . 41

4.10 Examples of time/budget correlation . . . 43

4.11 Examples of end time/residual budget bounds . . . 44

Application implementation 51 5.1 Average reward graphs and convergence . . . 53

5.2 Job instructions . . . 58

Application implementation 65 6.1 Average reward per arm, per parameter . . . 68

6.2 Box plot of tasks’ units duration . . . 69

(12)

XII

6.4 Cumulative submission time histograms of pw . . . 71

6.5 Overlapping cumulative submission time histograms . . . 72 6.6 Cumulative submission time histograms with same configuration 73 6.7 Costs distribution . . . 76

(13)

XIII

List of Tables

Identifying parameters’ value 27

4.1 Parameters: general range. . . 48

4.2 Parameters: end time optimization . . . 48

4.3 Parameters: residual budget optimization . . . 49

4.4 Parameters: multi purpose optimization . . . 49

Application implementation 51 5.1 Arms’ and fixed parameters’ values . . . 55

5.2 Costs’ details . . . 55

Application implementation 65 6.1 Results: state and percentage . . . 66

6.2 Results: correctness of relaunch mechanism. . . 66

6.3 Payments: percentage of the expected value . . . 75

6.4 Quality: analysis of date field . . . 77

6.5 Quality: fields error percentage . . . 78

(14)

(15)

XV

List of Algorithms

Application implementation 51

5.1 ReLauncher. Relaunching mechanism . . . 59 5.2 ReLauncher. Function periodicCheck() . . . 60 5.3 UCB1 algorithm . . . 62

(16)

(17)

XVII

List of Abbreviations

CML CrowdFlower Markup Language

HTML HyperText Markup Language

JS JavaScript

MAB Multi Armed Bandit

(18)

(19)

XIX

List of Symbols

K total number of assignments for a task

T maximum time granted to complete all the assignments h : min B overall budget allocated for the entire task $ b budget allocated for each single assignment $

Db bonus deadline min

Dr relaunch deadline min

pw basic payoff for the worker $

bw bonus for the worker in case of fast submission $

nh number of horizontal relaunches

nv number of vertical relaunches

l number of simultaneous active levels i first active level

(20)

(21)

1

Chapter 1 Introduction

1.1 The birth of "crowdsourcing"

“Crowdsourcing is the act of taking a job traditionally performed by a designated agent (usually an employee) and outsourcing it to an undefined, generally large group of people in the form of an open call.”[11]

“The application of Open Source principles to fields outside of software.”[11]

Jeff Howe Jeff Howe is the one who coined together with Mark Robinson the term crowd-sourcing in his article "The Rise of Crowdcrowd-sourcing" in 2006 [12]. Crowdcrowd-sourcing can be seen as the technological evolution of outsourcing taking advantage of the networked world full of the productive potential of millions of users and exploiting the much lower cost with respect to traditional employees.

The difference between the two mechanisms is well explained in Howe’s arti-cle by the words of Larry Huston, Procter & Gamble vice president of innova-tion and knowledge at the time: "Outsourcing is when I hire someone to per-form a service and they do it and that’s the end of the relationship. That’s not much different from the way employment has worked throughout the ages. We’re talking about bringing people in from the outside and involving them in this broadly creative, collaborative process. That’s a whole new paradigm". Nevertheless, crowdsourcing’s power was known even before the digital era, as there are examples dated 18th century. Started as idea competitions or in-novation contests, from the early 2000s it became a mean to solve problems, be they business, public or product related.

Getting back to present days, crowdsourcing is about online communities con-tributing with their work to some final purpose. Indeed, there are categories in which crowdsourcing can be divided, according to what the aim really is. In his book [13], Jeff Howe identified four primary strategies, which are:

Crowd Creation As the name suggests, it is about people creating content. It spans many fields as writing, photography, music, film and also science. [Marketing campaign]

(23)

Chapter 1. Introduction 3

Crowd Funding It is about sponsoring projects and ideas that wouldn’t get credit or loan by the traditional system and therefore couldn’t otherwise survive without external financial support. [Kickstarter]

Crowd Voting It is about leveraging users’ opinions and judgements about a certain topic to organize, filter and rate content. It generates the highest levels of participation. [Movie rating]

Crowd Wisdom It is founded on the statement "Given the right set of condi-tions, the crowd will almost always outperform any number of employ-ees". It exploits people’s knowledge to solve problems, making predic-tions or direct corporate strategy. [Wikipedia]

The common basis of all these crowdsourcing’s strategies is having a very large amount of data involved in the process and requiring human intelligence to sort it out.

The use of crowdsourcing systems may lead to improvements in terms of

Costs the more available a good, the lower its price (e.g. with the rise of plat-forms gathering amateur photographers, the photo’s monetary value of professional ones has decreased).

Time the greater the crowd, the less time needed to complete the same work.

Scalability the greater the crowd, the more man hours available simultane-ously to process large amount of data (it is like increasing the hardware available).

Flexibility a greater job can be divided into many similar small tasks.

Diversity different people from different countries each carrying their own knowledge and experience.

(24)

4 Chapter 1. Introduction

1.2 Thesis aim

Among all the variety of crowdsourcing cases there are paid platforms. They handle large amounts of work by decomposing them into microtasks: same, small, pretty straightforward jobs that will be solved by workers, like tagging pictures or transcribing receipt.

The general aim of this thesis is to provide a reliable mechanism for this kind of platforms that will guarantee increased performance on the requester side in time and budget management of the tasks. More precisely, the proposed mechanism’s goal is twofold:

1. minimization of the overall execution time of the task by means of re-launches;

2. study of a parameters’ optimization method involving payment, bonus, time deadlines and number of relaunches.

The approach consists in an application able to interact with the crowdsourc-ing platform, CrowdFlower, and, by trackcrowdsourc-ing the assignments duration, to re-launch those exceeding a predefined time threshold. The rere-launch act makes assignments available again in a shorter time with respect to the platform expi-ration time so that the overall execution time doesn’t get too stretched. More-over, the application of this mechanism results in finding the most appropriate combination of parameters’ values given the twofold objective and the task type.

However, the relaunching process is not trivially achieved. For the approach to operate properly, it needs a previous accurate study, in order to provide all the required elements on which to build the application. Indeed, the starting point consists in identifying the parameters involved in the microtasking pro-cess and, given the test task, their candidate values. The mechanism is then composed of several blocks: a MAB algorithm to pick the best value per pa-rameter; a Firebase application to track running assignments; a Node.js appli-cation connecting all the pieces to actually perform relaunches.

(25)

Chapter 1. Introduction 5

1.3 Thesis structure

The first part of the thesis consists of the theoretical ground setting.

In Chapter 2 there is the analysis of the state of the art regarding crowdsourc-ing. After defining microtasking, it narrows it down to the paid crowdsourcing systems to then provide general information about the context. Finally, it ana-lyzes the related work, focusing on time minimization topic.

Chapter 3 describes the problem and what can be done to overcome it, intro-ducing the parameters that are the key to the solution.

The second part deals with the actual research of the thesis.

Chapter 4 shows the different factors that come into play in the crowdsourcing environment. It describes their characteristics and explains how they influence the reasoning made in order to achieve the intended result and then it handles the ranges of the parameters and tries to identify in a theoretical way their best combination in order to achieve the purpose.

Chapter 5 is about the actual implementation of the application in all its part: CrowdFlower platform, the ReLauncher application, Firebase and JavaScript logger and MAB block.

The results of their implementation is summarized in Chapter 6 going from more general observation to the actual cost expense and the findings on pa-rameters’ values.

In Chapter 7 there are the comments of the entire work and the possible devel-opments for future work.

(26)

(27)

7

Chapter 2 State of the Art

2.1 Microtasking

Microtasking is the process of splitting a large job into a series of small tasks, or microwork, that can be distributed, over the Internet, to many people [24, 29]. These kind of tasks are repetitive and time-consuming, but not so simple to be automated, thus requiring human intelligence in order to complete reliably. They are characterized by large volume, independency and, indeed, human judgement. However, they are considered simple in that they usually don’t ask for specific skills and training.

To obtain more accurate and valuable results, it is useful to back tasks up with an objective set of rules, so to guide workers to a compliant outcome without risking it to be declared null.

Microtasking is largely adopted to process data online like labeling, transcrip-tion and translatranscrip-tion, actranscrip-tions that perfectly comply to the above requirements, but also to perform social studies. Workers complete tasks on a voluntary basis and receive payments directly over the Internet. Requesters exploit the work-force available concurrently so that even great amount of data requiring many man hours can be processed in much shorter time. That of reducing time-consuming tasks is, indeed, a major benefit provided by microtasking.

Nevertheless, it also introduces disadvantages like that of quality control of the results submitted by the workers.

2.2 Systems executing tasks and tactics

Crowdsourcing is very adaptable and flexibile and thus it can be applied to many different domains. What they all have in common is them facing human-centric challenges, that’s why a crowdsourcing system enlists a crowd of hu-mans to help solve a problem defined by the system itself and that’s why Anhai Doan defines it as a general-purpose problem-solving method [8].

Of all the crowdsourcing systems described in the paper, this thesis focuses on explicit systems that, as the name already suggests, start an explicit collabo-ration with the users. In turn, they are classified in more precise subgroups,

(29)

Chapter 2. State of the Art 9 among which systems executing tasks stand out.

This category deals with finding the task parts that can be subject to crowd-sourcing. Many of the jobs to be crowdsourced are those that cannot be auto-mated, can be divided into steps with objective rules and can be carried out online. All this in order to receive contributions from the users and combining them together to solve the initial problem. In this way, problems are solved in a divide-et-impera fashion to minimize resources as, for instance, time and money.

While finding such parts is task specific, the act of crowdsourcing them can be generalized. However, this generalization is based upon the task complexity and the task aim. Indeed, microtasks of limited complexity don’t need a dedi-cated negotiation process between requester and workers. For this reason, the best environment to collect them is the one implementing the marketplace tactic: rewards are set by the requester and if workers find it satisfactory for the effort required, they will commit to it [26].

That’s what specific platforms such as CrowdFlower and Amazon Mechanical Turk are for, which rely on paying users as a recruitment strategy and use a measure of trust and reputation to retain them.

The principle on which these paid crowdsourcing systems are based is that crowdsourcing work should be distributed between human users and ma-chines according to what each of them is best at, in a complementary and synergistic fashion. The resulting pool of people willing to work on the same initiative makes hundreds, or even thousands, of man hours available, thus reducing the overall effort. That is an example of the power of collective intel-ligence [13].

2.3 Crowdsourcing context: general information

The need of a new research direction stems from the Internet era where appli-cations require redefined methodologies that better analyzes them.

Crowdsourcing violates the basic assumptions of both machine learning (data

(30)

10 Chapter 2. State of the Art being independent from the model to be learned) and game theory (agents be-ing fully rational). Therefore, in [19], Liu et al. propose a different approach called mechanism learning with mechanism induced data that starts with a behav-ior model of the agents inferred from historical data to then optimize the mech-anism in order to predict future behaviors.

The vast majority of papers about crowdsourcing takes into account the first and most known platform about paid-crowdsourcing, Amazon Mechanical Turk, despite its not being the best one in terms of features offered [27]. How-ever, in this study the platform used is CrowdFlower. That’s why the infor-mation extracted from papers and collected in this and the following section will be general considerations applicable to every other paid-crowdsourcing platform.

2.3.1 Task categorization

Crowdsourcing offers the opportunity to solve those jobs that cannot be auto-mated and that require human interaction for many man/hour.

These tasks differ a lot from each other in terms of complexity, duration and, of course, subject. That is why they need to be classified according to the features that characterize them.

Gadiraju et al. present a profiling study on workers and propose a classifi-cation of tasks according to their goal. For this study [10], they collected in-formation on the crowdsourcing environment by means of a survey. One of the research questions was about the main factors that influence the worker’s choice in the task to complete. The ranking is computed based on a Likert-type question asked to 1000 workers: the monetary incentive offered is the most crucial one (4.02), the time required to complete the job (3.76) and the at-tractiveness of the topic (3.69) follow with marginal difference between them. Also ease of completion of a task plays an important role in the choice of job. In their paper, Gadiraju et al. also define six classes based on their goal that describe typically crowdsourced task:

(31)

Chapter 2. State of the Art 11

Information Finding (IF) It delegates the search for a particular piece or set of information to the worker.

Verification and Validation (VV) Workers have to check if given aspects com-ply to specific instructions or confirm that the content is appropriate.

Interpretation and Analysis (IA) It exploits crowd wisdom and uses work-ers’ interpretation skills.

Content Creation (CC) It asks for content generation, whether it’s suggesting names or summarizing documents.

Surveys (S) It allows to collect information from a wide and varying pool of people.

Content Access (CA) It just asks to access some content.

Each of these classes can have sub-classes that stand out due to their work-flow. Some of these are identified by [5] as common use cases:

Sentiment Analysis It asks for the interpretation of a specific content to tell its meaning.

Categorization Given a set of objects, it wants the category to which each of the item belongs based on specified criteria.

Content Moderation It asks contributors to adjust the content in order to com-ply to a set of objective rules.

Business Listing Verification Workers control the truthfulness of the business data of the requester.

Data Collection and Enhancement It is about the research of new or updated data.

Search Relevance It asks for the creation of training data for an algorithm.

Media Transcription Contributors have to fill data with the information that is written on photos.

The task used in this thesis belongs to the Content Creation category, more specifically to the Media Transcription one. Focusing on this class, Gadiraju et al. observe that it is the one requiring more effort to complete. Still, it has high attractiveness for workers. Moreover, according to [7], Content Creation is the most popular type of task in the 2009 - 2014 period.

(32)

12 Chapter 2. State of the Art

2.3.2 Pricing schemes and monetary incentives

The subject regarding prices and monetary expense is one of the most cov-ered in crowdsourcing literature. Indeed, there are many studies that tackle the pricing mechanism problem, which relies in the limited features offered for the pricing system in crowdsourcing platforms.

In [6], Difallah et al. deal with different pricing schemes in order to reduce both the overall execution time and the latency of workers. The assumption is that the worker population is low and there is the need of keeping people working longer on batches.

According to their results, a fixed pricing scheme, which is the basic one in almost every crowdsourcing platform, is not as appealing as other options can be in retaining workers. On the other hand, when a training phase is required to complete the job, overpaying workers at the beginning of the task seems to compensate the learning effort. However, it is the milestone pricing scheme the one with best performance, independently from the type of task.

Difallah et al. identify trends from aggregated data over time (2009 - 2014) in a following paper [7]. One of the analysis regards task reward and figures show that there is an upward tendency: in 2011, the most popular payment was $0.01; in 2014 it was $0.05. This fact is also related to the increased com-plexity of tasks over time.

In his article [14], Ipeirotis computes the distribution of HITs according to the price and the collected data shows that 25 percent of the HITs created on Me-chanical Turk have a price tag of just $0.01, 70 percent have a reward of $0.05 or less, and 90 percent pay less than $0.10.

High monetary incentive is not always the best solution against HITs starva-tion or lower start time. In fact, monetary rewards offered for the tasks that are typically crowdsourced are proportional to the amount of effort that is ex-pected for task completion by the crowd workers. Therefore, higher payments correspond to an increased complexity of the job, which also require more time to be completed. As observed in [10] above, workers value positively both the ease of completion and the amount of time needed to finish the task. So it can Crowdsourcing: relaunching mechanism and parameters optimization

(33)

Chapter 2. State of the Art 13 happen that high reward tasks are left behind in favor of an easier one.

This phenomenon is known as Simpson’s paradox, in which a trend appears in different groups of data, but it can disappear or reverse in others [22]. It oc-curred in [9], where one of the outcome of their work is that increasing the reward decreases the demand for the task, due to the fact that a higher pay involves higher complexity, thus leading to a lower utility for the worker. In [20], Mason and Watts perform two different tests that show that paying par-ticipants to work generates more work than not paying them. These results are consistent with standard economic theory, which predicts that the more a per-son is paid to do something, the more of that something they will do [18, 21]. Moreover, the outcome of the post-task survey shows that, independently from the payment received, workers felt that the appropriate reward for the work they had just performed was greater than what they had received, but the val-ues they expressed depended significantly on their actual compensation. This phenomenon is known as anchoring effect, which is a cognitive bias that occurs in decision making. It describes the common human tendency to rely too heavily on the first piece of information offered. All subsequent judgments revolve around the anchor [1].

2.3.3 Quality check

Crowdsourcing has a huge potential, but if the results are not fit for use, it is worthless. In order to achieve high-quality results, requesters might have to pay more their workers; sometimes they even need to employ an expert to check the outputs.

As quality of the results is related, the findings in Difallah’s work [6] tell that the average precision of results doesn’t depend on how many tasks workers complete. However, the standard deviation is higher for workers dropping out early, while long-term workers never yield low performance results. In [20], Mason and Watts aim at finding a correlation between financial incen-tives and performance of the outputs. Their conclusions show that it’s not how much a worker is paid that affects the accuracy of the outcome, but how they Crowdsourcing: relaunching mechanism and parameters optimization

(34)

14 Chapter 2. State of the Art are paid.

In the first case, due to the anchoring effect described above, workers feel like they are being rewarded less than they deserve. Therefore, they aren’t enough motivated to perform better, no matter how much they are actually paid. In the second case, findings tell that particular designs of the compensation scheme can have a significant effect on quality. Indeed, in the tests performed, a "quota" system results in better work for less pay than an equivalent "piece rate" system.

Kucherbaev et al. aim at improving the accuracy of a task by relaunching as-signments in [15]. Generally, it seems that an increase in reward can improve the accuracy. Also, assignments that are submitted in very short time are often an indicator of low accuracy in a setting with no or few input aids. Indeed, as they increase, so does the accuracy. The point is how to detect those as-signments that will produce inaccurate results by means of task-independent meta-data.

Assignment duration analysis Order all finished assignments from fastest to slowest and identify the outliers to be relaunched by using the Nearest Ranking method. Minimum assignment duration analysis - DurMin.

Interaction analysis Use the same technique as the AbandonB above, but in the training set assignments are label as accurate or not. Inaccurate

be-havior analysis- InaccB.

The performance of both techniques depends on the class of the task. Indeed, they don’t work well with assignments very fast by nature. However, they both provide benefits. Specifically, in an online setting InaccB allows to achieve an average accuracy of 95.56% with a cost overhead of 10.67%.

2.4 Related work: time minimization

Thanks to its scalability feature, crowdsourcing guarantees that a job will need less time than when assigned to just one person. However, time stretches due to abandonment or task starvation. While there are papers on the latter topic that look for the causes and suggest how to keep workers on the task [6], there Crowdsourcing: relaunching mechanism and parameters optimization

(35)

Chapter 2. State of the Art 15 aren’t many covering the former one.

Kucherbaev et al. focus on this subject and in [17] propose ReLauncher, an approach to identify likely abandoned assignments and relaunch them before the platform expiration time. Without this implementation, an abandoned as-signment will not be available to other workers until it expires, causing delays in the task completion: the long tail problem. The actual implementation will be analyzed later in Chapter 5 as it is the method used in this thesis.

In a following study [15], Kucherbaev et al. continue and deepen the topic con-firming that the slow task execution is caused by assignments’ abandonment, which can be detected based on different logics.

Assignment duration analysis Extract data from completed assignments to build a regression model and identify a threshold above which ments not yet submitted are considered abandoned. Maximum

assign-ment duration analysis- DurMax.

Interaction analysis - Heuristic technique Monitor the stream of events occur-ring at client-side: if it is interrupted or there is no relevant interaction for more than a decision time δ, then it is considered abandoned. Tab

visi-bility analysis- TabVis.

Interaction analysis - Probabilistic technique Compute decision trees by ap-plying recursive partitioning based on client-side events and then use it to predict other similar tasks. It is built upon a training set where as-signments are label as abandoned or not. It suits tasks belonging to the Information Finding class. Abandoning behavior analysis - AbandonB. These methods improve the overall time execution. In particular, in an online setting TabVis is able to consistently shorten the task duration by -45.86% on average with an increase in cost of just 0.33%.

In [3], Boutsis and Kalogeraki present REACT, a middleware whose aim is to schedule tasks to workers under time constraints. It dynamically assigns in-coming tasks to the most appropriate workers - one task at a time - based on their profiles, skills and real-time computational capabilities. Therefore, this

(36)

16 Chapter 2. State of the Art paper deals with both the extended execution time problem, which also in-cludes assignments abandonment, and the absence of a task assignment pol-icy.

The model behind this approach is built as an online Weighted Bipartite Graph Matching problem and exploits an algorithm to maximize the probability of choosing the right worker. Results show that this procedure actually selects the proper workers and it decreases the execution time up to 45

(37)

17

Chapter 3 Modeling the problem

3.1 The scenario

Crowdsourcing offers the opportunity to speed up those processes that are not subject to the usual automation workflow, as the kind of data involved re-quires human interaction. However, platforms that support a crowdsourcing-oriented working space don’t always guarantee specific tools that can improve the control over the working experience on the requester side.

3.1.1 The root of the problem

Paid crowdsourcing platforms build a communication network between re-questers that submit tasks and workers that solve them. They supervise the process and provide a set of rules and policies to better fit task requirements. Still, more features are needed to satisfy budget constraints and reduce overall time execution. Especially task execution timeliness is a known open issue in crowdsourcing, hardly ever examined by researchers.

Satisfying budget constraints means taking into account all the sources of cost (e.g. workers’ payment, platform related expense) and considering the worst case scenario. If the sum doesn’t exceed the maximum cap established, then the actual cost will be compliant to the specifics of the budget.

Even though it may seem trivial, with a relaunch mechanism and a bonus pol-icy as those adopted in this thesis it becomes trickier.

Reducing the overall time execution requires more effort.

When a requester publishes a task, this will continue to run until all the as-signments are submitted. Predicting when the task will finish is not trivial, as there could be assignments left unfinished that cause delays, thus leading to the long tail problem. These abandoned assignments become available to other workers only after the platform expiration time takes place. Therefore, the crucial point lies in identifying the abandoned assignments and making them available to other workers with the proper timing in order to avoid cre-ating unnecessary copies that would have been submitted in short time.

(39)

Chapter 3. Modeling the problem 19

3.1.2 The approach

This thesis addresses the above mentioned issues by proposing an ad hoc ap-proach that follows this structure:

1. Identification of the parameters and their values in order to fine-tune the microtasks’ execution for the twofold purpose. This topic is introduced in Section 3.2 and it continues in Chapter 4.

2. Implementation of a sound mechanism to find among different values the most appropriate one for each of the parameters. This theme is ex-amined in Subsection 5.3.4.

3. Development of an application that connects to the platform, keeps track of the assignments’ evolution in time in order to identify abandoned ones and then makes them available again so that other workers can start the newly generated copies as soon as possible. This subject is further ana-lyzed in Chapter 5.

Budget constraints can be further satisfied by the simple but not granted taking into account all the expense and by adopting a reliable pricing scheme. The results of the study described in [6] show that a fixed pricing scheme is not appealing as other options could be. Indeed, the milestone pricing scheme has higher performance independently from the type of task being processed. The above mentioned scheme can be reexamined as to specify a deadline as the milestone by which an extra reward will be assigned, otherwise the payment will consists in just a basic payment.

As far as costs are concerned, the major ones are the basic payoff and the bonus. Another entry in the expense list is the platform transaction fee, which is fixed to be 20% of the cost per page. Therefore, the total amount will depend on how many assignments will be processed and how many copies are created, but the first two elements are the only parameters strictly related to money that can be fine-tuned.

The joint effort of the approach and the pricing scheme allows the requester to meet more specific goals besides just finishing microtasks. In this case, it is about meeting budget and time constraints.

(40)

3.2 The parameters into play

The actual implementation of the approach relies on the parameters that can be exploited to improve the overall time execution and the actual cost.

In this work, the parameters taken into account are six and they are:

Payment pw It is the basic reward given to the worker for each submission.

Bonus bw It is the extra reward given if the worker meets a predefined time

deadline.

Bonus deadline Db It is the time deadline by which the extra reward is

as-signed.

Relaunch deadline Dr It is that moment in time from which assignments not

yet submitted are relaunched.

Parallel relaunch np It is the number of copies of an assignment created after

a relaunch deadline is met.

Iterative relaunch ni It is how many times a relaunch deadline can occur per

each assignment.

3.2.1 Payment

The payment pwexpresses how much the effort put into the completion of each

microtask is valued by the requester and it is independent from the timing of the submission.

As reported in [10], the monetary incentive offered is the most crucial factor that influences the worker’s choice in the task to complete. Therefore, consid-ering from the worker’s point of view that to higher rewards could correspond higher complexity (Simpson’s paradox), it is essential and not trivial to define the appropriate payment that combines both a reasonable cost - for the re-quester - and an attractive reward - for the worker.

If the goal is receiving accurate outcomes, it is important not to rely only on the payment, as it is possible to run into the anchoring effect. It is that phe-nomenon for which workers feel like they are being rewarded less than they

(41)

Chapter 3. Modeling the problem 21 deserve. Therefore, they aren’t enough motivated to perform better, no matter how much they are actually paid.

3.2.2 Bonus

The bonus bwis an extra reward assigned to those workers that satisfy the time

requirement defined by the bonus deadline. It helps in guaranteeing higher performance in the pricing scheme as the goal of a higher payment attracts more workers and it does it faster.

With this setting, the requester sends the message that a quick submission is valued positively. However, this could lead to workers trying to cheat.

3.2.3 Bonus deadline

The bonus deadline Db specifies the time by which a worker submitting the

assignment receives the extra reward.

It is important to choose reasonable values, because if the time span is too narrow, very few workers will fall into it and this could encourage false sub-missions; if the time span is too broad, then too many will get the bonus and the cost will raise.

3.2.4 Relaunch deadline

The relaunch deadline Dris that moment that determines the creation of a new

copy of those assignments that are not yet completed. Still, the original ones are not discarded until the expiration deadline defined by the platform.

Choosing a value or another influences both the cost and the time. The former is inversely proportional to the time as waiting more time to relaunch means less assignments created. The latter increases proportionally with time, be-cause the more the relaunch is delayed, the more the overall time execution increases.

(42)

3.2.5 Parallel relaunch

The parallel relaunch parameter np defines the number of copy of the

assign-ment to be relaunched such that they run, as the name suggests, in parallel. The value assigned to the parameter can affects greatly the cost. Indeed, if they all were to complete, the requester should guarantee a reward for all of them. On the other hand, the higher the value, the more likely it is that one of the assignment will be submitted.

It is important to notice that, assuming infinite budget and infinite iterative relaunches, the worst scenario that could happen is that at each iterative re-launch npnew assignment would be created, resulting in a exponential growth.

3.2.6 Iterative relaunch

The iterative relaunch parameter ni defines the number of copy of the

assign-ment to be relaunched such that they run subsequently, with just a brief over-lap with the previous and, if it exists, the following one. In other words, there is a cascade of relaunches.

The value assigned to the parameter can affect greatly the overall execution time. Indeed, the higher the value, the longer the requester has to wait for the task to finish. However, this is just an event that could potentially occur as it it highly unlikely that all the previous workers would abandon the assign-ment. If a similar circumstance were to happen, it could be reasonable to check whether that precise assignment has some faults.

3.3 Crowdsourcing graphic representation

Crowdsourcing microtasks have a workflow that is particularly suitable to be graphically depicted with a tree representation. In this representation, every turning point is related to one or more of the parameters listed above.

Consider an assignment that is available to be worked on. The root corre-sponds to the crossroads at which a worker can decide whether to start the job

(43)

Chapter 3. Modeling the problem 23 or not. Assuming a positive answer, from that point on the depth of the struc-ture goes hand in hand with the increase of time.

Each node indicates a new branch and a new branch leads to different paths. Every leaf in the tree reports the payoffs of both the worker and the requester (pr). In order, the leafs encountered show:

1. the submission by the bonus deadline (T1); 2. the submission by the relaunch deadline (T2);

3. the submission by the platform expiration deadline (T5).

The first and the latter also occur in every relaunch, while the second occurs in all relaunches but the last one. Figure 3.1 reports the graphic equivalent of what just described.

However, the tree representation requires a lot of space and in case of many relaunches it becomes unfeasible to draw the structure. For this reason, the optimal strategies are analyzed without the tree and at runtime, so they are online strategies.

Moreover, the downside of the tree representation is that it doesn’t show the time parallelism with the previous level in case of relaunches. For this last issue, a timeline can help in visualizing the events.

Figure 3.2 reports the duration of the assignment’s life both in its original copy and in its relaunch, highlighting the overlapping between the two.

(44)

24 Chapter 3. Modeling the problem T T0 Assignment T1 Db T2 Dr T5 T imeout T3 Relaunch T4 Db T6 Timeout end W W (pw+ bw, pr) Bonus W (pw, pr+ ε) By Relaunch W (pw, pr− ε) By T imeout R W W (pw+ bw, pr− 2ε) Bonus W (pw, pr− 2ε) By T imeout (0, 0) N ot By T imeout N o Bonus Commit (0, 0) N o Commit Relaunch (0, 0) N ot By T imeout N ot By Relaunch N o Bonus Commit (0, 0) N o Commit

Figure 3.1: Example of an assignment’s tree representation with one

relaunch. On the left, the corresponding timeline.

(45)

Chapter 3. Modeling the problem 25

T0: Start of the assignment T1: Bonus deadline Db

T2_{: Relaunch deadline D}_r T3: Start of the relaunch T4_{: Bonus deadline D}_b

T5: Deadline for submitting the assignment T6: Deadline for submitting the assignment

Figure 3.2: Timeline highlighting the partial parallelism between

original assignment and relaunch.

(46)

(47)

27

Chapter 4 Identifying parameters’ value

4.1 Crowdsourcing agents

The crowdsourcing success lies on the need of requesters to have some tasks completed under certain constraints and the will of workers to do additional work in order to receive an extra income. Considering the above mentioned goals for each of the agents involved, how are they going to behave to achieve it?

4.1.1 Requester

The requester will try to optimize the entire task, and therefore each assign-ment, either in terms of time or in terms of budget.

Mainly, he will try to maximize his value based on time, so once the budget is allocated, he is willing to use it all. Since the first positive leaf starting from the tree root is with the bonus deadline, the aim is to have all the assignment com-pleted by then. However, including a budget perspective, the highest payoff for the requester is just after the bonus deadline has expired. Figure 4.1 re-ports the payoffs of the requester in the different phases of the assignment. The logic behind them is that the requester judges with higher value the com-bination "fast submission - low cost". For these reasons, he will value more a submission delivered just after the bonus deadline has expired. When the as-signment is relaunched, his payoff decreases. The decrease takes into account both timing and budget factors and this quantity is estimated equal to ε. The moment when the original copy and the relaunch overlap is the worst case scenario for the requester.

T0 T1 T2 T3 T4 T5 T6

pr pr+ ε pr− ε

−ε −2ε

Figure 4.1: Requester’s payoffs. Above, those of the original

assignment. Below, those of the relaunch.

(49)

Chapter 4. Identifying parameters’ value 29

4.1.2 Worker

Assuming workers always aim at achieving their best payoff and assuming the pricing scheme adopted in this experiment, in a perfect world composed of ra-tional (and honest) workers this would lead to an equilibrium on the bonus, provided that the payoff is the highest.

Considering the case of perfect information, where a contributor has knowl-edge of the structure and of every parameter’s value, workers can be profiled in three major categories:

1. Serious workers. They actually work trying to submit as many assign-ments as possible in a short period of time, mainly that of the bonus. Their equilibrium is stable on the bonus as shown in Figure 4.2.

2. Active cheaters. They act like serious workers except they complete ran-domly as many assignments and as fast as they can, without caring about the quality. Minimizing the time spent over each assignment, they can in-crease the number of submissions and therefore maximizing their gain. Also for these workers, the equilibrium is on the bonus as shown in Fig-ure 4.2.

T0 T1 T2 T3 T4 T5 T6

pw+ bw pw

Figure 4.2: Timeline representing in green the payoff of the original

assignment, in yellow that of the relaunch and in red the equilibrium for serious workers and active cheaters.

3. Lazy cheaters. They try to exploit the relaunch mechanism to gain as much as it is allowed by the task. This concept is based on completing the assignment without submitting it and letting it be relaunched as deep in the tree as the budget upper bound allows, trying to commit to the relaunched copies again and again. In this way, they can submit all the copies all together, thus maximizing the income, taking into account that the timeout of the assignments should not yet be expired.

(50)

30 Chapter 4. Identifying parameters’ value These workers have the equilibrium on the bonus of the latest relaunch satisfying b, as shown in Figure 4.3.

T0 T1 T2 T3 T4 T5 T6

pw+ bw pw

Figure 4.3: Timeline representing in green the payoff of the original

assignment, in yellow that of the relaunch and in red the equilibrium for lazy cheaters.

On the other hand, in a case of imperfect information, it is unfeasible to follow the lazy cheater profile, because at least one of the key value is not publicly available, like the relaunch deadline or how many iterative relaunch there will be.

However, in a real world setting, workers cannot be so strictly categorized. Profiles are blended together and workers don’t always aim at achieving their best payoff. Moreover, there’s not always a strategy to be late in submitting a unit, everyday life happens: a phone call to answer, a meal to eat, a child to watch.

These considerations, more precisely those on the equilibrium, are valid as-suming a large number of workers. It is, indeed, a factor that influences the strategies of the workers themselves. A single worker committing to every assignment of a task will adopt a selfish strategy in order to maximize his in-come, resolving himself into a lazy cheater. The aim is to gain all the payoff of the worst case scenario (with respect to the requester’s point of view).

As the number of workers increases, the strategies adopted change, due to the fact that it is unknown how the opponent plays, which could cause a break in the strategy and, therefore, a loss in the payoff.

Moreover, in a set of workers, the ratio "serious workers - cheaters" could be an important matter as it can turn the tide of the completion time of the entire task. However, having such an amount of cheaters is highly unlikely. Indeed, the usual ratio adjusts the dynamics of the game.

According to [9], workers work towards maximizing the difference between

(51)

Chapter 4. Identifying parameters’ value 31 the utility of tasks and the utility of time. The former is related to what the con-tributor gains, such as the payoff and also learned skills and fun. The latter consists of the time spent in finishing the assignment. This means that the first one has to be larger than the second one to convince someone to work on a task.

Having introduced the utility of time as a factor into play, it is now reasonable to find an equilibrium like that of serious workers and active cheaters, even though the monetary reward is higher in the case of lazy cheaters’ equilibrium.

4.2 Parameters and their range

In order to start modeling the crowdsourcing mechanism, it is necessary to give information about what workers will have to face as assignment.

For this work, the task will be to transcribe receipts, which belongs to the con-tent creation category, more precisely to the media transcription class [see Sub-section 2.3.1]. It has a medium difficulty and it usually has high attractiveness. As found in a yet unpublished paper, this kind of assignments produce high quality results when the average duration is about 200 seconds, given an in-terface with web forms. By ten minutes, 75% of the assignments have already been submitted.

Before entering into the details of the parameters, it is useful to introduce the budget

4.2.1 Budget

In crowdsourcing, a task has a budget B, which can be potentially equally divided among all the K assignments that compose it. Therefore, each assign-ment would have a budget of

b = B

K (4.2.1)

Alternatively, the assignment budget could consist of the basic assignment payoff plus the bonus

b = pw+ bw (4.2.2)

(52)

32 Chapter 4. Identifying parameters’ value Either way, when the assignment is submitted and there is budget left, this could be shared directly with the running assignments in the first case or col-lected in a wallet from which all the assignments can draw in the second one. In this way, the budget dynamically changes until all the assignments are sub-mitted.

Supposing the task is represented as a tree in which all its assignments are drawn in depth as far as the budget upper bound allows, without all the routes already available, the changes in the actual allocated budget activates every time a new part of the tree.

Going backwards from the basic payoff to the budget, one can obtain that B = Kb = K(pw+ bw) = K(pw+

p

qpw) = K [pw (1 + p

q)]) (4.2.3) However, the budget expressed in this way forces the structure and the policy of each assignment, because it doesn’t allow any kind of relaunch mechanism. Shaping the budget according to the costs each assignment may require results in a lower and an upper bound for the budget. Indeed, the budget flexibility leads to different policies at assignment level depending on the needs and dif-ficulties of the specific data unit.

Therefore, the budget ranges from its lower bound

B = Kpw (4.2.4)

best scenario for the requester assuming minimizing the costs is its aim, to its upper bound B = K [pw (nl−1p p q + i+l−1 X j=i nj_p)] (4.2.5) worst case for the requester assuming the above objective. The role played by np, l and i is explained in the relaunch paragraph.

(53)

4.2.2 Worker’s basic payoff

A worker submitting an assignment will surely get at least pw, which is the

basic payoff, independently from the timing of the submission.

Usually, the range in which the payoff lies spans from $0.01 to $0.20. According to [14], in Amazon Mechanical Turk 25% of the tasks have a price tag of just $0.01, 70% have a reward of $0.05 or less, and 90% pay less than $0.10. The actual value varies according to the difficulty of a task and even to the target accuracy.

4.2.3 Bonus

The bonus bw is an extra reward assigned to those workers submitting a job by

a specific timeout, the bonus deadline Db.

The fixed bonus idea comes from the milestone pricing scheme reported in [6] and its adoption tells that the requester values highly the timing of the submission. It can be expressed as a ratio of the basic payoff

bw =

p

qpw (4.2.6)

More specifically, the value can be chosen among a set of ratios, according to the needs of the assignment:

{1,4 5, 3 4, 2 3, 3 5, 1 2, 2 5, 1 3, 1 4, 1 5}

It can be recommended to have a bonus not less than $0.01.

4.2.4 Bonus deadline

The bonus deadline Db specifies the time up to which a worker can get an

award for having quickly submitted an assignment.

Knowing that the average submission time for high quality assignments in receipt transcription in about 200 seconds, the range can be a neighborhood of that value. In this case, it spans from 120 and 240 seconds.

(54)

34 Chapter 4. Identifying parameters’ value In Figure 4.4 and 4.5 there is a timeline representation of where the bonus deadline Dbtakes place. In the second case, the bonus deadline in the relaunch

occurs exactly after Dr+ Db from the start.

T0_{: Start of the assignment} T1_{: Bonus deadline D}_b

T2: Deadline for submitting the assignment

Figure 4.4: A timeline representation of an assignment with no

relaunches

4.2.5 Relaunch deadline

The relaunch deadline Dr specifies the time up to which a worker can submit

an assignment without causing the creation of a new copy of the assignment itself. This timeout occurs after that of the bonus. It is important to specify the most appropriate time to start relaunching. Indeed, if this deadline takes place too early, the cost increases; if it takes place too late, the overall task execution rises.

Knowing that 75% of the assignments is submitted in ten minutes from the start, the relaunch deadline can take place from that moment on. For this work, the range will span from 10 to 13 minutes.

In Figure 4.5 there is a timeline representation of where the relaunch deadline Drtakes place.

4.2.6 Relaunch

A relaunch takes place when an assignment reaches the relaunch deadline without being submitted. At this point, the choice of the requester can vary between:

1. Relaunching one or more copy of the assignment such that they run in parallel - parallel relaunch.

(55)

T0: Start of the assignment T1: Bonus deadline Db

T2_{: Relaunch deadline D}_r T3: Bonus deadline Dr+ Db

T4_{: Deadline for submitting the assignment} T5_{: Deadline for submitting the assignment}

Figure 4.5: A timeline representation of an assignment with one

relaunch

2. Relaunching one or more copy of the assignment such that they run sub-sequently, with just a brief overlap with the previous and, if it exists, the following one - iterative relaunch.

3. Relaunching np ≤ NP parallel copy of the assignment and ni ≤ NI copy

in cascade, such that for every new line i, 1 ≤ i ≤ ni, there are npparallel

copy running. 4. Not relaunching.

When the iterative relaunch policy is applied, it prevents the creation of a new iterative copy if the last one running submits the result by the relaunch dead-line Dr.

As it is already hinted by the policies, the relaunches can be divided into two major categories, parallel and iterative, each of which has its own range. The former ranges {0, ..., NP} and the latter ranges {0, ..., NI}, where NP and NIare

the maximum number of relaunches. When at least one of the two parameters is set to 0, this prevents any kind of relaunch.

However, these numbers must take into account the allocated budget. Indeed, it may not be possible to support all the NP, NI relaunches, thus the upper

bound of the ranges will consist in the minimum between NP or NI and the

number of feasible relaunches with the allocated budget, respectively for the parallel relaunches and for the iterative ones. Moreover, the overlap in time of different levels of copies of the same assignment affects the budget, which in turn influences the number of relaunches, as said above. These considerations

(56)

36 Chapter 4. Identifying parameters’ value highlight that there is a chain of dependencies affecting the upper bound of the number of relaunches.

4.2.6.1 Parallel relaunch case

The cost due to the start of a new copy of the assignment is always given by c0 = pw+ bw (4.2.7)

In case of parallel relaunch, there cannot be more than two levels of copies, meaning the original assignment level and the relaunch one and the cost in the worst case is

cworst= (np+ 1)pw+ npbw (4.2.8)

Assuming b = m(pw+ bw), there are two scenarios:

1. If min(c, b) = c or if c = b, np is the upper bound for the number of

relaunches. 2. If min(c, b) = b, m = b pw+ bw (4.2.9) is the upper bound for the number of parallel relaunches.

Figure 4.6 gives a visual representation of the tree structure after the relaunch occurs. In this scenario, the worst case cost would be c = 3pw + 2bw.

4.2.6.2 Iterative relaunch case

Assuming no more than two levels at the same time, in case of iterative re-launch policy there are at most 2 simultaneous copies whatever the values of ni is, such that the worst case for the cost is

cworst = 2pw+ bw (4.2.10)

Unless the budget doesn’t allow to pay two workers, niis the upper bound for

the number of relaunches. This is a special case, since the behavior is the same as when using a parallel relaunch policy with just one relaunch.

(57)

Chapter 4. Identifying parameters’ value 37 Relaunch W W (pw+ bw, pr− 2ε) Bonus W (pw, pr− 2ε) By T imeout (0, 0) N ot By T imeout N o Bonus Commit (0, 0) N o Commit W W (pw+ bw, pr− 2ε) Bonus W (pw, pr− 2ε) By T imeout (0, 0) N ot By T imeout N o Bonus Commit (0, 0) N o Commit

Figure 4.6: Tree representation of a parallel relaunch assignment with np= 2.

Cr owdsour cing: relaunching mechanism and parameters optimization

(58)

38 Chapter 4. Identifying parameters’ value Assuming there can be up to l levels at the same time, the cost increases to

cworst = lpw + bw (4.2.11)

Given b = m(pw+ bw), there are two cases:

1. If min(c, b) = c or if c = b, niis the upper bound for the iterative number

of relaunches. 2. If min(c, b) = b, m = b pw+ bw (4.2.12) is the upper bound for the number of iterative relaunches.

The value of l varies according to the values of the number of iterative re-launches ni and that of the relaunch deadline Dr. Knowing the range of the

relaunch deadline, the maximum number of overlapping assignments is 3. In Figure 4.7 there is an example of an iterative relaunch with ni = 2. In such

a case, the cost can increase up to c = 3pw+ bw.

4.2.6.3 Parallel and iterative relaunch

Assuming there can be up to l levels at the same time starting from level i, the cost of the worst case sums to

cworst= nl−1p bw+ pw i+l−1

X

j=i

nj_p (4.2.13) Given b = m(pw+ bw), there are two cases:

1. If min(c, b) = c or if c = b, npand niare respectively the upper bound for

the number of parallel and iterative relaunches. 2. If min(c, b) = b, m = b pw+ bw (4.2.14)

(59)

Chapter 4. Identifying parameters’ value 39 is the upper bound for the number of total relaunches, therefore either the number of parallel relaunches or that or the iterative ones decreases:

i+l X j=i nl_p = m (4.2.15) Relaunch W W (pw+ bw, pr) Bonus W (pw, pr+ ε) By Relaunch W (pw, pr− ε) By T imeout R W W (pw+ bw, pr− 2ε) Bonus W (pw, pr− 2ε) By T imeout (0, 0) N ot By T imeout N o Bonus Commit (0, 0) N o Commit Relaunch (0, 0) N ot By T imeout N ot By Relaunch N o Bonus Commit (0, 0) N o Commit

Figure 4.7: Tree representation of an iterative relaunch assignment

with ni = 2.

(60)

Figure 4.8 shows the tree structure in case of a parallel and iterative relaunch policy with np = ni = 2. To simplify

the representation and just give an idea of how complex the structure gets as the number of relaunches increase, all the actions available in each level are grouped in the original assignment [green] and the relaunches [yellow].

OriginalAssignment R 1.1 R 2.1 . . . R 2.2 R 1.2 R 2.1 . . . R 2.2 . . . . . . R 1.nh-1 R 2.1 . . . R 2.2 R 1.nh R 2.1 . . . R 2.2 Figure 4.8: Tree representation of a parallel and iterative relaunch assignment with np= 2and ni = 2.

Cr owdsour cing: relaunching mechanism and parameters optimization

(61)

Chapter 4. Identifying parameters’ value 41 Figure 4.9 represents an assignment in its tree structure with payoffs pw =

$ 0.10and bw = 1₅pw = $ 0.02, deadlines Db = 3minutes and Dr = 10minutes,

relaunches np = 1and ni = 1.

W

($ 0.12, pr)

Bonus Deadline 3minutes

Relaunch Deadline 10minutes

Expiration Deadline 30minutes

Bonus Deadline 13minutes

Expiration Deadline 40minutes

Bonus W ($ 0.10, pr+ ε) By Relaunch W ($ 0.10, pr− ε) By T imeout R W W ($ 0.12, pr− 2ε) Bonus W ($ 0.10, pr− 2ε) By T imeout (0, 0) N ot By T imeout N o Bonus Commit (0, 0) N o Commit Relaunch (0, 0) N ot By T imeout N ot By Relaunch N o Bonus Commit (0, 0) N o Commit

Figure 4.9: Visual representation of the time deadline occurrences, the

effects of the budget choices and the relaunch policy.

(62)

4.3 Single-Purpose, Multi-Purpose

Crowdsourcing helps requesters in dealing with great amount of data that needs to be processed, which couldn’t be otherwise obtained by means of a computer. Indeed, it requires human processing capability.

The requester submits the task to the platform in order to receive an outcome from the workers. In exchange for the results of each single assignments, he offers a reward. The aim is to collect all the answers by a reasonable time, but also saving some of the allocated budget. Caring about just one of the two translates the problem into a single-purpose task, while the combination of both is a multi-purpose one.

With a single-purpose task, it is simpler to establish which value the parameter should take.

Assuming the aim is just to minimize the end time of the entire task, the re-quester is willing to use all the budget allocated to achieve it. In order, in-creasing the bonus and the basic payoff, to discourage any attempt to delay the submission, and, if relaunches are needed, opting for the parallel relaunch policy will do the job.

On the other hand, if the main aim is to save money without any relevant time constraint, then the requester is willing to give up on fast submission by re-ducing to the minimum the bonus or even erasing it. A solution could also be that of lowering the number of relaunches, which would otherwise result in higher costs.

In a multi-purpose setting like the one this thesis focuses on, it becomes more complex to find the best value for the parameters, because there is the need of a compromise to balance the relevant factors. Indeed, in order to reduce the time of the task, the requester has to pay more to encourage fast submission, while in order to save money, it has to wait more time. This means they are inversely proportional: when one decreases, the other increases.

For these reasons, it is important to find the most suitable trade-off between end time and residual budget, to find those upper bounds that don’t have to be crossed.

(63)

Chapter 4. Identifying parameters’ value 43 To recap, of the mechanisms exploitable in crowdsourcing, the bonus and the number of relaunches are helpful tools to reduce the time of the task. Lowering their values leads to a saving in money.

0 B T Residual Budget E nd T ime (a) 0 B T Residual Budget E nd T ime (b)

Figure 4.10: Two examples of how time and budget can be correlated.

Figure 4.10 represents two different ways in which the end time and the residual budget are correlated in the multi-purpose setting.

In the image on the left, Figure 4.10 a, time increases slowly as long as almost all of the allocated budget is used, but up to a turning point. After this mo-ment, time grows exponentially.

In the image on the right, Figure 4.10 b, time quickly rises even when exploit-ing almost all the budget, then it starts slowexploit-ing down.

Finding the most suitable trade-off between the two values varies according to the shape the above graph takes. In the first case, the requester can get a positive end time without using all the allocated budget. Indeed, spending all the money wouldn’t guarantee any advantage. Instead, in the second case, it is likely that the task will finish later in time, so if it is important to assure a given end time, then the requester needs to use more budget.

A useful idea would be that of deciding an upper bound beyond which the value cannot get for both the end time and the residual budget. All the inter-section points before these two limits are candidate points. Figure 4.11 shows Crowdsourcing: relaunching mechanism and parameters optimization

Crowdsourcing : relaunching mechanism and parameters optimization

S

CHOOL OF

I

NDUSTRIAL AND

I

NFORMATION

E

NGINEERING

Master of Science in Computer Science and Engineering

Communication and Society Engineering

C

ROWDSOURCING

:

RELAUNCHING

MECHANISM AND PARAMETERS OPTIMIZATION

Author:

Maria Cristina F

ID 835991

Supervisor:

Eng. Nicola G

Co-supervisor:

Eng. Florian D

Abstract

Sommario

Contents

List of Figures

List of Tables

List of Algorithms

List of Abbreviations

List of Symbols

Chapter 1

Introduction

Contents

1.1

The birth of "crowdsourcing"

1.2

Thesis aim

1.3

Thesis structure

Chapter 2

State of the Art

Contents

2.1

Microtasking

2.2

Systems executing tasks and tactics

2.3

Crowdsourcing context: general information

2.3.1

Task categorization

2.3.2

Pricing schemes and monetary incentives

2.3.3

Quality check

2.4

Related work: time minimization

Chapter 3

Modeling the problem

Contents

3.1

The scenario

3.1.1

The root of the problem

3.1.2

The approach

3.2

The parameters into play

3.2.1

Payment

3.2.2

Bonus

3.2.3

Bonus deadline

3.2.4

Relaunch deadline

3.2.5

Parallel relaunch

3.2.6

Iterative relaunch