CN106557871A - A kind of method for allocating tasks in gunz system based on stable matching algorithm - Google Patents

Abstract

The invention discloses a task allocation method based on a stable matching algorithm in a crowd intelligence system, which fully considers the quality level and preferences of workers, as well as the quality requirements and budget constraints of tasks, and transforms the original problem into a task with strict upper boundary requirements (budget constraints) ) and a loose lower bound requirement (quality requirement) for many-to-one matching problems, achieving stable and efficient task assignment results.

Description

A Task Allocation Method Based on Stable Matching Algorithm in Crowd Intelligence System

technical field

The invention belongs to the technical field of swarm intelligence systems, and in particular relates to a task allocation method based on a matching algorithm to ensure task quality requirements in a swarm intelligence system.

Background technique

The group intelligence system is an open, voluntary, new cooperation model that provides a reliable environment for companies or individuals. The swarm intelligence system is shared. Companies can publish questions or tasks on the swarm intelligence system, and individuals can choose questions or tasks. The scale of contributions from many individual users can achieve goals that were difficult to achieve in the past. By gathering the wisdom of crowds, the crowd intelligence system can complete tasks such as environmental data collection and design and evaluation of new products with low cost and high quality.

Due to the diversity of people's experience, proficiency, skills, and expertise, they have different preferences for tasks, and the quality with which they complete specific tasks also varies. Selecting a suitable set of workers for a specific task is crucial, a problem known as task assignment in swarm intelligence systems. In the task allocation of the crowd intelligence system, it is necessary to consider the different quality requirements and budgets of the released tasks, and at the same time, the ability and preference of workers should be considered in the selection of workers.

In a swarm intelligence system, different workers have different levels of quality based on their skills, experience, and proficiency. Assume that the task issuer knows the skill level of all workers. A worker with a high quality level tends to demand higher compensation when performing a job, because these workers need to spend more time training, and task issuers are more willing to pay more for more reliable results. remuneration. Since the completion of swarm intelligence tasks depends on the collective intelligence of workers, sufficient workers must be recruited for a task to be successful. The task issuer must ensure that he can attract enough workers to meet the quality requirements, and recruiting a large number of workers can achieve a higher quality level, but the task issuer's budget is limited, which also limits the number of workers he can recruit. Therefore, the total quality level of workers recruited by a task is greater than the quality requirements of the task, and the remuneration paid to workers is less than the budgeted value of the task.

Each worker has its own preference list for all tasks. For example, if there are two task issuers collecting traffic information at two different locations, workers prefer to choose the location closer to their own residence. Likewise, each task issuer also has its own preference list for all workers according to their quality level.

To sum up, a task allocation scheme that takes into account quality requirements, budget constraints, and workers' preferences is the key to the normal operation of the crowd intelligence system. Task allocation for swarm intelligence systems is a hot research issue, and reliable task allocation strategies for mobile swarm intelligence systems have been proposed in many literatures. Guaranteeing satisfactory assignments involves quality requirements and worker preferences, and previous solutions do not match workers and tasks well. Some propose the many-to-one matching problem, and although worker preferences and budget constraints are taken into account, quality requirements are not considered.

Contents of the invention

Aiming at the deficiency of the existing group intelligence system task allocation scheme, the present invention proposes a stable task allocation method that fully considers worker preferences, task quality requirements and budget constraints.

The technical scheme adopted in the present invention is: a task assignment method based on a stable matching algorithm in a crowd intelligence system, comprising the following steps:

Step 1: Get the quality level {r _s } _s∈S of each worker s and its preference list {＞ _s } _S , where S is the set of all workers; get the preference list {＞ _t } _τ , quality of each task t Requirements {q _t } t ∈ _τ and budget constraints {b _t } t ∈ _τ , where τ is the set of all tasks;

Step 2: According to the preference list {> _s } _S of worker s, write the preference order of s into the application list p(s) of s;

Step 3: Determine whether the application list p(s) of worker s is empty;

If yes, perform step 4 below;

If not, end this process;

Step 4: Take the first task t in the application list p(s), and remove t from p(s);

Step 5: Determine whether the total quality level of the workers currently assigned to task t is less than the quality requirements of task t;

