# Research on Dynamic Task Allocation Algorithm to Improve User Participation in the Witkey Mode

Authors: Yujie Wan; Minglan Fu; Lvqiang Chen; Debao Chen; Jiekun Li; Wei Zhou; Mengxue Liu
Journal: Advances in Multimedia
 (2022)

---

## Abstract

The task allocation process in the Witkey mode is dynamic and open, in which Witkey is a rational person. Due to Witkey's individual rationality, in order to make the result of task allocation stable, task allocation must reach the Nash equilibrium. However, the Nash equilibrium point does not necessarily have the highest total system revenue. In order to make the task allocation result stable and have a high total system revenue, this paper proposes an incentive measure based on integral ranking to improve user participation. When Witkey adopts the best response strategy to select task, the order of participating in the selection will affect the individual income of Witkey to a certain extent. The higher the order, the greater the probability of obtaining higher system income. Based on this idea, a dynamic task allocation algorithm with complex tasks in the Witkey mode is proposed by combining incentive measures with best response strategy and reasonable benefit allocation strategy. The finally simulation results verified the effectiveness of the proposed algorithm, and the impact of incentive measures on the total revenue of the system was also examined.


---

## Body

## 1. Introduction

The tasks in the Witkey platform are often complex or complicated, which they cannot solve or even find suitable partners to solve, and can only seek online help through the Witkey platform. Guest model is relying on the individual or cooperation team of wisdom and creative to create value to obtain the way of income. For example, the user use the Internet to solve the problems in science, technology, work, life, learning, and other aspects and let knowledge, wisdom, experience, and service turn into economic benefits [1]. This model well reflects that the Internet is a new concept of people-centered community where users achieve value output through work and is a creative Internet knowledge management mode. In the age of data, the free sharing of information has promoted the vigorous development of the Internet, such as the emergence of Wiki websites, search engines, blog websites, etc., which have brought a lot of convenience to our life and work. However, from the perspective of human resource management, whenever the use of personal knowledge, wisdom, ability, experience, and tasks need to cost a certain economic and time cost that do not need any cost of resource sharing is not practical and does not conform to the law of economics. Consequently, cost-free mode to the end will only hinder the role of the development of the Internet. Generally speaking, individuals protect their core capabilities, which makes shared resources difficult to improve when a certain apex is reached. In addition, the diversification and continuous improvement of online payment means enabling the Internet to price prices for knowledge, wisdom, ability, experience, etc., according to its need. It means that the era of completely free sharing of Internet information has passed and is changing to the era of the value of online resources [2]. This shift is actually a change in the state of intellectual freedom, which can effectively improve the enthusiasm of solution providers to obtain more targeted problem-solving capabilities. More importantly, under the value environment of Internet resources, the employment mode of the Witkey model is more flexible. It is no longer restricted by time, place, and way of work. The Internet allows workers from all over the world to work on a unified platform and a level playing field. The application of the Witkey model gives them more free working hours, and the competitive and cooperative ways can also bring them more ideas and creativity to the Witkey model. So, making good use of the knowledge of users, wisdom, service and experience of this platform can pay less cost to get the same quality service or even higher quality service to meet the needs of enterprises or individuals in some aspects. It is clear that the Witkey model is good to meet the supply and demand of service and a more efficient and lower cost matching [3].Rational people or rational agents are characterized by self-interest. Compared with the task assignment of collaborative agents in the general sense, the task assignment of rational users has some unique properties, such as the following: (1) the task assignment of rational users must meet the individual rationality [4, 5]. However, collaborative agents always make decisions that maximize system benefits within their capabilities (communication, computation, etc.). (2) For rational users, in order to maximize their individual benefits, they may deliberately make decisions that harm the benefits of others or system. (3) For rational users, after the completion of the task is completed, whether the benefit distribution is reasonable directly affects whether the cooperation can continue. Unreasonable allocation schemes may affect the enthusiasm of rational users to participate in future tasks and may even lead to their termination of the execution of the task midway. For cooperative agents, how to allocate the benefits is not a problem that must be considered. At the same time, because the income obtained after the task is usually a set value, for rational users, the benefit allocation scheme must meet the budget effectiveness of it [6, 7]. (4) In communication, in order to obtain better personal benefits, rational users may conceal personal information, such as geographical location, cost, or even conceal the specific content of the task. For collaborative agents, there is usually an implicit assumption that they are willing to transmit all their information to other agents or centralized managers as long as communication conditions allow. (5) Under the same conditions, the system income obtained from the rational user task allocation cannot be greater than the system income obtained from the task allocation of the collaborative agents.Due to the abovementioned differences, some existing complex task allocation algorithms for cooperative agents cannot be directly used to solve the complex task allocation of rational users in the Witkey mode. In this paper, we study the complex task assignment problem model in the Witkey model and a task assignment algorithm based on best response strategy is proposed. Based on this, a task assignment algorithm called Task Allocation Algorithm Considering Witkey Participation (TAACWP) is proposed to improve user participation. The final simulation results verify the effectiveness of this algorithm.The remainder of this article is organized as follows. Section2 summarizes the current situation of domestic and foreign research on related problems. Section 3 establishes a problem model for complex task benefit allocation and task assignment in the Witkey model. Section 4 describes the basic idea of the TAACWP algorithm and analyzes its convergence. Simulation results in Section 5 show that the algorithm proposed in this paper can efficiently distribute complex tasks and proceeds to rational users. Section 6 summarizes the work presented in this article.


## 2. Related Work

