Max-Min Fairness Multi-task Allocation in Mobile Crowdsensing

Abstract

Mobile Crowdsensing (MCS) has become a new paradigm of collecting and merging a large number of sensory data by using rich sensor-equipped mobile terminals. Existing studies focusing on multi-task allocation with the objective of maximizing the social utility may result in the problem of unbalanced allocation due to the limited resources of workers, which may damage the social fairness, and requesters who suffer unfairness will choose to leave the system, thereby destroying the long-term stability of the system. To address this issue, we introduce max-min fairness into the design of a novel fairness-aware incentive mechanism for MCS. We first formalize the max-min fairness-aware multi-task allocation problem by using the sensing time threshold of tasks as a constraint. By modeling the max-min fairness-aware multi-task allocation problem as a Stackelberg game consisting of multi-leader and multi-follower, we next compute the unique Stackelberg equilibrium at which the utilities of both requesters and workers are maximized. Then, we design a greedy algorithm to achieve max-min fairness while meeting the sensing time threshold required by the task. Finally, simulation results further demonstrate the impact of intrinsic parameters on social utility and price of fairness, as well as the feasibility and effectiveness of our proposed max-min fairness-aware incentive mechanism.

This work was supported in part by the National Natural Science Foundation of China (No. 62072411, 61872323, 61751303), in part by the Social Development Project of Zhejiang Provincial Public Technology Research (No. 2017C33054), in part by the Natural Science Foundation of Guangdong Province (No. 2018A030313061), and in part by the Guangdong Science and Technology Plan (no. 2017B010124001, 201902020016, 2019B010139001).

1 Introduction

With the rapid development of sensor technology, wireless communication, and the market of handheld mobile terminal, mobile terminals have integrated rich built-in sensors including accelerometers, gyroscopes, contact image sensors, cameras, microphones, and global positioning systems (GPS), have become an interface for mobile users to obtain important information such as the surrounding environment, which has catalyzed and evolved mobile crowdsensing (MCS) [1]. MCS uses handheld mobile terminals carried by ubiquitous mobile users to collect and merge sensory data [2, 3], a series of research results have been achieved in the fields of communication (WiFi-Scout [4]), environmental monitoring (Third-Eye [5],Creekwatch [6]), traffic conditions (Vtrack [7], ContriSense: Bus [8]), and health caring (HealthAware [9]).

The success of MCS often depends on the active participation of a large number of workers and high quality of sensory data contributed by them. However, collecting sensory data often consumes a high cost in terms of resource consumption and even exposes workers to potential privacy risks, which greatly inhibits the enthusiasm of workers [10]. Meanwhile, with the development of MCS, tasks continue to emerge, and worker resources are relatively limited and it is difficult to grow simultaneously. In the multi-task allocation for the purpose of maximizing social utility, strategic workers will give priority to tasks with high rewards in the worker-centric model, while the platform will give priority to assigning highly capable and reliable workers to tasks with high value in the requester-centric model. The unbalanced allocation of heterogeneous worker resources will widen the gap in utility between requesters, and thus leading to unfair resource allocation. Requesters who suffer unfairness will choose to leave the system, thereby destroying the long-term stability of the system. Therefore, considering social fairness from the perspective of requesters’ utility distribution is an important issue to be solved urgently for multi-task allocation in MCS.

In the literature, many efforts with social fairness have been devoted to incentivizing users in MCS. Huang et al. [11] focused on the crowdsensing task assignment problem with multiple data consumers, and proposed an auction mechanism which can achieve max-min fairness and the essential economic properties, such as truthfulness, individual rationality and budget balance. Li et al. [12] designed the framework for publishing tasks based on decoy effect mechanism on the platform side, and the payoff allocation based on fairness preference mechanism for the user side, respectively, which can increase the utility of the platform and the users. However, in addition to classic fairness concepts, most of the existing literatures combine the system model to define the special fairness concept. By considering the effects of malicious competition behavior and the “free-riding” phenomenon, Zhu et al. [13] proposed incentive mechanism based on an auction combining the concepts of reverse auctions and Vickrey auctions, which can effectively improve fairness of the bidding and the quality of the sensory data. Tao et al. [14] used Jain’s fairness index to evaluate the fairness of tasks, which measures whether tasks receive a fair share of system resources. And the maximum value 1 of Jain’s fairness index is achieved when all tasks receive the same number of data samples. Sooksatra et al. [15] considered multi-dimensional fairness while selecting winning providers, and designed a fairness-aware auction mechanism to incentive users to stay in the system in a long run. Unfortunately, the above literature lacks indicators such as price of fairness to measure social fairness and social utility are usually based on empirical models without accurate mathematical models to formulate and quantify the fairness, and some fairness concepts are difficult to apply directly to the general MCS system. In contrast, we initiate the study of strategy-proof and fairness-aware incentive mechanism for multi-task allocation in MCS for the first time, and show that our mechanism maintains max-min fairness at a low cost.

