3.1 Game theory

Game theory is concerned with the analysis of situations whereby multiple agents interact and their actions affect each others’ outcomes. With Game Theory, agents evaluate their potential choices considering the potential choices and utilities of other agents within a given scenario. Myerson (Reference Myerson1981) defines game theory as follows:

Often, intelligent rational decision-makers, within the game theory literature, are referred to as self-interested agents. Self-interest does not imply that agents are necessarily selfish or are only concerned about actions that improve their own circumstances and that their actions are harmful to others; rather, it implies that the agents have beliefs about what are favourable states in the world and their actions are motivated by the intention to bring about those states. This notion is captured by representing the agents’ desired states with utility functions that map states of the world to numeric values that quantify the degree of preferences of agents among states. This enables the impact of uncertainty on preferences be represented and agents to take actions that maximize their expected utility.

In early research on the topic, Von Neumann and Morgenstern (Reference Von Neumann and Morgenstern1944) proved a theorem that derives the existence of a utility function from a preference ordering and axioms on such orderings. This demonstrated that a utility function is sufficient to encode preferences over a complicated set of alternatives.

Game theory is divided into two branches, namely cooperative and non-cooperative that differ in how they formalize independence among agents. The terms cooperative and non-cooperative, when used in this context, differ from common vernacular, which would suggest that competition does not occur in the former and cooperation does not occur in the latter, neither of which is the case. Cooperative game theory describes the outcomes that occur when different combinations of agents come together, whereas non-cooperative game theory provides a more detailed model of the options available to individual agents and their individual utility functions. It should be noted, however, that any cooperative game can be converted to a non-cooperative representation. In game theory, the price of anarchy (Koutsoupias & Papadimitriou, Reference Koutsoupias and Papadimitriou2009; Roughgarden, Reference Roughgarden2010) can be viewed as a measure of the degree to which competition approximates cooperation in situations whereby agents have access to shared resources. It represents the ratio between the best possible system performance or utility, from the system designer’s perspective, that could be obtained if the system designer had complete or full control, as opposed to the performance with a group of strategically motivated autonomous agents (Koutsoupias & Papadimitriou, Reference Koutsoupias and Papadimitriou2009).

Problems in game theory have different types of solution concepts depending on the type of game being played. A game is said to have a dominant strategy solution if each player has a unique best strategy notwithstanding the strategies adopted by the other players in the game. A dominant strategy does not guarantee that the utilities received by agents will be optimal and, indeed, in the well-known prisoner’s dilemma game, this will not be the case. Outside the scope of mechanism design (see Section 3.2), where the goal is to construct games that have dominant strategies that are socially optimal or maximize the revenue for the designer, games that have dominant strategies are rare.

For games that do not have a dominant strategy solution, a more widely applicable solution concept is required. In games where players deterministically choose their moves, a pure strategy Nash Equilibrium represents such a solution concept. A Nash Equilibrium is a stable solution whereby no agent has an incentive to deviate from their current strategy given the strategies of the other agents. Once the players are in Nash Equilibrium, it is in all the players interest to remain in Nash Equilibrium. A problem, however, is that there may not be a unique Nash Equilibrium.

Not all games have pure strategy Nash Equilibria solutions. In games where players can randomize their strategies, however, stable solutions can be obtained in situations where it is assumed that agents are risk neutral and will act in such a manner as to maximize their expected payoff. This type of solution concept is referred to as a mixed strategy Nash Equilibrium. In this case, an agent chooses a probability distribution over their set of possible strategies and independently selects strategies using the probability distribution. Not all games have mixed strategy Nash Equilibria; if there is a finite set of agents and a finite set of strategies, however, the game will have such an equilibrium (Nash, Reference Nash1951; Nisan et al., Reference Nisan, Roughgarden, Tardos and Vazirani2007).

3.2 Mechanism design

Mechanism design is concerned with the problem of formulating the rules of games such that they exhibit desirable outcomes under the assumption that agents are rational and that their behaviour will be in accordance with a specified utility function. One of the key application areas of mechanism design is that of creating games that make minimal assumptions regarding the behaviour models of agents, such as DSIC games. In DSIC games, it is often relatively straightforward for both agents and mechanism designers to reason about what the optimal course of action is and what will occur within the game when compared to other types of games.