If yes, then perform the following step 6;

If not, then perform the following step 7;

Step 6: Execute the REDA algorithm;

Step 7: Calculate the difference △Q of all tasks that have not met the quality requirements and the total quality level △R of all unassigned workers;

Step 8: Judging the size of △ _Rrs and △Q;

If △ _Rrs is greater than the difference △Q, execute the REDA algorithm;

If △ _Rrs is less than the difference △Q, go to step 9

Step 9: Worker s cannot be assigned to task t, take the next worker information as worker s, and execute the above step 3;

Described REDA algorithm comprises the following steps:

Step 6.1: Obtain worker s and task t information, worker s∈S, task t∈τ;

Step 6.2: Determine whether the remaining budget of the task is greater than the worker's compensation;

If so, assign worker s to task t, then take the next worker information as worker s, and execute step 3 in reverse;

If not, perform the following step 6.3;

Step 6.3: Find out the worker set A whose quality level is lower than worker s among the workers currently assigned to task t;

Step 6.4: Determine whether there is a sub-set B of workers whose total quality level is less than the minimum quality level of worker s in set A;

If yes, select the set B _min with the smallest total quality level of workers in all sets that meet step 6.4, cancel the assignment relationship between task t and all workers in set B _min , assign worker s to task t, and then take the next worker information as Worker s, and turn around to execute the step 3;

If not, then worker s cannot be assigned to task t, take the next worker information as worker s, and go back to step 3.

The present invention assumes that each task issuer of the crowd intelligence system issues a specific task. In practice, each task publisher in the swarm intelligence system is allowed to publish multiple tasks. In this case, the task publisher can be regarded as multiple virtual task publishers, and a virtual task publisher only publishes a specific task.

In the present invention, each task issuer prefers workers with high quality level, so all task issuers have the same preference list (sorted according to the quality level of workers).

In the present invention, if a worker is unwilling to do some tasks, he can insert an empty task in his preference list, and put all unacceptable tasks behind the empty task.

The invention utilizes a stable matching algorithm, fully considers the preferences of workers and task publishers in the swarm intelligence system, the budget limit and quality requirements of tasks, and the quality level of workers, and realizes stable task allocation in the swarm intelligence system.

Description of drawings

The flowchart of Fig. 1 embodiment of the present invention;

The REDA algorithm flowchart of Fig. 2 embodiment of the present invention;

The TAQR algorithm of the embodiment of the present invention of Fig. 3 and benchmark algorithm success rate comparison experiment result figure, wherein (a) M=8 (b) N=50;

The TAQR algorithm of the embodiment of the present invention and the worker's satisfaction comparison experiment result figure of benchmark algorithm of Fig. 4, wherein (a) M=12 (b) N=40;

Fig. 5 is a comparison experiment result diagram of the time complexity between the TAQR algorithm of the embodiment of the present invention and the benchmark algorithm, where (a) M=4, (b) N=40.

detailed description

In order to facilitate those of ordinary skill in the art to understand and implement the present invention, the present invention will be described in further detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the implementation examples described here are only used to illustrate and explain the present invention, and are not intended to limit this invention.

The goal of the present invention is to achieve a stable allocation of tasks in the crowd intelligence platform, taking into account the preferences of workers and task publishers, the budget constraints and quality requirements of tasks, and the quality level of workers. In order to solve this problem, the present invention regards the task allocation problem of the swarm intelligence platform as a many-to-one matching problem with a strict upper boundary requirement (budget restriction) and a loose lower boundary requirement (quality requirement), proposes a corresponding algorithm and proves the algorithm The distribution results are stable and efficient.

First make the following definitions:

Definition 1: (task allocation) The task allocation μ of the Swarm Intelligence platform is a mapping S∪τ→2 ^S ∪τ that satisfies the following five conditions:

1) For all workers s∈S, there is μ(s)∈τ;

2) For all task issuers t∈τ, there is μ(t)∈S;

3) For any s∈S and t∈τ, when s∈μ(t), there is μ(s)=t, where μ(t) refers to the set of workers matched to task t;