This section analyzes the status of research at home and abroad from two aspects of benefit allocation algorithm and complex task allocation algorithm for rational agents.Benefit allocation algorithm: When the task set accomplished by all possible sets of users is known, the solution concept of the cooperative game can be used to make benefit allocation if they are independent of each other [8, 9]. However, in practical applications such as Witkey, the task set that a user set can accomplish is generally unknown, and for n users, there is a possible set of 2n users with high temporal and spatial complexity. Meanwhile, when a task is assigned to a single set of users, the task cannot be reassigned to other user sets, so the sets of tasks that can be accomplished by different user sets are also not generally independent of each other.In the CRA (Consensus-based Reward Allocation) algorithm [10], a concept called “return” was introduced to distribute benefits. Return is the ratio of the remuneration each user receives to its cost. To achieve fairness, the CRA tries to align returns for all users. The fairness is reflected in the higher the cost of users to get a more share of the revenue. However, this is actually not conducive to the improvement of the total system revenue. Instead, to increase the total revenue of the system, it should be tried to allocate tasks to lower cost users to complete. The IRA (Intermediary Recruitment Algorithm) algorithm can also solve the benefit assignment and task assignment of complex tasks, but the algorithm time complexity is high when the number of services required is large [11].Complex task assignment algorithm of rational agents: Game theory is an effective method to study the decision-making of rational agents. Learning algorithms based on game theory mainly include the following: Best Response, (BR) [12, 13], Fictitious Play (FP) [14], Computationally Efficient Sampled FP (CESFP) [15], etc. Among them, for the optimal response strategy to obtain good task allocation results, then the benefits must be reasonably distributed, and the best response strategy does not account for the allocation of benefits. In virtual countermeasure algorithms, rational user decisions are based on their own historical information, which is not conducive to improving the quality of task assignment.Other similar studies on rational multiagent systems have mainly focused on resource allocation [16–20] and the single-agent task assignment [21–26]. The difference between resource assignment and task assignment is that the resources owned by the user in the resource assignment can be transferred, while the services provided by the user in Witkey customer cannot be transferred between the users [24]. The single-agent tasks are tasks that can be done without the collaboration of multiple agents. While there are also tasks in the Witkey mode that can require only one user, there are also many complex tasks that require multiple users to complete [25].In addition to the Witkey system, there are task allocation modes where rational users participate in practical applications and platforms such as crowdsourcing, such as the public intelligence perception system [21–23, 26] and space crowdsourcing [24, 25, 27, 28]. Existing crowdsourcing platforms propose corresponding benefits and task assignment algorithms; however, the allocation algorithms are mostly for single-user tasks [29]. Less consideration is given to the cases when more users complete the task. Therefore, in order to trade off the multiuser allocation situation under complex tasks, this paper presents a multiuser-oriented complex task allocation algorithm.


## 3. Definition of the Problem Model

This section gives the definition of the dynamic task allocation problem model in the Witkey platform: the task allocation in Witkey platform is a dynamic process. The task allocation model at the momentτ includes the following three sets: Witkey set Rτ:=r1τ,r2τ,…,rnττ, service set S:=s1,s2,…,sl, and task set Tτ:=t1τ,t2τ,…,tmττ, and nτ and mτ, respectively, represent the number of services available to the Witkey platform and the task needed to be completed at the moment τ, whose value changes over time. Assuming that the Witkey platform needs at most l types of services to complete complex tasks, a Witkey platform can provide at most l of services. that is, l represents the maximum number of services that users on the Witkey platform can provide.Fori∈1,2,…,nτ, j∈1,2,…,l, RSi,jτ=1 (RSi,jτ=0) denotes that Witkey can(not) provide services sj. TSNiτ indicates the number of skills the i th guest riτ has. aski,jτ represents the lowest price Witkey riτ can charge for the skills sj to complete task. If RSi,jτ=0, aski,jτ=0. This paper considers complex tasks in the Witkey mode, so for j∈1,2,…,l and k∈1,2,…,mτ , STj,kτ=1 (STj,kτ=0) indicates that the task tkτ requires (not) services sj. For each Witkey, riτ∈Rτ at the moment τ, it corresponds to an integral as djτ∈N (N representing the set of natural numbers). The gains corresponding to all tasks at the time τ are indicated as Uτ:=u1τ,u2τ,…,umττ. Each task corresponds to a maximum waiting time expressed as Eτ:=e1τ,e2τ,…,emττ. For k∈1,2,…,mτ, ekτ∈N+.The benefit allocation scheme for all tasks is represented asTSτ. For k∈1,2,…,mτ and j∈1,2,…,l, TSk,jτ represents the share of revenue that task tkτ would give to Witkey who provides service sj at moment τ. If the task tkτ can be completed at a moment τ and riτ choose to perform the task tkτ and provide services sj, then the revenue TSk,jτ share will be obtained by riτ. RTSτ denote the tasks chosen by Witkey and services provided by Witkey at time τ. TSNkτ indicates the number of skills required for the task tkτ. RTSi,0τ is the number of the task selected by riτ∈Rτ at the time τ. Therefore, RTSi,0τ∈1,2,…,mτ. For i∈1,2,…,nτ, j∈1,2,…,l, and RTSi,jτ=1 (RTSi,jτ=0) means that it riτ (not) provides services sj for the task tRTSi,0τ at all times τ. If RTSi,0τ=0, then for ∀j∈1,2,…,l, RTSi,jτ=0 is true.The tasktkτ can be completed if tkτ acquired all the required skills. Given the task selection scheme for all users RTSτ, the system gain at the time τ is defined as the sum of all tasks that can be completed, recorded as SRτ. The optimal allocation of complex tasks in the Witkey model is the benefit allocation and task allocation scheme that can maximize the system benefits.The status of Witkey and tasks at momentτ is indicated as follows:Status of the task: State of Witkey: At the moment τ, the state of Witkey riτ∈Rτ is expressed as riτ:=<RSi,⋅τ,RTSi,⋅τ,aski,⋅τ,diτ>. In particular, RSi,⋅τ is row i of RSτ; RTSi,⋅τ:=RTSi,0τ,RTSi,1τ,…,RTSi,lτ; aski,⋅τ is row i of askτ; diτ is the integral of Witkey riτ at the moment τ.Status of the task: The status of the tasktkτ∈Tτat the momentτis represented astkτ:=<ST⋅,kτ,TSNkτ,ukτ,TSk,⋅τ>. Among these,ST⋅,kτis the column k ofSTτ.TSNkτ∈Z+tkτ represents the number of skills required for the task tkτ. ukτ represents the gains available after the task tkτ is completed. TSk,⋅τ is the row k of TSτ, indicating the benefit distribution scheme of tkτ at the time.To facilitate analysis, the following assumptions are made for the abovementioned problem model:Hypothesis 1.
Each guest can choose one task at any one time and provide one service, while the number of specific services required for each task is 1.Hypothesis 2.
At any moment, Witkey will only choose the task that brings it the maximum individual benefit.Hypothesis 3.
For the tasks assigned by the Witkey platform, Witkey has the right to refuse and choose another task that can bring it more individual benefits.
Based on the above dynamic task assignment environment, this paper addresses the following dynamic task assignment problems:(1)maxRTS1…RTSΓSSRΓ=maxRTS1…RTSΓ∑τ=1Γ∑tkτ∈Tτ∧completekτukτ.
SSRΓ represents the sum of all the tasks that can be completed from time 1 to time Γ. RTS1…RTSΓ satisfies the constraint of “Hypothesis 1”. If the value of Completekτ is true, the value indicating that the task tkτ can be completed under the task assignment state RTSτ at the moment τ. Otherwise, the task tkτ cannot be completed.