Games within mechanism design are described in terms of allocation rules, payment rules, monotone unctions, and implementability. An allocation rule is a function that determines how items are allocated to agents, such as mapping bids within an auction to what agents receive. A payment rule is a function that, given an allocation, determines what agents pay. A function is called monotone if for larger values provided in the domain, larger values are given in the range. For example, in an auction an allocation function would be called monotonic if for larger bids, an agent wins more. For a single parameter environment where the only unknown parameter is that of the agent’s private valuations, an allocation rule is said to be implementable if a payment rule for a sealed-bid auction exists such that the sealed-bid auction is DSIC. For the mechanisms discussed in this section, the utility of an agent is defined as a quasilinear function, which is equal to the difference between the value an agent puts on an item minus the price the agent pays for the item if the price is not higher than the valuation. If the price is higher than the valuation, the agent’s utility is zero.

A fundamental result in mechanism design is that of Myerson’s Lemma (Roughgarden, Reference Roughgarden2003; Myerson, Reference Myerson2013). Myerson’s Lemma states that an allocation rule is implementable if and only if it is a monotone function and, if this is the case, a unique payment rule exists, which is determined by an exact payment formula given in Myerson (Reference Myerson2013). Given, from Myerson’s Lemma, that implementability and monotonicity are equivalent and that, typically, it is relatively easy to determine if an allocation rule is monotonic, the lemma significantly simplifies the problem of formulating games that are implementable.

The well-known Vickrey second-price sealed-bid auction (Vickrey, Reference Vickrey1961) can be viewed as a special case of Myerson’s Lemma. In a Vickrey auction, agents submit bids privately to an auctioneer and the price that the winning agent pays is equal to that of the second highest bidder. This provides an incentive for agents to bid in a truthful manner. The reason for this is that if an agent underbids, there is a chance that they will not receive the item if another agent has bid higher. This would be irrational in that the price that the agent would pay for an item, if they had bid truthfully and won, could be less than their valuation in that they only pay that of the second highest bid. If an agent overbids, there is a chance that another agent will make a bid that is higher than the original agent’s valuation, but lower than the original agent’s bid. In this case, the original agent will pay more for the item than their valuation. Thus, to maximize their expected utility, agents should bid honestly.

The Vickrey auction is useful in situations whereby the objective of the auction is to maximize the social surplus, whereby the winner of the auction is the agent that values the item the most. A modification of the Vickrey auction, using a reserve price, can be used to maximize the expected revenue under assumptions regarding prior distributions of beliefs over agents’ valuations, such as that their valuations are drawn from the identical distributions.

Myserson’s Lemma is used in the design of DSIC mechanisms in single parameter environments, where agents’ private valuations are unknown. For multi-parameter environments, such as combinatorial auctions, whereby agents have different valuations over different items, the Vickrey–Clarke–Groves (VCG) mechanism (Groves, Reference Groves1973) is used. The main idea in the VCG mechanism is that, when evaluating their reported valuations and the prices potentially paid for items, it forces agents to internalize their externalities or the social cost of their participation in the auction. For instance, if a winning agent did not participate, the utility of other agents would increase in that they would receive items that would have been received by the winning agent. The VCG payment rule quantifies this.

A key problem with using complicated incentive structures in crowdsourcing platforms is that agents are often only presented with the mechanism for a short time period and for a small number of tasks. In conventional platforms, most crowdsourcing tasks have relatively low returns, such as a few euros, and it is for this reason that agents will not spend a significant amount of time considering the implications of a complicated payment scheme. As such, it is expected that the agents often will not fully understand a payment scheme unless it is quite simple, stated clearly and appropriately, or can be intuitively understood. If this is not the case, it cannot be assumed that agents will act precisely as required or behave in a manner that is rationally implied by the rules of the game. Mechanism design aids in addressing this problem by providing a principled approach to the construction of DSIC games that ease the reasoning burden in determining the correct action to take.

