Sage Journals: Discover world-class research

Abstract

It is crucial to stimulate active participation of smartphone workers in crowdsourced sensing systems. This is due to the fact that it takes a smartphone worker considerable cost in terms of dedicated smartphone resources, human intervention, and possible privacy breach. Many incentive mechanisms have been proposed. However, existing incentive mechanisms suffer a serious common problem: they all assume full rationality of smartphone worker. Such fully rational smartphone workers are often too idealized! A smartphone worker may not be able to get the complete information and hence fails to compute the optimal strategy. In the real world, however, smartphone workers are usually bounded rational. Being bounded rational, a smartphone worker would not change the current strategy until its utility becomes too low. In this article, we propose an evolutionary stable participation game framework for crowdsourced sensing systems with smartphone workers of bounded rationality. Based on the evolutionary dynamics, we design and implement an evolutionary stable participation mechanism. It is proved that the system converges to an evolutionary equilibrium, which is globally asymptotically stable and robust to any degree of perturbations of the workers. Extensive simulation results show that the evolutionary participation mechanism leads the system to an evolutionary equilibrium quickly.

Keywords

Crowdsourced sensing smartphones evolutionary game sensing data

Introduction

Smartphones have become necessary for most people today. The powerful sensors embedded in smartphones, such as accelerometer, gyroscope, microphone, global positioning system (GPS), and camera, allow one to easily collect sensing data about surroundings and share the data with remote users. As a consequence, crowdsourced sensing has emerged as a compelling paradigm to collect sensing data on a large scale. It envisions a wide variety of application domains, including health, commerce, social network, environment monitoring, transportation, safety, and privacy.¹

A crowdsourced sensing system² consists of a platform and a large group of smartphone workers, as illustrated in Figure 1. The platform hosts a number of lasting sensing processes which recruit smartphones to contribute sensing data of a specific type to support a monitoring application (e.g. traffic congestion monitoring, and noise level monitoring). A smartphone worker may join one of the sensing processes by collecting the required sensing data and reports the sensing data to the platform to be leveraged by the specific sensing process.

Figure 1.

The system structure of a crowdsourced sensing system.

It is crucial for crowdsourced sensing systems to stimulate smartphone workers to actively participate in sensing processes by contributing sensing data. This is due to the fact that it takes a smartphone worker considerable cost in terms of dedicated smartphone resources central processing unit, bandwidth and energy), human intervention, and possible privacy breach. Many incentive mechanisms have therefore been proposed.^3–6 Reverse Auction based Dynamic Price (RADP)³ is the first reverse auction incentive mechanism for crowdsourced sensing systems. Yang et al.⁴ propose two different incentive mechanisms for a platform-centric model and a user-centric model in crowdsourced sensing systems. A reverse auction-based incentive mechanism⁵ is proposed for user participation level determination and payment allocation. Liu and Zhu⁶ consider maximizing the performance of a crowdsourced sensing system with an incentive mechanism.

Existing incentive mechanisms are good in theory, but suffer a major common problem: they all assume full rationality of smartphone worker. Being fully rational, a smartphone worker always selects the best strategy to maximize its own benefit. In the meanwhile, such a fully rational worker needs the complete system information and possesses the sufficient computational ability. Such fully rational smartphone workers are often too idealized! This is due to the fact that a smartphone worker may not be able to get the complete information and hence fails to compute the optimal strategy. In the real world, smartphone workers are instead usually bounded rational. Being bounded rational, a smartphone worker would not change the current strategy until its utility becomes too low. When choosing a new strategy, a smartphone worker may only access to incomplete information and then decides the new strategy. Thus, bounded rationality can better characterize smartphone workers in the real-world crowdsourced sensing systems.

In this article, we propose an evolutionary stable participation game framework for a real-world crowdsourced sensing system with smartphone workers of bounded rationality. We study and analyze the dynamic behavior of such smartphone workers. We then propose a fast and distributed evolutionary stable participation algorithm to allow the workers to evolve their strategies simultaneously in parallel. A worker makes its decision in a comparative manner (i.e. comparing its payoff with the system average payoff). The system will eventually evolve to an evolutionary equilibrium which is globally asymptotically stable, that is, it is robust to any degree of perturbations of the workers. We have performed extensive evaluations, and the numerical results verify the key features of the distributed evolutionary stable participation algorithm.

The main results and contributions of our work are listed as follows:

We build the first evolutionary stable participation game framework, to the best of our knowledge, for crowdsourced sensing systems with smartphone workers who are bounded rational. We study the evolutionary dynamics of bounded rational workers.