## 4. Best Response Strategy and Intermediary Recruitment Algorithm

### 4.1. Best Response Strategy

ti,τ represents the task selected by Witkey riτ∈Rτ at the moment τ, and the task selection rule is shown in formula (2):(2)ti,τ+1←argmaxtkτ∈Tτ∧sj∈S∧needk,jτTSk,jτ⋅RSi,jτ,where needk,jτ indicates whether service sj needed by task tkτ is provided by other Witkey except riτ under the task assignment status RTSτ in the moment τ.Return False, if provided; Others, True. Meanwhile, the benefit allocation strategy for all tasks meets the budget effectiveness conditions shown in formula (3):(3)∑sj∈S,STj,kτ=1TSk,jτ≤ukτ.At some point, when all Witkey, tasks, and the benefit distribution scheme of tasks remain unchanged, all Witkeys take turns to perform the strategy shown in formula (1) to make the best choice. The optimal task selection process is a kind of weak noncircular game, and each weak noncircular game has limited improvement characteristics [30]. Thus, the procedure will converge to a Nash equilibrium point. Formula (1) ensures the individual rationality of the task assignment and the stability of the task assignment results.


### 4.2. Intermediary Recruitment Algorithm

Because the incentives to increase users engagement examined in this paper are based on existing task assignment and benefit assignment algorithms, a simple description of the basic idea of “intermediary recruitment algorithm” was given. The proposed algorithm simulates the operation mechanism of the talent recruitment market with an intermediary to solve the task selection problem of self-interest service agent. Workers who provide services are seen as applicants, skills as intermediaries, and tasks as companies to hire employees. Unlike the real recruitment market, a “service intermediary” only manages the workers who can provide specific services and the tasks that need them. “service intermediary” pairs workers and tasks based on information about the number of workers who can provide the service, the costs, the number of tasks that need the service, and the remuneration that can be provided. The proposed algorithm can reasonably distribute the benefits of complex tasks to a certain extent and improve the total system income of task distribution, but because the results of task allocation do not guarantee individual rationality, the task distribution is not stable.The steps of one task assignment by the intermediary recruitment algorithm are described as follows:Step 1.
All “service intermediary” count basic information about the workers who can provide the service and the tasks that need the service. Witkey is sorted from small to large at the minimum asking price, and the tasks are sorted from large to small by the revenue share allocated to the corresponding skills. Witkey and task were paired in order. It was success, if the gain share was greater than the minimum asking price, or the pairing failed.Step 2.
All tasks take turns to check whether all the required services are paired successfully. For services without paired success, try to increase the share of revenue allocated to workers who can provide the service until it can be increased.Step 3.
Check if all workers pair with only one task. If so, this task assignment ends; otherwise, go to Step4.Step 4.
For workers who pair more than one tasks, select a task that brings the maximum individual benefits from the paired successful task and reject other tasks. The rejected intermediary then entered the competitive price adjustment phase until no task provided the worker with greater individual benefit beyond the worker's currently chosen task, at which point the worker paired only a successful task.Step 5.
This round of task assignment ends. Update the data and go to the next round of task assignment.


### 4.3. Incentive Measures

It can be seen from formula (1) that in the process of choosing the optimal task according to the optimal response strategy, the earlier he chooses the task, the more likely it is to obtain greater individual benefits. Therefore, for every Witkey, riτ∈Rτ at the moment τ, it is given an integral, recorded as djτ∈N. Witkey turns the optimal selection strategy in order of the integral from large to small. If the Witkey riτ∈Rτ abandons the current maximum individual gain in order to increase the total system gain, the incremental value of the system gain is added to the customer as a new integral.(4)diτ+1=diτ+SRτ+1−SRτ,where SRτ+1 means that the total system revenue when Witkey riτ∈Rτ gives up the current task that brings itself maximum individual benefits and chooses to perform a task that can get greater system benefits. At this time, other tasks chosen by Witkeys except Witkey riτ∈Rτ are satisfied with individual rationality. In other words, only Witkey riτ∈Rτ sacrificed its own individual income, thus increasing the total revenue of the system. Therefore, in order to motivate Witkey riτ∈Rτ to participate in the execution of tasks, the increased system revenue is added to Witkey riτ∈Rτ as an integral. At the same time, the increased system revenue can also increase its participation in performing tasks to a certain extent.