4.1 Behavioural economics

A key tenet of game theory is the assumption that agents will act in a rational manner with regard to maximizing their welfare. Behavioural economics takes a different view and, rather than assuming that agents are rational, it makes predictions based on the observed behaviour of people (Kahneman, Reference Kahneman2003). It considers the role of cognitive, emotional, psychological, and social factors in the economic decision-making of individuals and institutions. There are many cognitive biases and psychological traits that inhibit people from making rational decisions and cloud their judgement, such as overconfidence, projection bias, and the effects of limited attention. A core aspect of behavioural economics is that of bounded rationality. An individual’s rationality is limited by the tractability of the problem at hand, the cognitive limits of their minds, and the amount of time they have available to make decisions. There are several sources of error regarding human economic decision-making. People often make decisions based on rules of thumb or heuristics rather than using logic. Additionally, people understand and respond to events using mental models that frame the situation based on anecdotes and stereotypes.

Cumulative prospect theory (Tversky & Kahneman, Reference Tversky and Kahneman1992) is an influential theory within the field and represents a model for decision-making under risk and uncertainty. It is based on the observation that people often make decisions using a psychological reference point, such as the status quo, and generally care more about avoiding losses than acquiring equivalent gains relative to the reference point. Additionally, people typically overestimate the likelihood of rare events, but underestimate the likelihood of regular events.

Critics of behavioural economics (Berg & Gigerenzer, Reference Berg and Gigerenzer2010) argue that it does not make more realistic assumptions than neoclassical economics, as its proponents (Rabin, Reference Rabin2002; Camerer, Reference Camerer2003) claim, and that while it does study what decisions humans make, it does not account for how they make them. The result is that it is even more tied to the way humans think than its neoclassical counterpart. Neoclassical economists have relied on the ‘as if’ argument, which is to say that although humans do not solve the difficult optimization problems of neoclassical economics when making decisions, they behave as if they do. Behavioural economists point to counter cases from experiments where the predictions of neoclassical economics fail. In offering prospect theory, whereby greater weight is given to losses than gains, behavioural economics provides a better fit for the choices observed in experiments. According to Berg and Gigerenzer (Reference Berg and Gigerenzer2010), the problem, however, is that prospect theory requires summing up every possible outcome and even more difficult computations to produce a decision than neoclassical optimization. Thus, behavioural economists must also rely on the ‘as if’ argument.

Mechanism design does not suffer from many of the criticisms directed at game theory in general by behavioural economists, who are mostly concerned with problems that naturally occur in the wild, rather than games that have been specifically designed to have desirable properties. For instance, with game theory, it will often be the case that a game will not have a unique equilibrium, but an array of possible outcomes. Mechanism design enables the creation of games that do not have this property. In the construction of DSIC games, one of the consequences of mechanism design is the easing of the reasoning burden of the participants. A key goal in this area is often the construction of games whereby the optimal course of actions is obvious. Even in situations whereby the optimal course of action is not obvious, if it is not a ‘one shot’ game, the participants will learn the optimal course of action over time either through direct experience, competition, or through communication via blog posts, etc. As noted in Shah and Zhou (Reference Shaw, Horton and Chen2015), incentive compatibility is relevant in situations whereby people encounter a mechanism over extended periods of time or whereby the financial rewards are large. In such cases, it would be expected that the participants or others, such as bloggers or researchers, would devise strategies to game the mechanism. Behavioural economics could not be used to address this problem.

4.2 Incentive theory of motivation

Incentive theory is a psychological theory of motivation that focuses on the role rewards play in motivating people towards a given course of action. Beyond biological factors, two types of reward are considered in incentive theory, namely intrinsic and extrinsic rewards. Intrinsic rewards arise from internal factors, whereas extrinsic rewards arise from external factors. Incentive theory draws much from the research of the behavioural psychologist B. F. Skinner on operant conditioning (McLeod, Reference McLeod2007). With incentive theory, a reward, which may be either tangible or intangible, is given immediately after the occurrence of an action to increase the likelihood of the action being performed again. As such, it is based on the principle of positive reinforcement. With positive reinforcement, behaviour is altered by a continuously associating a positive meaning to a given course of action over an extended period. For rewards to be motivating, they need to be obtainable. In addition to positive reinforcement, Skinner identified two other responses or operants from the environment that can follow behaviour, namely neutral operants and punishers. Neutral operants neither increase nor decrease the likelihood of the behaviour being performed again, whereas punishers decrease the likelihood and weaken behaviour.

