Microtasks have been widely adopted by many crowdsourcing platforms as a unit for human computation. Recently, tools to support programmers to implement complex crowdsourcing applications with microtasks have been proposed. One approach is to provide a library of functions that can be called by programs written in imperative programming languages. Another approach is to allow SQL queries to invoke microtasks. The former approach provides large expressive power, while the latter allows declarative descriptions with limited expressive power. This paper proposes the Condition-Task-Store (CTS) abstraction, which is an alternative declarative approach to implement complex datacentric crowdsourcing with microtasks. The CTS abstraction is unique in that it has all the following features: (1) it naturally extends the task template adopted by many crowdsourcing platforms to define microtasks, (2) it allows declarative descriptions of crowdsourcing systems, and (3) it has large expressive power.
As computer network technologies evolved, crowdsourcing became popular in many application domains. Software systems that take the crowdsourcing approach are called crowdsourcing systems [2].
Crowdsourcing systems are often constructed on crowdsourcing platforms, which provide fundamental functions for implementing crowdsourcing systems. For example, the Amazon Mechanical Turk (MTurk) [3] is a crowdsourcing platform that provides a market in which workers perform microtasks (called HITs in MTurk) with a small payment amount per task. Crowdsourcing platforms often provide APIs for requesters to register microtasks in the platforms.
Because there are frequent patterns appearing in programs for crowdsourcing systems, software tools have been developed to support the implementation of complex crowdsourcing systems. For example, Turkit [4] provides a library of functions to define and call tasks from general-purpose programming languages and introduces the crash-and-rerun Copyright c 2013 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. programming model for minimizing the cost of re-running programs. Recently, the declarative approach to the development of crowdsourcing systems has emerged because declarative abstractions have an affinity toward crowdsourcing applications. Declarative descriptions do not impose unnecessary timing constraints, and we can adopt many well-known optimization techniques. For example, there are proposals that use SQL-like languages to describe data-centric crowdsourcing systems [7] [8] [13]. However, they provide limited expressive power (see Section 4).
In this paper, we offer the following two key contributions:
(
The CTS abstraction is unique in that it has all the
following features: (
Many approaches to support the development of complex
crowdsourcing systems have been proposed. They differ
from one another in the abstraction they use to describe
crowdsourcing systems.
(
To our knowledge, this paper is the first to investigate the CTS abstraction. The abstraction models crowdsourcing systems as a set of CTS rules, each of which is similar to a task template. Technically, a CTS rule can be implemented by combining two ECA rules [12]: one generates microtasks and the other stores results in the database (and can be implemented by using imperative languages). The CTS abstraction provides a higher-level, user-friendly abstraction designed for describing crowdsourcing systems, which has a well-defined semantics and proven large expressive power.
Our discussion on the expressive power is related to game theory. Recently, the literature on algorithmic game theory has addressed various aspects involving both algorithms and games, such as complexities of computing equilibrium of games [15]. To our knowledge, our paper is the first to discuss classes of games that can be implemented by abstractions for crowdsourcing. 3. THE CTS ABSTRACTION
The task template is a popular form for defining and registering microtasks into crowdsourcing platforms. Figure 1 shows an example of a task template in XML format for microtasks (HITs) of MTurk, which asks a worker to enter how many movies he or she watched in a month. The essential components of a task template are the question to be shown (QuestionContent) and the type of the values to be received by workers (AnswerSpecification). Task templates can contain variables (called placeholders) with which we can define many microtasks that are based on the same template but differ in the values bound to the variables.
Requesters first write task templates to define and insert microtasks into the task pool. Then, workers perform the tasks that exist in the task pool. 3.2
In the CTS abstraction, a crowdsourcing system is described by a set of CTS rules. We assume that there exists a relational database. CTS rules read and write data to and from the database.
A CTS rule is the fundamental building block of the CTS abstraction. We first give a simple example and next show another example that requires more than one CTS rule.
We use the task shown in Figure 2 to ask workers to tag books. The details are as follows: • The database has the Book(bid, title, author) relation to store book information. • For each book stored in the Book relation, tags are given by three workers. • The result is stored in the Tag(bid, tag) relation. • Workers are paid 10 (cents or any currency) per task, if any other workers entered the same tag.
The crowdsourcing system can be described only by the CTS rule in Figure 3. A CTS rule consists of three parts: condition, task, and store. We explain each part below. The condition part: We write the condition to generate and insert a task into the task pool. The condition specifies what tuples need to exist in the database for generating a task. For example, the condition in Figure 3 states that a task is generated for each tuple existing in the Book relation. The task part: We write a task template that contains a question to be posed to workers. The question can contain variables (such as $author and $title) bound to values in the condition (i.e., the variables are replaced with values each time the task is generated). The task part also specifies additional information, including the variables and its associated types, to store entered values.
Because there are frequently occurring patterns that
appear in task template specifications, we provide template
generators that allow users to describe task templates
without specifying implementation details such as HTML tags.
The task part in Figure 3 states that we use the Entry
template generator with the following parameters: (
As the example above suggests, a CTS rule is a natural extension of the widely-used task template. Because we can omit the condition and task parts, a CTS rule can be used to describe the following four types of processing. 1. Generate a task when the condition is satisfied, and store the result into the database. 2. If the condition part is omitted, generate a task with no condition, and store the result into the database. 3. If the task part is omitted, compute and store values into the database when the condition is satisfied. 4. If both of the condition and task parts are omitted, store values into the database with no condition.
We consider a crowdsourcing system to rate restaurants, in which workers perform the following two types of tasks: Task 1: Enter names of restaurants (Figure 4). A 10 cent payment is paid if the average rating by others is higher than 3.
Task 2: Enter an evaluation rating (1 to 5) for the given restaurant (Figure 5). Three workers perform this task for each restaurant, and they receive 10 cents per task.
We assume that the results of Task 1 are stored in Restaurant(rname), and that those of Task 2 are stored in Rating(rname, value). Then, Figure 6 shows CTS rules for Tasks 1 and 2.
The CTS rule for Task 1 has no condition: thus, the task is
unconditionally generated. Unless the count number is
specified, the number of generated tasks is determined as follows:
(
The condition of the CTS rule for Task 2 states that it generates a task for each tuple stored in Restaurant relation. Thus, the task is generated for each restaurant entered in Task 1. Workers receive 10 cents for performing a task. 2 Discussion. As the examples above suggest, the description is declarative, and each rule is invoked when its condition is satisfied. Compared to the code written in imperative programming languages, CTS rules naturally describe the parallel and asynchronous processing of computation involving human workers. On the other hand, the CTS abstraction is more expressive than the declarative query languages that do not support the transitive closure, because it essentially supports a loop with a dynamic condition check [1].
An important point is that the incentive structure plays a critical role to appropriately exploit the wisdom of crowd and (at least theoretically) ensure data quality. Because the incentive structure and rules involving multiple humans can be modeled as games, we can use game theory to discuss their behaviors. For example, with a simple game-theoretic analysis, the incentive structure of Example 1 guarantees that rational workers enter tags that others can easily come up with. Similarly, the incentive structure of Example 2 guarantees that rational workers for Task 1 enter the names of restaurants that are likely to receive high ratings. 3.3
This section first defines the CTS rules and then explains the syntactic sugar for the concise description of rules. 3.3.1
Definition 1. A program of the CTS abstraction is a set of CTS rules, each of which is modeled as a triple Ri = (Ci, Ti, Si), running over a relational database schema. Here, Ti is a task template, Ci is the condition to generate a task using Ti, and Si is the description of how to store the result in the database. The database contains a predefined relation with the schema Worker(pid, payoff) to store information on workers and the accumulated values of the payoffs they received so far.
• Ci is a sequence P1(x11, . . . , x1n1 ), . . . , Pm(xm1, . . . , xmnm ) of zero or more atoms. Some of the atoms can be arithmetic atoms, such as x11 = 3. • Ti is either a triple (q, x¯, y¯) or null. Here, q is a question for workers, x¯ is a sequence of variables bound by Ci, and y¯ is a sequence of variables to store the results of performing the task. • Si is a sequence Q1(y11, . . . , y1n1 ), . . . , Qm(ym1, . . . , ymnm ) of one or more atoms, where each yjk is any of a variable bound by Ci, a variable that appears in y¯, or a constant. Each atom can be followed by either /update or /delete. 2 3.3.2
We introduce the following variety of syntactic sugars to
make the rule description concise.
(
There are cases in which parameters and attributes can be omitted in each atom, as described below.
• We can omit a parameter if the rule does not
consume the value of the bounded variable. For example,
Restaurant(name:x) is an atom that omits zip.
• We can omit an attribute name if the attribute name
is the same as the variable name. For example,
Restaurant(name:name, zip:y) can be represented
as Restaurant(name, zip:y) because the attribute
and the variable have the same name.
(
Given a description d of the CTS abstraction, the evaluation of d on instance ins of the database is performed by evaluating each CTS rule in a bottom-up way on ins. More precisely, • For each CTS rule (Ci, Ti, Si) ∈ d, check if Ci is satisfied with ins in the following way: for each atom ak in Ci (from left to right), check if there exists any tuple to bind variables in ak to the values that are consistent with the values bound to the variables appeared in a0 . . . ak−1. • For every combination V of values that satisfies all the atoms in Ci, perform one of the following: – If Ti 6= null, replace variables in Ti with values in
V and insert the task into the task pool.
– If Ti = null, create new tuples using values in V
for the atoms that appear in Si. Then, perform
one of the following: insert the tuples into ins,
update ins with the tuples (when the atom is
followed by /update), or delete the tuples from ins
(when followed by /delete).
• If a worker completes the generated task, (
For example, assume that we have the CTS rule shown in Figure 7. We first check if there exists a tuple that matches Image(i, size, type:"photo") in the database. Assume that the Image relation has tuple t = (img98, 100, photo). Then, i and size are bound to img98 and 100, respectively. Next, check if there exists a tuple that matches Large(size) with size=100. If exists, we replace $i in the task template with img98 and insert the task into the task pool to ask workers to choose the category for the image img98. If the task is performed, the result of performing the task is stored into LargePhoto, and the payoff attribute of the Worker relation is incremented by 1.
Given a set d of CTS rules, the semantics of d is defined as a set of rational consequences of d, in a similar way as the semantics of CyLog codes [9]. A rational consequence of d is a set of facts that are derived from the rules and the equilibrium [16] of the games, i.e., the states reached by rational workers.
This section discusses the expressive power of the CTS abstraction. First, we show that the CTS abstraction is Turing complete. Then, we introduce a criterion to measure the expressive power of programming languages, which focuses on the class of games the language can implement. Finally, we compare the expressive power of the CTS abstraction with those of other frameworks. 4.1
Theorem 1. The CTS abstraction is Turing complete. Proof Outline. Figure 8 is a set of CTS rules that implements any Turing machine. Formally, a Turing machine consists of a quintuple (K, Σ, δ, s, H) where K is a finite set of states, Σ is an alphabet, s ∈ K is the initial state, H ∈ K is the set of halting states, and δ is the transition function [6]. Intuitively, we need the following three components to implement a turing machine.
Element 1. Memory of the machine’s inner state Element 2. Head reading and writing information stored in the tape Element 3. The long tape in infinitum.
In Figure 8, TuringMachine(id, st, head) implements Elements 1 and 2. Here, st records the current state whose domain is K, and head stores the position of the head. Tape(pos, sym) implements Element 3, in which each tuple (p, s) states that symbol s (whose domain is Σ) is written at position p of the tape. Rule(st, sym, new st, new sym, dir) stores the rules δ to read and write symbols on the tape and move the head.
Rule 1 initializes a Turing machine (the initial state is s). Rule 2 states how the head moves and writes symbols onto the tape according to the rules stored in Rule(st, sym, new st, new sym, dir). It states that if the inner state is st and the symbol at the current position of the head is sym, write new sym at the position, update the inner state by new st, and move the head to pos+dir. Rule 3 extends the tape when the head reaches a position that the head never visited before. We need Rule 3 because Rule 2 always requires that Tape(pos, sym) exists. We also need a rule to stop the machine if it reaches the halting states H ⊆ K. The rule is obvious and omitted due to the space limitation.
Defining the CTS rules to implement a Turing machine proves that the CTS abstraction is Turing complete. 2 4.2
This section proposes to use the game concept as a measure of the expressive power of programming languages for crowdsourcing, because the class of games that the language can implement affects the way in which the implemented system can exploit the power of the wisdom of crowd. First, we enumerate several classes of games and show the relationship among the classes.
Definition 2. G1 is a class of games that satisfy the following conditions: 1. Every input from a human is not affected by the inputs from others, and 2. The payoffs are computed by a primitive recursive function of the input values. 2 An example of a game in G1 is one that asks humans to enter tags for a given image without telling them what tags are entered by other humans. Payoffs are defined for each combination of worker inputs. For example, workers receive payoffs when they enter the same tag. Games in G1 are called simultaneous games in game theory.
Definition 3. GN is a class of programs in which (
Each game in GN has at most N phases, each of which
asks a human to enter data considering some information
computed from data in the previous phases. For example,
assume that we want to divide a set of cakes into two groups
whose total prices are equivallent to each other. Then, a
program that (
An example of a game in G∗ is to ask workers to write a paragraph that explains a given keyword. Workers update the paragraph until the paragraph is satisfied by the majority of the crowd. When the paragraph is completed, every writer (worker) who contributed to the paragraph receives a payoff, which is computed by dividing a fixed total payment by the number of the contributors.
Theorem 2. GN is a proper subset of G∗.
Proof. For every g, g ∈ GN ⇒ g ∈ G∗ and for any given i, there exists g ∈ G∗ s.t. g has i+1 input phases and therefore g 6∈ GN . 2 Theorem 3. Assume that we allow Turing machines to interact with humans at any step of its execution. Let M be the set of all such machines. M can implement any g ∈ G∗. Proof. The sequence of interactions with workers that can be generated by a primitive recursive function can be implemented by some m ∈ M . The information shown and the payoffs can be computed if m is a Turing machine. 2
Note that being Turing complete is not a sufficient condition to be able to implement G∗, because the power of interactions with humans does not matter for a language to be Turing complete. G∗ contains indefinite-length sequential games (in game theory) that can be expressed with Turing machines that are able to interact with humans at any step of its execution.
From the definition of the CTS rules, the following holds.
games in G∗.
The CTS abstraction can implement any 2 4.3
We implemented the Crapid system, a prototype system to develop crowdsourcing systems using the CTS abstraction. Crapid takes as input a set of CTS rules and outputs executable code. Crapid supports various task-template generators (i.e., Entry, Choice, Decision, and Comparisons as of May 2013) and payoff functions to help users easily define microtasks in CTS rules. Crapid provides a formbased user interface. When a user chooses a task-template generator, Crapid provides an appropriate set of selection boxes and drop-down menus to specify CTS rules. The output code is executable on Crowd4U [10], a crowdsourcing platform deployed at universities.
This paper introduced the CTS abstraction, a declarative
approach for implementing complex crowdsourcing with
microtasks. The paper also introduced a novel criterion to
measure the expressive power of programming languages for
crowdsourcing by focusing on the class of games we can
implement with the language. The class represents the size of
mechanism design space, i.e., the set of possible mechanisms
we can implement to exploit the wisdom of the crowd. The
CTS abstraction is unique in that it has all the following
features: (
Future work includes the development of various rewriting techniques for the CTS abstraction. For example, we plan to adapt various optimization techniques for crowdsourcing systems [7] [8] [13] into our context.
Acknowledgements. The authors are grateful to Prof. Shigeo Matsubara of Kyoto university for his helpful comments, and to the contributors of Crowd4U, whose names are partially listed at http://crowd4u.org. This research was partially supported by PRESTO from the Japan Science and Technology Agency, and by the Grant-in-Aid for Scientific Research (#25240012) from MEXT, Japan.