We propose an evolutionary stable participation mechanism based on the evolutionary dynamics. We prove that the proposed mechanism converges to the evolutionary equilibrium, which is globally asymptotically stable.

With extensive numerical results, we show that the evolutionary stable participation mechanism achieves desirable performance and robustness to any degree of perturbations of workers.

The rest of this article is organized as follows. The related work is presented in section “Related work.” We describe the system model and evolutionary stable participation game in section “Preliminaries.” We then propose the evolutionary stable participation algorithm in section “Evolutionary stable participation game.” The performance of the proposed mechanism is evaluated in section “Simulations.”We finally conclude in section “Conclusion.”

Related work

In this section, we review related work. First, we present applications of crowdsourced sensing. Second, we discuss several incentive mechanisms for crowdsourced sensing. Next, we present the use of evolutionary games in other areas. Finally, we also discuss other issues of crowdsourced sensing.

Crowdsourced sensing applications

In the past few years, there are many crowdsourced sensing–based applications being studied and proposed.^7–11 In Zhu et al.,¹⁰ the authors proposed a participatory urban traffic system using buses as probe vehicles to sample the road traffic conditions. Simoens et al.¹² proposed a scalable Internet system called GigaSight to collect videos from remote devices continuously. For bus arrival time prediction, Zhou et al.¹³ proposed a participatory system with cell tower signals, movement status, and audio recordings. Hyperfit was proposed in Jarvinen et al.¹⁴ to develop tools for personal nutrition and exercise management. In Bulusu et al.,¹⁵ the authors proposed two mobile camera-phone sensing systems to track price dispersion in homogeneous consumer goods.

This article focuses on modeling the participation dynamics of smartphone workers, which provides useful insight for developers of crowdsourced sensing applications.

Incentive mechanisms

Since providing incentives is a critical issue, there have been a number of studies of incentive mechanisms.^3–6 Most existing studies are based on theoretical auctions. With auctions, smartphone workers submit reverse bids for sensing tasks; the auctioneer would decide the set of winning bids and also the payments to each of the winning bids. The objective of the auctioneer is to maximize the total social welfare or the total revenue of the platform. Such auction-based mechanisms are typically able to guarantee truthfulness and individual rationality.

Such auction-based mechanisms typically make the following assumptions. First, smartphone workers are completely strategic and always able to select their respective strategies for optimizing their own utilities. Second, every smartphone worker has an accurate estimation on the cost of performing a sensing task. In reality, however, such assumptions are impractical.^7,16 In addition, these existing mechanisms typically consider in a crowdsourced sensing market, there is only one crowdsourcer which requests for sensing data from sensing smartphone workers. Nevertheless, a practical crowdsourced sensing market may have many crowdsourcers.

In this article, we study the evolving dynamics of smartphone workers in a practical setting. More specifically, a smartphone is able to choose different crowdsourcers over time.

Evolutionary games

The evolutionary game theory was originally exploited to study the interactive behavior of animals which belong to a population¹⁷ and later was applied in economics and sociology for studying behaviors of human players. It is especially useful to learn and understand how individuals of a large population converge to an evolutionary equilibrium based on the replicator dynamics.¹⁸ There are some studies which apply evolutionary game theory in cognitive radio network¹⁹ and wireless networks.²⁰

However, these studies consider specific issues related to the context and hence they are inappropriate for being applied in crowdsourced sensing.

Other issues in crowdsourced sensing

Besides providing incentive to smartphone workers, there are other issues^21–25 in crowdsourced sensing systems. A framework called ARTsense was proposed in Wang et al.²¹ to solve the problem of “trust without identity” in crowdsourced sensing systems, with an anonymous reputation management protocol. In Boutsis and Kalogeraki,²² a crowdsourced sensing system with privacy preservation was proposed, which enables users to disclose information without compromising their privacy. Xing et al.²³ developed a mutual privacy preserving regression modeling approach called M-PERM. Liu et al.²⁴ focused on the issue of efficient 3G budget utilization when the 3G communication capability of users is limited. Focusing on the problem of social welfare and fairness maximizing, Luo et al.²⁵ proposed two schemes for information service crowdsourcing scenarios.

Preliminaries

We introduce the system model of a crowdsourced sensing system and the background of evolutionary game theory briefly in this section, for the sake of completeness. The detailed introduction of the evolutionary game theory can be found in Smith.¹⁸

System model