### 4.4. Algorithmic Description

This section provides a simple description of the task assignment algorithm (Task Allocation Algorithm Considering Witkey Participation, TAACWP) as shown in the Algorithm1:Algorithm 1: TAACWP.
import: nτ, mτ, ΓOutput: the maximum total system revenueSSRΓ and its counterpart. RTS1…RTSΓ(1)
FORτ∈1,2,…,Γ(2)
Use the “intermediary recruitment algorithm” for a round of task assignment.(3)
Record the system benefitsSSRτ at the moment τ.(4)
FORi∈1,2,…,nτ(5)
Save all Witkey’s current task selection statusRTSτ.(6)
FORk∈1,2,…,mτ(7)
FORj∈1,2,…,L(8)
Witkeyi selects tasks and provides skills j.(9)
All others, except Witkeyi, adopt the optimal reaction strategy selection task in turn in the order of integration from large to small, and the results of guiding two consecutive rounds of the optimal reaction are exactly the same.(10)
Record the new system benefits.SSR′τ(11)
END FOR(12)
END FOR(13)
IFSSR′τ>SSRτ(14)
diτ=diτ+SSR′τ−SSRτ(15)
ELSE(16)
Restore the task selection status for all Witkey customers.RTSτ(17)
END IF(18)
END FOR(19)
Update data for Witkey and tasks: Remove tasks that are beyond the “maximum waiting time”, add new tasks and new customers, and update Witkey's points, skills, and other information.(20)
END FOR


## 4.1. Best Response Strategy

ti,τ represents the task selected by Witkey riτ∈Rτ at the moment τ, and the task selection rule is shown in formula (2):(2)ti,τ+1←argmaxtkτ∈Tτ∧sj∈S∧needk,jτTSk,jτ⋅RSi,jτ,where needk,jτ indicates whether service sj needed by task tkτ is provided by other Witkey except riτ under the task assignment status RTSτ in the moment τ.Return False, if provided; Others, True. Meanwhile, the benefit allocation strategy for all tasks meets the budget effectiveness conditions shown in formula (3):(3)∑sj∈S,STj,kτ=1TSk,jτ≤ukτ.At some point, when all Witkey, tasks, and the benefit distribution scheme of tasks remain unchanged, all Witkeys take turns to perform the strategy shown in formula (1) to make the best choice. The optimal task selection process is a kind of weak noncircular game, and each weak noncircular game has limited improvement characteristics [30]. Thus, the procedure will converge to a Nash equilibrium point. Formula (1) ensures the individual rationality of the task assignment and the stability of the task assignment results.


## 4.2. Intermediary Recruitment Algorithm

Because the incentives to increase users engagement examined in this paper are based on existing task assignment and benefit assignment algorithms, a simple description of the basic idea of “intermediary recruitment algorithm” was given. The proposed algorithm simulates the operation mechanism of the talent recruitment market with an intermediary to solve the task selection problem of self-interest service agent. Workers who provide services are seen as applicants, skills as intermediaries, and tasks as companies to hire employees. Unlike the real recruitment market, a “service intermediary” only manages the workers who can provide specific services and the tasks that need them. “service intermediary” pairs workers and tasks based on information about the number of workers who can provide the service, the costs, the number of tasks that need the service, and the remuneration that can be provided. The proposed algorithm can reasonably distribute the benefits of complex tasks to a certain extent and improve the total system income of task distribution, but because the results of task allocation do not guarantee individual rationality, the task distribution is not stable.The steps of one task assignment by the intermediary recruitment algorithm are described as follows:Step 1.
All “service intermediary” count basic information about the workers who can provide the service and the tasks that need the service. Witkey is sorted from small to large at the minimum asking price, and the tasks are sorted from large to small by the revenue share allocated to the corresponding skills. Witkey and task were paired in order. It was success, if the gain share was greater than the minimum asking price, or the pairing failed.Step 2.
All tasks take turns to check whether all the required services are paired successfully. For services without paired success, try to increase the share of revenue allocated to workers who can provide the service until it can be increased.Step 3.
Check if all workers pair with only one task. If so, this task assignment ends; otherwise, go to Step4.Step 4.
For workers who pair more than one tasks, select a task that brings the maximum individual benefits from the paired successful task and reject other tasks. The rejected intermediary then entered the competitive price adjustment phase until no task provided the worker with greater individual benefit beyond the worker's currently chosen task, at which point the worker paired only a successful task.Step 5.
This round of task assignment ends. Update the data and go to the next round of task assignment.


## 4.3. Incentive Measures

It can be seen from formula (1) that in the process of choosing the optimal task according to the optimal response strategy, the earlier he chooses the task, the more likely it is to obtain greater individual benefits. Therefore, for every Witkey, riτ∈Rτ at the moment τ, it is given an integral, recorded as djτ∈N. Witkey turns the optimal selection strategy in order of the integral from large to small. If the Witkey riτ∈Rτ abandons the current maximum individual gain in order to increase the total system gain, the incremental value of the system gain is added to the customer as a new integral.(4)diτ+1=diτ+SRτ+1−SRτ,where SRτ+1 means that the total system revenue when Witkey riτ∈Rτ gives up the current task that brings itself maximum individual benefits and chooses to perform a task that can get greater system benefits. At this time, other tasks chosen by Witkeys except Witkey riτ∈Rτ are satisfied with individual rationality. In other words, only Witkey riτ∈Rτ sacrificed its own individual income, thus increasing the total revenue of the system. Therefore, in order to motivate Witkey riτ∈Rτ to participate in the execution of tasks, the increased system revenue is added to Witkey riτ∈Rτ as an integral. At the same time, the increased system revenue can also increase its participation in performing tasks to a certain extent.