4) Strict lower bound (budget constraint): ∑ _s∈μ(t) r _s ≤ b _t for all t∈τ;

5) Under loose upper bound (quality requirement): Α={t:t∈Α,∑ _s∈μ(t) r _s ≥q _t } represents the set of tasks whose quality requirement can be satisfied. Indicates the success rate, |.| indicates the number of elements in the set. When Suc=1, μ is a full task assignment, otherwise it is a partial task assignment.

This model is a crowd intelligence platform that includes quality requirements and relies on joint efforts. Most of the many-to-one matching models in the literature do not consider the lower limit constraints like the model in the present invention. The many-to-one matching models considering the lower bound constraints all assume that the quality level of each worker is the same, that is, r _s =1. In this simplified model, if and only if the total quality level of workers is greater than the quality level required by the task ∑ _s∈S r _s ≥∑ _t∈τ q _t will achieve complete task allocation. However, when the quality levels of workers are different, ∑ _s∈S r _s ≥∑ _t∈τ q _t , it can no longer meet the quality requirements of each task. For example, if the quality level ratio of two workers is 0.3:0.7, and the quality requirement ratio of two tasks is 0.4:0.5, although there is 0.3+0.7>0.4+0.5, there is no task allocation method that can satisfy both The quality requirements of the task. Verifying that there is a complete assignment of tasks is equivalent to checking whether the following linear programming problem has a feasible solution.

Wherein, when μ(s)=t, x _s,t =1, otherwise x _s,t =0.

In fact, the present invention only focuses on whether the objective function has a feasible solution, which is an NP-hard problem. Therefore, the present invention can only improve the success rate of task assignment as much as possible.

An allocation is stable if no worker or task issuer has a better choice than the assignment, since both workers and task issuers will discard the assignment if they have a better choice. On the swarm intelligence platform where workers freely choose tasks and task publishers freely recruit workers, task allocation can only be achieved if the allocation results are stable. Stable task allocation is characterized by individual rationality, fairness, and non-wastefulness.

Definition 2: (individual rationality) When the allocation μ satisfies the following conditions, the allocation is individual rationality.

1) Each worker is willing to be assigned to the current task instead of being unassigned, ie

2) Each task issuer prefers the currently assigned set of workers over a subset of that set, i.e.

Individual rationality is the minimum requirement for task assignment. In order to define fairness, the concept of a Type I blocking pair is first introduced.

Definition 3: (Type I blocking pair) if there is a task publisher t, worker s and non-empty subset And when the following conditions are met, worker s and task t form a type I blocking pair.

1) Task issuer t prefers worker s to workers in set A, and worker s also prefers task t to his current assigned task.

2) Worker s can replace workers in subset A without violating the budget constraint of task t.

3) The departure of worker s will not affect the quality requirements of the task μ(s) he is currently assigned.

Mathematically, that is, when there is a task issuer t, a worker s and a non-empty subset And when the following conditions are met, worker and task t can form a type I blocking pair. The specific conditions are as follows:

1) t _s μ(s), and r(s)≥∑ _s'∈Α r _s'

2)r _s +∑ _{s'∈μ(t)\Α} r _s' ≤b _t

3)∑ _{s'∈μ(u(s))} r _s' -r _s ≥q _t

Type I blocking pairs can lead to allocation instability, as workers consider replacing their current assigned task with a preferred task.

Definition 4: (Fairness) The task assignment μ is fair only when there are no Type I blocking pairs.

Definition 5: (Type II blocking pair) When certain conditions are met, worker s and task t form a type II blocking pair (s, t). The specific conditions are as follows:

1) Worker s prefers task t to his current assigned task;

2) Adding worker s to task t will not exceed t's budget limit.

3) If the worker s leaves, it will not affect the total quality level requirement of the currently assigned task μ(s).

Mathematically, in an assignment, a worker s and a task t form a Type II blocking pair if certain conditions are met. The specific conditions are as follows:

1)t _s μ(s)

2) r _s +∑ _s'∈μ(t) r _s' ≤b _t