Our main contributions are summarized as follows:

• We introduce the concept of max-min fairness, and formalize the max-min fairness-aware multi-task allocation problem by taking into account the sensing time threshold of tasks.

• We model the multi-task allocation as a Stackelberg game consisting of multi-requester and multi-worker, and then transform the max-min fairness-aware multi-task allocation problem into the max-min fairness-aware incentive mechanism design problem.

• We show how to compute the unique Stackelberg equilibrium, consisting of a unique Nash equilibrium for the sensing plan game and a unique Nash equilibrium for the reward declaration game, at which the utilities of both requesters and workers are maximized.

• We design a greedy algorithm to achieve max-min fairness while meeting the sensing time threshold required by the task. Simulation results further demonstrate how intrinsic parameters impact on the social utility, and the price of fairness.

In the rest of this article, we first introduce the preliminaries and formulate the problem in Sect. 2, and develop a max-min fairness-aware incentive mechanism as well as the design details of our mechanism in Sect. 3. Section 4 evaluates the performance, and conclusions are drawn in Sect. 5.

2 Preliminaries and Problem Formulation

2.1 System Model

Multi-task allocation is a MCS framework consisting of a platform, a set ${\mathcal{W}} = \left\{ {w_{1} , \ldots ,w_{i} , \ldots ,w_{n} } \right\}$ of workers, and a set ${\mathcal{R}} = \left\{ {r_{1} , \ldots ,r_{j} , \ldots ,r_{m} } \right\}$ of requesters. Taking into account the practical factors (e.g., time, location, effort, etc.), without loss of generality, a worker (or requester) is usually assumed to be able to participate in (or publicize) only one task. It is easy to find that this paper is not limited to this assumption, when a worker (or requester) chooses to participate in (or publicize) multiple tasks, we simply treat her as multiple workers (or requesters). As illustrated in Fig. 1, a typical transaction of multi-task allocation in MCS can be described as follows: First, each requester $r_{j}$ posts a task $\tau_{j}$ with its budget $B_{j}$, unit value $\kappa_{j}$, and sensing time threshold $V_{j}$, which are sent to the platform (step 1). The platform collects and publishes the set ${\mathcal{T}} = \left\{ {\tau_{1} , \ldots ,\tau_{j} , \ldots ,\tau_{m} } \right\}$, $B = \left\{ {B_{1} , \ldots ,B_{j} , \ldots ,B_{m} } \right\}$ as well as $K = \left\{ {\kappa_{1} , \ldots ,\kappa_{j} , \ldots ,\kappa_{m} } \right\}$ of tasks (step 2). After reading the description of tasks, each worker $w_{i}$ submits a set $\varGamma_{i}$ of tasks that she is interested and her unit cost $c_{i}$ to the platform (step 3). After collecting the workers’ unit cost set ${\mathcal{C}} = \left\{ {c_{1} , \ldots ,c_{i} , \ldots ,c_{n} } \right\}$, the tasks’ unit value set $K$ and sensing time threshold set $V$, the platform will decide each task is allocated to which users, and the winning workers set for each task $\tau_{j}$ is denoted as ${\mathcal{S}}_{j}$ (step 4). Then each worker $w_{i} \in {\mathcal{S}}_{j}$ determines her sensing time $t_{ij}$, uploads the sensory data to the platform and gets the payment from the platform as her reward (step 6). Conveniently, Table 1 lists frequently used notions in this paper.

Fig. 1.

Framework of multi-task allocation in mobile crowdsensing

Table 1. Summary of notations in this paper.

Each rational and selfish worker will not participate in a task unless there exists a sufficient payment to compensate for her cost. Given the budget $B_{j}$ and the winning workers set ${\mathcal{S}}_{j}$ for task $\tau_{j}$, as well as the unit cost $c_{i}$, the worker $w_{i}$ is only interested in maximizing her own utility by making her optimal sensing time $t_{ij}$.

Definition 1

(Worker’s Utility). A worker $w_{i} 's$ utility $u_{i}^{w}$ is defined as

$$ u_{i}^{w} = \left\{ {\begin{array}{*{20}l} {p_{ij} \left( {B_{j} ,T_{j} } \right) - c_{i} t_{ij} ,} \hfill & {if\,w_{i} \in {\mathcal{S}}_{j} \,and\,t_{ij} \ne 0} \hfill \\ {0,} \hfill & {otherwise} \hfill \\ \end{array} } \right. $$

(1)

Where $c_{i} t_{ij}$ is the total cost of $w_{i}$ performing the task $\tau_{j}$, $t_{ - ij}$ is the sensing time strategy profile for a set ${\mathcal{S}}_{j}$ excluding $w_{i}$, and thus the set of sensing time strategy profile of all workers in ${\mathcal{S}}_{j}$ can be written as $T_{j} = \left( {t_{ij} ,t_{ - ij} } \right)$. The reward received by worker $w_{i}$ is proportional to her sensing time $t_{ij}$, $p_{ij} \left( {B_{j} ,T_{j} } \right)$ based on the task $\tau_{j} 's$ budget $B_{j}$ and the sensing time strategy profile $T_{j}$ is defined as

$$ p_{ij} \left( {B_{j} ,T_{j} } \right) = B_{j} \times \frac{{t_{ij} }}{{\mathop \sum \nolimits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} }} $$