The use of extrinsic rewards can have both positive and negative effects in relation to intrinsic rewards. As noted in Cameron et al. (Reference Cameron, Banko and Pierce2001), when explicitly tied to performance standards and success, extrinsic rewards have positive effects on intrinsic motivation. In cases whereby extrinsic rewards are loosely tied to behaviour or signify failure, such as when the extrinsic reward received is lower than expected, however, the effects on intrinsic motivation are negative.

Criticisms of incentive theory include that it does not consider the role played by cognitive and inherited factors in relation to learning and behavioural change. It also does not account for social learning whereby humans learn by observation or communication rather than direct personal experience.

In Bosha et al. (Reference Bosha, Cilliers and Flowerday2017), the use of incentive theory is investigated in bolstering user participation in a participatory crowdsourcing project to collect data related to public safety in East London, South Africa. In certain situations, incentive theory will be useful to induce learning and to bolster participation in crowdsourcing. In many crowdsourcing applications on platforms, such as MTurk, however, the objective is the completion of tasks that aid the requester, not changing the behaviour of users. In a similar manner to behavioural economics (see Section 4.1), incentive theory does not address the adversarial situation whereby participants in a crowdsourcing system adopt strategies to game the platform. Incentive compatibility, from a mechanism design perspective, is required in such situations.

4.3 Gamification

Gamification can be viewed as the application of video game design principles to make work tasks appear like a game so as to increase the motivation for users to engage (Morschheuser et al., Reference Morschheuser, Hamari and Koivisto2016). As such, it increases the intrinsic rewards (see Section 4.2) for performing tasks by making task completion more enjoyable. This is important in crowdsourcing applications whereby users may often be participating for free or for very little monetary rewards. In such systems, intrinsic motivations, such as enabling the users to be creative or to gain social recognition, can often outweigh extrinsic factors from a motivational perspective.

Platforms that incorporate gamification features often use design patterns to induce motivations in users regarding feelings of autonomy, mastery, flow, and suspense (Morschheuser et al., Reference Morschheuser, Hamari and Koivisto2016). Motivational affordances adopted in this space frequently include points, badges, leader boards, avatars, and stories.

In Hamari (Reference Hamari2013), the authors investigated the introduction of gamification, and specifically the incorporation of badges, into a utilitarian peer-to-peer trading service known as Sharetribe. The results indicated that the claim of significant overall increases in usage frequency, quality, or social interaction due to gamification could not be supported. Nevertheless, the users that did actively engage with badges were also more likely to engage with the service, leave comments on listings, complete transactions, and list their goods for trade.

For certain types of application, gamification may increase user participation. The goals of gamification and incentive engineering, however, are somewhat different. With gamification the objective is to increase users’ intrinsic rewards and engagement, whereas with incentive engineering, it is to ensure that users’ incentives are structured to have desirable properties. Indeed, there is no reason both could not be used in the same platform.

4.4 Qualitative approaches

Many problems within the incentivization space are computationally hard and cannot be easily or intuitively modelled using rational utility maximizing agents whereby the utility functions represent all implicit and explicit rewards for a particular course of action. One of the primary goals of mechanism design is to make minimal assumptions regarding the behaviour models of agents, such as that if there is an obvious dominant incentive compatible strategy, the agents will play such a strategy. Such weak behaviour models, however, may not be sufficient to explain the behaviour of agents in other types of scenario whereby certain parameters of the problem are not under the control of the system designer.