We consider a crowdsourced sensing system with a platform and a finite set of smartphone workers $N = {1, 2, 3, \dots, N}$ , shown in Figure 1. The platform has a finite set of sensing processes $M = {1, 2, 3, \dots, M}$ . A sensing process is typically sponsored by a crowdsourcer. A sensing process consists of a series of sensing tasks for collecting the same kind of sensing data (i.e. air quality, noise level, or traffic status, GPS trajectories,^26–28 radio signal strength.)^29–33 A sensing process is divided by time slots, shown in Figure 2. A worker who is interested can accomplish a task in a time slot. Since the issue of marginal effect and data redundancy arises in crowdsourced sensing systems with a large population of workers,³⁴ each sensing process has a limited budget $B_{m}$ , which is to be shared by all the workers participating the same sensing process m in the same time slot.

Figure 2.

The three steps in a single time slot of crowdsourced sensing procedure.

The basic procedure of crowdsourced sensing is described as follows. A worker joins one sensing process and submits its selection to the platform. The worker then conducts the task which belongs to the sensing process, obtains the required sensing data, and sends it to the platform. The platform receives the sensing data and makes the payment to each of the workers.

Evolutionary game

An evolutionary game has the following main characteristics, which make the evolutionary game applicable in a crowdsourced sensing system:

Bounded rationality. Each play in an evolutionary game has only bounded rationality. This is either due to the lack of complete information or the computational ability.

Dynamics of the game model. In an evolutionary game, a player observes other players, learns from the observations, and makes the decision based on its acquired knowledge. The evolutionary game model captures the strategy dynamics and interactions among a large number of players in the same population, which can be modeled by the replicator dynamics to study the evolvement of the system.

Evolutionary equilibrium. The concept of Nash equilibrium is widely used as a solution in traditional games. It ensures that given all the strategies of other players, no player can improve its payoff by deviating from the equilibrium. However, in dynamic systems where players are free to choose their strategies simultaneously, a better solution concept is needed. The evolutionary equilibrium is such a solution concept, by which the equilibrium is robust to the perturbation caused by a small fraction of players.

Replicator dynamics and evolutionary stable strategy

Replicator dynamics

As mentioned above, the evolutionary game theory is proposed in biology to study interactions among animals of the same population.¹⁷ The game consists of a large population of animals (i.e. players), choosing different strategies and therefore having different fitness (i.e. payoffs). Animals with the higher fitness reproduce more offsprings, which truthfully inherit the strategy of their parents. The composition of the population changes as the reproduction process takes place over time. This process can be modeled by a set of ordinary differential equations called replicator dynamics.

Formally, a player in the population chooses a pure strategy i in a finite strategy set $I = {1, 2, 3, \dots, I}$ . Then, the reproduction process can be described with the population state $x (t) = (x_{1} (t), x_{2} (t), x_{3} (t), \dots, x_{I} (t))$ , where $x_{i} (t)$ denotes the proportion of players choosing the strategy i at time t. The replicator dynamics is therefore defined as follows

{\overset{\cdot}{x}}_{i} (t) = β x_{i} (t) (f (i, x (t)) - \bar{f} (x (t))), \forall i \in I

(1)

where $β$ is the rate of strategy adaptation, $f (i, x (t))$ is the payoff of a player choosing strategy i, and $\bar{f} (x (t))$ is the average payoff of the population. The replicator dynamics implies that a strategy is attractive when it is better than the average. Furthermore, the more players choosing the better strategy, the bigger probability that other players will be motivated to choose it.

Evolutionary stable strategy

The evolutionary stable strategy (ESS) is a refined equilibrium concept of the Nash equilibrium, which naturally leads to the idea of evolutionary equilibrium.¹⁸ Suppose that most of the players of the population choose strategy i, and only a small fraction $ϵ$ of players deviate from i to choose a mutant strategy, j. The proportion of players can be denoted as $x_{(1 - ϵ) i + ϵ j} = (x_{i} = 1 - ϵ, x_{j} = ϵ, x_{k} = 0, \forall k \neq i, j)$ , where $x_{m}$ denotes the fraction of users choosing the strategy m, and $P (m, x_{(1 - ϵ) i + ϵ j})$ denotes the corresponding payoff of the player who chooses the strategy m. Formally, ESS is defined as follows.

Definition 1 (ESS)

A strategy i is an ESS if for every strategy $j \neq i$ , there exists an $\bar{ϵ} \in (0, 1)$ such that $P (i, x_{(1 - ϵ) i + ϵ j}) > P (j, x_{(1 - ϵ) i + ϵ j})$ for any $j \neq i$ and $ϵ \in (0, \bar{ϵ})$ .