(2)

Substituting (2) into (1), a worker $w_{i} 's$ utility $u_{i}^{w}$ can be rewritten as

$$ u_{i}^{w} = \left\{ {\begin{array}{*{20}l} {B_{j} \times \frac{{t_{ij} }}{{\mathop \sum \nolimits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} }} - c_{i} t_{ij} ,} \hfill & {if\,w_{i} \in {\mathcal{S}}_{j} \,and\,t_{ij} \ne 0} \hfill \\ {0,} \hfill & {otherwise} \hfill \\ \end{array} } \right. $$

(3)

At the requester side, a requester $r_{j}$ will receive a service benefit as long as there exists a non-empty set ${\mathcal{S}}_{j}$ of workers participating in her publicized task $\tau_{j}$, and the total sensing time is not lower than the threshold $V_{j}$. The service benefit $b_{j} \left( {\kappa_{j} ,T_{j} } \right)$ based on the task $\tau_{j} 's$ unit value $\kappa_{j}$ and the sensing time strategy profile $T_{j}$ is defined as

$$ b_{j} \left( {\kappa_{j} ,T_{j} } \right) = \left\{ {\begin{array}{*{20}l} {\left( {\kappa_{j} \mathop \sum \limits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} } \right)^{\theta } ,} \hfill & {if\,{\mathcal{S}}_{j} \ne \varnothing \,and\,\mathop \sum \limits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} \ge V_{j} } \hfill \\ {0,} \hfill & {otherwise} \hfill \\ \end{array} } \right. $$

(4)

Definition 2

(Requester’s Utility). A requester $r_{j} 's$ utility $u_{j}^{r}$ is defined as

$$ u_{j}^{r} = \left\{ {\begin{array}{*{20}l} {\left( {\kappa_{j} \mathop \sum \limits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} } \right)^{\theta } - B_{j} ,} \hfill & {if\,{\mathcal{S}}_{j} \ne \varnothing \,and\,\mathop \sum \limits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} \ge V_{j} } \hfill \\ { - B_{j} ,} \hfill & {otherwise} \hfill \\ \end{array} } \right. $$

(5)

where the range of $\theta \in \left( {0,1} \right)$ makes $u_{j}^{r}$ a strictly concave function in $\mathop \sum \limits_{{x:w_{x} \in S_{j} }} t_{xj}$, which reflects the common phenomenon of diminishing marginal utility in economics.

2.2 Max-Min Fairness-Aware Multi-task Allocation Problem

We consider the multi-task allocation in MCS as a general resource allocation problem assigning different quantities of the given workers to different tasks. Formally, such a problem is given for a set of $m$ tasks ${\mathcal{T}} = \left\{ {\tau_{1} , \ldots ,\tau_{j} , \ldots ,\tau_{m} } \right\}$, and defined by the set of all feasible solution ${\rm X}$, i.e., allocations and $m$ utility functions $u_{j} :{\rm X} \to R^{ + }$ for each requester $r_{j} .$ Note that, $\chi_{1}$ and $\chi_{2}$ will be regarded as equivalent if $u_{j} \left( {\chi_{1} } \right) = u_{j} \left( {\chi_{2} } \right),\forall j:r_{j} \in {\mathcal{R}}$.

Definition 3

(Max-Min Fairness). A solution $\chi_{MM}$ is max-min fairness if the requester obtaining the lowest utility, still receives the highest possible utility.

$$ \chi_{MM} = arg\;\mathop {max}\limits_{{\chi \in {\rm X}}} \mathop {min}\limits_{j = 1, \ldots ,m} u_{j} \left( \chi \right) $$

(6)

Given the definition of max-min fairness, we now study the multi-task allocation problem, that is, the platform, as a decision maker, allocates which workers to which task in a balanced way under the constraint of sensing time threshold to balance the utilities of requesters, such a problem can formulated as follows:

Definition 4

(MMFMTA). The max-min fairness-aware multi-task allocation problem can be formulated as follows:

$$ \left\{ {\begin{array}{*{20}l} {\begin{array}{*{20}l} {\chi_{MM} = \text{arg}\;\mathop {\text{max}}\limits_{{\chi \in {\rm X}}} \mathop {\text{min}}\limits_{j = 1, \ldots ,m} u_{j} \left( \chi \right)} \hfill \\ {\begin{array}{*{20}c} {s.t.} & {\mathop \sum \limits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} \ge V_{j} ,\forall j:r_{j} \in {\mathcal{R}}} \\ \end{array} } \hfill \\ \end{array} } \hfill \\ \hfill \\ \end{array} } \right. $$