## 4.4. Algorithmic Description

This section provides a simple description of the task assignment algorithm (Task Allocation Algorithm Considering Witkey Participation, TAACWP) as shown in the Algorithm1:Algorithm 1: TAACWP.
import: nτ, mτ, ΓOutput: the maximum total system revenueSSRΓ and its counterpart. RTS1…RTSΓ(1)
FORτ∈1,2,…,Γ(2)
Use the “intermediary recruitment algorithm” for a round of task assignment.(3)
Record the system benefitsSSRτ at the moment τ.(4)
FORi∈1,2,…,nτ(5)
Save all Witkey’s current task selection statusRTSτ.(6)
FORk∈1,2,…,mτ(7)
FORj∈1,2,…,L(8)
Witkeyi selects tasks and provides skills j.(9)
All others, except Witkeyi, adopt the optimal reaction strategy selection task in turn in the order of integration from large to small, and the results of guiding two consecutive rounds of the optimal reaction are exactly the same.(10)
Record the new system benefits.SSR′τ(11)
END FOR(12)
END FOR(13)
IFSSR′τ>SSRτ(14)
diτ=diτ+SSR′τ−SSRτ(15)
ELSE(16)
Restore the task selection status for all Witkey customers.RTSτ(17)
END IF(18)
END FOR(19)
Update data for Witkey and tasks: Remove tasks that are beyond the “maximum waiting time”, add new tasks and new customers, and update Witkey's points, skills, and other information.(20)
END FOR


## 5. Simulation Results

In Section5.1, the algorithm TAACWP is compared with the other four algorithms for the average running time and the average system gains under four different datasets. Section 5.2 validates the effectiveness of TAACWP's task assignment strategy and examines whether incentives have effects on rational people.Simulation environment:Memory: 3.0 G B; CPU, Intel (R) Pentium (R) CPU G2030; Main frequency: 3.0 GHz;Operating system: Windows 7.For the dataset, to our knowledge, there is currently no standard database for Coalitional skill games. For resource-constrained project scheduling issues, “Project Scheduling Problem Library” is available [31]. It is its standard database, but the resources in it do not have multiple skills. Another similar dataset is the iMOPSE [32, 33], The resources have multiple skills (the resources can be considered as the service agent in the coalitional skills game), but the task in iMOPSE requires only one resource. For some other similar problems, the datasets used are artificially randomly generated [34, 35]. In this paper, dataset 1, dataset 2, and dataset 3 are completely randomly generated. Dataset 4 was generated based on iMOPSE and was specifically generated as follows. The future needs to establish a corresponding database for the coalitional skill game problem model.Dataset 1.
(total of 15 runs, maximum number of iterationsΓ=100, generated dynamic task assignment data of 1.1–1.20) generates date which satisfies the following rules at the moment τ. (randoma,b represents a random integer in the set): nτ=30, l=15 and mτ=30. For riτ∈Rτ, askiτ←random1,2, and RSNiτ←random1,3. For tk∈T, uk←TSNk×random1,m/2, TSNkτ←random2,5, and ekτ←random5,10.Dataset 2.
(total of 15 runs, each maximum number of iterationsΓ=200, generated dynamic task assignment data of 2.1–2.20) generates date which satisfies the following rules at the moment τ. (randoma,b represents a random integer in the set a,b): nτ=30, l=15 and mτ=60. For riτ∈Rτ, askiτ←random1,2, and RSNiτ←random1,3. For tk∈T, uk←TSNk×random1,m/2, TSNkτ←random2,5, and ekτ←random5,10.Dataset 3.
(total of 15 runs, each maximum number of iterationsΓ=200, generated dynamic task assignment data of 2.1–2.20) generates date which satisfies the following rules at the moment τ. (randoma,b represents a random integer in the set a,b): nτ=30, l=15, and mτ=60. For riτ∈Rτ, askiτ←random1,2, and RSNiτ←random1,3. For tk∈T, uk←TSNk×random1,m/2, TSNkτ←random2,4, and ekτ←random5,10.Dataset 4.
Witkey and task data in dataset 4 are from the following iMOPSE-based data, generating the following steps:Step 6.
Draw300 user information (namely corresponding Witkey): 100_20_22_15, 100_20_23_9_D1, 200_40_91_15, 100_20_45_15, 200_40_45_9, 100_20_47_9, 100_20_65_9, 100_20_65_15, 200_40_45_15, 200_40_90_9, 200_40_130_9_D4, 200_40_133_15.Step 7.
Information for 400 tasks are extracted from the datasets 200_40_91_15 and 200_40_133_15.Step 8.
MakeRSNiτ⟵random1,2 and TSNkτ⟵random2,5 established by randomly adding or deleting the corresponding skills.Step 9.
Forriτ∈Rτ, askiτ⟵random1,2. For tk∈T, uk⟵TSNk×random1,m/2 and ekτ⟵random5,10.
For the dataset, the generation process of dynamic data is as follows: At the momentτ, randomly select random1,Nτ/10 Witkey data meeting the above conditions to replace the Witkey data at moment τ−1, and specifically which to replace is randomly determined. The tasks that can be completed and tasks that cannot be completed are randomly replaced with new task data that meet the above requirements.