Several approaches have been developed that address the incentivization problem using qualitative techniques such as subgraph matching (Ebden et al., Reference Drexler and Miller2015), content analysis (Shaw et al., Reference Shah-Mansouri and Wong2011), volunteering (Mao et al., Reference Mao, Kamar, Chen, Horvitz, Schwamb, Lintott and Smith2013), and SCOUT (Stewart et al., Reference Stewart, Lubensky and Huerta2010). Such systems are not explicitly designed in terms of utility maximizing agents; rather different models are adopted to represent system behaviour. The commonalities and differences of the systems are not expressed in a formal manner, however, and the relationship amongst them is thus difficult to ascertain due to disparity of the techniques used. In situations where the parameters of the problem are under the control of a system designer, the use of mechanism design, in contrast to qualitative approaches, will yield the benefits of DSIC games discussed in Section 3.2.

4.5 Game theoretic incentive engineering

In Sections 5 and 6 several applications of game theory to crowdsourcing are discussed from an offline and online perspective, respectively. The difference between offline and online approaches is related to the adoption of reinforcement learning techniques, which are adopted in the latter, but not the former. As is illustrated Figure 1, the game theoretic incentivization mechanisms discussed in Sections 5 and 6 can be classified in number of ways, such as in relation to whether they are incentive compatible, approximate, or operate in an online manner.

The Stackelberg game (see Section 5.1) and reputational (see Section 5.2) incentivization schemes were not developed using results from mechanism design. In the case of the former, a pre-existing game was used in modelling the desired incentive structures. In the case of the latter, the interaction between requesters and worker agents is captured in the formalism of repeated games.

With mechanism design, it is not assumed that a game pre-exists in the wild or that a given problem should be altered to match a model of a pre-existing game; rather the rules of the game should be engineered such that the expected behaviour of agents will be in accordance with the system designer’s objectives. Incentive compatibility is a key concept in mechanism design and refers to situations whereby it is in all agents’ interests to provide private information truthfully or act in accordance with their preference. DSIC is a stronger form of the concept and refers to games whereby truth-telling is always in an agent’s interest regardless of the actions of other agents. The multiplicative incentivization mechanism (see Section 5.3) is incentive compatible, but it is also DSIC in that the agents within the scenario whereby it is adopted do not interact.

Profit maximization (see Section 5.4.1) and interval cover (see Section 5.4.2) represent two approaches that have been developed using mechanism design. With profit maximization, the incentivization problem is addressed in the context of profit maximization for a mobile sensing scenario. With interval cover, a VCG mechanism is used for the case when agents have identical quality ratings and an approximation algorithm when not.

In terms of online algorithms, multi-armed bandit (MAB) (see Section 6.1) and dynamic procurement auction (see Section 6.2) approaches are considered. Online approaches, which are used in situations whereby the values of courses of action are uncertain, address the trade-off of exploring new courses of action and exploiting pre-existing courses of action that have previously given good results. This is useful in situations whereby the objective is to maximize the utility of the work performed subject to a budget constraint and in which the costs of the workers are unknown.

5.1 Platform and user-centric mobile phone sensing

In Yang et al. (Reference Yang, Xue, Fang and Tang2012), approaches to incentivizing users to participate in crowdsourcing using smartphone technology are discussed. As noted in Yang et al. (Reference Yang, Xue, Fang and Tang2012), smartphones support a wide range of sensing technologies, such as Global Positioning System receivers, microphones, accelerometers, gyroscopes, and cameras, amongst others. These sensors can be used in the creation of novel technologies and in the augmentation of pre-existing services, such as social media services, with information related to the user’s or device’s context and the environment in which they are embedded. The connectivity of these devices is near pervasive and, as such, smartphone technology has the potential to become the largest sensing platform constructed in history. To enable the creation of a smartphone platform that incentivizes users to allow their mobile device to be used for sensing, two approaches are proposed, namely the platform-centric model and the user-centric model. With the platform-centric model, a reward is provided by the platform, which is shared amongst participating users.

With both approaches, it is assumed that there is a principal agent or platform owner that gains from a discrete set of sensing tasks being performed and a group of agents that have smartphones with the computational, sensing, and communication resources available to perform the tasks, but incur a cost for doing so. With the platform-centric model, the problem is viewed in terms of the goal of the platform owner in maximizing their utility. The platform owner wishes to receive the greatest benefit in terms of the sensing tasks performed whilst minimizing cost. In contrast to this, the smartphone users wish to receive the greatest price (cost to the platform owner) for performing tasks.