(7)

3 Max-Min Fairness-Aware Incentive Mechanism

We model the interaction between requesters and workers as a two-stage Stackelberg game consisting of multi-requester and multi-worker. In the first stage, a requester $r_{j}$’s strategy is her budget $B_{j}$. After the platform allocates the winning worker set ${\mathcal{S}}_{j}$ to the task $\tau_{j}$, in the second stage, a worker $w_{i}$ choose her optimal strategy, i.e., sensing time $t_{ij}$.

Given Eq. (5), the utility maximization problem for each requester $r_{j}$ can be formulated as:

$$ \begin{array}{*{20}l} {\left\{ {\begin{array}{*{20}l} {u_{j}^{r} \triangleq \mathop {\hbox{max} }\limits_{{B_{j} }} \left( {\kappa_{j} \mathop \sum \limits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} } \right)^{\theta } - B_{j} } \hfill \\ {s.t. B_{j} \ge 0,\forall j:r_{j} \in {\mathcal{R}}} \hfill \\ \end{array} } \right.} \hfill \\ \end{array} $$

(8)

Given Eq. (3), the utility maximization problem for each worker $w_{i}$ can be formulated as:

$$ \begin{array}{*{20}l} {\left\{ {\begin{array}{*{20}l} {u_{i}^{w} \triangleq \mathop {\hbox{max} }\limits_{{t_{ij} }} B_{j} \times \frac{{t_{ij} }}{{\mathop \sum \nolimits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} }} - c_{i} t_{ij} } \hfill \\ {s.t. t_{ij} \ge 0,\forall i,j:w_{i} \in {\mathcal{S}}_{j} } \hfill \\ \end{array} } \right.} \hfill \\ \end{array} $$

(9)

Aiming at the max-min fairness-aware multi-task allocation problem (7), we design a fair incentive mechanism based on Stackelberg game, which includes the sensing time game, the reward declaration game, and the max-min fairness-aware multi-task allocation algorithm. The Nash equilibria in the sensing time game and the reward declaration game are defined as follows.

Definition 5.

A set of strategies $T^{*} = \left\{ {t_{1}^{*} , \ldots ,t_{n}^{*} } \right\}$ is a NE of the sensing time game, if the following condition is satisfied

$$ u_{i}^{w} \left( {t_{i}^{*} ,t_{ - i}^{*} } \right) \ge u_{i}^{w} \left( {t_{i} ,t_{ - i}^{*} } \right),\forall i:w_{i} \in {\mathcal{W}} $$

(10)

Definition 6.

A set of strategies $B^{*} = \left\{ {B_{1}^{*} , \ldots ,B_{m}^{*} } \right\}$ is a NE of the reward declaration game, if the following condition is satisfied

$$ u_{j}^{r} \left( {B_{j}^{*} } \right) \ge u_{j}^{r} \left( {B_{j} } \right),\forall j:r_{j} \in {\mathcal{R}} $$

(11)

For the proposed multi-requester multi-worker Stackelberg game, Eq. (10) and Eq. (11) together form a Stackelberg equilibrium, which is defined as follows.

Definition 7.

Let $T^{*} = \left\{ {t_{1}^{*} , \ldots ,t_{n}^{*} } \right\}$ be a NE of the sensing time game, and $B^{*} = \left\{ {B_{1}^{*} , \ldots ,B_{m}^{*} } \right\}$ be a NE of the reward declaration game, the point $\left( {T^{*} ,B^{*} } \right)$ is an equilibrium for the Stackelberg game if for any $\left( {T,B} \right)$ that $T \ne T^{*}$ and $B \ne B^{*}$ , the following conditions are satisfied:

