The Application And Practice Of Auction Mechanism In Task Allocation

Task allocation is a common problem in production and our daily lives.From arranging the tasks for employees to the implementation of complex large projects,task allocation plays a very important role.In task allocation problem,the efficiency of allocation,resource utilization rate and the benefits of participants are all important factors in evaluating a task allocation mechanism.A reasonable task allocation mechanism can not only improve the efficiency of allocation,but also guarantee the fairness of the distribution.What's more,it can maximize the social welfare of the allocation.When the requirements of the task become more detailed and specific,how to express it accurately and simplistically?When there are several constraints among the tasks,how can we find out the priority of these tasks?How can we guarantee the final target can be reached if the tasks have time constraints?These problems have greatly increased the complexity of the task allocation.Faced with these issues,the main work and contribution of this article is as follows:1.A task allocation method based on auction theory has been proposed.In this article,we take the task as an exclusive,valuable resource(commodity)in auction.Participates in the auction are targets which resource are distributed.Facing different types of task allocations,we adopt appropriate auction mechanisms.2.The second price auction mechanism in task allocation is designed.In normal task allocation problems,we propose a general distribution method and try to adopt an auction model to solve the task allocation problem.We take the bidder with lowest price as the winner for each task while he only pays the second lowest price.In this article,it has been proved that the mechanism has individual rationality,budget balance,and authenticity.Also,the computational efficiency is given out.Through experiments,it proves that this mechanism can effectively improve social welfare.3.Greedy double auction mechanism for job allocation is designed.Job allocation is a special form of task allocation.We take the job as a special resource,using the greedy mechanism quickly find out how to assign the jobs.We compare it with the time priority auction mechanism.It proves that the mechanism has individual rationality,budget balance and authenticity.Also,we give out the time complexity of corresponding algorithm.4.The collaborative planning for time-constrained multi-task auction is proposed.In this mechanism,the order of tasks is often provided.The auctioneer has a clear set of inputs and a set of outputs.The bidder can freely combine any commodity element and bid for it while each bid has strict time constraints.We use a mixed multi-unit auction mechanism to assign tasks and get solutions.A solution can not only meet the final goal,but also guarantee that there is no shortage of commodity during the execution of the task.Among the solutions,we can find optimal solutions that maximize auctioneer's revenue or minimize completion time.