### 5.1. Algorithm Performance Comparison

In this section, the total sum of the system benefitsSSTΓ and the average running time SSTΓ/Γ of the TAACWP (where SSTΓ denotes the total time spent during the dynamic task assignment process): general genetic algorithm (GGA), SAA algorithm (Service and Adams' Algorithm, SAA) for Dataset 1, Dataset 2, Dataset 3, and Dataset 4 [36], Combinatorial auction algorithm (Combinatorial Bids based Algorithm, CBA) [37], and the VAA algorithm (Vig & Adams' Algorithm, VAA) [38]. Witkey in the CBA is self-beneficial, while Witkey in the GGA and SAA is not. At moments τ∈1,2,…,Γ, the dynamic task assignments have consistent data generation rules.Dataset 1.1 was used to obtain the optimal parameters for the GGA. With cross probability (CP) and variant probability (MP) taking different values, GGA runs 100 times, and the average system gain is shown in Table1(rows indicate the value of MP, columns indicate the value of CP). Simulation results show that the average system gain is greatest when CP is 0.3 and MP is 0.1. Other parameters of the GGA were set as follows: population size 100 and maximum number of iterations 10000.Table 1
Mean system gains of GGA when CP and MP take different values.
MP0.010.050.10.150.20.40.60.8CP0.115214148451654415802158161134910389106680.214302156841628316717147561176610763101250.2514956143161595716277144651151611235111580.314449142241676214597134701157810739100550.3514144157181479514767131331136911157105590.414566159141563514637124241165211620107280.515852160461532814414128291145010663105390.614909146891548014175129051135510598108830.81491315731154791297412803108981105310881Under Dataset1, 2, 3, and 4, TAACWP, GGA, CBA, VAA, and SAA are shown in Tables 2–5, respectively.Table 2
Average system gain and the average runtime under dataset 1.
DatasetTAACWPTimeGGATimeCBATimeVAATimeSAATime1.1176986.011676227.32171890.002179241.67120000.0011.2195116.271596327.16161560.002173921.70113030.0011.3178647.111423627.63176110.002175961.54125390.0011.4176685.611645626.68176530.001169521.58126300.0011.5192155.251428727.38170680.002168831.6589030.0011.6184945.531632527.51166970.002175361.56101670.0011.7199666.021516427.31171870.002184861.5574750.0011.8187546.621638627.98175070.003167261.76101300.0011.9162586.021626325.77164560.002180491.66109630.0011.10175998.711645826.61190630.002168531.62115290.0011.11181386.501642227.58169480.002164361.6194850.0011.12188737.151627126.82183910.002170611.55110650.0011.13204057.101563726.88180830.002175481.47110330.0011.14194557.211653726.43175440.002177071.5979700.0011.15166654.531647527.77162860.002179321.56105140.001Table 3
Average system gain and average runtime under dataset 2.
Dataset 2TAACWPTimeGGATimeCBATimeVAATimeSAATime2.19888919.136714554.12955590.003918182.65599570.0012.29886813.177000755.88910440.003964302.27572040.0012.310275413.876683555.73922180.003969462.62546730.0012.49748720.496743853.30932690.002972272.43502680.0012.59967516.776655955.82981960.002960032.24540190.0012.610169013.736880753.80935960.002882632.73510640.0012.710417114.546706654.10936620.002909002.49561260.0012.810174913.586414055.47923790.002941312.31639470.0012.910127218.886612154.18924030.003936972.28552980.0012.1010315413.516979354.15890380.002931302.26503470.0012.119948513.766534454.26953010.002924262.66539320.0012.1210673015.267005453.63933530.002929422.29519100.0012.1310128714.936995254.81899240.002945952.99554660.0012.149629314.416841854.01909960.002937062.38492410.0012.1510023414.016990453.59949900.002975272.35603360.001Table 4
Average system gain and average runtime under dataset 3.
Dataset 3TAACWPTimeGGATimeCBATimeVAATimeSAATime3.1571866.295463041.39528900.003540323.42478790.0013.2563726.385756040.15495640.003545423.56382070.0013.3586705.825690043.72527590.003527923.31458990.0013.4556475.795886050.89543870.003553372.93424650.0013.5551715.935795750.85523310.003542703.89429590.0013.6590956.275515850.75557960.003522373.72456130.0013.7587445.695641350.06549930.002540872.97475070.0013.8557636.215554855.64528840.003532902.94437930.0013.9567395.755540155.82548020.003555173.84400480.0013.10587895.535655655.47552850.002532122.88416120.0013.11588516.495707155.47528010.003489913.29458230.0013.12587046.185511555.29523220.003535582.99475620.0013.13567725.905574955.25546550.002521543.15445350.0013.14574855.455596655.32532650.003532093.20461390.0013.15571806.035889955.70543090.003557504.10435710.001Table 5
Average system gain and average runtimes under dataset 4.
Dataset 4TAACWPTimeGGATimeCBATimeVAATimeSAATime4.1283564.992409726.66214440.001264361.89105370.0014.2295775.582117127.39264500.002260021.8862230.0014.3265976.392506027.04185700.001244681.6678330.0014.4289155.362240227.82225260.002245691.7655570.0014.5248715.522388727.89188830.001250441.6489750.0014.6247415.262285928.20207040.001259611.8295700.0014.7235955.422245827.90215280.002209881.7981450.0014.8245396.762140527.98233090.002248741.6189030.0014.9277055.272433527.53235080.001212061.67123350.0014.10219165.612192627.37254290.001207191.6757810.0014.11245975.652567426.99234220.002240381.8174320.0014.12287345.682284527.91206810.001229901.7291040.0014.13270835.942176828.28203040.001254701.66118400.0014.14239694.662294127.47255870.002212471.6376870.0014.15267035.172294927.32258160.001249591.85111330.001The results in Tables2–5 show that the sum of system gains from TAACWP is higher than the other four algorithms and the average running time of TAACWP is shorter than GGA. Among them, due to the excessive search space of GGA, the system has the worst profit and the longest running time. Therefore, based on the best response strategy, the adjustment of task income allocation scheme by using the intermediary allocation algorithm can also improve the system income when the service agent is self-interested.