$$ \left\{ {\begin{array}{*{20}l} {u_{i}^{w} \left( {B^{*} ,t_{ij}^{*} ,t_{ - ij}^{*} } \right) \ge u_{i}^{w} \left( {B^{*} ,t_{ij} ,t_{ - ij}^{*} } \right),} \hfill & {\forall i:w_{i} \in {\mathcal{W}}} \hfill \\ {u_{j}^{r} \left( {B_{j}^{*} ,T^{*} } \right) \ge u_{j}^{r} \left( {B_{j} ,T^{*} } \right),} \hfill & {\forall j:r_{j} \in {\mathcal{R}}} \hfill \\ \end{array} } \right. $$

(12)

At the Stackelberg equilibrium, neither the requesters nor the workers have incentive to deviate, and thus the fairness-aware multi-task allocation problem can be transformed to the fairness-aware incentive mechanism design problem:

Definition 8

(MMFIM). The max-min fairness-aware incentive mechanism design problem can be formulated as follows

$$ \left\{ {\begin{array}{*{20}l} {\chi_{MM} = \arg \mathop {\hbox{max} }\limits_{{\chi \in {\rm X}}} \mathop {\hbox{min} }\limits_{j = 1, \ldots ,m} u_{j} \left( \chi \right)} \hfill \\ {\begin{array}{*{20}c} {s.t.} & {\left\{ {\begin{array}{*{20}c} {\begin{array}{*{20}l} {\mathop \sum \limits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} \ge V_{j} ,\forall j:r_{j} \in {\mathcal{R}}} \hfill \\ {\begin{array}{*{20}l} {u_{i}^{w} = \mathop {\hbox{max} }\limits_{{t_{ij} \ge 0}} u_{i}^{w} ,\forall i:w_{i} \in {\mathcal{W}}} \hfill \\ {u_{j}^{r} = \mathop {\hbox{max} }\limits_{{B_{j} \ge 0}} u_{j}^{r} ,\forall j:r_{j} \in {\mathcal{R}}} \hfill \\ \end{array} } \hfill \\ \end{array} } \\ \end{array} } \right.} \\ \end{array} } \hfill \\ \end{array} } \right. $$

(13)

3.1 NE in the Sensing Time Game

Given the set of winning workers ${\mathcal{S}}_{j}$ for task $\tau_{j}$ allocated by the platform, we focus on determining whether there exists a NE in the sensing time game, and whether the NE is unique. If the answers to the above two questions are affirmative, then how to calculate the unique NE is very necessary. In order to address these issues, we first introduce the concept of optimal sensing time strategy for the workers.

Definition 9

(Optimal Sensing Time Strategy). Given $B_{j}$, ${\mathcal{S}}_{j}$ and $t_{ - ij}$, a worker $w_{i} 's$ optimal sensing time strategy $\bar{t}_{ij}$ maximizes $u_{i}^{w} \left( {\bar{t}_{ij} ,t_{ - ij} } \right)$ over all $\bar{t}_{ij} \ge 0$.

According to Definition 5, each worker will choose her optimal sensing time strategy in a NE, and hence we can obtain the value of $\bar{t}_{ij}$, as shown in Lemma 1.

Lemma 1.

Given a task $\tau_{j}$ with the corresponding budget $B_{j}$ and the set of winning workers ${\mathcal{S}}_{j}$ , the optimal sensing time strategy for worker $w_{i} \in {\mathcal{W}}$ is

$$ \bar{t}_{ij} = \left\{ {\begin{array}{*{20}l} {\epsilon,} \hfill & {if\,l = 1} \hfill \\ {0,} \hfill & {if\,i \ge z} \hfill \\ {\frac{{B_{j} \left( {\left| {{\mathcal{S}}_{j} } \right| - 1} \right)\left[ {\mathop \sum \nolimits_{{x:w_{x} \in {\mathcal{S}}_{j} }} c_{x} - c_{i} \left( {\left| {{\mathcal{S}}_{j} } \right| - 1} \right)} \right]}}{{\left( {\mathop \sum \nolimits_{{x:w_{x} \in {\mathcal{S}}_{j} }} c_{x} } \right)^{2} }},} \hfill & {otherwise} \hfill \\ \end{array} } \right. $$

(14)

where the workers in ${\mathcal{S}}_{j}$ are sorted by the unit cost such that $c_{1} \le c_{2} \le \cdots \le c_{l}$, $z = \hbox{max} \left\{ {x:2 \le x \le l,c_{x} \le \frac{{\mathop \sum \nolimits_{y = 1}^{x} c_{y} }}{x - 1}} \right\}$ and $\epsilon$ is a sufficiently small positive number, which is approximately 0 here.

Proof:

For the special case of $\left| {{\mathcal{S}}_{j} } \right| = 1$, the single worker $w_{i}$ can enjoy the total reward $B_{j}$ by contributing a small sensing time, denoted as $\bar{t}_{ij} \, = \, \epsilon$.

For the other cases, we know that $t_{ij} \in \left[ {0,\frac{{B_{j} }}{{c_{i} }}} \right]$ as $u_{i}^{w} \ge 0$ according to Eq. (3). The first-order and second-order derivatives of $u_{i}^{w}$ with respect to $t_{ij}$ are shown as follows

$$ \left\{ {\begin{array}{*{20}l} {\frac{{\partial u_{i}^{w} }}{{\partial t_{ij} }} = \frac{{B_{j} \left( {\mathop \sum \nolimits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} - t_{ij} } \right)}}{{\left( {\mathop \sum \nolimits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} } \right)^{2} }} - c_{i} } \hfill \\ {\frac{{\partial^{2} u_{i}^{w} }}{{\partial^{2} t_{ij} }} = \frac{{ - 2B_{j} \mathop \sum \nolimits_{{x:w_{x} \in S_{j} \backslash \left\{ {w_{i} } \right\}}} t_{xj} }}{{\left( {\mathop \sum \nolimits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} } \right)^{3} }}} \hfill \\ \end{array} } \right. $$

(15)

Given any $B_{j} > 0$, we know that $\frac{{\partial^{2} u_{i}^{w} }}{{\partial^{2} t_{ij} }} < 0$, which implies that $u_{i}^{w}$ is a strictly concave function in $t_{ij}$, and thus the optimal sensing time $\bar{t}_{ij}$ is unique if it exists. Let $\frac{{\partial u_{i}^{w} }}{{\partial t_{ij} }} = 0$, we obtain

$$ B_{j} \left( {\mathop \sum \limits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} - t_{ij} } \right) = c_{i} \left( {\mathop \sum \limits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} } \right)^{2} $$