3)∑ _{s'∈μ(u(s))} r _s' -r _s ≥q _t

Type II blocking pairs lead to unstable assignments because the task issuer has enough budget to recruit all the workers who want to do the task.

Definition 6: (Wasteless) Task allocation μ is wasteless only when there are no type II blocking pairs.

The proposed algorithm is implemented based on a traditional stable matching algorithm - Delayed Acceptance Algorithm (DA) - which can achieve stable matching results in the classic many-to-one matching problem. However, this traditional algorithm has two drawbacks. First, the workers in the swarm intelligence system are heterogeneous, which is manifested in the different compensation and technical level of the workers, so the task assignment results generated by the DA algorithm are unstable. Second, the DA algorithm does not consider the lower bound of quality requirements, and the distribution results make the success rate of task completion low. The distributed algorithm proposed by the invention can generate a stable task allocation that strictly meets budget constraints and improves the success rate of tasks with quality requirements.

In the present invention, a worker is limited to accept only one task, but each task can be assigned to multiple workers. In the present invention, it is assumed that the quality level of each worker for the same task is constant and all participants (including workers and task publishers) on the swarm intelligence system know all preference lists, and the preference lists are fixed.

Please see Fig. 1, the task distribution method based on stable matching algorithm in a kind of crowd intelligence system provided by the present invention, comprises the following steps:

Step 1: Get the quality level {r _s } _s∈S of each worker s and its preference list {＞ _s } _S , where S is the set of all workers; get the preference list {＞ _t } _τ , quality of each task t Requirements {q _t } t ∈ _τ and budget constraints {b _t } t ∈ _τ , where τ is the set of all tasks;

Step 2: According to the preference list {> _s } _S of worker s, write the preference order of s into the application list p(s) of s;

Step 3: Determine whether the application list p(s) of worker s is empty;

If yes, perform step 4 below;

If not, end this process;

Step 4: Take the first task t in the application list p(s), and remove t from p(s);

Step 5: Determine whether the total quality level of the workers currently assigned to task t is less than the quality requirements of task t;

If yes, then perform the following step 6;

If not, then perform the following step 7;

Step 6: Execute the REDA algorithm;

Step 7: Calculate the difference △Q of all tasks that have not met the quality requirements and the total quality level △R of all unassigned workers;

Step 8: Judging the size of △ _Rrs and △Q;

If △ _Rrs is greater than the difference △Q, execute the REDA algorithm;

If △ _Rrs is less than the difference △Q, go to step 9

Step 9: Worker s cannot be assigned to task t, take the next worker information as worker s, and execute the above step 3;

See also Fig. 2, the REDA algorithm that present embodiment adopts, comprises the following steps:

Step 6.1: Obtain worker s and task t information, worker s∈S, task t∈τ;

Step 6.2: Determine whether the remaining budget of the task is greater than the worker's compensation;

If so, assign worker s to task t, then take the next worker information as worker s, and execute step 3 in reverse;

If not, perform the following step 6.3;

Step 6.3: Find out the worker set A whose quality level is lower than worker s among the workers currently assigned to task t;

Step 6.4: Determine whether there is a sub-set B of workers whose total quality level is less than the minimum quality level of worker s in set A;

If yes, select the set B _min with the smallest total quality level of workers in all sets that meet step 6.4, cancel the assignment relationship between task t and all workers in set B _min , assign worker s to task t, and then take the next worker information as Worker s, and turn around to execute the step 3;

If not, then worker s cannot be assigned to task t, take the next worker information as worker s, and go back to step 3.

Analyze the distribution results of the algorithm. The following theorem can be proved.

Theorem 1: The event complexity of the proposed task allocation algorithm is O(|S||τ|d), where d refers to the running time of finding β _min in the REDA algorithm.

Theorem 2: (Individual Rationality) The task allocation of the algorithm has individual rationality.

Theorem 3: (No waste) The distribution result of the algorithm has no waste.

Theorem 4: (Fairness) The proposed task allocation algorithm is fair.

Theorem 5: (Stability) The proposed task assignment algorithm is stable.

Give an example to describe the specific process of this algorithm, and analyze the results. As shown in Table 1 below, there are 6 workers and their corresponding preference lists and quality levels, 2 tasks and their corresponding budget constraints and quality requirements. Obviously all task issuers' preference lists would be s _5t s _2t s _6t s _3t s _4t s ₁ .

Table 1

The operation process of the task allocation algorithm is as follows:

Round 1: Worker s ₁ applies for task t ₁ : the quality requirements of t ₁ are not met and the budget is sufficient. Assign s ₁ to t ₁ , then μ(s ₁ )=t ₁ , μ(t ₁ )=s ₁ .

The second round: worker s ₂ applies for task t ₂ : the quality requirements of t ₂ are not met and the budget funds are sufficient. Assign s ₂ to t ₂ , then μ(s ₂ )=t ₂ , μ(t ₂ )=s ₂ .

Round 3: Worker s ₃ applies for task t ₂ : the quality requirements of t ₂ are not met and the budget is sufficient. Assign s ₃ to t ₂ , then μ(s ₃ )=t ₂ , μ(t ₂ )={s ₂ ,s ₃ }.

Fourth round: worker s ₄ applies for task t ₂ : the quality requirements of t ₂ are not met and the budget is sufficient. Assign s ₄ to t ₂ , then μ(s ₄ )=t ₂ , μ(t ₂ )={s ₂ ,s ₃ ,s ₄ }.

The fifth round: worker s ₅ applies for task t ₂ : the quality requirements of t ₂ are not met, but the budget funds are not enough to pay s ₅ , the set of workers with lower priority than s ₅ Α={s ₂ ,s ₃ ,s ₄ }, in Α, there are two sets whose quality level of workers is less than s ₅ and can spare enough budget for s ₅ , namely {s ₂ } and {s ₃ ,s ₄ }. Since the total mass level of {s ₃ , s ₄ } is less than {s ₂ }, then β _min = {s ₃ , s ₄ }, remove β _min from the matching set of task t ₂ , assign s ₅ to t ₂ , that is, μ(s ₅ )=t ₂ , μ(t ₂ )={s ₂ ,s ₅ }.

Round 6: Worker s ₆ applies for task t ₂ : t ₂ has sufficient budget, but its quality requirements have been met. After judgment, assigning worker s ₆ to task t ₂ will cause the quality requirements of other tasks to not be met. So s ₆ is rejected by t ₂ .

Round 7: Worker s ₃ applies for task t ₁ : the quality requirements of t ₁ are not met and the budget is sufficient. Assign s ₃ to t ₁ , then μ(s ₃ )=t ₁ , μ(t ₁ )={s ₁ ,s ₃ }.

Eighth round: worker s ₄ applies for task t ₁ : the quality requirements of t ₁ are not met and the budget is sufficient. Assign s ₄ to t ₁ , then μ(s ₄ )=t ₁ , μ(t ₁ )={s ₁ ,s ₃ ,s ₄ }.

Ninth round: worker s ₅ applies for task t ₁ : the quality requirements of t ₁ are not met and the budget is sufficient. Assign s ₅ to t ₁ , then μ(s ₅ )=t ₁ , μ(t ₁ )={s ₁ , s ₃ , s ₄ , s ₅ }.

The final task allocation result is μ(t ₁ )={s ₁ , s ₃ , s ₄ , s ₅ }, μ(t ₂ )={s ₂ ,s ₅ }.

Here, the performance of the proposed algorithm is evaluated, and the task allocation algorithm proposed by the present invention is referred to as the TAQR algorithm, and the benchmark for comparison is the Anchor algorithm. Each simulation experiment was run 500 times to eliminate system randomness.

Experiment 1: Verify the success rate of task completion

Simulation experiments show that TAQR has a higher task completion rate than Anchor. The prerequisite for the success of a task is that the total quality level of workers is higher than the quality requirements of the task. The success rate is the ratio of successfully completed tasks to the total tasks. q, b, r are numbers randomly selected from [3,5], [6,10], [1,2] respectively. Figure 3(a) is the curve of task completion success rate changing with the number of workers, which shows that the success rate of TAQR is 16% higher than that of Anchor. Figure 3(b) is a curve of the success rate of task completion as a function of the number of tasks, and the success rate difference between TAQR and Anchor is close to 18%.

Experiment 2: Comparison of Worker Satisfaction

Simulation experiments show that TAQR has higher performance than Anchor in terms of worker satisfaction. Worker satisfaction is defined as the percentage rank of its matching tasks in its preference list. q, b, r are numbers randomly drawn from [3,5], [6,10], [1,4] respectively. Figure 4(a) is the curve of worker satisfaction changing with the number of workers, and the TAQR algorithm is about 5% higher than Anchor's worker satisfaction. Figure 4(b) is the curve of worker satisfaction changing with the number of tasks, and the worker satisfaction of TAQR algorithm is 6% greater than that of Anchor.

Experiment 3: Running Time

Figure 5 shows that the time complexity of Anchor is lower than that of TAQR algorithm, no matter with the increase of the number of workers or the number of tasks. q, b, r are numbers randomly drawn from [0.8,1.5], [1.4,2], [0,1] respectively. Combining Figures 3 and 4, TAQR improves the performance (task completion rate and worker satisfaction) of the crowd intelligence system by increasing the running time (within a reasonable range).

It should be understood that the parts not described in detail in this specification belong to the prior art.

It should be understood that the above-mentioned descriptions for the preferred embodiments are relatively detailed, and should not therefore be considered as limiting the scope of the patent protection of the present invention. Within the scope of protection, replacements or modifications can also be made, all of which fall within the protection scope of the present invention, and the scope of protection of the present invention should be based on the appended claims.

Claims (3)

1. A task assignment method based on a stable matching algorithm in a crowd intelligence system, assuming that each task issuer of the crowd intelligence system only publishes one task; it is characterized in that, comprising the following steps: Step 1: Get the quality level {r _s } _{s ∈ S} and its preference list {＞ _s } _s for each worker s, where S is the set of all workers; get the preference list {＞ _t } _τ , quality of each task t Requirements {q _t } t ∈ _τ and budget constraints {b _t } t ∈ _τ , where τ is the set of all tasks; Step 2: According to the preference list {> _s } _S of worker s, write the preference order of s into the application list p(s) of s; Step 3: Determine whether the application list p(s) of worker s is empty; If yes, perform step 4 below; If not, end this process; Step 4: Take the first task t in the application list p(s), and remove t from p(s); Step 5: Determine whether the total quality level of the workers currently assigned to task t is less than the quality requirements of task t; If yes, then perform the following step 6; If not, then perform the following step 7; Step 6: Execute the REDA algorithm; Step 7: Calculate the difference △Q of all tasks that have not met the quality requirements and the total quality level △R of all unassigned workers; Step 8: Judging the size of △ _Rrs and △Q; If △ _Rrs is greater than the difference △Q, execute the REDA algorithm; If △ _Rrs is less than the difference △Q, go to step 9; Step 9: Worker s cannot be assigned to task t, take the next worker information as worker s, and execute the above step 3; Described REDA algorithm comprises the following steps: Step 6.1: Obtain worker s and task t information, worker s∈S, task t∈τ; Step 6.2: Determine whether the remaining budget of the task is greater than the worker's compensation; If so, assign worker s to task t, then take the next worker information as worker s, and execute step 3 in reverse; If not, perform the following step 6.3; Step 6.3: Find out the worker set A whose quality level is lower than worker s among the workers currently assigned to task t; Step 6.4: Determine whether there is a sub-set B of workers whose total quality level is less than the quality level of workers s in set A; If yes, select the set B _min with the smallest total quality level of workers in all sets that meet step 6.4, cancel the assignment relationship between task t and all workers in set B _min , assign worker s to task t, and then take the next worker information as Worker s, and turn around to execute the step 3; If not, then worker s cannot be assigned to task t, take the next worker information as worker s, and go back to step 3. 2. the task distribution method based on stable matching algorithm in the swarm intelligence system according to claim 1, is characterized in that: if each task issuer in the swarm intelligence system needs to issue multiple tasks, then the task issuer is regarded as multiple tasks. A virtual task publisher, a virtual task publisher only publishes a specific task. 3. The task assignment method based on stable matching algorithm in the crowd intelligence system according to claim 1, characterized in that: the preference lists of all task publishers are the same.