基于序列的分配方式是一个简单且应用广泛的资源分配方式。分配机构需要把一系列不可分割的物品分配给多个代理人,代理人对物品有偏好,分配过程是代理人根据给出的序列依次选择物品且只能选择剩余的物品。该分配方式不具备防策略性,即代理人可以通过谎报自己对物品的偏好来获得更好的效用。因此研究者提出了基于序列的物品分配的操纵问题,研究代理人如何采取策略,给出一个使自己效益达到最大的物品偏好。该问题在只有两个代理人(一个是操控者,一个是非操控者)时是多项式可解的,也被证明了当代理人个数为输入的时候是NP难的。那么对于常数个代理人,哪怕只有三个代理人的时候,该问题的计算复杂性并不清楚,成为了一个重要的公开难题。本文最重要的一项贡献就是解决了这个公开难题,给出了一个算法,该算法在任何常数个代理人时都是多项式运行时间。在算法设计中,我们提出了两个重要的概念:关键问题和不变性。关键问题与原问题有相同的最优解,但是关键问题可以利用贪心算法快速解决。解决原始问题则可以转换成寻找与原始问题具有相同最优解的关键问题。我们定义了问题的支配关系,提供了搜索关键问题的空间,与原始问题有相同最优解的关键问题一定在原始问题支配的问题中。基于关键问题,已经可以大大减少解空间,可以设计一个枚举搜索算法,枚举所有被原始问题支配的问题,通过贪心算法计算每个问题的解,其中最好的一个解为原问题的解。该算法仍然是指数运行时间的。在暴力搜索过程中,有许多重叠的子问题,为了进一步得到多项式算法,我们引入了不变性的概念。这个概念根据序列将问题分为两段,前一段只要保证不变性,后一段则是完全一样的问题,这样就可以对前一段进行最优求解。然后就可以通过动态规划的思想来避免重复的子问题,从而得到多项式时间的算法。除此之外,我们还研究了该问题的近似算法,证明了当操控者汇报真实的物品偏好时最少能拿到价值达到最优解的价值的一半的物品集合,即一个0.5倍的近似算法。同时证明了在采用真实物品偏好这个策略下,这个近似率是紧致的。最后,我们用回溯法实现了暴力搜索算法,用记忆化搜索实现了动态规划算法,用模拟分配实现了近似算法。通过实验证明了,暴力搜索性能最差,被许多极端情况限制,近似算法只有在小规模实例中比较接近最优解,动态规划算法在各种情况下都有不错的表现,是三个算法中综合性能最佳的算法。