(16)

Denote ${\mathcal{S}}_{j}^{ + } = \{ w_{i} \in {\mathcal{S}}_{j} :t_{ij} > 0\}$. By summing up Eq. (16) over all workers in ${\mathcal{S}}_{j}^{ + }$, we have

$$ \mathop \sum \limits_{{x:w_{x} \in {\mathcal{S}}_{j}^{ + } }} t_{xj} = \frac{{B_{j} \left( {\left| {{\mathcal{S}}_{j}^{ + } } \right| - 1} \right)}}{{\mathop \sum \nolimits_{{x:w_{x} \in {\mathcal{S}}_{j}^{ + } }} c_{x} }} $$

(17)

Since $t_{ij} = 0$ for $w_{x} \in {\mathcal{S}}_{j} \backslash {\mathcal{S}}_{j}^{ + }$, we know that $\mathop \sum \limits_{{x:w_{x} \in {\mathcal{S}}_{j}^{ + } }} t_{xj} = \mathop \sum \limits_{{y:w_{y} \in {\mathcal{S}}_{j} }} t_{yj}$. By substituting Eq. (17) into Eq. (16), we have

$$ t_{ij} = \frac{{B_{j} \left( {\left| {{\mathcal{S}}_{j}^{ + } } \right| - 1} \right)\left[ {\mathop \sum \nolimits_{{x:w_{x} \in {\mathcal{S}}_{j}^{ + } }} c_{x} - c_{i} \left( {\left| {{\mathcal{S}}_{j}^{ + } } \right| - 1} \right)} \right]}}{{\left( {\mathop \sum \nolimits_{{x:w_{x} \in {\mathcal{S}}_{j}^{ + } }} c_{x} } \right)^{2} }} $$

(18)

Next, we determine the set ${\mathcal{S}}_{j}^{ + }$. Any worker $w_{i} \in {\mathcal{S}}_{j}$ with $c_{i} < \frac{{\mathop \sum \nolimits_{{x:w_{x} \in {\mathcal{S}}_{j}^{ + } }} c_{x} }}{{\left| {{\mathcal{S}}_{j}^{ + } } \right| - 1}}$ has $t_{ij} > 0$, such a worker belongs to ${\mathcal{S}}_{j}^{ + }$. Furthermore, it can be seen that $t_{ij}$ is a monotonically decreasing function on variable $c_{i}$. Therefore, a worker with smaller cost has more incentive to devote more time. And hence ${\mathcal{S}}_{j}^{ + }$ consists of a consecutive set of workers, namely ${\mathcal{S}}_{j}^{ + } = \left\{ {w_{1} , \ldots ,w_{s} } \right\}$ for some $s \in \left[ {2,l} \right]$. Notice that if $c_{x} \ge \frac{{\mathop \sum \nolimits_{y = 1}^{x} c_{y} }}{x - 1}$ then $c_{x + 1} \ge \frac{{\mathop \sum \nolimits_{y = 1}^{x + 1} c_{y} }}{x}$. Thus $s$ must be the last index $x$ satisfying

$$ c_{x} \le \frac{{\mathop \sum \nolimits_{y = 1}^{x} c_{y} }}{x - 1} $$

(19)

Then the lemma follows.

By substituting Eq. (14) into Eq. (9), the maximum utility $u_{i}^{w}$ of a worker $w_{i}$ is