This definition implies that if strategy i is an ESS, then the mutant strategy j cannot invade the population, as long as the percentage of mutant players is small enough.

Definition 2 (strict Nash equilibrium)

A strategy i is a pure Nash equilibrium strategy if for every strategy $j \neq i$ , it satisfies $P (i, x_{i}) > P (j, x_{i})$ .

Setting $ϵ \to 0$ , we can see that a strict Nash equilibrium is an ESS. It naturally leads to $P (i, x_{i}) > P (j, x_{i})$ , for any strategy $j \neq i$ . Suppose that all the other players choosing strategy i, which is an ESS, a player who deviates from strategy i and chooses any mutant strategy $j \neq i$ will immediately have a loss in payoff.

Evolutionary stable participation game

We next present the evolutionary stable participation game and introduce its properties. We first propose the evolutionary stable participation game model and then propose the evolutionary dynamics of the system based on the strategy evolvement of a single worker. As a result of following the evolutionary dynamics, the system eventually converges to an evolutionary equilibrium. Furthermore, we prove that the evolutionary equilibrium is globally, asymptotically stable, that is, the system is robust to any degree (not necessarily small) of perturbations of the workers.

Evolutionary stable participation game formulation

An evolutionary stable participation game is defined by a tuple $(N, M, x (t), P_{n} (S_{n}, x (t)))$ :

$N = {1, 2, 3, \dots, N}$ is a finite set of workers, also referred as players.

$M = {1, 2, 3, \dots, M}$ is a finite set of the sensing processes. Each sensing process aims at collecting a kind of sensing data. The strategy set of a worker is $S = {1, 2, 3, \dots, M}$ . The sensing process consists of a lot of tasks, and each task can be completed by a worker in a time slot. The sensing process is repeated. Each time slot consists of the following three steps, shown in Figure 2:

Step 1: Collecting data. The worker collects the sensing data for the sensing process.

Step 2: Sending data and getting payment. The worker sends the data to the platform and gets the payment from the platform, along with other statistical information about the previous slot.

Step 3: Adapting strategy. The worker decides whether to change its selection of the sensing process, based on the evolutionary stable participation algorithm (described in section “Evolutionary stable participation algorithm”).

$x (t) = (x_{m} (t), \forall m \in M)$ is the population state of workers over M sensing processes at time t, where $x_{m} (t)$ is the proportion of workers choosing sensing process m at time t. For all t, $\sum_{m \in M} x_{m} (t) = 1$ .

$P_{n} (S_{n}, x (t))$ is a set of payoff functions, with the strategy of worker $S_{n} \in S$ , and the population state $x (t)$ . Each sensing process m has a fixed budget $B_{m}$ for a time slot. Considering such factors as data redundancy and marginal effect in crowdsourced sensing,³⁴ the payoff of a worker n choosing the sensing process m is modeled as follows

P_{n} (m, x (t)) = \frac{B_{m}}{N x_{m} (t)}

(2)

where $N x_{m} (t)$ denotes the number of the workers choosing the sensing process m. It implies that the budget of the sensing process is shared among all the workers participating in time slot t. We also have $\bar{P} (x (t)) = (\sum_{m = 1}^{M} B_{m}) / N$ as the system-wide average payoff. We note that participation in collecting sensing data naturally incurs a cost to a worker. However, considering that the cost is a private parameter and cannot be observed by other workers, it is natural that workers use the above payoff rather than the net income to make decisions in the real world, suggested by Clark and Oswald.³⁵ In the following analysis, we compare the worker’s payoff and the system average payoff, which is calculated by the platform and is disseminated to all workers by the platform.

Evolutionary dynamics

We next present the algorithm for worker to adapt its strategy over time. We first discuss a worker’s behavior in strategy evolvement. In the third step of each time slot, a worker selects the sensing process for the next time slot. A common assumption is that the worker is fully rational and always chooses the strategy that maximizes its own utility. However, this assumption is unrealistic for two main reasons. First, it is clear that the worker needs to collect all the payoff functions and the strategy profiles of other players. But this is impractical due to privacy issues. Second, several prior studies^7,16 show that workers would like to participate because of improving one’s creative skills, having an opportunity of taking up freelance work, being part of a community, or even just for fun. Thus, a more practical assumption is that a worker has only bounded rationality, meaning that the working is not always maximizing its utility. Instead, it sticks to the current strategy and does not change its strategy until its payoff is too low. We make an assumption that the threshold is the system-wide average payoff.