The platform-centric model takes the form of a Stackelberg game. In a Stackelberg game or competition, there is a single leader agent that makes the first move and a group of follower agents that move or perform actions subsequently. A Stackelberg game models the situation whereby the leader agent has an advantage of moving first given that they know ex ante that the follower agents cannot perform a leader action and that the follower agents will observe their action. In economics, the leader agent is sometimes referred to as the market leader.

For the user-centric model, an auction procedure with the following properties was designed:

• ∙ Individual rationality: The utility of the smartphone users is zero if they do not perform sensing tasks. If sensing tasks are performed, users receive a utility of the price paid by the platform minus the user’s cost (see Section 3.2). If the user’s cost for performing a task is greater than the price paid by the platform, they do not perform the task.

• ∙ Profitability: The incentives are structured in such a manner that the value the platform owner receives for the tasks being performed does not go beyond their costs in terms of making payments to users.

• ∙ Computational efficiency: Although it is computationally intractable to determine an exact solution to the problem posed, polynomial time approximate algorithms can be used to ensure results with bounded quality.

• ∙ Truthfulness: The incentives are structured such that it is not in the agents’ interest to deviate from the truthful revelation of their costs or value of the work required to perform the task.

In terms of commercial applications, this research would not be suitable for systems such as MTurk and CrowdFlower (see Section 5.3) in that mobile phone crowdsourcing tasks typically operate over longer durations of time than typical tasks on those platforms. One potential commercial application area, although not specifically intended for such systems, is within Witkeys.

In China, a Witkey is a crowdsourcing site that enables the online purchase of services and information, which is used by users of either a personal or professional nature. Such sites, enable tasks to be posted and users offer a small reward for solutions to the tasks. Other users attempt to solve the tasks and compete to have their solutions selected by the requesters. There are several Witkey sites, including Witkey.com, Taskcn.com, Zhubajie.com, and K68.cn (Yang et al., Reference Yang, Adamic and Ackerman2008). The founder of Witkey.com, which was the first of such sites, coined the term. A Witkey site plays the role of a third party in a knowledge market, receiving payments from requesters and transferring payment to the providers of completed tasks that have been selected as winning submissions. The tasks posted on Witkey sites usually require a given skill set to complete and a moderate investment of time.

An analysis of the strategic behaviour of users in the Taskcn Witkey site, which is one of the largest, is provided in Yang et al. (Reference Yang, Adamic and Ackerman2008). In Taskcn, market inefficiencies are observed in that with uncoordinated user participation, many users race to complete for the most popular tasks, which leads to a low probability of individual users winning. This is a likely contributing factor as to why most users of the site only make a smaller number of submissions and then become inactive. The users that remain active, however, tend to strategically choose tasks that they have a higher probability of winning and which attract less competition. A small number of users win multiple tasks and increase their submission to win ratio over time. It is unclear, however, as to whether this is because of them learning a better strategy for task selection or whether it due to their increasing reputation rating from past wins and thus having a higher probability of being selected as a winner than other users.

5.2 Reputation-based incentivization

In Zhang et al. (Reference Zhang and Van der Schaar2012), the authors discuss a reputation-based incentivization scheme, which is based on social norms. The interaction between requesters and worker agents is modelled in the formalism of repeated games. A protocol is proposed that prevents the problem of free riding and incentivizes agents to contribute to task-solving processes. The free riding problem is related to situations whereby agents are paid ex ante or prior to completing tasks. In such cases, if correct incentives schemes, such as a reputation-based scheme, are not in place, there could be an incentive for payment to be received, but not for effort to be expended on the task.