$$ u_{i}^{w} = \left\{ {\begin{array}{*{20}l} {B_{j} ,} \hfill & {if\,l = 1} \hfill \\ {0,} \hfill & {if\,i \ge z} \hfill \\ {B_{j} \times \left[ {1 - \frac{{c_{i} \left( {z - 1} \right)}}{{\mathop \sum \nolimits_{{x:w_{x} \in {\mathcal{S}}_{j} }} c_{x} }}} \right]^{2} ,} \hfill & {otherwise} \hfill \\ \end{array} } \right. $$

(20)

As a result, the output of Algorithm 1 is the unique NE of the sensing time game.

3.2 NE in the Reward Declaration Game

Given the set of winning workers ${\mathcal{S}}_{j}$ for task $\tau_{j}$ and the NE $T^{*}$ in the sensing time game, rational and self-interested requesters will strategically declare the budget $B_{j}$ to maximize her own utility. We now introduce the concept of optimal reward declaration strategy for the requesters.

Definition 10

(Optimal Reward Declaration Strategy). Given ${\mathcal{S}}_{j}$ and $T_{j}^{*}$, a requester $r_{j} 's$ optimal reward declaration strategy $\bar{B}_{j}$ maximizes $u_{j}^{r}$ over all $\bar{B}_{j} \ge 0$.

According to Definition 6, each strategic requester will choose her optimal reward declaration strategy in a NE, and hence we can obtain the value of $\bar{B}_{j} ,\forall j:r_{j} \in {\mathcal{R}}$.

Lemma 3.

Given $T_{j}^{*}$, the optimal reward declaration strategy $\bar{B}_{j}$ of requester $r_{j} \in {\mathcal{R}}$  is

$$ \bar{B}_{j} = \mathop {\hbox{max} }\limits_{{B_{j} \ge 0}} \left( {\kappa_{j} \mathop \sum \limits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj} } \right)^{\theta } - B_{j} $$

(21)

Proof:

This proof can be directly obtained by substituting $T_{j}^{ *}$ into Eq. (8), and is omitted here.

As a result, the output of Algorithm 2 is the unique NE of the reward declaration game.

3.3 Max-Min Fairness-Aware Multi-task Allocation Algorithm

In this section, we design a greedy max-min fairness-aware multi-task allocation two-stage algorithm, i.e., allocate a set of winning workers ${\mathcal{S}}_{j}$ for each task $\tau_{j}$ that satisfies the sensing time threshold $V_{j}$, as shown in Algorithm 3. In the first stage, the platform allocates workers to tasks in sequence to meet the sensing time threshold. In the second stage, the platform gives priority to allocating workers to the requester with the lowest utility to maintain the max-min fairness.

Firstly, the platform reorders elements in ${\mathcal{C}}$ so that $c_{1} \le c_{2} \le \ldots \le c_{n}$, and initializes $S_{j} = \varnothing , \forall j:r_{j} \in {\mathcal{R}}$. Similarly, reorder elements in ${\rm K}$ so that $\kappa_{1} \ge \kappa_{2} \ldots \ge \kappa_{z}$. In the first stage (lines 6-20), the platform judges whether the sensing time threshold $V_{j}$ of task $\tau_{j}$ is satisfied according to the order of ${\rm K}$, and then judges the next task. Otherwise, it is judged whether the unit cost $c_{i}$ of the worker $w_{i}$ meets the condition for joining the set of winning workers $S_{j}$, and update the set $S_{j}$, the sum of sensing time $\mathop \sum \limits_{{x:w_{x} \in {\mathcal{S}}_{j} }} t_{xj}$ and the requester $r_{j} 's$ utility $u_{j}^{r}$. Otherwise, delete $\tau_{j}$ from the task set ${\mathcal{T}}$, update $S_{j} = \varnothing$ and $u_{j}^{r} = 0$. When the sensing time threshold of all tasks are satisfied, the algorithm runs in the second stage (lines 21–25). The platform will find the requester with minimum utility value $r_{j\,min}$ and allocate the following workers to the task $\tau_{j\,min}$ until the set ${\mathcal{W}}$ is empty.

4 Performance Evaluation

4.1 Simulation Setup

In this section, we provide numerical results to evaluate the performance of the max-min fairness-aware incentive mechanism, and verify the impact of intrinsic parameters on social utility and price of fairness (PoF). Throughout our experiments, we assume that the value of $\kappa_{j} ,\forall j \in \left[ {1,m} \right]$ is subject to a Gaussian distribution $\kappa_{j} \sim N\left( {\mu_{1} ,\sigma_{1}^{2} } \right)$ (here, we fix $\mu_{1} = 100$). Similarly, we assume that the value of $V_{j} ,\forall j \in \left[ {1,m} \right]$ and the value of ${\mathcal{C}}_{i} ,\forall i \in \left[ {1,n} \right]$ are subject to a Gaussian distribution $V_{j} \sim N\left( {\mu_{2} ,\sigma_{2}^{2} } \right)$ and ${\mathcal{C}}_{i} \sim N\left( {\mu_{3} ,\sigma_{3}^{2} } \right)$ respectively (here, we fix $\mu_{2} = 3$ and $\mu_{3} = 5$).

4.2 Social Utility

Figure 2 illustrates how the social utility $U\begin{array}{*{20}c} { \triangleq \mathop \sum \nolimits_{{j:r_{j} \in {\mathcal{R}}}} u_{j}^{r} } \\ \end{array}$ is impacted by intrinsic parameters: (a) $m$; (b) $n;$ (c) $\sigma_{1}^{2} ;$ (d) $\sigma_{2}^{2} ;$ (e) $\sigma_{3}^{2}$. The social utility under the proposed max-min fairness-aware incentive mechanism is denoted as $U_{F}$, and the social optimum without considering fairness is denoted as $U$.

