Spatial crowdsourcing: An AI-based quality-aware task allocation and procrastination prevention mechanism

Abstract

In a distributed system framework, spatial crowdsourcing (SC) is a highly important area of research where task allocation to task executors (TEs) is an important step. Tasks are requested by a task provider and are allocated by an SC platform to TEs. However, TEs may submit the allocated task as late as possible, known as procrastination. Plenty of research works are available on task allocation in SC, whereas few research works are found that address procrastination. In a bipartite graph setting, a procrastination-aware scheduling is proposed. A recent work uses ChatGPT for procrastinating agents. Balanced distribution of tasks has not been addressed there. Recently, an algorithm was proposed that distributes tasks in a balanced manner in different slots to mitigate procrastination in SC. Here, we propose a quality-aware task allocation mechanism in an SC environment that combines a data science approach with a reinforcement learning-based approach. Once TEs are allocated tasks, we have proposed an AI-enabled (learning-the-variance) algorithm to distribute the tasks into slots with a more balanced distribution than any of the existing algorithms to mitigate procrastination. Our procrastination prevention mechanism outperforms existing methods, which is shown by extensive simulations. Analytically, it is shown that the proposed mechanism maintains a balanced distribution.

Keywords

spatial crowdsourcing distributed network procrastination variance learning

1. Introduction

When a large set of tasks is (task and job will synonymously be used) to be accomplished from a crowd is generally termed as crowdsourcing.¹ Mobile crowdsourcing (MCS), an extension of crowdsourcing, harnesses sensory and mobile devices to accomplish crowdsourcing tasks.² In MCS, a few tasks in some locations may not get enough task executors (TEs),³ and such a lack of TEs or agents is the reason for the inception of location-based crowdsourcing or spatial crowdsourcing (SC). In SC, TEs are allocated tasks with location information and a deadline (spatio-temporal constraint) to complete the tasks. For example, on-demand food delivery⁴ and transportation⁵ services, traffic information collection,⁶ etc.

At an abstract level in SC, we have task providers (TPs) who disseminate the tasks to the TEs through a platform, constrained by deadlines and specific locations.^7–11 Henceforth, TPs, TEs, and the platform will be assumed as agents (even if it is not explicitly mentioned in the context) in their usual sense.

As per recent research, SC is a highly important area of research in a distributed system framework.^12,13 There are multiple features of SC that reveal its distributed nature, which are discussed below.

In a distributed system, nodes or computing devices are distributed over a network and can act independently without the involvement of a central server. Similarly, TPs and TEs in SC as nodes, spread over different geographical locations, can perform task requests and task execution independently, bypassing the need for a central SC platform. However, the SC platform is needed only to match TP and TEs and assign tasks to TEs. It means, a TP can request tasks to the TEs, and each TE can execute the assigned tasks in a parallel manner and independently. The nodes in a distributed system are connected through a network. In the same way, a TP and a TE or two different TEs in SC can communicate with each other for task assignment, payment, rewards, etc., over mobile networks or the internet.

The nodes in SC can play the dual role of TP and TE, and each node can directly communicate with a subset of the other nodes. For such a direct communication, the connection (edge) between any two nodes is established if the distance between those two nodes is within a threshold value, and those nodes are called neighbours. A node that acts as a TP node can provide/float tasks to its neighbour TE nodes. The TE nodes may agree to accept the request or forward the requested tasks to their neighbour TE node(s). In this way, SC, in a sense, is general enough to be mapped to (has a connection with) a P2P Network,^14,15 where a node in SC can act as both TP and TE, but one at a time, and can send task requests to the TEs through the SC platform. The TEs who agree upon executing the tasks accept and execute the tasks. During task execution, the TEs act as peers and cooperate with each other for exchanging information, validating results, etc.

In an SC environment, a time-constrained agent, when assigned tasks with a deadline at a specific location, may delay submission of the assigned task, which is termed as procrastination^16–19 in behavioural economics.^20,21 This late submission of tasks or procrastination may be problematic for TP in many applications. So, there are two benefits if the prevention of procrastination is achieved. One immediate benefit will be for the TP, as she will be getting the completed tasks at certain intervals instead of getting all the tasks in tandem as late as possible. As a result, the TP will have sufficient time to process the submitted tasks at their end. Secondly, the quality of the accomplished task will be maintained as the task will be carried out uniformly throughout the period given to the TE.

In the literature, there are a few research works that address the issue of procrastination. One procrastination-aware scheduling is proposed in a bipartite setting in Wang et al.²² In their work, they have matched a set of jobs to several slots (a.k.a schedules, defined in Section 3). Each slot has a certain time limit and is constrained by a cost threshold. This method of matching jobs to different slots is not balanced. Due to such unbalanced matching, some slots will be matched with less number of jobs (NOJ) and some will be matched with more jobs. In this case, the slot with less NOJ is prone to procrastination.²⁰

Arakawa et al.²³ address the fact that if one agent procrastinates, then the agent will be helped through a large generative model as an API to give them some kind of continuation so that they can continue their work. But, they haven’t addressed the fact that how the tasks are to be distributed in a balanced manner.

In a recent work,²⁴ a poly-time job distribution algorithm in different slots in the SC environment is proposed to prevent procrastination. In that paper, the job allocation into slots is balanced to some extent. But a more balanced allocation of jobs into different schedules could be achieved.

In this paper, we propose two AI-enabled methods for task allocation and procrastination prevention, presented in two phases. In the first phase, we have proposed a quality-aware task allocation (QATA) algorithm. This algorithm first selects $k$ -heavy hitters, that is, $k$ number of TEs with top performance by a probabilistic method called Count-min-Sketch (CMS),²⁵ a data science approach, and assigns a subset of tasks to them. Here, the $k$ top-performing TEs, we mean that the TEs who performed tasks the highest number of times. For the rest of the TEs and tasks, this algorithm takes $ϵ$ -greedy, a multi-armed bandit (MAB)-based approach^26,27 to select TEs and assign tasks for them. QATA uses a proportionate ratio approach to assign tasks to the selected TEs, based on the total quality scores (defined in Section 4.1) of the TEs. In the second phase, we have proposed an AI-enabled (learning-the-variance) algorithm to distribute the tasks within a time horizon in a smooth (balanced) way so that procrastination can be prevented. We have considered the balanced allocation of jobs into schedules (balancing effect) in terms of total cost (TC), average cost (AC), and NOJ of each slot in this paper (defined in Section 3).

Mainly, by load balancing, it is meant as balancing the NOJ in different schedules or slots. In our paper, we have balanced the schedules or slots in terms of the cost of the jobs. However, along with considering the cost, balancing with NOJ is also considered while comparing with NOJ in UCSMPP and OFFPSP.

Recent research on task allocation addresses dynamic appearance of tasks and workers,^28–30, multi-objective optimization,³¹ heterogeneity and collaboration,³² etc. But, to the best of our knowledge, the problem of task assignment, along with procrastination prevention, has not been addressed in SC.

Our main contributions in this paper are summarized below:

We have proposed two methods (we have used the term methods or algorithms synonymously) in this paper – (i) for task allocation and (ii) for the prevention of procrastination.

A data science approach (CMS) is used for QATA, as it is faster in finding top-performing TEs (as the time complexity is linear). Along with CMS, an MAB-based approach is taken to address the cold start problem. The proposed approach for QATA has achieved a maximum task allocation to the TEs with a higher quality score.

In the second method, we have proposed an AI-enabled (learning-the-variance) algorithm to prevent procrastination by uniformly distributing the assigned tasks into several slots with equal deadlines.

We have compared our proposed procrastination prevention algorithm with the current state-of-the-art (SOTA) algorithms from the perspective of the distribution of tasks within a given time horizon and found that our proposed method has achieved a better balanced distribution of jobs than SOTA. We have also shown analytically that our proposed algorithm maintains the balanced distribution.

The remaining part of the paper is arranged in the following order. Relevant and recent literature is given in Section 2. The system model is furnished in Section 3. Sections 4 and 5 discuss the proposed algorithm and the analysis, respectively. Section 6 presents the simulation of the second proposed work, and it is compared with the relevant existing works in Section 7. The conclusion and future works are discussed in Section 8.

2. Literature review

One of the best explanations of procrastination is presented by George Akerlof et al.,²⁰ where he procrastinated for a long time in sending a parcel to his friend in the USA. A detailed discussion is given in the archived version of this paper.³³

A number of research works could be found in the direction of load balancing and time-constrained task scheduling in crowdsourcing and in other computational models. Some of them are, Mukhopadhyay et al.,^8,34 Meitei and Marchang,³⁵ Al-Muqarm and Hussien,³⁶ Feng and Xiao,³⁷ Zhao et al.,³⁸ and Zhou et al.³⁹ These works have focused either on scheduling with load balancing as in³⁵ or scheduling with deadline in Mukhopadhyay et al.,^8,34 Feng and Xiao,³⁷ Zhao et al.,³⁸ Zhou et al.,³⁹ or both Al-muqarm and Hussien.³⁶ Also, learning algorithms are employed for ground truth inference⁴⁰ and task allocation⁴¹ in SC. None of these works has addressed procrastination.

Arakawa et al.²³ (as mentioned in Section 1) have addressed procrastination using a large generative model. However, how to prevent such procrastination by balanced distribution of tasks within a time horizon has not been discussed.

Wang et al.²² have proposed an algorithm called Procrastination-aware-Scheduling for Tasks (OFFPSP). This algorithm has distributed a given set of jobs into a number of schedules (slots) based on a threshold set for each schedule, but not in a balanced manner. With these unbalanced schedules, the TP may face the same problem (will not get ample time) as stated earlier.

In Debnath et al.,²⁴ one procrastination preventive algorithm (UCSMPP) in the SC environment is proposed, where all the allotted jobs to the TEs are re-ordered according to their cost. From this ordered job list, jobs are pair-wise (first and last jobs, second and second last jobs, and so on) assigned to the corresponding schedules (slots). This way, all the jobs with higher cost are distributed among all the schedules, and those schedules become balanced in terms of cost (TC and AC) and NOJ. This algorithm shows a better balancing effect than in Wang et al.²² But this balancing effect could be improved, and that improvement has been proposed in our paper.

Debnath et al.²⁴ only address the problem of procrastination by balancing the allocation of tasks into slots using a novel classical algorithmic approach, but do not address the prior task assignment problem, that is, the tasks to be assigned to the TEs before the prevention of procrastination. In this paper, first, we have proposed a task assignment method with the combination of CMS and MAB, then addressed the problem of procrastination with a variance-based learning method. Such a combination of CMS and MAB approach for task assignment and a variance-based learning approach to address procrastination has not been applied in the SC literature to the best of our knowledge. In the sense that the task must be assigned to the TEs first, and then the possible procrastination is to be addressed, it is a more realistic approach than the approach proposed in Debnath et al.²⁴ in the SC scenario.

Another concept of behavioural economics is loss aversion, which states that the participating agents perceive loss more seriously than the equivalent profit. There are a few research works on this aspect of behavioural economics in MCS and/or SC scenarios. Some of them are Li et al.^42,43 and Liu et al.⁴⁴ in crowdsourcing and Liu et al.⁴⁵ in other computational models. This loss aversion-aware SC is another important research direction one can pursue.

3. System models

3.1. Notations and their usage

Our proposed algorithm first allocates tasks to the currently available TEs. After the allocation, when agents start executing the tasks, they may procrastinate, that is, the TEs may submit the allocated tasks on the last day or penultimate day, which may cause problems to the TP. In this model, our proposed algorithm pinpoints the prevention of procrastination by scheduling those allocated tasks in a balanced manner for an arbitrary $i^{th}$ TE $t e_{i}$ , such that it is scalable for any number of TEs. We also assume that the TEs can execute different types of tasks, and the number of tasks they can execute per unit time (task execution capacity) is also different. Now, we describe our model components below.

TP and TEs: Consider that we have $m$ agents spread over the SC region. Out of those $m$ agents, $m^{^{'}}$ are TPs and $m^{^{″}}$ are TEs. A TP/TE dual represents a node when SC is mapped to a distributed network. So, we can define a set of TPs as $T P = {t p_{1}, t p_{2}, t p_{3}, \dots, t p_{m^{^{'}}}}$ , where $| T P | = m^{^{'}}$ and a set of TEs as $T E = {t e_{1}, t e_{2}, t e_{3}, \dots, t e_{m^{^{″}}}}$ , where $| T E | = m^{^{″}}$ . Accordingly, $m = m^{^{'}} + m^{^{″}}$ .

Set of jobs: A set of $n$ jobs dispensed by any TP $t p_{i} \in T P$ with costs denoted as $Γ = {γ_{1}, γ_{2}, \dots, γ_{n}}$ and $C = {χ_{1}, χ_{2}, \dots, χ_{n}}$ , respectively, where $χ_{i} \in C$ is the cost of $γ_{i} \in Γ$ . $χ_{i} \in C$ may be considered as the amount of internet expenses, battery power, or distances to be travelled, etc., according to the requirement of the SC system. $Γ$ has a time horizon to complete, which is defined next. When a TE $t e_{i}$ is assigned some tasks at a location $l_{i}$ (defined in this section), is represented by $Γ t e_{i} = {{γ_{h}, γ_{h + 1}, \dots, γ_{s}}, l_{i}}$ with costs $C t e_{i} = {χ_{h}, χ_{h + 1}, \dots, χ_{s}}$ , where ${γ_{h}, γ_{h + 1}, \dots, γ_{s}} \subset Γ$ , ${χ_{h}, χ_{h + 1}, \dots, χ_{s}} \subset C$ and $h \geq 1, s > h$ .