### 5.2. Validation of the Effectiveness of the TAACWP Incentive Measures

This section examines the effect of incentives on the total system benefits of the TAACWP algorithm, in which the TAACWP algorithm with no incentives is recorded as TAACWP1. The simulation results are shown in Table6:Table 6
Average system gains and average runtime for TAACWP and TAACWP1 under dataset 1, dataset 2, dataset 3, and dataset 4.
Dataset 1TAACWPTAACWP1Dataset 2TAACWPTAACWP1Dataset 3TAACWPTAACWP1Dataset 4TAACWPTAACWP11.117698176642.198889985293.157186571044.128356282841.219511194572.298868982423.256372562984.229577294951.317864178122.31027541021013.358670586414.326597265171.417668176282.497487969433.455647555874.428915288251.519215191282.599675991013.555171551254.524871247751.618494184162.61016901012043.659095590414.624741246561.719966199122.71041711036843.758744587024.723595235011.818754186992.81017491010763.855763557104.824539244871.916258162392.91012721008173.956739566544.927705275961.1017599175782.101031541027043.1058789587254.1021916217861.1118138180842.1199485991733.1158851588014.1124597245161.1218873187982.121067301059963.1258704586804.1228734286791.1320405203742.131012871008183.1356772567274.1327083270161.1419455194102.1496293958953.1457485574054.1423969239301.1516665165872.15100234998253.1557180571464.152670326588The simulation results from Table6 show that the system benefits of TAACWP are greater than TAACWP1. The simulation results further show that using incentives can guarantee the higher system gain, even if the user is rational.


## 5.1. Algorithm Performance Comparison

In this section, the total sum of the system benefitsSSTΓ and the average running time SSTΓ/Γ of the TAACWP (where SSTΓ denotes the total time spent during the dynamic task assignment process): general genetic algorithm (GGA), SAA algorithm (Service and Adams' Algorithm, SAA) for Dataset 1, Dataset 2, Dataset 3, and Dataset 4 [36], Combinatorial auction algorithm (Combinatorial Bids based Algorithm, CBA) [37], and the VAA algorithm (Vig & Adams' Algorithm, VAA) [38]. Witkey in the CBA is self-beneficial, while Witkey in the GGA and SAA is not. At moments τ∈1,2,…,Γ, the dynamic task assignments have consistent data generation rules.Dataset 1.1 was used to obtain the optimal parameters for the GGA. With cross probability (CP) and variant probability (MP) taking different values, GGA runs 100 times, and the average system gain is shown in Table1(rows indicate the value of MP, columns indicate the value of CP). Simulation results show that the average system gain is greatest when CP is 0.3 and MP is 0.1. Other parameters of the GGA were set as follows: population size 100 and maximum number of iterations 10000.Table 1
Mean system gains of GGA when CP and MP take different values.
MP0.010.050.10.150.20.40.60.8CP0.115214148451654415802158161134910389106680.214302156841628316717147561176610763101250.2514956143161595716277144651151611235111580.314449142241676214597134701157810739100550.3514144157181479514767131331136911157105590.414566159141563514637124241165211620107280.515852160461532814414128291145010663105390.614909146891548014175129051135510598108830.81491315731154791297412803108981105310881Under Dataset1, 2, 3, and 4, TAACWP, GGA, CBA, VAA, and SAA are shown in Tables 2–5, respectively.Table 2
Average system gain and the average runtime under dataset 1.
DatasetTAACWPTimeGGATimeCBATimeVAATimeSAATime1.1176986.011676227.32171890.002179241.67120000.0011.2195116.271596327.16161560.002173921.70113030.0011.3178647.111423627.63176110.002175961.54125390.0011.4176685.611645626.68176530.001169521.58126300.0011.5192155.251428727.38170680.002168831.6589030.0011.6184945.531632527.51166970.002175361.56101670.0011.7199666.021516427.31171870.002184861.5574750.0011.8187546.621638627.98175070.003167261.76101300.0011.9162586.021626325.77164560.002180491.66109630.0011.10175998.711645826.61190630.002168531.62115290.0011.11181386.501642227.58169480.002164361.6194850.0011.12188737.151627126.82183910.002170611.55110650.0011.13204057.101563726.88180830.002175481.47110330.0011.14194557.211653726.43175440.002177071.5979700.0011.15166654.531647527.77162860.002179321.56105140.001Table 3
Average system gain and average runtime under dataset 2.
Dataset 2TAACWPTimeGGATimeCBATimeVAATimeSAATime2.19888919.136714554.12955590.003918182.65599570.0012.29886813.177000755.88910440.003964302.27572040.0012.310275413.876683555.73922180.003969462.62546730.0012.49748720.496743853.30932690.002972272.43502680.0012.59967516.776655955.82981960.002960032.24540190.0012.610169013.736880753.80935960.002882632.73510640.0012.710417114.546706654.10936620.002909002.49561260.0012.810174913.586414055.47923790.002941312.31639470.0012.910127218.886612154.18924030.003936972.28552980.0012.1010315413.516979354.15890380.002931302.26503470.0012.119948513.766534454.26953010.002924262.66539320.0012.1210673015.267005453.63933530.002929422.29519100.0012.1310128714.936995254.81899240.002945952.99554660.0012.149629314.416841854.01909960.002937062.38492410.0012.1510023414.016990453.59949900.002975272.35603360.001Table 4
Average system gain and average runtime under dataset 3.
Dataset 3TAACWPTimeGGATimeCBATimeVAATimeSAATime3.1571866.295463041.39528900.003540323.42478790.0013.2563726.385756040.15495640.003545423.56382070.0013.3586705.825690043.72527590.003527923.31458990.0013.4556475.795886050.89543870.003553372.93424650.0013.5551715.935795750.85523310.003542703.89429590.0013.6590956.275515850.75557960.003522373.72456130.0013.7587445.695641350.06549930.002540872.97475070.0013.8557636.215554855.64528840.003532902.94437930.0013.9567395.755540155.82548020.003555173.84400480.0013.10587895.535655655.47552850.002532122.88416120.0013.11588516.495707155.47528010.003489913.29458230.0013.12587046.185511555.29523220.003535582.99475620.0013.13567725.905574955.25546550.002521543.15445350.0013.14574855.455596655.32532650.003532093.20461390.0013.15571806.035889955.70543090.003557504.10435710.001Table 5
Average system gain and average runtimes under dataset 4.
Dataset 4TAACWPTimeGGATimeCBATimeVAATimeSAATime4.1283564.992409726.66214440.001264361.89105370.0014.2295775.582117127.39264500.002260021.8862230.0014.3265976.392506027.04185700.001244681.6678330.0014.4289155.362240227.82225260.002245691.7655570.0014.5248715.522388727.89188830.001250441.6489750.0014.6247415.262285928.20207040.001259611.8295700.0014.7235955.422245827.90215280.002209881.7981450.0014.8245396.762140527.98233090.002248741.6189030.0014.9277055.272433527.53235080.001212061.67123350.0014.10219165.612192627.37254290.001207191.6757810.0014.11245975.652567426.99234220.002240381.8174320.0014.12287345.682284527.91206810.001229901.7291040.0014.13270835.942176828.28203040.001254701.66118400.0014.14239694.662294127.47255870.002212471.6376870.0014.15267035.172294927.32258160.001249591.85111330.001The results in Tables2–5 show that the sum of system gains from TAACWP is higher than the other four algorithms and the average running time of TAACWP is shorter than GGA. Among them, due to the excessive search space of GGA, the system has the worst profit and the longest running time. Therefore, based on the best response strategy, the adjustment of task income allocation scheme by using the intermediary allocation algorithm can also improve the system income when the service agent is self-interested.