Fig. 2.

The impact of intrinsic parameters against social utility: (a) $m$; (b) $n;$ (c) $\sigma_{1}^{2} ;$ (d) $\sigma_{2}^{2} ;$ (e) $\sigma_{3}^{2} .$

First, the max-min fairness-aware multi-task allocation algorithm sacrifices some utilities of requesters, which leads to no matter how the intrinsic parameters change, $U_{F}$ is lower than $U$.

In Fig. 2(a), we fixed $n = 150$ and $\sigma_{1}^{2} = \sigma_{2}^{2} = \sigma_{3}^{2} = 5$, as the number of requesters increases, workers have more freedom of choice and avoid fierce competition, thus increasing the social optimum $U$. Similarly, in Fig. 2(b) we fixed $m = 10$ and $\sigma_{1}^{2} = \sigma_{2}^{2} = \sigma_{3}^{2} = 5$, as the number of workers increases, more workers can contribute more sensing time and bring greater service benefit, which increases the social optimum $U$. While in Fig. 2(a) and Fig. 2(b), as the number of requesters or workers increases, the social utility $U_{F}$ has fluctuated. This is because the interested task set $\Gamma _{i}$ of $w_{i}$ is randomly generated based on the task set ${\mathcal{T}}$, which leads to the difference and randomness of the winning workers set ${\mathcal{S}}_{j}$ allocated to the task.

In Fig. 2(c), we fixed $m = 10$, $n = 150$ and $\sigma_{2}^{2} = \sigma_{3}^{2} = 5$, it can be found that as $\sigma_{1}^{2}$ increases, that is, as the unit value of tasks become more diverse, the social utility $U_{F}$ and social optimum $U$ all have fluctuated and the gap between $U_{F}$ and $U$ is obvious. This is because workers will be assigned to high-value tasks preferentially without considering fairness, while some workers may be assigned to tasks with low value, which increases the gap between $U$ and $U_{F}$.

A similar phenomenon can be found in Fig. 2(d) and Fig. 2(e), as $\sigma_{2}^{2}$ and $\sigma_{3}^{2}$ increase respectively, $U_{F}$ and $U$ all have fluctuated, and it is easy to find that the gap between $U_{F}$ and $U$ in Fig. 2(d) is more significant than Fig. 2(e). In Fig. 2(d), as $\sigma_{2}^{2}$ increases, i.e., the sensing time threshold of tasks become more diverse, some tasks with higher value cannot meet the sensing time threshold, which will cause a relatively large loss of service benefit, and thus $U_{F}$ is far less than $U$. Whereas, in Fig. 2(e), as $\sigma_{3}^{2}$ increases, thus as the cost of workers become more diverse, workers with high cost have more opportunities to be assigned to tasks with lower value, which avoids bidding failures caused by too many workers competing for the same task and increases the number of winning workers, and thus $U_{F}$ is close to $U$.

4.3 Price of Fairness

In order to measure the loss of social utility $U_{F}$ compared to the social optimum $U$, we study the price of fairness in this section. Price of fairness is defined as $PoF = \frac{{U - U_{F} }}{U}$, it is easy to find that the range of PoF is $\left[ {0,1} \right]$. Similarly, from Fig. 2, we demonstrate how intrinsic parameters (a) $m$; (b) $n;$ (c) $\sigma_{1}^{2} ;$ (d) $\sigma_{2}^{2} ;$ (e) $\sigma_{3}^{2}$ impact on PoF. When the gap between $U_{F}$ and $U$ is small, the value of PoF will be small, otherwise, the value of PoF will be large. As shown in Fig. 3(a), when the number of requesters $m$ ranges from 16 to 20, the gap between $U_{F}$ and $U$ is small, and thus the value of PoF is small. However, when $m$ ranges from 26 to 30, the gap between $U_{F}$ and $U$ becomes more significant and thus the value of PoF becomes larger. Figure 3(b), Fig. 3(c), Fig. 3(d) and Fig. 3(e) are consistent with the situation in Fig. 3(a), and the reasons are similar.

Fig. 3.

The impact of intrinsic parameters against PoF: (a) $m$; (b) $n;$ (c) $\sigma_{1}^{2} ;$ (d) $\sigma_{2}^{2} ;$ (e) $\sigma_{3}^{2} .$

5 Conclusion

In this paper, we modeled the interaction between requesters and workers as a Stackelberg game consisting of multi-requester and multi-worker and developed a max-min fairness-aware incentive mechanism to address the dilemma that tasks are constantly emerging and worker resources are relatively limited in MCS. Under the proposed multi-task allocation algorithm, the distribution of requesters’ utility satisfies max-min fairness, which incentives users to keep sustainability in MCS effectively.