We then discuss two factors that affect a worker’s choice in strategy evolvement. The first factor is the fraction of workers participating in the sensing process, shown in equation (3). In the real world, a worker observes the trend and follows it. The second factor is the “extra percentage of payoff” of a sensing process. It reflects the appealing of improving the utility of a sensing process. We assume that the platform is responsible for collecting the statistics and computing the average.

We next propose the algorithm for each worker based on the evolutionary game model. The algorithm is repeated in each time slot (i.e. in each generation). A worker chooses one sensing process (i.e. strategy m) based on a probability distribution denoted by the product of above two factors. At the end of each time slot, the worker receives the payment, along with the statistics from the platform. Then, it decides whether to change its strategy or not. The basic idea is to let a worker choose a better sensing process if its payoff is lower than the system-wide average payoff. The probability is based on two factors, that is, the “extra percentage of payoff” $P_{n} ((m, x (t)) - \bar{P} (x (t))) / \bar{P} (x (t))$ of the sensing process m and the fraction of workers $x_{m} (t)$ choosing sensing process m.

The rate of strategy adaptation is governed by the evolutionary dynamics, as shown by Theorem 1.

Theorem 1

The evolutionary dynamics of the evolutionary stable participation game is given as

{\overset{\cdot}{x}}_{m} (t) = α x_{m} (t) (\frac{P (m, x (t))}{\bar{P} (x (t))} - 1), \forall m \in M

(3)

where $α$ is the strategy adaptation factor and the derivative is with respect to time slot t.

We then propose the evolutionary stable participation algorithm for each worker as follows.

Analysis on evolutionary equilibrium

We then investigate the evolutionary equilibrium of the evolutionary stable participation game. Since we have $P_{n} (m, x (t)) = B_{m} / N x_{m} (t)$ in equation (2), the evolutionary dynamics in equation (3)) becomes the following

{\overset{\cdot}{x}}_{m} (t) = α x_{m} (t) (\frac{\frac{B_{m}}{N x_{m} (t)}}{\frac{1}{N} \sum_{i = 1}^{M} B_{i}} - 1), \forall m \in M

(4)

according to Theorem 1.

We then propose the evolutionary equilibrium in Theorem 2, based on equation (4).

Theorem 2

The evolutionary stable participation algorithm converges to an evolutionary equilibrium

x^{*} = (x_{m}^{*} = \frac{B_{m}}{\sum_{i = 1}^{M} B_{i}}), \forall m \in M

(5)

and it is globally asymptotically stable.

We prove that the ESS in equation (5) is globally, asymptotically stable. It is an important characteristic since the evolutionary stable participation algorithm is robust to any degree of mutations of the workers.

Theorem 2 implies that the system eventually evolves to the evolutionary equilibrium $x^{*}$ . We have the following.

Corollary 1

The evolutionary stable participation mechanism converges to the equilibrium $x^{*}$ such that workers choosing different sensing processes receive the same payoff, that is

