Research Of Algorithms Based On Sequential Allocation Problem

Sequential allocation is a simple and widely used resource allocation method.The organization needs to allocate a series of indivisible goods to multiple agents.Agents have preferences profile for goods.The allocation process is that agents select remaining goods according to the given sequence.The allocation method does not have anti-strategy,that is,agents can obtain better utility by lying about their preference sequence for goods.Therefore,the researchers put forward the manipulation problem of goods allocation based on sequence,and study how agents adopt strategies,and give a series of goods preference to maximize their own benefits.The problem is polynomial solvable when there are only two agents(one is the ma-nipulator and the other is the non-manipulator).It is also proved that the problem is NP hard when the number of agents is input.So for constant agents,even if there are only three agents,the computational complexity of this problem is not clear,and it is left as an important open problem.The most important contribution of this paper is to solve this open problem and give an algorithm,which is polynomial running time for any constant agent.In algorithm design,we propose two important concepts: crucial problem and invari-ance.The crucial problem has the same optimal solution as the original problem,but the crucial problem can be solved quickly by greedy algorithm.Solving the original problem can be transformed into finding the same optimal solution as the original problem.We define the dominating relation of the problem and provide the space to search the crucial problem.The crucial problem with the same optimal solution as the original problem must be in the dominating problem of the original problem.Based on the problems,we can greatly reduce the solution space.We can design an enumeration search algorithm to enumerate all the problems dominated by the original problem.We can calculate the solution of each problem through the greedy algorithm,and the best one is the solution of the original problem.The algorithm is still exponential.In the process of violent search,there are many overlapping subproblems.In order to get the polynomial algorithm,we introduce the concept of invariance.In this concept,the sequence assignment problem is divided into two parts.As long as the former part is invariant,the latter part is exactly the same problem,so we can solve the former part optimally.In this way,the idea of dynamic programming can be used to avoid repeated subproblems,and the algorithm of polynomial time can be obtained.In addition,we also study the approximation algorithm of the problem.We prove that when the operator reports the real preference of the goods,he can get at least half of the value of the goods to reach the optimal solution,that is,an approximation algorithm of 0.5times.At the same time,it is proved that the approximation rate is compact under the strategy of real goods preference.At last,we implement the violence search algorithm by backtracking,the dynamic planning algorithm by memory search,and the approximate algorithm by simulation as-signment.Experiments show that the performance of violent search is the worst,lim-ited by many extreme cases,the approximation algorithm is more effective in small-scale cases,and the dynamic programming algorithm has good performance in all kinds of cases,which is the best algorithm among the three algorithms.