The approach presented in Zhang et al. (Reference Zhang and Van der Schaar2012) integrates payment and reputation schemes in the design protocols for crowdsourcing. In terms of maximizing the revenue of a crowdsourcing site, there is a trade-off between keeping worker agents incentivized such that they act in accordance with the social norm and lowering the percentage of payments received by workers, and, thus, increasing the revenue of the site. If the payments made to agents are too low, the agents will be less inclined to conform to the social norm and their reputations will decrease, leading to worker agents being prohibited from performing tasks and to a reduction in revenue. The protocol designer, therefore, must achieve a balance between increasing the per transaction revenue for the site and the incentivization of the worker agents in contributing to revenue maximization.

In addition to the commercial platforms discussed in Sections 5.1 and 5.3, a reputation-based incentivization scheme could be useful in the Upwork platform. Upwork, formerly known as Elance oDesk, is a crowdsourcing platform that enables businesses and professionals to connect and collaborate on a freelancing basis. It is the world’s largest online platform for outsourced contracts (Ghani et al., Reference Ghani, Kerr and Stanton2014) and differs from MTurk in several ways. Upwork provides functionality to view workers’ profiles, including information related to their identity, feedback, skills, and a rating. It helps to enable workers be chosen by requesters based on selection criteria. Additionally, functionality is provided to clients for interviewing, hiring, and collaborating with freelancers through the platform. An application is provided that tracks time and takes screen shots as freelancers are working. In terms of payments, Upwork takes a percentage of the fees payed to workers.

5.3 Multiplicative incentives

Crowdsourcing is becoming increasingly popular in the production of labelled data for supervised learning within the machine learning community. With supervised machine learning, when learning a classification model, algorithms require a large set of training material that is labelled positively or negatively for a given class or group of classes. In Shah and Zhou (Reference Shaw, Horton and Chen2015), the problem of outsourcing the labelling process to the crowd is considered. The primary problem with crowdsourcing such data is that it will be of low quality/accuracy in that crowd workers are typically not experts and, as such, it can be expensive to obtain good results if appropriate incentives are not put in place.

The approach presented in Shah and Zhou (Reference Shaw, Horton and Chen2015) introduces a requirement, referred to as the no-free-lunch axiom, that is intended to discourage spammers and miscreants. The system works by introducing a gold standard of material, which has a correct, known classification to the system operator, in a random manner to the rest of the material that has not been classified. The users performing the classification are unaware of which material forms part of the gold standard and which is unclassified. The users receive payment for answers they provide in the gold standard. The incentive mechanism takes a multiplicative form. Each answer provided in the gold standard is given a score and the payment given to the user is the product of the scores. For correct classifications, the user’s payment is increased by a given ratio; for incorrect answers the user’s payment is multiplied by zero, and for skipped answers it is multiplied by one. Thus, if the user provides an incorrect answer on any of the gold standard questions, they will receive a payment of zero. This introduces a truthful incentive to skip questions in situations where the user does not know the answer, rather than to guess.

Potential commercial platforms that could avail of multiplicative updates include MTurk, CrowdFlower, and Witkeys (see Section 5.1). MTurk is the most widely known commercial crowdsourcing platform and is a microtask marketplace for work that requires human intelligence. The platform draws from the fact that there are still many tasks that can be performed by humans more efficiently, or to a higher standard, than by computers. For example, transcribing audio recordings or identifying objects in photographs or videos. Within MTurk there are two types of users, namely requesters and workers (sometimes referred to as Turkers). The microtasks in MTurk are referred to as HITs. The platform charges a fee to requesters on top of the payment to workers. In MTurk, the requesters design and post their tasks and set the price for accepted submissions. The workers decide which tasks they will perform. Subsequently, the requester reviews the work submitted by workers and either accepts or rejects the tasks. The tasks designed by requesters are usually quite simple and could potentially form the elementary components of more complex tasks and, as such, the price for completing a task is usually quite low along with the amount of time it takes to complete.