Schedules and their deadlines: The time horizon or deadline $ζ$ (within which all the allocated jobs are to be completed) is divided into a set of schedules $Δ = {δ_{1}, δ_{2}, \dots, δ_{l}}$ and the duration of each $δ_{i}$ is $τ_{i}$ . Here $τ_{1} = τ_{2} = \dots = τ_{| Δ |}$ and $| Δ | = ζ / τ_{i}, w h e r e τ_{i} \in R, τ_{i} \neq 0, a n d τ_{i} \leq ζ$ . So, we can write $ζ = {τ_{1}, τ_{2}, \dots, τ_{l}}$ . $τ_{i}$ depends on the applications we are working in, and thus, our algorithm is flexible enough to be amenable to any such application. Let, for a TE $t e_{e}$ , $| Γ t e_{e} | = 10$ and $ζ_{e} = 21$ days. The platform distributes these 10 tasks into $Δ$ , where each $δ_{i} \in Δ$ has a deadline of 7 days. That means $τ_{1} = τ_{2} = \dots = τ_{| Δ |} = 7$ . If $τ_{i} = 7$ days, $| Δ | = ζ / τ_{i} = l = 3$ , and $Δ = {δ_{1}, δ_{2}, δ_{3}}$ . Accordingly, the deadline of the schedule $δ_{1}$ is first 7 days, the deadline of the schedule $δ_{2}$ is next 7 days, and so on. Each $δ_{i}$ is comprised of a subset of $Γ t e_{e}$ , defined as $δ_{i}^{w} : {γ_{j} ∣ γ_{j} \in Γ t e_{e} ∖ ⋃_{\begin{matrix} i^{^{'}} = 1 \\ i^{^{'}} \neq i \end{matrix}}^{l} δ_{i^{^{'}}}^{w}}, δ_{i}^{w} \subseteq Γ t e_{e}$ . So, each schedule $δ_{i}$ is a tuple denoted as $δ_{i} = {δ_{i}^{w}, τ_{i}}$ , where $τ_{i} \in ζ$ . After allocation of jobs into schedules, the TC of the $i^{th}$ schedule is represented by $δ_{i}^{c}$ , and the AC of $δ_{i}^{c}$ is calculated by dividing the TC of $δ_{i}^{c}$ by the NOJ of $δ_{i}^{c}$ . This setting applies to any single TE $t e_{e}$ assigned with some tasks $Γ t e_{e}$ .

Locations of tasks: As the proposed model deals with SC, location is an integral part of the problem. With such a viewpoint, an entire SC zone is divided into a set of locations $L = {l_{1}, l_{2}, \dots, l_{m}}, w h e r e m = | L |$ . Any location $l_{e} \in L$ is populated with a set of jobs $Γ$ by a TP $t p_{e}$ of that location. We have developed our algorithm by considering an arbitrary ( $e^{th}$ ) location so that it could be applicable to all $m$ locations under consideration in this SC model.

3.2. Objective

There are two objectives of our proposed model. Given any $t p_{i}$ and currently available TEs to $t p_{i}$ , our first objective is to maximize the allocation of tasks to each TE available to $t p_{i}$ as per the equation given below. As our first objective is to maximize the number of tasks allocated to each available TE, we are not considering the cost of a task as the allocation parameter during task allocation.

\begin{aligned} Maximize & | Γ t e_{i} | \\ Subject to \\ \sum_{i = 1}^{m^{^{″}}} Γ t e_{i} = Γ, \\ \forall_{Γ t e_{i}, Γ t e_{j}} \in Γ, {Γ t e_{i} \cap Γ t e_{j}} = \emptyset . \end{aligned}

Given a set of jobs $Γ t e_{i}$ for any TE $t e_{i}$ and the set of schedules $Δ$ , jobs are to be allocated into several schedules $δ_{i}$ ( $δ_{i} \in Δ$ ) in a balanced way for an agent (or for the set of agents who will perform the same set of jobs). The formulation of the objective function is given below.

\begin{aligned} Minimize & σ^{2} (δ_{1}^{c}, δ_{2}^{c}, \dots, δ_{l}^{c}) \\ Subject to \\ τ_{i} = \frac{ζ}{| Δ |}, \\ \sum_{c = 1}^{| Δ |} τ_{c} = ζ, \end{aligned}

where

σ^{2}

is the variance (see equation (8)) of schedules in terms of TC.

4. Proposed algorithms

In this section, we shall describe the algorithms proposed in this paper. First, the proposed task assignment algorithm is discussed, and then the proposed procrastination prevention algorithm is explained in detail.

4.1. Task assignment

The proposed method of task allocation first requires the TP to float task requests to its neighbouring TEs. If these TEs are not willing to participate in task assignment or require more TEs, they are required to forward the request to their neighbouring TEs. If the neighbouring TEs of TP refuse to forward the tasks, a game-theoretic setting may be considered by incorporating a tit-for-tat strategy, where if they don’t forward the task request, they will be penalized when they participate in future task assignments. Now, when the TP receives a list of TEs along with their quality scores, it gives the set of tasks and the received list of TEs along with their location to the SC platform. In this list, a TE might appear more than once with her quality score. A quality score for an agent $t e_{i}$ may be $q_{i} > 0$ or $q_{i} < 0$ for each appearance. The overall quality score, $t q_{i}$ of TE $t e_{i}$ , is calculated as the sum of quality scores of all its appearances. The total quality score $t q_{i}$ of $t e_{i}$ is calculated at the time of finding $k$ -heavy hitters using CMS. Having the list of TEs, the platform then takes two different approaches to assign tasks to the TEs.

4.1.1. Phase 1: CMS

In the first phase of the first proposed approach, the platform finds the $k$ top-performing agents. This can be mapped to find the $k$ -heavy hitters problem. We use a probabilistic data structure called CMS to find the heavy hitters, that is, the top performing agents based on the number of times the agent or the TE appears in the list given by the TP. After finding the top $k$ agents, the platform assigns $α | Γ |$ tasks located at a specified location, say $l_{i}$ , provided by the concerned TP, to those agents, where $0 < α < 1$ . The NOJ assigned to a TE is determined by the proportionate ratio method based on the total quality score of the top $k$ agents. Here, given a list of TEs, the platform is trying to identify the top-performing TEs using CMS, as if it is learning which TEs perform the best. So, the CMS can be thought of as a fast and clever learning approach.

Regarding CMS, the following mechanism is used. First, two parameters $K^{'}$ and $λ$ are taken. Then we make a list of $k$ -heavy hitters. It is ensured that all the TEs who appear at least $M / K^{'}$ (for brevity of the notation and ease of analysis, here it is considered that $M$ is the total TEs altogether in original list) times in the original list will be there in the list of $k$ heavy hitters. Also, it is ensured that every TE that appears in the list of $k$ heavy hitters occurs at least $(M / K^{'}) - λ M$ times in the original list. This setup ensures that there are no false negative cases (i.e., there are heavy hitters not appearing in the list of $k$ heavy hitters). However, there may be false positive cases (no heavy hitters can appear as heavy hitters in the list). But with suitable legitimate choices of $λ$ , we can ensure that those TEs also appear substantial number of times in the original list. This gives us a legitimate view of the sensitivity analysis of approximation of errors. To have good approximation results, we use $p$ number of hash functions (to be denoted with $h_{1}, h_{2}, \dots, h_{p}$ as the case may be) and for each hash function, a TE can be mapped in one of $q$ containers. Here, $p \times q << M$ . SHA256 hash function is used to produce a 256-bit string for each TE and then mod with $q$ maps each TE to a container that belongs to $q$ . For $p$ hash functions, either it can be drawn uniformly at random from a family of hash functions or a TE is hashed by a single hash function $p$ times, but each time a TE is appended by some different nudge. For determining the heavy hitter, ${min}_{i = 1}^{p} {CMS [i] [h_{i} (TE)]}$ is taken into consideration, and finally that value is taken as the value of the heavy hitter corresponding to that TE if it finally qualifies as the heavy hitter.

Error analysis: For error analysis, we fix a TE that qualifies for the heavy hitter and a hash function $p_{i} \in p$ ( $p_{i}$ is clear from the context). The count of TE will have two parts: (a) a fixed count for the TE and (b) the number of collisions for the TE when we hash other TEs. Let us suppose, we denote the actual count of the TE by $f_{a}$ and collision by $f_{c}$ . The total count is denoted by $f_{Tot}$ and is given by

\begin{aligned} f_{Tot} = f_{a} + f_{c} . \end{aligned}

(1)

f_{c}

is a random variable, so

f_{Tot}

is also the random variable.

Now, the count of $f_{c}$ we can capture by the concept of indicator random variable (IRV). To analyse this, let us call our fixed TE as $i$ and all other TEs by $j$ and $j \neq i$ . We define IRV corresponding to $j$ as:

\begin{aligned} X_{j} & = I {j^{th} TE collides with i} \\ = {\begin{cases} 1, & if collides, \\ 0, & otherwise. \end{cases} \end{aligned}

So,

\begin{aligned} f_{c} & = \sum_{j} X_{j} \\ \leq \sum_{j = 1}^{M} X_{j} \end{aligned}

Let us calculate

P r {j^{th} TE collides with i}

. We, hash under the assumption that the hash function distributes the TE uniformly.

So $P r {j^{th} TE collides with i} = 1 / q$ , where $q$ is the number of containers defined earlier. Now, taking the expectation of both sides of equation (1), we get:

\begin{aligned} E [f_{Tot}] & = E [f_{a} + f_{c}] \\ = E [f_{a}] + E [f_{c}] [by linearity of expectation] \\ \leq f_{a} + E [\sum_{j = 1}^{M} X_{j}] \\ = f_{a} + \sum_{j = 1}^{M} E [X_{j}] [by linearity of expectation] \\ = f_{a} + \sum_{j = 1}^{M} P r {j^{th} TE collides with i} \\ [by the property of IRV] \\ = f_{a} + \frac{M}{q} . \end{aligned}

So, we get

\begin{aligned} E [f_{Tot}] \leq f_{a} + \frac{M}{q} . \end{aligned}

(2)

Going back to equation (1), we can write

f_{c}

\begin{aligned} f_{c} = f_{Tot} - f_{a} [f_{c} is the amount of increased estimate of f_{a}] . \end{aligned}

Taking the expectation of both sides

\begin{aligned} E [f_{c}] & = E [f_{Tot}] - E [f_{a}] \\ \leq f_{a} + \frac{M}{q} - f_{a} [from equation (2)] \\ = \frac{M}{q} \\ = \frac{λ M}{e} [taking q = \frac{e}{λ}] . \end{aligned}

Now, applying Markov inequality, we get the bound of

f_{c}

as follows:

\begin{aligned} P r [f_{c} \geq e . E [f_{c}]] \leq \frac{1}{e}, \end{aligned}

that is,

\begin{aligned} P r [f_{c} \geq e \cdot \frac{λ M}{e}] & \leq \frac{1}{e} \end{aligned}

\begin{aligned} \Rightarrow P r [f_{c} \geq λ M] & \leq \frac{1}{e} . \end{aligned}

(3)

From equations (1) and (3) we can write:

\begin{aligned} P r [f_{Tot} \geq f_{a} + α M] \leq \frac{1}{e} . \end{aligned}

(4)

Now, we can take

min

of all hash values for the fixed TE into consideration as follows:

\begin{aligned} P r [{min}_{i = 1}^{p} f_{Tot} \geq f_{a} + α M] \\ = \prod_{i = 1}^{p} P r [f_{Tot} \geq f_{a} + α M] [if minimum satisfies, so does other] \\ \leq {(\frac{1}{e})}^{p} [by equation (4)] \\ = \frac{1}{e^{p}} . \end{aligned}

(5)

Now, the question is how much error (denoted by

β

) is our target? If the target is

β

then from equation (5), we can write

\begin{aligned} \frac{1}{e^{p}} & \leq β \\ \Rightarrow 1 & \leq β . e^{p} \\ \Rightarrow β . e^{p} & \geq 1 \\ \Rightarrow e^{p} & \geq \frac{1}{β} \\ \Rightarrow p & \geq \ln (\frac{1}{β}) . \end{aligned}

(6)

So, for a 0.5% error, the number of hash functions that will be sufficient is 6, calculated from equation (6).

Justification of time efficiency and scalability issue: Now, a follow-up analysis for space can justify the time efficiency and scalability issue.

Space is also an important parameter here. The amount of space required is:

\begin{aligned} p \times q = \frac{e}{λ} \cdot \ln (\frac{1}{β}) . \end{aligned}

One good choice for

λ = 1 / 2 k^{'}

. If

k^{'} = 100, β = 0.5 %

, then the space required is

\begin{aligned} \approx 2 \times 100 \times e \times 6 \\ = C \times 1000 [C is constant] . \end{aligned}

This shows that, with low space, that is, a big vector, namely the original list, is reduced to a small vector to be processed for finding the heavy hitters and thereby justifying the time efficiency and scalability issue.

4.1.2. Phase 2: MAB-based approach

In the second phase, we propose a reinforcement learning (RL)-based approach to select the remaining TEs and allocate tasks to them. RL involves an agent that learns from its environment, where the environment could be known or unknown to the agent. The environment can be represented as a set of states. The agent interacts with the environment by taking an action to change its current state to another state. There can be multiple actions associated with a state, and each action has a probability. The sum of all the probabilities of such actions is 1. Taking one of these actions, an agent transitions to a specific state. For each state change, an agent receives a reward, which can be positive or negative and is unknown to the agent; however, the agent is not guided on which action to take (see Figure 1). The agent’s objective is to find out the action that yields maximum rewards.

Figure 1.

Block diagram of reinforcement learning.

MAB is one kind of RL method where there are $n$ options/actions (arms of a slot machine) available to the agent. Pulling an arm, that is, choosing an option or action provides a reward drawn from an unknown distribution. The objective of an agent is to maximize the cumulative reward over a sequence of actions. So, an MAB problem can be viewed as a single-state RL problem. Mapping of each component of RL to the MAB is given in Table 1. In this phase, we have proposed an algorithm based on an $ϵ$ -greedy strategy, one of the MAB algorithms. The TEs can be considered as arms of the MAB, which are to be selected by the platform (as an RL agent), in this algorithm. When the platform chooses a TE and assigns tasks to her, it earns a reward.

In $ϵ$ -greedy, with probability $ϵ$ the platform explores, that means the platform chooses $k$ random arms, that is, random TEs, and with probability $(1 - ϵ)$ , the platform exploits, that means the platform chooses $k$ top arms, that is, top performing TEs, where $ϵ \in [0, 1]$ . For both exploration and exploitation phases, the platform uses the same proportionate method to assign tasks. If there is only one TE to be chosen in the exploration phase or the exploitation phase, the platform assigns all the remaining tasks if the number of remaining tasks is less than the lowest number of tasks assigned to the TE in the last exploitation phase or else the platform assigns the lowest number of tasks assigned to the TE in the last exploitation phase. When all TEs are assigned tasks, if some tasks are left unassigned, the platform will assign these tasks as one task at a time to all the TEs chosen as the first $k$ top-performing agents in the first phase, repeatedly. The NOJ allocated to a TE $t e_{i}$ is $| Γ t e_{i} |$ .

Table 1.

Mapping RL to MAB.

RL concept	MAB equivalence
State	Single (implicit) state
Actions	Arms (TEs)
Reward	Reward $R_{i}$ from arm $i$
Policy	Strategy for choosing arms
Transitions	No state transitions
Value function	Expected reward of each arm

RL: reinforcement learning; MAB: multi-armed bandit; TE: Task Executor.

In the proposed task assignment method, we have used CMS for selecting the top $k$ performing TEs. Then, for the rest of the TEs, we have used an $ϵ$ -greedy based approach for further selection of TEs. If there is (are) new TE(s) in the list who have not performed any task until now, they might get selected in the exploration round of the $ϵ$ -greedy based approach. For our combined approach of CMS and MAB, historical TE data across the rounds is retained, and the cold-start problem is handled by the $ϵ$ -greedy-based approach.

We provide the algorithm in Algorithm 1 followed by a numerical example.

Reward of SC platform: The reward for the platform for assigning tasks to a TE is the value derived from completed tasks minus the TC incurred by the platform. The reward has several components: (i) NOJ assigned to $t e_{i}$ , that is, $| Γ t e_{i} |$ , (ii) the total quality score of the TE $t q_{i}$ , (iii) the cost of the platform for assigning each task to the TE $C_{p}$ , which is uniform for all TEs, and (iv) an inherent value for each task being completed, which is called base value ( $V_{base}$ ). With these components, the reward of the platform ( $R W$ ) for selecting a TE (arm) is given in equation (7). $Q_{tot}$ is the total quality score of all the TEs. The $V_{base}$ is an adjustable parameter in the sense that the higher the quality score of a TE, the higher will be the actual value obtained by the platform for that TE, where actual value is $V_{base} \times (t q_{i} / Q_{tot})$ of TE $t e_{i}$ ,

\begin{aligned} {R W}_{t e_{i}} = | Γ t e_{i} | \times [(V_{base} \times \frac{t q_{i}}{Q_{tot}}) - C_{p}^{i}] . \end{aligned}

(7)

It is to be noted that for sustainability, the platform needs some operational cost, and because of that, the platform requires some reward. Here, $V_{base}$ and $C_{p}$ are the main ingredients for calculating the reward of the platform. $V_{base}$ is calculated as a function of the amount a TP pays for per unit task execution and the actual money disbursed to the TE for per unit task execution. For per-unit task assignment, the platform needs to expend some amount, such as internet costs, etc. For our setting, this cost is denoted by $C_{p}$ and realistically kept uniform throughout.

The policy in our proposed algorithm for the platform is a $ϵ$ -greedy policy for choosing a TE. The value function for the platform here is equivalent to the reward for each TE, as we are choosing each TE only once for assigning the current set of tasks to the currently available TEs. However, in the long run, the value function will be the expected reward for choosing a TE several times in future task allocations. Unlike other RL algorithms, an agent in the MAB algorithm cannot change state, as the environment is considered a single state with multiple actions.

4.1.3. QATA algorithm

QATA (Algorithm 1) allocates tasks using a combined approach based on CMS and MAB for selecting TEs and a common approach (proportionate ratio based on quality score) for assigning tasks to the TEs. Lines 2 to 12 find $k$ top performing TEs using CMS, and $α \times Γ$ tasks are assigned based on the proportionate ratio of the total quality score of each TE. The total quality score $t q_{i}$ for each TE $t e_{i}$ is calculated at each run in CMS. Using CMS, the platform can find the top quality TEs in one pass, that is, in linear time. For the remaining TEs in $T E$ , the platform takes an $ϵ$ -greedy (in MAB) based approach for selecting TEs (lines 13 to 37). If the remaining list $T E$ has a length more than 1, with probability $1 - ϵ$ , CMS is applied to find $k$ top performing TEs, and tasks are allocated using the proportionate ratio based on the total quality score of each selected TE. Otherwise, the TE is assigned with the rest of the tasks if the NOJ is less than the least NOJ assigned to the TE of the $k$ top performing TEs; otherwise, it is assigned with the least NOJ tasks ( ${NOJ}_{least}$ ) assigned to the TE of the latest $k$ top performing TEs. In the same way, with probability $ϵ$ , we choose random $k$ TEs and assign tasks.

Then Algorithm 1 returns the list of TEs assigned with the tasks to the next proposed algorithm, procrastination preventive scheduling of jobs: a balanced perspective (PPSJBP). Example: Consider that the list of TEs with their quality scores and a set of 400 tasks are submitted to the SC platform by the TP. In this list, a TE appears more than once, meaning multiple times she has participated in task execution, and each appearance associates a quality score which is assigned after submitting tasks. A quality for each TE is either $+ 2$ or $- 1$ according to the performance of the TE. The submitted list of TEs is $T E = {< t e_{1}, - 1 >, < t e_{2}, - 1 >, < t e_{5}, - 1 >, < t e_{3}, - 1 >, < t e_{4}, - 1 >, < t e_{6}, - 1 > |, < t e_{2}, - 1 >, < t e_{3}, - 1 >, < t e_{4}, + 2 >, < t e_{1}, - 1 >, < t e_{5}, + 2 >, < t e_{6}, - 1 > |, < t e_{4}, + 2 >, < t e_{1}, - 1 >, < t e_{6}, + 2 >, < t e_{2}, + 2 >, < t e_{3}, - 1 > |, < t e_{1}, + 2 >, < t e_{3}, + 2 >, < t e_{2}, + 2 >, < t e_{6}, + 2 > |, < t e_{2}, + 2 >, < t e_{1}, + 2 >, < t e_{3}, + 2 > |, < t e_{1}, + 2 >, < t e_{3}, + 2 >, < t e_{2}, + 2 > |, < t e_{1}, + 2 >, < t e_{3}, + 2 >}$ . With this list, the platform finds the top $k$ performing TEs using CMS algorithm. The top $k$ TEs mean the TEs that appear most often. Along with that, the platform also determines the total quality score of each TE. In this example, the platform finds the TEs $< t e_{2}, 6 >, < t e_{3}, 5 >, < t e_{1}, 5 >$ as top $k$ TEs as they appeared most of the time, along with their total quality score. The number of times these top TEs appear in the list is an approximate count using CMS. The platform will assign the first $400 \times 0.65 = 160$ tasks (with $α = 0.65$ ) using the proportionate ratio method based on the total quality score of each selected TE. Accordingly, $t e_{1}$ is assigned with 104 tasks, $t e_{2}$ and $t e_{3}$ are assigned with 78 tasks each. Now, for $t e_{4}$ , $t e_{5}$ , and $t e_{6}$ , we apply the exploration–exploitation method (based on $ϵ$ -greedy of MAB) until all the TEs are assigned tasks or until all tasks are assigned to the TEs. In this example, we run $ϵ$ -greedy with probability $1 - ϵ$ (where $ϵ = 0.5$ ) and we find $t e_{3}$ and $t e_{6}$ with total quality scores 3 and 2 as top $k$ performing TEs and assign $(400 - 260) \times 0.65 = 91$ tasks using proportionate method to them, where $t e_{3}$ and $t e_{6}$ are assigned with 54 and 37 tasks, respectively. The list of TEs and tasks both are not empty, and there are 49 tasks left. So, with probability $ϵ = 0.5$ , we choose a TE randomly from the available TEs. We have only one TE left, $t e_{5}$ , with a total quality score of $1$ . So we assign the next 37 tasks from the task list as there is only one TE left and the least number of tasks assigned in the last exploration phase is 37, which is $< 49$ . There are no TE left to assign tasks, but the platform is left with $49 - 37 = 12$ more tasks. To maximize the task allocation, these tasks will be distributed to the first top $k$ TEs, $t e_{1}$ , $t e_{2}$ , and $t e_{3}$ repeatedly such that out of 12 tasks $t e_{1}$ is assigned with the first task, $t e_{2}$ is assigned with the second task, $t e_{3}$ is assigned with third task and so on. $t e_{1}$ , $t e_{2}$ , and $t e_{3}$ are chosen to assign these 12 tasks as they are top-performing TEs.

The list of TEs ( $T E$ ) and the assigned tasks are propagated to the second proposed algorithm, PPSJBP, to prevent/reduce the chance of procrastination (in Section 4.2).

4.2. Prevention of procrastination

In this section, we have discussed the proposed algorithm called PPSJBP. The algorithm, PPSJBP, is based on minimizing the variance of all the schedules based on TC that is, all the jobs are distributed among the schedules in a balanced manner based on TC. When all schedules are balanced, all jobs with a higher cost will uniformly be distributed into different schedules. Thus, the accumulation of higher-cost jobs into one schedule will be prevented. As mentioned earlier in Section 1 that in the case of an unbalanced distribution of jobs, there may be fewer NOJ in any schedule with high cost. With less NOJ, the participating agents might have a mindset of Akerlof’s story²⁰ and hence the participating agent will be prone to procrastination. But when the jobs are distributed into the schedules in a balanced manner, there is no scope for such a mindset which leads to the prevention of such delay, that is, procrastination. This algorithm is presented here for an arbitrary TE $t e_{i}$ allocated with tasks at a location $l_{i}$ and is applicable to any such TE (also mentioned earlier). We have presented a schematic diagram of the proposed algorithm, and then the underlying algorithm is discussed. An example of this algorithm is furnished at the end of this section.

4.2.1. Schematic diagram of PPSJBP

Figure 2 shows the flow diagram of our proposed algorithm. The set of tasks assigned to any $i^{th}$ TE, which is represented by $Γ t e_{i}$ , is available to the platform (block 1). The platform randomly distributes those tasks into $Δ$ (block 2). This process of distributing jobs into $Δ$ is repeated for $K$ (defined in Algorithm 2) times. For each repetition $k^{^{'}} \in K$ , the variance of $Δ_{k^{^{'}}}$ ( $Δ$ at ${k^{'}}^{th}$ repetition) based on TC is obtained as per equation (8) and compared with $min_var$ , which contains the $(k^{^{'}} - 1)^{th}$ minimum variance (block 3). If the variance of $Δ_{k^{^{'}}}$ is less than $min_var$ , then min_var is updated. At this step, the platform learns the minimum variance. When $k^{^{'}} > K$ , the platform obtains the set of schedules with minimum variance (block 4). Then, these schedules are published to the TEs in non-increasing order of TC (block 5).

\begin{aligned} σ^{2} (Δ_{k^{^{'}}}) = \frac{Σ_{i = 0}^{| Δ_{k^{^{'}}} |} (δ_{i k^{^{'}}}^{c} - {\bar{δ}}_{k^{^{'}}}^{c})^{2}}{| Δ_{k^{^{'}}} | - 1}, \end{aligned}

(8)

where

{\bar{δ}}_{k^{^{'}}}^{c}

is the mean of TC of all

δ_{i} \in Δ_{k^{^{'}}}

Figure 2.

Flow diagram of the proposed algorithm, procrastination preventive scheduling of jobs: a balanced perspective (PPSJBP).

4.2.2. Description of the proposed algorithm

Line 1 initializes $K$ and $min_var$ with two different large numbers and $Δ$ as an empty set in which the set of schedules with minimum variance will be assigned. Lines 2 to 18 repeat the process of random distribution of jobs into $Δ^{temp}$ and finding the minimum variance, for $K$ times. Lines 3 and 4 initialize $S_C$ as a list with $l$ number of 0, $Δ^{temp}$ as an empty set with $l$ empty subsets and assigns $Γ t e_{i}$ to $Γ^{temp}$ . Each empty subset in $Δ^{temp}$ represents an empty schedule. All initialization and assignment in lines 3 and 4 would be repeated for each $k^{^{'}} \in K$ . Lines 5 to 9 randomly assign $Γ_{temp}$ into $Δ^{temp}$ and find the TC of jobs that are assigned to each schedule. Line 6 selects a schedule and a job index randomly and assigns these to $r$ and id, respectively. Line 7 assigns the job $γ_{id}$ into $r^{th}$ schedule of $Δ^{temp}$ and delete the same job from $Γ_{temp}$ . In line 8, the cost, that is, $χ_{id}$ of the job $γ_{id}$ is added with the current value of $r^{th}$ index of $S_C$ and assigned to it. Lines 10 to 13 find the variance of $S_C$ , that is, the cost of all schedules and assigns it to $ν$ , where in line 12, $S_C^{mean}$ is the AC. In line 15, $ν$ is compared to $min_var$ , which contains the current minimum variance. If $ν \leq min_var$ , $ν$ replaces the current content of $min_var$ and assigns the schedules in $Δ^{temp}$ to $Δ$ . Here, the learning of minimum variance by the platform comes into the picture. Line 19 publishes the set of schedules with minimum variance $Δ$ (obtained in line 16) in non-increasing order of TC.

A note on value of $K$ : Corollary 1 (Section 5) reveals that the number of variances to be calculated to achieve the best minimum variance with a lower bound probability of 0.37 is approximately 1472 when $K = 4000$ (by expression $K / e$ of Corollary 1). That means if we calculate 1472 variances (i.e., the number of iterations), there is at least 37% chance to obtain the best minimum variance. When we take $K = 8000$ , to achieve the lower bound of 0.37, we need to find 2943 variances. To increase this lower bound, the value of $K$ is to be increased because this lower bound of 37% is giving a benchmark. If we compute less number of variances, the scenario would not be realistic. So, increasing the value of $K$ will give higher accuracy.

However, based on the simulation, we have observed that the value of $K$ could be in the range of $8 \times | Γ |$ to $40 \times | Γ |$ . Example: Let us have an example, where $Γ t e_{4} = {< γ_{1}, 4 >, < γ_{2}, 2 >, < γ_{3}, 8 >, < γ_{4}, 1 >, < γ_{5}, 9 >, < γ_{6}, 10 >, < γ_{7}, 5 >}$ , $T = 900$ and each $τ_{i} = 300$ . Hence, $l = 900 / 300 = 3$ and $Δ = {δ_{1}, δ_{2}, δ_{3}}$ . Let $K = 100$ . At each $k^{^{'}} \in K$ , the variance of TC of $Δ$ is calculated and compared with the previous minimum variance. At $k^{^{'}} = 4$ , the platform found the minimum of all variances and the corresponding distribution of tasks with their TC is $δ_{1} = {< γ_{1}, γ_{3} >, 12}$ , $δ_{2} = {< γ_{2}, γ_{4}, γ_{5} >, 12}$ , and, $δ_{3} = {< γ_{6}, γ_{7} >, 15}$ . Now, $δ_{1}, δ_{2}$ , and $δ_{3}$ will be published according to non-increasing order of TC. $δ_{3}$ will be published first with a cost of 15, which is to be submitted within the first 300 time units. Then $δ_{2}$ with cost 12 will be published next, which is to be submitted in the next 300 time units (starting from $301^{st}$ time unit) and $δ_{1}$ will be published last. So, the proposed algorithm ensures a smooth (balanced) submission of tasks instead of the submission on $T^{th}$ day or as late as possible, that is, prevention of procrastination.

Time complexity: The time complexity by PPSJBP is $O (K \times | Γ |)$ , where $K$ is the number of repetition of sampling of jobs, $| Γ |$ is the total NOJ.

In CMS, along with heavy hitters (TEs), a few non-heavy hitters (who are not very far away from the heavy hitters) may also creep in (false positive cases). For the task assignment phase, this is not a big issue, as non-heavy hitters are also close to the heavy hitters. However, in PPSJBP, we had to assign exact tasks in exact slots; otherwise, variance minimization could be troublesome. We have addressed this variance minimization by the learning-the-variance method (PPSJBP). The time complexity of PPSJBP is $O (K \times | Γ |)$ , which may be computationally intensive at large scales. But to have the exactness in variance minimization, we had to follow this trade-off (exactness in computation vs. time complexity), like other learning algorithms.

5. Analysis of the proposed algorithms

This section analyses QATA in terms of expected reward and regret bound, and PPSJBP in terms of balancing effect.

5.1. Analysis of QATA

The following analysis is motivated by Slivkins et al.²⁶ and Sutton and Barto.⁴⁶

Lemma 1
The expected reward of the SC platform for $t e_{i}$ after $T$ rounds,
$\begin{aligned} E [R_{t e_{i}}] = \sum_{t = 1}^{T} [| Γ t e_{i} |^{t} \times [(V_{base} \times \frac{t q_{i}^{t}}{Q_{tot}^{t}}) - C_{p_{i}}^{t}]] \cdot P r {t e_{i}^{t}} . \end{aligned}$

Proof.
The reward of the SC platform for $t e_{i}$ at each round $t \in T$ ( $T$ is the total number of rounds) depends on the choice of $t e_{i}$ , that is, if $t e_{i}$ wishes to participate in the current task allocation, then the platform gets reward for $t e_{i}$ , otherwise not. So, we need to consider the probability of $t e_{i}$ for participating in the $t^{th}$ round of task allocation, that is, $P r {t e_{i}}$ . Thus, the platform receives some non-zero reward, ${R W}_{t e_{i}}^{t}$ , in some rounds and 0 in others. Let us consider $R_{t e_{i}}$ , a random variable that takes the total rewards over $T$ rounds. We need to find the expected reward, that is, $E [R_{t e_{i}}]$ . To calculate the expected reward of $T$ rounds, we are interested in the reward obtained in each round. For that, $R_{t e_{i}}^{t}$ can be thought of as a random variable that represents the reward obtained at round $t$ against $t e_{i}$ , which is defined as
$\begin{aligned} R_{t e_{i}}^{t} = {\begin{cases} {R W}_{t e_{i}}^{t} & with P r {t e_{i}} of\ participation, \\ 0, & with (1 - P r {t e_{i}}) of\ participation . \end{cases} \end{aligned}$
So the expected value of $R_{t e_{i}}^{t}$ will be (equation (9)):
$\begin{aligned} E [R_{t e_{i}}^{t}] & = {R W}_{t e_{i}}^{t} \cdot P r {t e_{i}} + 0 \cdot (1 - P r {t e_{i}}) \\ = {R W}_{t e_{i}}^{t} \cdot P r {t e_{i}} . \end{aligned}$
(9)
And for $T$ rounds, the total reward obtained by the platform for $t e_{i}$ will be (equation (10)):
$\begin{aligned} R_{t e_{i}} & = R_{t e_{i}}^{1} + R_{t e_{i}}^{2} + \dots + R_{t e_{i}}^{T} \\ = \sum_{t = 1}^{T} R_{t e_{i}}^{t} . \end{aligned}$
(10)
From equations (9) and (10), we can derive equation (11).
$\begin{aligned} E [R_{t e_{i}}] & = E [\sum_{t = 1}^{T} R_{t e_{i}}^{t}] \\ = \sum_{t = 1}^{T} E [R_{t e_{i}}^{t}] \\ = \sum_{t = 1}^{T} {R W}_{t e_{i}}^{t} \cdot P r {t e_{i}^{t}} \\ = \sum_{t = 1}^{T} [| Γ t e_{i} |^{t} \times [(V_{base} \times \frac{t q_{i}^{t}}{Q_{tot}^{t}}) - C_{p_{i}}^{t}]] \cdot P r {t e_{i}^{t}} \\ from\ equation\ (7) . \end{aligned}$
(11)
This proves Lemma 1.

The following lemma is motivated by the proposition given in Slivkins et al.²⁶
Lemma 2
The proposed algorithm based on the $ϵ$ -greedy approach achieves a regret bound of $E [R (t)] \leq t^{2 / 3} \cdot O (F \ln t)^{1 / 3}$ with $ϵ_{t} = t^{- 1 / 3} \cdot O (F \ln t)^{1 / 3}$ , where $ϵ_{t}$ is the probability to explore at each of $t$ rounds, and $F$ is the number of TEs (arms) in the $ϵ$ -greedy-based approach.
Proof.
First, we define the regret in the $ϵ$ -greedy based approach. If $M_{a}$ is the expected reward generated by a TE $a$ , selected at random, and $M^{}$ is the best expected reward generated by selecting the top performing TE in the $ϵ$ -greedy based approach at each of $t$ rounds, then the regret is defined as (equation (12)), where $a_{s}$ is the TE selected at $s^{th}$ round:
$\begin{aligned} Rg (t) = M^{} \cdot t - Σ_{s = 1}^{t} M_{a_{s}} . \end{aligned}$
(12)

Consider ${\hat{M}}_{a}$ is the true average reward generated by the TE $a$ . At $t^{th}$ round for any TE $a$ with the regret $| {\hat{M}}_{a} - M_{a} | \leq η$ , we have the Hoeffding inequality as:
$\begin{aligned} P r {| {\hat{M}}_{a} - M_{a} | \leq η} \geq 1 - \frac{2}{t^{4}} . \end{aligned}$
(13)

Equation (13) states that the difference between the true mean ${\hat{M}}_{a}$ and the expected mean $M_{a}$ is within a small value $η$ has a very high probability. It could be represented as per equation (14), the complement of the above event:
$\begin{aligned} P r {| {\hat{M}}_{a} - M_{a} | \geq η} \leq \frac{2}{t^{4}} . \end{aligned}$
(14)

This follows from the union bound.⁴⁷ The quantity $2 / t^{4}$ is considered to show that the probability of the regret being greater than $η$ is negligible as $t$ grows large. Now, we can rewrite Hoeffding’s inequality with $F$ TEs, each TE is selected at random with exploration probability $ϵ_{t}$ for $t^{th}$ round with regret $| {\hat{M}}_{a} - M_{a} |$ , as in equation (15)²⁶:
$\begin{aligned} P r {| {\hat{M}}_{a} - M_{a} | \leq η} \geq 1 - 2 e^{- 2 η^{2} (t ϵ_{t} / F)} . \end{aligned}$
(15)
At $t^{th}$ round, the TE $a$ is explored with probability $ϵ_{t}$ . So, the exploration takes place $t ϵ_{t}$ rounds in expectation, and each TE is selected uniformly at random with probability $1 / F$ . In expectation, the number of times the TE $a$ is selected during exploration is $t ϵ_{t} / F$ .

From equations (13) and (15), we obtain $η = \sqrt{2 F \ln t / t ϵ_{t}}$ . Given this, we shall prove that the expected overall regret is asymptotically bounded by $t^{2 / 3} \cdot O (K l o g t)^{1 / 3}$ .

Now, consider the case where a TE $a$ is selected at the exploration round, which generates a minimum reward. If we scale the range of the minimum and maximum rewards to $[0, 1]$ for the ease of calculation, then we have the regret as $M^{} - M_{a} = 1 - 0 = 1$ , since $M^{} \leq 1$ and $M_{a} \geq 0$ . The scaling could be done as below.

In our paper, reward of a TE $t e_{i}$ is denoted by ${R W}_{t e_{i}}$ , the value of which lies within the bounds $[LB,\ UB]$ . Here, LB is some lower bound and UB is some upper bound. The normalized value of ${R W}_{t e_{i}}$ is defined as:
$\begin{aligned} R W_{t e_{i}}^{norm} = \frac{R W_{t e_{i}} - LB}{UB - LB} \end{aligned}$
where $LB > 0$ and $UB > LB$ .

That means the regret at exploration with probability $ϵ_{t}$ is at most 1 and the same at exploitation with probability $(1 - ϵ_{t})$ is at most $\sqrt{2 F \ln t / t ϵ_{t}}$ . We denote $\tilde{R} g (t) = ϵ_{t} \cdot 1 + (1 - ϵ_{t}) \cdot \sqrt{2 F \ln t / t ϵ_{t}}$ as regret for both exploration and exploitation at $t^{th}$ round. Since $\tilde{R} g (t)$ is a random variable as it takes the difference of the expected mean reward and the true mean reward of a randomly selected TE $a$ , we can write,
$\begin{aligned} E [\tilde{R} g (t)] & = ϵ_{t} \cdot 1 + (1 - ϵ_{t}) \cdot \sqrt{\frac{2 F \ln t}{t ϵ_{t}}} \\ \leq ϵ_{t} + \sqrt{\frac{2 F \ln t}{t ϵ_{t}}}, \end{aligned}$
(16)
where $t > 0, F > 0$ , and $0 \leq ϵ_{t} \leq 1$ .

Substituting $ϵ_{t}$ , the exploration probability with $ϵ_{t} = t^{- 1 / 3} (F \ln t)^{1 / 3}$ in equation (16), we get:
$\begin{aligned} E [\tilde{R} g (t)] & \leq ϵ_{t} + \sqrt{\frac{2 F \ln t}{t ϵ_{t}}} \\ = t^{- \frac{1}{3}} (F \ln t)^{\frac{1}{3}} + \sqrt{2} t^{- \frac{1}{3}} (F \ln t)^{\frac{1}{3}} \\ = t^{- \frac{1}{3}} (F \ln t)^{\frac{1}{3}} (1 + \sqrt{2}) \\ \approx t^{- \frac{1}{3}} (F \ln t)^{\frac{1}{3}} \end{aligned}$
(17)

$\begin{aligned} by\ ignoring (1 + \sqrt{2}), the\ constant\ term . \end{aligned}$
So, the overall expected regret over $t$ is:
$\begin{aligned} E [R g (t)] & = E [\sum_{s = 1}^{t} \tilde{R} g (s)] \\ = \sum_{s = 1}^{t} E [\tilde{R} g (s)] \\ = \sum_{s = 1}^{t} s^{- \frac{1}{3}} (F \ln s)^{\frac{1}{3}} . \end{aligned}$
(18)
We observe here that $\ln s \leq \ln t$ , for $1 \leq s \leq t$ . So, $(F \ln s)^{1 / 3} \leq (F \ln t)^{1 / 3}$ , which gives $s^{- 1 / 3} (F \ln s)^{1 / 3} \leq s^{- 1 / 3} (F \ln t)^{1 / 3}$ . Hence, from equation (18), we can write
$\begin{aligned} E [R g (t)] & = \sum_{s = 1}^{t} s^{- \frac{1}{3}} (F \ln s)^{\frac{1}{3}} \\ \leq (F \ln t)^{\frac{1}{3}} \sum_{s = 1}^{t} s^{- \frac{1}{3}} \\ = O ((F \ln t)^{\frac{1}{3}}) \sum_{s = 1}^{t} s^{- \frac{1}{3}} \\ \approx O ((F \ln t)^{\frac{1}{3}}) \int_{1}^{t} s^{- \frac{1}{3}} d s \\ approximated\ by\ the\ integral\ for\ large t \\ = O ((F \ln t)^{\frac{1}{3}}) {[\frac{3}{2} s^{\frac{2}{3}}]}_{1}^{t} \\ = O ((F \ln t)^{\frac{1}{3}}) \frac{3}{2} (t^{\frac{2}{3}} - 1) \\ \leq O ((F \ln t)^{\frac{1}{3}}) t^{\frac{2}{3}} \\ = t^{\frac{2}{3}} O ((F \ln t)^{\frac{1}{3}}) . \end{aligned}$
So, this proves the regret bound of the $ϵ$ -greedy based approach.

In the $ϵ$ -greedy strategy in MAB, an agent (the SC platform) explores with probability $ϵ_{t}$ , that is, chooses an arm (TE in our case) randomly. And with probability $(1 - ϵ_{t})$ , the agent exploits, that is, chooses the arm with the current best reward. This process is repeated for several rounds or time steps, say $t$ . The goal is to minimize the overall regret (defined in equation (12) of Lemma 2) over $t$ rounds. In order to do that, we need to balance the exploration and exploitation throughout $t$ rounds, which is known as the exploration–exploitation trade-off. In the initial time steps of $ϵ$ -greedy, more exploration is required than in the later time steps. It is because, at the beginning, the agent (platform in our case) does not have enough estimation that which arm is promising (the arm that produces high reward). With the increment of $t$ , the estimation of arms by the agent increases, and the need for exploration decreases. That means the probability to explore (i.e., $ϵ_{t}$ ) reduces or decays when time step $t$ increases. Accordingly, when $t$ increases, $(1 - ϵ_{t})$ increases, which means the probability of exploitation also increases. That means the agent can exploit more arms that produce higher rewards because the agent learns or estimates more arms as $t$ grows.

The correct decay rate of $ϵ_{t}$ maintains the balance between exploration and exploitation. If $ϵ_{t}$ is too large, for example, $ϵ_{t} = (F \ln t / t)^{1 / 2}$ , the number of explorations will be more, causing not enough exploitation of arms that produce high rewards. If $ϵ_{t}$ is too small, for example, $ϵ_{t} = (F \ln t / t)^{1 / 4}$ , then there will not be enough explorations leading to exploiting arms that produce average rewards. With $ϵ_{t} = (F \ln t / t)^{1 / 3}$ , the probability of exploration decays with a stable rate so that it balances the exploration–exploitation.
5.2. Analysis of PPSJBP

The following analysis is motivated by Upfal Eli⁴⁸ and Cormen et al.⁴⁹

Lemma 3
The probability of allocation of all higher cost jobs (suppose $J$ ) among $n$ jobs (where $| J | < n$ ) in a single schedule is $1 / l^{J}$ , where $l$ is the number of schedules.
Proof.
Let us fix any arbitrary schedule $j$ among $l$ schedules. Now, we define the event $A_{i j}$ (where $i = {1, \dots, J}$ ) as any $i \in J$ , is scheduled in an arbitrary schedule $j$ . Given the event $A_{i j}$ , we are interested in finding $P r {A_{1 j} \cap A_{2 j} \dots \cap A_{J j}}$ . If this probability is calculated, then we will find that for all $i \in J$ , event $A_{i j}$ will occur. So, we can write
$\begin{aligned} P r {A_{1 j} \cap A_{2 j} \cap \dots \cap A_{J j}} = P r {A_{1 j}} \cdot P r {A_{2 j} | A_{1 j}} \\ \cdot P r {A_{3 j} | A_{1 j} \cap A_{2 j}} \dots P r {A_{J j} | A_{1 j} \cap A_{2 j} \cap \dots \cap A_{(J - 1) j}} . \end{aligned}$
(19)
Now, according to our algorithm, any higher cost jobs ( $J$ ) may be allocated to the same schedule. But allocation of one higher cost job to one schedule has no impact on the other job, which is yet to be allocated to the same schedule. Consider the probability $P r {A_{2 j} | A_{1 j}}$ , where event $A_{1 j}$ , which has already occurred, that is, the $(1 j)^{th}$ job is already been allocated to a schedule, has no impact on the event $A_{2 j}$ , that is, event $A_{2 j}$ is independent of event $A_{1 j}$ . So we can write, $P r {A_{2 j} | A_{1 j}} = P r {A_{2 j}}$ . Similarly for probability $P r {A_{3 j} | A_{1 j} \cap A_{2 j}}$ , where two events $A_{1 j}$ and $A_{2 j}$ , which has already occurred have no impact on the event $A_{3 j}$ . So, it can be written as, $P r {A_{3 j} | A_{1 j} \cap A_{2 j}} = P r {A_{3 j}}$ . In a similar manner, we can also write $P r {A_{J j} | A_{1 j} \cap A_{2 j} \cap \dots \cap A_{(J - 1) j}} = P r {A_{J j}}$ . Accordingly, we can rewrite equation (19) for the event $A_{i j}$ that job $i$ is allocated to the same schedule $j$ as follows: $P r {A_{1 j} \cap A_{2 j} \cap \dots \cap A_{J j}} = P r {A_{1 j}} \cdot P r {A_{2 j}} \dots P r {A_{J j}}$ . The probability of the $i^{th}$ higher cost job to be allocated to the $j^{th}$ schedule is: $P r {A_{i j}} = 1 / l$ . So, for two higher cost jobs $P r {A_{i j} \cap A_{k j}} = (1 / l) \cdot (1 / l)$ , where $i < k$ . Similarly, for $J$ higher cost jobs, we have, $P r {A_{1 j} \cap A_{2 j} \cap \dots \cap A_{J j}} = (1 / l) \cdot (1 / l) \dots (1 / l) = (1 / l)^{J} = 1 / l^{J}$ .
Observation: When $| Γ |$ is large, we can say that the probability of allocating all higher cost jobs in a single schedule is much less. For example, consider 50 jobs out of 200 jobs are of higher cost, and there are six schedules. So, the probability of allocating higher cost jobs to any one schedule out of six schedules is $1 / 6^{50} = 1.2371931 \times 10^{- 39}$ , which is very less. It means that over a repeated number of random allocations of jobs, the chances of the accumulation of higher cost jobs into any one schedule are almost 0.

In PPSJBP, all the jobs are distributed into $| Δ |$ slots (schedules) by our randomized algorithm framework. In this process, a job allocated to a slot will not be allocated to any other slot (samples without replacement). Our randomized algorithm is repeated for $K$ number of times, and in each $k^{^{'}} \in K$ rounds, a job allocated to a slot will not be allocated to any other slot, is maintained. After $K$ repetitions, the allocation of jobs that produces minimum variance is given for execution. In Lemma 3, it is mentioned that allocation of all higher cost jobs (say $J$ ) into one of $l$ slots is $1 / l^{J}$ , that is, the probability of allocation of all higher cost jobs in a single slot is very less. Now, a higher cost job, which is also a job being allocated in PPSJBP, is under the randomized algorithm framework. As the higher cost job is allocated using the randomized algorithm, the independence of higher cost jobs is maintained. Lemma 4
The expected NOJ to be assigned in a given schedule is $| Γ | / | Δ |$ , considering an arbitrary iteration.
Proof.
We have here, $| Γ |$ number of trials of assigning jobs into the given schedule (as $| Γ |$ is the total NOJ available in our setting). Among those trials, there are successes (the sampled job is landing in the given schedule) such that each success occurs with probability of $P$ and some failure with probability of $Q = P - 1$ . Every trial is independent and has the probability $1 / | Δ |$ , as $| Δ |$ is the number of schedules available. Now, we take $R$ as a random variable to denote the successful assignment of jobs into the given schedule among $| Γ |$ trials, range within $[1, \dots, | Γ |]$ . So the value of $R$ can be represented as $R = i$ , where $i \in [0, \dots, | Γ |]$ . So, the probability of $R$ for $i$ number of successes can be written as, $P r {R = i} = (\begin{matrix} | Γ | \\ i \end{matrix}) P^{i} Q^{| Γ | - i}$ . This is true as there are $(\begin{matrix} | Γ | \\ i \end{matrix})$ ways to choose $i$ number of successes among $| Γ |$ trials and any one such successes occurs with the probability $P^{i} Q^{(| Γ | - i)}$ (as in that elementary event, $i$ successes will be there along with $(| Γ | - i)$ number of failures). Also, we can write:
$\begin{aligned} \sum_{i = 0}^{| Γ |} P r {R = i} & = \sum_{i = 0}^{| Γ |} (\begin{matrix} | Γ | \\ i \end{matrix}) {(\frac{1}{| Δ |})}^{i} {(1 - \frac{1}{| Δ |})}^{| Γ | - i} \\ = 1. \end{aligned}$
(20)
Now, the expected number of successes, that is, expected NOJ in every schedule can be calculated as below. From this proof, it is evident that our proposed PPSJBP distributes the jobs in each schedule in a balanced way.
$\begin{aligned} E [R] & = \sum_{i = 0}^{| Γ |} i \cdot P r {R = i} \\ = \sum_{i = 1}^{| Γ |} i (\begin{matrix} | Γ | \\ i \end{matrix}) {(\frac{1}{| Δ |})}^{i} {(1 - \frac{1}{| Δ |})}^{| Γ | - i} \\ = \sum_{i = 1}^{| Γ |} i (\frac{| Γ |!}{i! (| Γ | - i)!}) {(\frac{1}{| Δ |})}^{i} {(1 - \frac{1}{| Δ |})}^{| Γ | - i} \\ = \sum_{i = 1}^{| Γ |} i (\frac{| Γ | (| Γ | - 1)!}{i (i - 1)! (| Γ | - i)!}) {(\frac{1}{| Δ |})}^{i} {(1 - \frac{1}{| Δ |})}^{| Γ | - i} \\ = \sum_{i = 1}^{| Γ |} (\frac{| Γ | (| Γ | - 1)!}{(i - 1)! (| Γ | - i)!}) {(\frac{1}{| Δ |})}^{i} {(1 - \frac{1}{| Δ |})}^{| Γ | - i} \\ = \frac{| Γ |}{| Δ |} \sum_{i = 1}^{| Γ |} (\begin{matrix} | Γ | - 1 \\ i - 1 \end{matrix}) {(\frac{1}{| Δ |})}^{i - 1} {(1 - \frac{1}{| Δ |})}^{| Γ | - i} \\ [as (| Γ | - 1 - i + 1)! = (| Γ | - i)!] \\ = \frac{| Γ |}{| Δ |} \sum_{i = 0}^{| Γ | - 1} (\begin{matrix} | Γ | - 1 \\ i \end{matrix}) {(\frac{1}{| Δ |})}^{i} {(1 - \frac{1}{| Δ |})}^{(| Γ | - 1) - i} \\ = \frac{| Γ |}{| Δ |} [by\ equation (20)] . \end{aligned}$
(21)
Observation. Consider the synthetic dataset where $| Γ | = 200$ , we have $| Γ | / | Δ | = 200 / 4 = 50$ and this value is the NOJ allocated in each schedule. In Section 7.3, the comparison between OFFPSP and PPSJBP with the parameter NOJ (Figure 3(a)) shows that in PPSJBP, NOJ in each schedule is more balanced and in comparison with UCSMPP, the balancing of NOJ in each schedule is almost similar. We have similar observations for Bus Driver Scheduling and KDD Cup 2015 datasets (Figures 3(b) and 3(c)). Lemma 5
The probability $P r {R \geq 1.5 E [R]} \leq e^{- | Γ | / 12 | Δ |}$ , for any schedule $δ_{i}$ , where $i \in [1, | Δ |]$ .
Figure 3.
Comparison among UCSMPP, PPSJBP, and OFFPSP over the number of jobs in each schedule. (a) Synthetic, (b) Bus Driver Scheduling, and (c) KDD Cup 2015 datasets.
Proof.
We can find the probability $P r {R \geq 1.5 E [R]}$ using Chernoff Bound as: $P r (R \geq (1.5) E [R]) = P r (R \geq (1 + (1 / 2)) E [R]) \leq e^{(- E [R] {(1 / 2)}^{2}) / 3}$ .

We know that $E [R] = | Γ | / | Δ |$ . So, plugging this into the above equation, we get:
$\begin{aligned} P r (R \geq (1.5) E [R]) & \leq e^{- \frac{E [R] {\frac{1}{2}}^{2}}{3}} \\ \leq e^{- \frac{| Γ |}{3 | Δ |} \cdot (\frac{1}{2})^{2}} \\ = e^{- \frac{1}{4} \cdot \frac{| Γ |}{3 | Δ |}} \\ = e^{- \frac{| Γ |}{12 | Δ |}} . \end{aligned}$

From the above discussion, we can see that a little deviation of any schedule from balanced job assignment has the probability upper bounded by $e^{- | Γ | / 12 | Δ |}$ . Now, as $| Γ |$ grows larger, $P r (R \geq (1.5) E [R])$ will be decreasing exponentially.
Observation: With $| Γ | = 200$ and $Δ = 4$ , the above said probability can be calculated as $e^{- 200 / 12 \times 4} = e^{- 4.17} = 0.0154$ , which is less. In terms of our dataset for simulation, namely, the Bus Driver Scheduling (BDD) dataset and the KDD Cup 2015 dataset, $| Γ | = 359$ and $| Γ | = 2999$ , respectively. So the said probability will be less than the case where $| Γ | = 200$ .

Now a connection will be established between finding our minimum variance with repetition and the online hiring assistant problem for stating our next analytical result. In the online hiring assistant problem, there are $m$ number of candidates who appear for the interview process in an online fashion, that is, we don’t know the list of the candidates a priori. In this problem, we don’t want to interview all the $m$ number of candidates yet, we want to find the best candidate or a candidate close to the best candidate (that is the target). The natural question that arises is how many samples we need to explore before we are sure that our target is achieved with a good probability. In the literature,^49–55 it is shown that we need to sample $m / e$ number of candidates to make sure that our target is achieved with a probabilistic lower bound of $1 / e$ . In our problem, for each iteration, we calculate a variance. So, as a thought experiment, we can think that the variances are appearing in an online fashion, just like the candidates in the online hiring assistant problem. So the variances here resemble the candidates, and we need to find out the best (minimum) variance. So, the problem boils down to the fact that of how many such variances need to be sampled (to be calculated) before we achieve our target of finding the minimum variance.
Corollary 1.
$K / e$ number of variances to be calculated (per iteration, we calculate one variance) to make sure that the minimum variance will be achieved with a probabilistic lower bound $1 / e$ .
Proof.
The proof follows from the connection we have established above, that is, we need $m / e$ number of samples for the probability to be at least $1 / e$ . Following this connection, we can say that $K / e$ number of variances to be calculated for making sure that we get a probabilistic lower bound of $1 / e$ (i.e., with probability at least $1 / e$ ).

Observation: Consider the value of $K = 4000$ , number of repeated random allocation of jobs. According to Corollary 1, we have to iterate the random allocation of jobs to schedules $K / e$ times, that is, $4000 / e \approx 1472$ times to get success with the probability of $1 / e \approx 0.37$ , that is, if we repeat the random allocation process for 1472 times, the chance to get best minimum variance is at least 37%. Now, if we iterate our random allocation process for $K$ times, the lower bound of the probability will also increase. So, we can say that with a larger value of $K$ , the lower bound of the probability of getting the best minimum variance is greater than $1 / e$ .
6. Simulation and results

6.1. Setup

Number of schedules: We have considered $| Δ | = 4$ , $ζ = 4$ weeks, and $τ_{i} = 1$ week, $\forall_{i \in (1, | Δ |)}$ for simulation.

Dataset: We have used one synthetic dataset and two real datasets: (i) Bus Driver Scheduling dataset⁵⁶ and (ii) KDD Cup 2015 dataset.⁵⁷

Synthetic dataset: It is generated randomly using a normal distribution with 200 jobs. Five samples of this dataset are shown in Table 2.

Bus Driver Scheduling dataset: From BDD dataset, we have extracted the values from “Bus_Line_Id (job)” and “Duration” columns. There are a total of 359 buses running per day, according to BDD. The total running cost of every bus for a day is obtained by adding all the run time durations of that day, for example, $Bus\_Line\_Id : 1$ has a set of costs as = ${20, 70, 70, 70, 85, 55, 70, 85, 55, 70, 85, 55, 70, 70, 70, 140}$ in minutes, and the total is 1145 minutes for a day. Five random samples are shown in Table 3.

KDD Cup 2015 dataset: KDD Cup 2015 dataset contains online course enrolment and course log information of a large number of students. A student can enrol in multiple courses, and every course has at most seven events which are – Access, Video, Discussion, Navigate, Problem, Wikipedia, and Page Close. Each event under every course (enrolled by a student) is considered a job in this paper. In each enrolled course, the total time spent on an event is calculated and considered as the cost of the event (job). In total, 2999 such jobs are derived from the KDD Cup 2015 dataset, and a sample is displayed in Table 4 (10 samples of such jobs).

The values extracted from the KDD Cup 2015 and BDD datasets are considered as the cost of jobs for the simulation of PPSJBP (mentioned above). The unit of job cost ( $χ$ ) in Table 2, Tot_Dur ( $χ$ ) in Table 3 and Cost ( $χ$ ) in Table 4 is in minutes.

Table 2.
Synthetic dataset.

Sl # Job ( $Γ$ ) Job cost ( $χ$ )

1 $γ_{1}$ 10

2 $γ_{2}$ 40

3 $γ_{3}$ 25

4 $γ_{4}$ 100

5 $γ_{5}$ 89

Sl #	Job ( $Γ$ )	Job cost ( $χ$ )
1	$γ_{1}$	10
2	$γ_{2}$	40
3	$γ_{3}$	25
4	$γ_{4}$	100
5	$γ_{5}$	89

Table 3.

BDD dataset.

Sl#	Job ( $Γ$ )	Tot_Dur ( $χ$ )
1	1	1145
2	2	1110
3	3	850
4	4	1090
5	5	840

Table 4.

KDD Cup 2015 dataset.

course_id	Job ( $Γ$ )	Cost ( $χ$ )
81UZ	navigate	10
	access	15
	video	4
G8EP	video	1
	page_close	1
	discussion	4
3cnZ	access	2
	video	1
	page_close	1
	discussion	5

If a TE or an agent in SC is assigned a set of jobs (with different costs) with a single and large enough time frame so that all the assigned tasks can be completed within the time frame, the TE might procrastinate. For example, a TE is assigned six jobs with costs 11, 11, 8, 7, 9, and 12 (in hours), with a 12-day time frame (considering 2 days to complete each job). As there is a single time frame, the TE procrastinates for, say, four tasks. So she has to execute four tasks in a single day instead of eight days. On the other hand, consider that a time frame of 4 days (a slot) is given for each pair of tasks (where the TC of all such pairs is balanced). In this case, the possible procrastination could be prevented because the TE has to submit each pair of tasks within 4 days. If the TC of each slot is not balanced, there is again a chance of procrastination (see Section 1 for more details).

There is no direct mapping or relationship of cost to procrastination behaviour for KDD Cup 2015 and BDD datasets. But, from the above discussion, we can infer that the cost can be mapped with procrastination on the basis of the data derived from KDD Cup 2015 and BDD datasets for simulation of our proposed method, PPSJBP. This mapping could be done for the TC of assigned jobs to any TE. This is because a TE might procrastinate when she is assigned jobs and deadlines to execute those jobs.

It is also to be mentioned that there is no bus (in BDD) or no student (in KDD Cup 2015) labelled with procrastination. That means these real datasets do not specify anything about procrastination. However, for our simulation regarding procrastination, getting the jobs and their costs (time) were the important ingredients. The KDD Cup 2015 and BDD datasets are providing the jobs and their corresponding costs. The ground truth labelling of which jobs procrastinated for how much time was absent in the KDD Cup 2015 and BDD datasets. If ground truth data were available, one further simulation in that direction could be done, along with our extensive simulation study with these real-world datasets. Depending on the availability of that ground truth dataset, that particular simulation is kept for our future work.

6.2. Results of simulation

We have presented the results of simulation of the proposed algorithm in different directions, which are (i) comparison between a set of schedules with minimum variance and other randomly chosen sets of schedules, (ii) by varying $K$ , (iii) comparison between with and without ordering of dispensing schedules.

6.2.1. Comparison between set of schedules with minimum variance and other randomly chosen sets of schedules

This simulation shows the comparison between a set of schedules with minimum variance and other randomly chosen sets of schedules. For this simulation, we have chosen four different sets of schedules at random, which have high variance and compared with minimum variance set of schedules where $K = 25, 000$ for both BDD dataset (Figure 4(a)) and KDD Cup 2015 dataset (Figure 4(b)). In both of these figures, we can see that the variances of randomly chosen sets of schedules and a set of schedules with minimum variance have a significant difference.

Figure 4.

Comparison between a randomly chosen set of schedules with the minimum variance set. (a) Comparison using Bus Driver dataset and (b) Comparison using KDD Cup 2015 dataset.

This simulation establishes the fact that the proposed algorithm is able to allocate all jobs into the schedules in the most balanced manner according to their costs. It follows Lemma 3, which states that the probability of accumulation of all higher cost jobs into a single schedule is very less. We claim this because when the set of schedules with minimum variance is achieved after $K$ iterations, we have seen that the schedules are almost balanced in terms of TC, that is, all higher cost jobs along with other jobs are uniformly distributed among all schedules. The connection we have established in Section 5 reveals that the number of variances to be calculated to achieve the best minimum variance with a lower bound probability of 0.37 is approximately 1472 (when $K = 4000$ ). That means if we calculate 1472 variances (i.e., the number of iterations), there is at least 37% chance to obtain the best minimum variance. When we take $K = 8000$ , to achieve the lower bound of 0.37, we need to find 2943 variances. To increase this lower bound, the value of $K$ is to be increased because this lower bound of 37% is giving a benchmark. If we compute less number of variances, the scenario would not be realistic. So, increasing the value of $K$ will give higher accuracy. Accordingly, in our simulation, we have considered $K = 8000$ and higher, which is sufficiently larger than the value given in the benchmark.

6.2.2. By varying K

The purpose of this simulation is to show that if we vary $K$ from $8000$ to $12, 000$ (varied by 1000), our proposed algorithm achieves the most balanced set of schedules for each variation (Figure 5). That means our proposed algorithm produces a balanced set of schedules not only once (say, for $K = 8000$ ) but for all variations of $K > 8000$ . This simulation follows Lemma 5 in the sense that in each variation of $K$ , a minimum variance set of schedules is achieved where each schedule is balanced, that means, no schedule has deviated from getting the balanced job distribution.

Figure 5.

Balanced sets of schedules by varying $K$ with synthetic dataset.

6.2.3. Comparison between with and without ordering of dispensing schedules

This simulation shows the comparison when the schedules are dispensed with and without ordering of TC (from Figures 6(a) to 6(c)). In each figure, the plots on the left-hand side and right-hand side show with and without ordering, respectively. In the right-hand side of Figure 6(a), we can see that if schedule 3 is dispensed before schedule 4, the verification time for schedule 4 would comparatively be less than schedule 3 because schedule 4 is heavier than schedule 3. The left-hand side of the same figure shows that the schedule with the largest cost, that is, schedule 4, is dispensed first, then schedule 1, and so on, which provides more time for verification of comparatively heavier schedules after submission of tasks. In this simulation, the minor difference among the costs of each schedule is scaled so that the dispensing of schedules with and without ordering could be clearly understood.

Figure 6.

Comparison between with and without ordering of dispensing schedules. (a) Synthetic dataset, (b) Bus Driver dataset and (c) KDD Cup 2015 dataset.

6.2.4. Brief empirical study of

α

and

ϵ

A brief study is given for hyperparameter $α$ (task allocation ratio to top- $k$ TEs) and $ϵ$ (exploration rate for $ϵ$ -greedy), with $α = {0.5, 0.65, 0.8}$ and $ϵ = 0.45$ .

The Bus Driver Scheduling dataset with 359 data is considered for this study. We have randomly selected 100 tasks and considered $α = {0.5, 0.65, 0.8}$ (see Section 4.1 for the application of $α$ ) for studying the total number of assigned tasks to the selected TEs against the total quality score of those TEs. Let us consider a total of six TEs, that is, $T E = {t e_{1}, t e_{2}, t e_{3}, t e_{4}, t e_{5}, t e_{6}}$ . Out of these TEs, $t e_{1}, t e_{2}, t e_{3}$ are the top $k$ heavy hitters (obtained using CMS) with total quality scores 5, 6, and 5, respectively. Then, for the rest of the TEs, the $ϵ$ -greedy based approach is applied with $ϵ = 0.45$ . With $(1 - ϵ) = 0.55$ , we have obtained $t e_{4}$ and $t e_{5}$ with total quality scores 3 and 1, respectively, from the exploitation phase. And the TE $t e_{6}$ with total quality score 2 is obtained from the exploration phase. Figure 7(a) shows the study where 100 random samples from the BDD dataset were taken. The plot/graph generated in Figure 7(a) is interpreted below.

Figure 7.

Number of tasks assigned with parameter $α$ versus total quality with different numbers of random samples collected from Bus Driver Scheduling dataset: (a) 100 random samples, (b) 200 random samples and (c) 300 random samples.

The $X$ -axis denotes the three different percentages ( $α$ ) of 100 sampled tasks to be assigned to the TEs selected from CMS, and the exploitation and exploration phase of $ϵ$ -greedy. The $Y$ -axis denotes the TEs (along with their total quality scores) selected from CMS, and exploitation and exploration phases of $ϵ$ -greedy as TOP_TE (16), X_TE(4), and P_TE(2), respectively. The $Z$ -axis denotes the total number of tasks assigned to each type of TEs. In Figure 7(a), the red bars represent the total tasks assigned to the top TEs selected from CMS with $α = {0.5, 0.65, 0.8}$ . Similarly, in Figure 7(a), the green bars and blue bars represent the total tasks assigned to the TEs obtained from the exploitation and exploration phase of the $ϵ$ -greedy based approach, respectively, with $α = {0.5, 0.65, 0.8}$ .

A similar study is carried out for randomly selected 200 tasks and 300 tasks from the same dataset, and the same set of $α$ (shown in Figures 7(b) and 7(c), respectively).

7. Comparison with existing research

Our proposed algorithm (PPSJBP) is compared with OFFPSP,²² which used a threshold-based algorithm to allocate jobs to every schedule (without balancing), but our proposed algorithm has generated balanced (in terms of TC and NOJ) schedules without any threshold (this gives a general flavour to our proposed algorithm as threshold-based allocation is somewhat imposing extra restriction on the allocation of jobs to the schedules). In OFFPSP, a job is allocated to a schedule if the ratio of marginal utility to the cost (utility/cost) of that job is maximum compared to all other jobs. If the utility of the last allocated job is higher than that of the other jobs, the last job is kept, and the other jobs are discarded. These discarded jobs have not been processed further (as per the algorithm presented in Wang et al.²²). This creates a disparity in the job allocation process, and it is also observed that OFFPSP may not perform efficiently in terms of balancing the scheduled jobs. We have considered the uniform utility for all jobs for the simulation. We have also compared PPSJBP with UCSMPP proposed in Debnath et al.²⁴ Even though UCSMPP has shown a better balancing effect than OFFPSP, PPSJBP has achieved a better balancing effect than UCSMPP.

7.1. Setup for comparison

We have (1) threshold for $δ_{i}$ : $δ_{i}^{T h} = \sum_{i = 1}^{| Δ |} \sum_{j = 1}^{| δ_{i} |} χ_{i j} / | Δ |$ , and (2) considered the utility of $γ_{i} \in Γ$ is $1$ as setup (for OFFPSP) for comparison. This comparison is presented based on (i) TC, (ii) AC, (iii) NOJ in each schedule and (iv) combined total effect (CTE) (Section 7.4).

7.2. Based on TC per schedule

In this simulation, shown in Figures 8(a) to 8(c), we have compared PPSJBP, UCSMPP, and OFFPSP in terms of TC of each schedule. We see that PPSJBP has produced a better-balanced effect in distributing jobs into schedules compared to both UCSMPP and PPSJBP.

Figure 8.

Comparison among UCSMPP, PPSJBP, and OFFPSP over total cost of each schedule: (a) Synthetic, (b) Bus Driver Scheduling and (c) KDD Cup 2015 datasets.

7.3. Based on NOJ and AC per schedule

We have also compared PPSJBP with OFFPSP and UCSMPP in terms of AC (from Figures 9(a) to 9(c)) and NOJ (from Figures 3(a) to 3(c)). In both cases, PPSJBP outperforms OFFPSP while it behaves almost similarly to UCSMPP. This is because UCSMPP has distributed the jobs into each schedule deterministically, whereas in PPSJBP, the jobs are assigned randomly. Another reason is that we have adopted a similar method of dividing the overall deadline ( $ζ$ ) used in UCSMPP. But as we are achieving a more balanced distribution of jobs in terms of TC, it will provide smoother execution of tasks in each schedule. We have found that NOJ of all schedules are almost balanced in our proposed method, which properly justifies Lemma 4.

Figure 9.

Comparison among UCSMPP, PPSJBP, and OFFPSP over AC in each schedule: (a) Synthetic, (b) Bus Driver Scheduling and (c) KDD Cup 2015 datasets.

7.4. Based on CTE

This section shows the CTE of TC, AC, and NOJ on OFFPSP, UCSMPP and PPSJBP by comparing their behaviour over CTE. We have shown the comparison of CTE in two segments. First segment uses the sum of TC, AC and NOJ of each schedule and shows that PPSJBP has better balancing effect than the other two (Figures 10(a) to 10(c)). In the second segment, we have calculated the variance of the summation of TC, AC and NOJ of all the schedules for each dataset and drawn the comparison by taking 100% of values of TC, AC and NOJ (Figure 11(a)) and then by taking 75% and 50% of values of TC, AC and NOJ (Figures 11(b) and 11(c)). The purpose of such partial consideration of values of TC, AC and NOJ is to show that the variance over a summation of partial values of TC, AC and NOJ for each schedule also produces a better balancing effect for PPSJBP than OFFPSP and UCSMPP (Figures 11(b) and 11(c)).

Figure 10.

Comparison among UCSMPP, PPSJBP, and OFFPSP over combined total value: (a) Synthetic, (b) Bus Driver Scheduling and (c) KDD Cup 2015 datasets.

Figure 11.

Comparison over variances of combined values with varying proportion: (a) 100% proportion, (b) 75% proportion and (c) 50% proportion.

7.5. Statistical validation

For statistical validation, we consider the proposed method PPSJBP, which gives a balanced distribution of tasks (in terms of cost) into slots with low variance, as the null hypothesis $H_{0}$ . And we consider that the PPSJBP will produce an unbalanced distribution with high variance compared to a baseline method, OFFPSP, as an alternative hypothesis $H_{1}$ . Using the Mann–Whitney U-test,⁵⁸ we have shown that the probability of the unbalanced allocation by PPSJBP or the probability of producing high variance by PPSJBP, that is, $H_{1}$ , is significantly low. Or, in the other way, we can say that the null hypothesis has a very high probability of occurring. The statistical validation test is conducted with different numbers of sample variances for PPSJBP and the same variance for OFFPSP (as it always produces the same distribution of tasks into slots). The test outcome and remarks are given in Table 5 (the $p$ -values for all samples are corrected up to 10 decimal places to keep the table short).

Table 5.
Mann–Whitney $U$ -test using four sets of samples.

#Samples $P$ -values U score Remarks

5 0.0037474788 0.0 Reject $H_{1}$

10 0.0000243773 0.0 Reject $H_{1}$

15 0.0000003433 0.0 Reject $H_{1}$

20 0.0000000040 0.0 Reject $H_{1}$

#Samples	$P$ -values	Remarks
5	0.0037474788	Reject $H_{1}$
10	0.0000243773	Reject $H_{1}$
15	0.0000003433	Reject $H_{1}$
20	0.0000000040	Reject $H_{1}$

7.6. User study on procrastination

Earlier, we constructed a real-world dataset by distributing some assignment questions to a group of high school students (or crowdworkers) of standard VII to standard IX. It is distributed to observe if students procrastinate or not. Five students of standard IX were given assignments on English and Mathematics. Four students of standard VII were given assignments on English, Mathematics (Maths), Bengali, and Science. Seven students of standard VIII were given assignments on Mathematics, English, Physical Science (PHY SC.), and Life Science (L SC.). So, 16 students in total were given the assignments according to their standards on 22 September 2024 (i.e., date of giving the assignments (DoA) was 22 September 2024). The date of submission (DoS) of the assignments was on 23 October 2024. Based on the student’s submission, we have prepared a dataset regarding the procrastination behaviour of the students. The students who have submitted the assignments on the penultimate day or on DoS are considered or identified as procrastinating students. The dataset contains the student identity (Std Id), Standard (in which class they study), Subject on which the assignments were given, DoA, DoS, and Label. The Label column contains one of three values: (i) if a student has not submitted the assignment, that is, not submitted, (ii) if submitted, whether she has procrastinated, and (iii) not procrastinated. We have randomly picked the samples of the students against a subject from the dataset to check if they have procrastinated or not.

These samples are given in Tables 6 and 7, which show the procrastination behavior of students (crowdworkers). The pattern in the dataset shows realistically that crowdworkers procrastinate during the execution of their jobs.

Table 6.
School assignment: Procrastination 1.

Std Id Standard Subject DoA DoS Label

Std 1 VII ENGLISH 22 Sep 2024 23 Sep 2024 Not procrastinated

Std 4 VII SCIENCE 22 Sep 2024 22 Oct 2024 Procrastinated

Std 8 VIII PHY SC. 22 Sep 2024 28 Sep 2024 Not procrastinated

Std 11 VIII PHY SC. 22 Sep 2024 26 Sep 2024 Not procrastinated

Std 14 IX ENGLISH 22 Sep 2024 24 Sep 2024 Not procrastinated

Std Id	Standard	Subject	DoA	DoS	Label
Std 1	VII	ENGLISH	22 Sep 2024	23 Sep 2024	Not procrastinated
Std 4	VII	SCIENCE	22 Sep 2024	22 Oct 2024	Procrastinated
Std 8	VIII	PHY SC.	22 Sep 2024	28 Sep 2024	Not procrastinated
Std 11	VIII	PHY SC.	22 Sep 2024	26 Sep 2024	Not procrastinated
Std 14	IX	ENGLISH	22 Sep 2024	24 Sep 2024	Not procrastinated

DoA: date of giving the assignments; DoS: date of submission; PHYS SC.: Physical Science.

Table 7.

School assignment: Procrastination 2.

Std Id	Standard	Subject	DoA	DoS	Label
Std 3	VII	MATHS	22 Sep 2024	10 Oct 2024	Not procrastinated
Std 5	VIII	PHY SC.	22 Sep 2024	22 Oct 2024	Procrastinated
Std 10	VIII	L SC.	22 Sep 2024	NA	No Submission
Std 13	IX	MATHS	22 Sep 2024	23 Oct 2024	Procrastinated
Std $16$	IX	ENGLISH	22 Sep 2024	23 Oct 2024	Procrastinated

DoA: date of giving the assignments; DoS: date of submission; PHYS SC.: Physical Science; L SC.: Life Science.

8. Conclusion

In this paper, we have addressed the problem of task allocation and the prevention of procrastination of allocated tasks in SC. We have also shown that an SC environment can be mapped to a distributed network. To address the issue of task allocation, we have proposed a method to find top-performing TEs using a data science approach (CMS) and allocated a subset ( $α \times Γ$ ) of tasks to them. To select other TEs and assign tasks, we have proposed an $ϵ$ -greedy, an MAB-based approach. We have assigned the tasks (as per their order in the task list) to the top-performing TEs first and then to the other TEs to maximize task allocation to the top-performing TEs.

To address the second problem,, that is, to prevent procrastination, we have proposed a novel method named PPSJBP, which distributes jobs into different schedules (in the most balanced manner) as per their TC to avoid procrastination in SC applications. Every schedule is given an equal time frame by subdividing the total time frame so that the on-time and efficient completion of jobs is guaranteed. Another aspect of PPSJBP is that the schedules that are finally given to the agents are presented in non-increasing order of their TC. The benefit of this is twofold: (1) the agents will have less burden as they will be going down the line to execute jobs in several schedules and (2) the TP will have ample time to work on the little bit heavy schedule as it is submitted earlier. So PPSJBP is relying on two facts: aligning the jobs into the schedules by a randomized repetitive procedure (balancing), and rearranging the set of schedules with minimum variance in non-increasing order of the cost of each schedule (benefiting TP). We have compared our scheme with the existing algorithms with synthetic as well as real datasets through extensive simulation, and it is observed that our proposed method outperforms the existing one in terms of balancing effect. Also, we have shown analytically that our proposed algorithm maintains the balanced distribution. There could be many other directions to the prevention of procrastination. One direction could be to use Platform-centric data about agents to avoid procrastination in a better way. Another direction could be to give incentives to the agents on the way of performing the task to avoid procrastination. Such an incentive-based system integrated with a game-theoretic setting could be another viable option to motivate TEs to avoid procrastination in an SC environment. In a dynamic or real-time scenario, tasks and TEs appear/arrive dynamically or in an online fashion to the platform. Similarly, when a TE completes task execution, she can leave the platform immediately, or she can also leave if she is unassigned to a task, after a certain amount of time (wait time). This is also applicable to a task. In case of dynamic arrival, there is no prior information to the platform about TEs or tasks before their arrival to the platform. Our future work, as a third future direction, will be extended to address such a dynamic nature of both TE and tasks.

Footnotes

ORCID iDs

Naren Debnath

Sajal Mukhopadhyay

Fatos Xhafa

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

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.

Code/data availability

The code for the implementation of the proposed method, PPSJBP, will be available upon request.

Studies not involving humans or animals

This article does not contain any studies with human or animal participants.

There are no human participants in this article, and informed consent is not required.

References

Qing-liang

Xin-hui

. A dynamic decision model of users’ sustained participation in crowdsourcing innovation. Int J Serv Oper Inform 2018; 9: 223–241.

Gummidi

SRB

Xie

Pedersen

. A survey of spatial crowdsourcing. ACM Trans Data Syst 2019; 44: 1–46.

Zhao

Han

. Spatial crowdsourcing: current state and future directions. IEEE Commun Magaz 2016; 54: 102–107.

Wang

, et al. Recommending-and-grabbing: a crowdsourcing-based order allocation pattern for on-demand food delivery. IEEE Trans Intell Transp Syst 2022; 24: 838–853.

Lucic

Wan

Ghazzai

, et al. Leveraging intelligent transportation systems and smart vehicles using crowdsourcing: an overview. Smart Cities 2020; 3: 341–361.

Wang

Liu

Sun

. A secure and privacy-preserving navigation scheme using spatial crowdsourcing in fog-based vanets. Sensors 2017; 17: 668.

Djigal

Liu

Luo

, et al. Buda: budget and deadline aware scheduling algorithm for task graphs in heterogeneous systems. In: 2022 IEEE/ACM 30th international symposium on quality of service (IWQoS), online, 10–12 June 2022, pp.1–10. IEEE Xplore Digital Library.

Mukhopadhyay

Singh

Mukhopadhyay

, et al. An egalitarian approach of scheduling time restricted tasks in mobile crowdsourcing for double auction environment. Int J Web Grid Serv 2021; 17: 221–245.

Cheng

Chen

, et al. Task allocation in dependency-aware spatial crowdsourcing. In: 2020 IEEE 36th international conference on data engineering (ICDE), Dallas, Texas, 20–24 April 2020, pp.985–996. New York, USA: IEEE.

10.

Tong

Zhou

Zeng

, et al. Spatial crowdsourcing: a survey. VLDB J 2020; 29: 217–250.

11.

Yadav

Chandra

Sairam

. A budget and deadline aware task assignment scheme for crowdsourcing environment. IEEE Trans Emerg Top Comput, 2021; 10: 1020–1034.

12.

Wang

, et al. Toward privacy-preserving task assignment for fully distributed spatial crowdsourcing. IEEE Internet Things J 2021; 8: 13991–14002.

13.

Liu

Dai

, et al. Exploring both individuality and cooperation for air-ground spatial crowdsourcing by multi-agent deep reinforcement learning. In: 2023 IEEE 39th international conference on data engineering (ICDE), Anaheim, United States, 3–7 April 2023, pp.205–217. New York, USA: IEEE.

14.

Liu

Zhang

, et al. Blocksc: a blockchain empowered spatial crowdsourcing service in metaverse while preserving user location privacy. IEEE J Select Areas Commun 2023; 42: 880–892.

15.

Phuttharak

Loke

. Iterative spatial crowdsourcing in peer-to-peer opportunistic networks. Electronics 2020; 9: 1085.

16.

Kleinberg

Oren

. Time-inconsistent planning: a computational problem in behavioral economics. In: Proceedings of the fifteenth ACM conference on economics and computation, Palo Alto, California, 8–12 June 2014, pp.547–564. New York, USA: ACM .

17.

Kleinberg

Oren

Raghavan

. Planning with multiple biases. In: Proceedings of the 2017 ACM conference on economics and computation, Massachusetts, USA, 26–30 June 2017, pp.567–584. New York, USA: ACM.

18.

Tang

Teng

Wang

, et al. Computational issues in time-inconsistent planning. In: Thirty-first AAAI conference on artificial intelligence, San Francisco, California, 4–9 February 2017, pp.3665–3671. Palo Alto, California: The Association for the Advancement of Artificial Intelligence (AAAI).

19.

Tim

. CS269I: Incentives in Computer Science. Lecture #19: Time-Inconsistent Planning. Stanford University, https://timroughgarden.org/f16/l/l19.pdf, last accessed on December 5, 2016.

20.

Akerlof

. Procrastination and obedience. Am Econ Rev 1991; 81: 1–19.

21.

Kahneman

Tversky

. Prospect theory: an analysis of decision under risk. Singapore: World Scientific, 2013. chapter 6, pp.99–127.

22.

Wang

Tong

, et al. Procrastination-aware scheduling: a bipartite graph perspective. In: 2019 IEEE 35th international conference on data engineering (ICDE), Macao, China, 8–11 April 2019, pp.1650–1653. New York, USA: IEEE.

23.

Arakawa

Yakura

Goto

. Catalyst: domain-extensible intervention for preventing task procrastination using large generative models. In: Proceedings of the 2023 CHI conference on human factors in computing systems, Hamburg, Germany, 23–28 April 2023, pp.1–19. ACM, New York, USA.

24.

Debnath

Mukhopadhyay

Xhafa

. An efficient algorithm to prevent procrastination in spatial crowdsourcing. In: Proceedings of conference on P2P, parallel, grid, cloud and internet computing, San Benedetto del Tronto, Italy, 13–15 November 2024, pp.142–153. Switzerland: Springer Nature.

25.

Cormode

Muthukrishnan

. An improved data stream summary: the count-min sketch and its applications. J Algorithms 2005; 55: 58–75.

26.

Slivkins

, et al. Introduction to multi-armed bandits. Found Trends® in Mach Learn 2019; 12: 1–286.

27.

Sutton

Barto

, et al. Reinforcement learning: an introduction. vol. 1. Cambridge, Massachusetts: MIT Press, 1998.

28.

Sun

Guo

, et al. Deep reinforcement learning for task assignment in spatial crowdsourcing and sensing. IEEE Sens J 2021; 21: 25323–25330.

29.

Zhu

, et al. Prediction-aware adaptive task assignment for spatial crowdsourcing. IEEE Trans Mobile Comput 2024; 23: 13048–13061.

30.

Zhao

Chen

, et al. Task allocation in spatial crowdsourcing: an efficient geographic partition framework. IEEE Trans Knowl Data Eng 2024; 36: 4943–4955.

31.

Alabbadi

Abulkhair

. Multi-objective task scheduling optimization in spatial crowdsourcing. Algorithms 2021; 14: 77.

32.

Liang

Tan

Liu

, et al. Multi-skill collaboration-based task assignment in spatial crowdsourcing. In: International conference on computer application and information security (ICCAIS 2021), Biarritz, France, vol. 12260, 1–3 November 2022, pp.42–48. Bellingham, Washington, USA: SPIE.

33.

Debnath

Mukhopadhyay

Xhafa

. Mitigating procrastination in crowdsourcing via efficient scheduling algorithm. arXiv preprint arXiv:2401.00681 2024.

34.

Mukhopadhyay

Vikash

Mukhopadhyay

, et al. A balanced dissemination of time constraint tasks in mobile crowdsourcing: A double auction perspective. In: Advances on P2P, parallel, grid, cloud and internet computing: Proceedings of the 15th international conference on P2P, parallel, grid, cloud and internet computing (3PGCIC-2020) 15, Yonago, Tottori, Japan, 28–30 October 2021, pp.74–85. Berlin, Germany: Springer.

35.

Meitei

Marchang

. Provisioning load balancing in time-sensitive task allocation for mobile crowdsensing. J Netw Syst Manag 2024; 32: 13.

36.

Al-muqarm

AMA

Hussien

. Dynamic cost-optimized resources management and task scheduling with deadline constraint for mobile crowd sensing environment. Int J Intell Eng Syst 2023; 16: 201–219.

37.

Feng

Xiao

. Three-dimensional task allocation for smart transportation in spatial crowdsourcing: an intelligent role division approach. Adv Eng Inform 2024; 62: 102736.

38.

Zhao

Zheng

, et al. Destination-aware task assignment in spatial crowdsourcing: a worker decomposition approach. IEEE Trans Knowl Data Eng 2019; 32: 2336–2350.

39.

Zhou

Fan

Wang

. Task scheduling for mobile edge computing enabled crowd sensing applications. Int J Sens Netw 2021; 35: 88–98.

40.

Jiang

. A novel ground truth inference algorithm based on instance similarity for crowdsourcing learning. Appl Intell 2022; 52: 17784–17796.

41.

Zhao

Dong

Wang

, et al. A task allocation algorithm based on reinforcement learning in spatio-temporal crowdsourcing. Appl Intell 2023; 53: 13452–13469.

42.

Qiu

Liu

, et al. Analysis of behavioral economics in crowdsensing: a loss aversion cooperation model. Sci Program 2018; 2018: 4350183.

43.

Wang

Liu

, et al. Crowdsensing from the perspective of behavioral economics: an incentive mechanism based on mental accounting. IEEE Int Things J 2019; 6: 9123–9139.

44.

Liu

Yang

et al. An incentive mechanism based on behavioural economics in location-based crowdsensing considering an uneven distribution of participants. IEEE Trans Mobile Comput 2020; 21: 44–62.

45.

Liu

Huang

, et al. Cooperation promotion from the perspective of behavioral economics: an incentive mechanism based on loss aversion in vehicular ad-hoc networks. Electronics 2021; 10: 225.

46.

Sutton

Barto

. Reinforcement learning: an introduction. Cambridge, MA: A Bradford Book, 2018.

47.

Roughgarden

. Cs261: a second course in algorithms lecture# 18: Five essential tools for the analysis of randomized algorithms, 2016.

48.

Upfal Eli

. Probability and computing: randomized algorithms and probabilistic analysis. Cambridge: Cambridge University Press, 2005.

49.

Cormen

Leiserson

Rivest

, et al. Introduction to algorithms. Cambridge, Massachusetts: PHI Learning (Originally MIT Press), 2010.

50.

Ajtai

Megiddo

Waarts

. Improved algorithms and analysis for secretary problems and generalizations. SIAM J Disc Mathem 2001; 14: 1–27.

51.

Bateni

Hajiaghayi

Zadimoghaddam

. Submodular secretary problem and extensions. ACM Trans Algorithms 2013; 9: 1–23.

52.

Correa

Cristi

Epstein

, et al. Sample-driven optimal stopping: from the secretary problem to the iid prophet inequality. arXiv preprint arXiv:2011.06516 2020.

53.

Hajiaghayi

Kleinberg

Parkes

. Adaptive limited-supply online auctions. In: Proceedings of the 5th ACM conference on electronic commerce, New York, USA, 17–20 May 2004, pp.71–80. New York, USA: ACM.

54.

Kleinberg

. A multiple-choice secretary algorithm with applications to online auctions. In: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Vancouver, British Columbia, Canada, 23–25 January 2005, pp.630–631. Philadelphia, PA, United States: SIAM.

55.

Nuti

. The secretary problem with distributions. In: International conference on integer programming and combinatorial optimization, Eindhoven, The Netherlands, 27–29 June 2022, pp.429–439. Berlin, Germany: Springer.

56.

Constantino

de Mendonca

de Araujo

, et al. Solving a large real-world bus driver scheduling problem with a multi-assignment based heuristic algorithm. J Univers Comput Sci 2017; 23: 479–504.

57.

Feng

Tang

Liu

. Understanding dropouts in MOOCs. In: Proceedings of the AAAI conference on artificial intelligence, Honolulu, HI, USA, vol. 33, 27 January–1 February 2019, pp.517–524. Palo Alto, California, USA: The Association for the Advancement of Artificial Intelligence (AAAI).

58.

Conover

. Practical nonparametric statistics, 3rd ed. New York: Wiley, 1999.

Spatial crowdsourcing: An AI-based quality-aware task allocation and procrastination prevention mechanism

Abstract

Keywords

1. Introduction

2. Literature review

3. System models

3.1. Notations and their usage

3.2. Objective

4. Proposed algorithms

4.1. Task assignment

4.1.1. Phase 1: CMS

4.2. Prevention of procrastination

4.2.1. Schematic diagram of PPSJBP

5. Analysis of the proposed algorithms

5.1. Analysis of QATA

6.1. Setup

Table 2. Synthetic dataset. Sl # Job ( Γ ) Job cost ( χ ) 1 γ 1 10 2 γ 2 40 3 γ 3 25 4 γ 4 100 5 γ 5 89

6.2.1. Comparison between set of schedules with minimum variance and other randomly chosen sets of schedules

7.1. Setup for comparison

7.2. Based on TC per schedule

Table 5. Mann–Whitney U -test using four sets of samples. #Samples P -values U score Remarks 5 0.0037474788 0.0 Reject H 1 10 0.0000243773 0.0 Reject H 1 15 0.0000003433 0.0 Reject H 1 20 0.0000000040 0.0 Reject H 1

Footnotes

ORCID iDs

Funding

Declaration of conflicting interests

Code/data availability

Studies not involving humans or animals

References

Table 2.
Synthetic dataset.

Sl # Job ( $Γ$ ) Job cost ( $χ$ )

1 $γ_{1}$ 10

2 $γ_{2}$ 40

3 $γ_{3}$ 25

4 $γ_{4}$ 100

5 $γ_{5}$ 89

Table 5.
Mann–Whitney $U$ -test using four sets of samples.

#Samples $P$ -values U score Remarks

5 0.0037474788 0.0 Reject $H_{1}$

10 0.0000243773 0.0 Reject $H_{1}$

15 0.0000003433 0.0 Reject $H_{1}$

20 0.0000000040 0.0 Reject $H_{1}$