## 5.2. Validation of the Effectiveness of the TAACWP Incentive Measures

This section examines the effect of incentives on the total system benefits of the TAACWP algorithm, in which the TAACWP algorithm with no incentives is recorded as TAACWP1. The simulation results are shown in Table6:Table 6
Average system gains and average runtime for TAACWP and TAACWP1 under dataset 1, dataset 2, dataset 3, and dataset 4.
Dataset 1TAACWPTAACWP1Dataset 2TAACWPTAACWP1Dataset 3TAACWPTAACWP1Dataset 4TAACWPTAACWP11.117698176642.198889985293.157186571044.128356282841.219511194572.298868982423.256372562984.229577294951.317864178122.31027541021013.358670586414.326597265171.417668176282.497487969433.455647555874.428915288251.519215191282.599675991013.555171551254.524871247751.618494184162.61016901012043.659095590414.624741246561.719966199122.71041711036843.758744587024.723595235011.818754186992.81017491010763.855763557104.824539244871.916258162392.91012721008173.956739566544.927705275961.1017599175782.101031541027043.1058789587254.1021916217861.1118138180842.1199485991733.1158851588014.1124597245161.1218873187982.121067301059963.1258704586804.1228734286791.1320405203742.131012871008183.1356772567274.1327083270161.1419455194102.1496293958953.1457485574054.1423969239301.1516665165872.15100234998253.1557180571464.152670326588The simulation results from Table6 show that the system benefits of TAACWP are greater than TAACWP1. The simulation results further show that using incentives can guarantee the higher system gain, even if the user is rational.


## 6. Conclusion

In this paper, we propose an optimization algorithm that motivate rational Witkey to participate in performing tasks. The users in the Witkey model are rational people, who always choose the tasks that can bring them the most personal benefits and are easy to accomplish. The task requester's goal is to acquire all the required skills and then complete the task. For rational Witkey, the stability of the task assignment results can be guaranteed only when the benefits are reasonably distributed and the task assignment achieves a Nash equilibrium. However, the self-interest will inevitably affect the improvement of the total system income. By encouraging Witkey to give up the task that brings itself greater individual benefits, it is necessary to choose the task that can maximize the total benefits of the system. Consequently, certain incentives must be taken. In the process of selecting tasks according to the optimal response strategy, the execution order will partly affect the individual benefits of Witkey. According to this feature, this paper proposes the incentive measure for additive integral, proposes the TAACWP algorithm to solve the benefit distribution of complex tasks in Witkey mode, and the final simulation results verify the effectiveness of the algorithm. We also came to another conclusion: adding incentives seems to yield more benefits, but may not be the best option in all cases because of the computational cost. Future research work will further summarize the dynamic characteristics of Witkey task assignment; consider the Witkey integrity, skill level, and other characteristics; and improve the dynamic task assignment model. Moreover, we also will consider applying the proposed algorithm to various crowdsourcing platform task allocation scenarios and shop floor scheduling. On this basis, the task assignment algorithm meets the characteristics of individual rationality, budget effectiveness, privacy protection, and stability of task assignment results.



---

*Source: 5301768-2022-04-23.xml*