CrowdFlower is a crowdsourcing somewhat similar to MTurk in that its focus is on relatively simple microtasks. The target market for CrowdFlower is narrower and more focused than that of MTurk in that it primarily targets tasks related to the labelling, enrichment, and cleaning of data for data science and machine learning algorithms. In contrast to MTurk, which offers little in the way of quality control measures, CrowdFlower enables advanced worker targeting and provides management tools, such functionality to monitor the performance of workers on tasks. In terms of the workflow, CrowdFlower uses a similar model to MTurk. Tasks are posted and on a continual basis and contributors discover work through job boards and, subsequently, decide whether to take on the tasks. Once a contributor uploads a completed task, the work is evaluated using a hidden subset of known answers. The contributors’ performance on these tasks determines their reputation and the degree to which the system trusts them.

5.4 Approximate algorithms

Often with the design of mechanisms, an important objective is to ensure that the game is DSIC. One reason for this is that it significantly simplifies or eases the burden of reasoning about what moves should be made by players when compared to alternative approaches. Another reason is that the mechanism designer will typically have a good idea of what will happen or what agents will do in such games. In addition to games being DSIC, a common requirement is that the social surplus or revenue be maximized and that the allocation and payment rules be executed in polynomial time. This can cause problems because optimization problems of this type are often NP-hard. As noted in Section 3.2, with social surplus maximization, goods are allocated to the agents that value them the most. This section discusses approximation algorithms that maintain the DSIC requirement, but relax the optimality requirement for maximization. Both the profit maximization and interval cover algorithms discussed here would not be suitable for sort-lived tasks performed on a once-off basis. Thus, in a similar manner to the research discussed in Section 5.1, the algorithms would be most suited (with modifications), from a commercial perspective, to the Witkey platform.

6.1 Multi-armed bandits

MAB algorithms explore the trade-off between resource exploration and exploitation. In the context of crowdsourcing, the requester of a set of tasks wishes to maximize their utility in terms of having the tasks performed and receiving results, whilst minimizing their costs. A problem, however, exists in terms of what price should be given to perform tasks in that the cost distributions of the workers will be unknown to the requester. If the price placed on performing a task is too high, the budget of the requester will be exhausted quickly or the price for the completion of all tasks will be high. If the price for performing a task is too low, it will be starved of high-quality workers. With MAB algorithms, the agents repeatedly choose amongst actions that have an uncertain reward. A goal with the development of such algorithms is to asymptotically minimize the regret over time when the actions chosen are compared to what the actions would have been if they had been chosen optimally with hindsight (Blum & Monsour, Reference Blum and Monsour2007).

The use of MABs is a general approach to online learning. In Tran-Thanh et al. (Reference Tran-Thanh, Stein, Rogers and Jennings2014), the problem of assigning tasks to workers with a limited budget is addressed using a MAB in a crowdsourcing context.

6.2 Dynamic procurement auctions

With crowdsourcing tasks, often the requester wishes to develop a payment scheme subject to a budget constraint such that the utility of the tasks performed is maximized, whereas worker agents seek to maximize their individual utility by choosing what tasks to perform and at what price they will participate. In Singla and Krause (Reference Singla and Krause2013), the problem of divergent goals between the requester and worker agents is addressed using procurement auctions.

There are two types of models for procurement auctions that could be adopted by the requester; these are referred to as the bidding model and the posted price model. With a bidding model, the workers bid for the price they are willing to perform the crowdsourcing task. With this type of auction, an agent will not bid a price too low in that if it were accepted, they would not be happy with the utility. A price too high, however, will also not be bid in that it would reduce the chance of winning. The model will not always reveal the correct valuation of the agents’ costs, however. For example, sometimes the agents will not know their true costs as they could be difficult to determine or the agents will not fully understand the mechanism. Issues, such as whether they trust the requester, could also be factored into the price.

With a posted price model, the workers are sequentially given a price and they either accept or reject the offer. As the workers respond, the offered price is varied, depending on the response given.

The approach adopted in Singla and Krause (Reference Singla and Krause2013), which uses a posted price model, is guaranteed to be budget feasible, approximately optimal in terms of the utility obtained by the requester, and truthful regarding the bids made by the workers given limited information or assumptions in relation to their costs. This extends and builds upon research on MABs for online auctions (Babaioff et al., Reference Babaioff, Dughmi, Kleinberg and Slivkins2015) to the case of procurement auctions under budget constraints.