P (m, x^{*}) = P (m', x^{*}), \forall m, m' \in M

(6)

Analysis on complexity and cost

In this section, we analyze the complexity of the framework and the cost of each smartphone worker. The result of this analysis would show that this framework is lightweight and the cost of each smartphone work is minimal. This indicates that the framework can be adopted in real-world application scenarios.

As we can see in section “Evolutionary dynamics”, according to the framework, in each time slot, the platform collects information from different sensing processes and disseminates simple statistics about the previous time slot to all smartphone workers. Such complexity is minimal to a platform which typically has abundant computing resources.

In each time slot, a smartphone worker decides if to change the current selection of sensing process. This decision is made on a simple comparison of its payoff against the system-wide average. If the decision is to change to another sensing process, a random variable is then generated. Then, the worker performs the sensing task as required and sends the sensing data to the platform. It is clear that the cost of a smartphone worker is constant. This suggests that the cost per worker is small and a worker easily affords such a cost in practice.

Evolutionary stable participation algorithm

We then describe the evolutionary stable participation algorithm in Algorithm 1. The algorithm is designed in a distributed and parallel manner. Workers can evolve their strategies simultaneously in each time slot. The platform confirms the selected sensing processes (i.e. the strategies) of all the workers, makes the payments, and disseminates the necessary statistical information to all the workers.

Algorithm 1. Evolutionary stable participation algorithm
Input The finite set of workers $N$ ,
The finite set of sensing processes $M$ ,
The payoff functions $P_{n} (S_{n}, x (t))$ .
Initialization:
Set the global strategy adaptation factor $α \in (0, 1]$ . Each worker chooses a sensing process randomly.
1: for each worker n and each time slot t do
2: in parallel:
3: collect the sensing data required by the sensing process $S_{n}$ .
4: send the collected sensing data to the platform and receive the payment $P_{n} (S_{n}, x (t))$ .
5: receive the information of the population state $x (t)$ and the system average payoff $\bar{P} (x (t))$ .
6: if $P_{n} (S_{n}, x (t)) < \bar{P} (x (t))$ then
7: generate a random value $δ$ according to a uniform distribution on $(0, 1)$ .
8: if $δ < α (1 - \frac{P_{n} (S_{n}, x (t))}{\bar{P} (x (t))})$ then
9: select another sensing progress m with evolving probability $E_{m} = \frac{x_{m} (t) max {(P_{n} (m, x (t)) - \bar{P} (x (t))), 0}}{\sum_{i = 1}^{M} x_{i} (t) max {(P_{n} (i, x (t)) - \bar{P} (x (t))), 0}}$ .
10: else
11: stick to the current sensing process.
12: end if
13: end if
14: end for

The dynamics of worker participation in our algorithm can be described with the evolutionary dynamics in Theorem 1.

Simulations

In this section, we conduct simulations to evaluate our evolutionary stable participation algorithm. We first determine the strategy adaptation factor $α$ and then evaluate the convergence time and the global asymptotic stability of the proposed algorithm.

Simulation setup

We consider a crowdsourced sensing system with N workers and M sensing processes, and we set $M = 5$ in our simulations. Note that the proposed game model and the algorithm can handle a much larger number of sensing processes. Each sensing process m has a budget $B_{m} = 200 m$ for each time slot. We implement the evolutionary stable participation algorithm with $N = 3000$ and $N = 6000$ , respectively. At the beginning, each worker n randomly selects a sensing process $m \in M$ .

We also implement another distributed decision-making approach, the best response. In this approach, each worker selects the sensing process that maximizes its utility with an assumption that all the other workers’ strategy profiles are the same as those in the previous slot. The feedback of the best response approach is simply based on the previous slot. Hence, some games do not converge, for example, the Paper-Scissor-Rock game. Nevertheless, since it requires only few information and computation, the best response approach is still a useful baseline.

Strategy adaptation factor $α$

The strategy adaptation factor $α$ is determined by the crowdsourced sensing platform, which can be understood as the learning and adaptation speed of a worker. The convergence time with different factor $α$ , $N = 3000$ and 6000 workers, and $M = 5$ sensing processes are shown in Figure 3. Each reported result is averaged over 100 instances. It can be seen that the convergence time of the evolutionary stable participation algorithm decreases as the strategy adaptation factor $α$ increases. What’s more, the convergence time increases slightly when the number of workers N is doubled, from $N = 3000$ to $N = 6000$ .

Figure 3.

The convergence time of the evolutionary stable participation mechanism with different strategy adaptation factor $α$ , and $N = 3000$ and 6000 workers.

In the following simulations, we set the strategy adaptation factor $α = 0.5$ .

Convergence time

We evaluate the convergence time of the evolutionary stable participation algorithm. Numerical results with $N = 3000$ and 6000 workers are shown in Figures 4 and 5. It is clear that the proposed algorithm converges to the evolutionary equilibrium $x^{*} = (x_{m}^{*} = (B_{m}) / (\sum_{i = 1}^{M} B_{i})), \forall m \in M$ in less than 10 time slots. Furthermore, all the workers receive the identical payoff $P_{n} (S_{n}, x (t)) = (\sum_{m = 1}^{M} B_{m}) / N$ when they reach the ESS $x^{*}$ .

Figure 4.

Fractions of the workers choosing each sensing process and the payoff of each sensing process with $N = 3000$ workers and $M = 5$ sensing process, with the evolutionary stable participation mechanism.

Figure 5.

Fractions of the workers choosing each sensing process and the payoff of each sensing process with $N = 6000$ workers and $M = 5$ sensing process, with the evolutionary stable participation mechanism.

However, the convergence of the best response approach is not guaranteed at all, shown in Figures 6 and 7. We observe that distinct strategy thrashes between the sensing process 4 and 5. Note that they are the best and second best strategy if all the workers act toward the assumption. All the other workers do not change their strategy profiles. Each worker tries to maximize its own utility based on the assumption. It is clear that a better adaptive distributed approach which utilizes the historical information is required.

Figure 6.

Fractions of the workers choosing each sensing process and the payoff of each sensing process with $N = 3000$ workers and $M = 5$ sensing process, with the best response approach.

Figure 7.

Fractions of the workers choosing each sensing process and the payoff of each sensing process with $N = 6000$ workers and $M = 5$ sensing process, with the best response approach.

Global asymptotic stability

We then evaluate the global asymptotic stability of the evolutionary equilibrium. When the algorithm converges to the evolutionary equilibrium, we randomly pick up a fraction $ϵ \in (0, 1]$ of workers and let them choose mutant strategies. The evolutionary dynamics of worker mutation with $ϵ = 0.5$ and 0.8, $N = 6000$ workers, and $M = 5$ sensing processes are shown in Figures 8 and 9.

Figure 8.

Figure 9.

With the evolutionary stable participation algorithm, the system can quickly recover from the mutant states in less than 10 time slots. This demonstrates that the algorithm is robust to the perturbations of the workers. Considering that a worker may change its choosing sensing process by following the popularity, it is important to ensure the stability of data collection in the crowdsourced sensing systems.

The performance of the best response approach is shown in Figures 10 and 11. Notice that in this case the best response approach never converges to an equilibrium. Thus, the impact of the mutant is not studied.

Figure 10.

Fractions of the workers choosing each sensing process and the payoff of each sensing process with $N = 6000$ workers and $M = 5$ sensing process, with the best response approach. The fraction of mutant workers $ϵ = 0.5$ .

Figure 11.

Conclusion

We propose a novel evolutionary stable participation game framework for crowdsourced sensing systems with a large population of workers. In the real world, considering the privacy issue and worker behavior, it is unrealistic to assume that the workers are fully rational. Instead, bounded rationality is more suitable for characterizing the workers. We propose an evolutionary stable participation algorithm based on the evolutionary game theory. Rather than maximizing its utility, a bounded rational worker learns and improves its strategy over time with the statistical information provided by the platform. The system converges to an evolutionary equilibrium in short time, which is globally and asymptotically stable.

Footnotes

Academic Editor: Hongke Zhang

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by Wenzhou Science and Technology Bureau (Nos 2016G0024 and 2016G0001) and the Key Project of Wenzhou Vocational & Technical College (No. WZY2016004).

References

Lane

Miluzzo

. A survey of mobile phone sensing. IEEE Commun Mag 2010; 48(9): 140–150.

Liu

Zhu

Social welfare maximization in participatory smartphone sensing. Comput Netw 2014; 73: 195–209.

Lee

Hoh

. Sell your experiences: a market mechanism based incentive for participatory sensing. In: Proceedings of the IEEE international conference on pervasive computing and communications, Mannheim, 29 March–2 April 2010.

Yang

Xue

Fang

. Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing. In: Proceedings of the 18th annual international conference on Mobile computing and networking, Istanbul, 22 August 2012, pp.173–184. New York: ACM.

Koutsopoulos

. Optimal incentive-driven design of participatory sensing systems. In: Proceedings of the IEEE INFOCOM, Turin, 14–19 April 2013.

Liu

Zhu

Social welfare maximization in participatory smartphone sensing. In: Proceedings of the 8th international conference, Zhangjiajie, China, 7–10 August 2013, pp.351–365. Berlin: Springer.

Brabham

DC.

Moving the crowd at istockphoto: the composition of the crowd and motivations for participation in a crowdsourcing application. First Monday, 2 June 2008, http://firstmonday.org/article/view/2159/1969

Xiao

. Csi-based indoor localization. IEEE T Parall Distr 2013; 24(7): 1300–1309.

Zhu

Jiang

Zhao

. Correlating mobility with social encounters: distributed localization in sparse mobile networks. Wirel Netw 2015; 21(1): 201–215.

10.

Zhu

. A compressive sensing approach to urban traffic estimation with probe vehicles. IEEE T Mobile Comput 2013; 12(11): 2289–2302.

11.

Zhu

Liu

. Pova: traffic light sensing with probe vehicles. IEEE T Parall Distr 2013; 24(7): 1390–1400.

12.

Simoens

Xiao

Pillai

. Scalable crowd-sourcing of video from mobile devices. In: Proceedings of the 11th annual international conference on Mobile systems, applications, and services, Taipei, Taiwan, 25–28 June 2013.

13.

Zhou

Zheng

How long to wait? Predicting bus arrival time with mobile phone based participatory sensing. In: Proceedings of the 10th international conference on Mobile systems, applications, and services, Windermere, 25–29 June 2012.

14.

Jarvinen

Lahteenmaki

. Hyperfit: hybrid media in personal nutrition and exercise management. In: Proceedings of the 2008 second international conference on pervasive computing technologies for healthcare, Tampere, 30 January–1 February 2008.

15.

Bulusu

Chou

Kanhere

. Participatory sensing in commerce: using mobile camera phones to track market price dispersion. In: Proceedings of the ACM UrbanSense, Raleigh, NC, 4 November 2008.

16.

Brabham

DC.

Moving the crowd at threadless: motivations for participation in a crowdsourcing application. Inform Comm Soc 2010; 13(8): 1122–1145.

17.

Smith

Price

GR.

The logic of animal conflict. Nature 1973; 246: 15.

18.

Smith

JM.

Evolution and the theory of games. Cambridge: Cambridge university Press, 1982.

19.

Chen

Huang

Evolutionarily stable spectrum access. IEEE T Mobile Comput 2012; 12(7): 1281–1293.

20.

Niyato

Hossain

Dynamics of network selection in heterogeneous wireless networks: an evolutionary game approach. IEEE T Veh Technol 2009; 58(4): 2008–2017.

21.

Wang

Cheng

Mohapatra

. Artsense: anonymous reputation and trust in participatory sensing. In: Proceedings of the IEEE INFOCOM, Turin, 14–19 April 2013.

22.

Boutsis

Kalogeraki

. Privacy preservation for participatory sensing data. In: Proceedings of the 2013 IEEE international conference on pervasive computing and communications, San Diego, CA, 18–22 March 2013.

23.

Xing

Wan

. Mutual privacy-preserving regression modeling in participatory sensing. In: Proceedings of the 2013 IEEE INFOCOM, Turin, 14–19 April 2013.

24.

Liu

Zheng

. Efficient 3g budget utilization in mobile participatory sensing applications. In: Proceedings of the IEEE INFOCOM, Turin, 14–19 April 2013.

25.

Luo

Tham

Fairness and social welfare in incentivizing participatory sensing. In: Proceedings of the IEEE sensor, mesh and Ad Hoc communications and networks, Seoul, South Korea, 18–21 June 2012.

26.

Zhu

Wang

Forman

. Mining large-scale GPS streams for connectivity refinement of road maps. Comput J 2015; 58(9): 2109–2119.

27.

Zhu

Zhao

Zhang

Delay-constrained data aggregation in vanets. IEEE T Veh Technol 2015; 64(5): 2097–2107.

28.

Jiang

Zhu

Wang

. TMC: exploiting trajectories for multicast in sparse vehicular networks. IEEE T Parall Distr 2015; 26(1): 262–271.

29.

Wang

. hJam: attachment transmission in WLANs. IEEE T Mobile Comput 2013; 12(12): 2334–2345.

30.

Tan

Liu

. Side channel: bits over interference. IEEE T Mobile Comput 2012; 11(8): 1317–1330.

31.

Tan

Ngan

H-L

. Chip error pattern analysis in IEEE 802.15. 4. IEEE T Mobile Comput 2012; 11(4): 543–552.

32.

Zhang

. Cuts: improving channel utilization in both time and spatial domain in WLANs. IEEE T Parall Distr 2014; 25(6): 1413–1423.

33.

Wang

Zhang

. Tim: fine-grained rate adaptation in WLANs. IEEE T Mobile Comput 2016; 15(3): 748–761.

34.

Jaimes

Vergara-Laurens

Labrador

. A location-based incentive mechanism for participatory sensing systems with budget constraints. In: Proceedings of the IEEE International Conference on Pervasive Computing and Communications (PERCOM), Lugano, 19–23 March 2012.

35.

Clark

Oswald

AJ.

Satisfaction and comparison income. J Public Econ 1996; 61(3): 359–381.

Evolutionary stable participation game of smartphones in crowdsourced sensing

Abstract

Keywords

Introduction

Related work

Crowdsourced sensing applications

Incentive mechanisms

Evolutionary games

Other issues in crowdsourced sensing

Preliminaries

System model

Evolutionary game

Replicator dynamics and evolutionary stable strategy

Replicator dynamics

Evolutionary stable strategy

Definition 1 (ESS)

Definition 2 (strict Nash equilibrium)

Evolutionary stable participation game

Evolutionary stable participation game formulation

Evolutionary dynamics

Theorem 1

Analysis on evolutionary equilibrium

Theorem 2

Corollary 1

Analysis on complexity and cost

Evolutionary stable participation algorithm

Simulations

Simulation setup

Strategy adaptation factor α

Convergence time

Global asymptotic stability

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References

Strategy adaptation factor $α$