资源分配是计算科学领域研究的热点问题之一,其应用场景包括计算资源共享、工业生产、边界争端处理等等。在已有的资源分配研究中,研究者通常会根据应用场景的不同而设定不同的资源分配目标,并设计针对性的资源分配方法。例如,在计算资源分配中,研究者会关注如何分配计算资源以高效的完成待处理的计算任务;在边界争端处理中,研究者通常关注如何分配资源以保证分配的公平性。随着民主政治的发展,社会选举已成为现代社会的重要组成部分。与此同时,社会选举也逐渐成为多Agent系统研究领域关注的重要应用场景之一,其中Agent通常用来建模参与选举的选民或候选人。在社会选举中,选举组织者(例如国家政府)通常需要建立多个投票站来方便不同选区的选民进行选举投票。而且,选举组织者还需要部署保护资源(如安保资源),提供选民服务资源(例如用于电子投票服务的计算资源与用于选民服务的工人资源)来保证选举过程的高效有序进行。因为社会选举过程与选举结果具有广泛的关注性与影响性,这使得社会选举中的资源分配拥有更多元化的要求,并为资源分配研究提出了新的挑战。第一,选举组织者需要考虑如何分配保护资源来保证选举过程的安全进行,保证选举结果不被操控。然而,已有的选举保护资源分配研究只关注如何分配给定的有限保护资源。当保护资源不充分时,即使采取最优分配策略也无法保证选举结果不被操控。第二,选举组织者通常需要考虑如何在各个投票站之间公平的分配已有的选民服务资源。这些服务资源往往同时包含不可分割资源与可分割资源,例如在电子投票服务系统中,既有不可分割的CPU资源又有可分割的存储资源。本文主要关注最大化最小公平分配准则,即最大化收益最小Agent(例如投票站)获得的效用。然而,在已有的无货币补偿的最大化最小公平分配问题研究中,研究者往往只关注不可分割的资源的分配。第三,由于不同投票站附近选民数量通常具有多样性,各个投票站应该被赋予不同的资源分配权重,所以选举组织通常需要考虑如何在分配权重存在多样性的Agent之间进行资源的公平分配。但是,已有的无货币补偿的最大化最小公平分配问题通常假设每个Agent拥有相同的分配权重。第四,选举组织者通常还需要考虑如何在分配到每个投票站的服务工人之间进行合理的服务房间(例如投票统计房间)分配,即服务房间岗位资源分配。其中,每个服务房间岗位容量往往具有多样性,而且一个工人只能被分配到房间岗位能力要求不超过其自身能力的房间中去。然而,已有的房间资源分配研究通常假设每个房间具有相同的容量而且每个Agent可以被分配到任意房间。为了更好地实现社会选举中的资源分配,针对上述问题,本文分别提出了相应的资源分配算法,其主要工作与贡献归纳如下:1)针对选举保护资源分配,本文研究如何以最少的保护资源消耗来确保选举结果不被操控。首先证明了寻找资源消耗最少且能够保证选举结果不被操纵的资源分配策略是NP难的。其次,提出了一个整数线性规划表达式来计算最优的分配策略。再次,提出了一个(|C|-1)因子近似算法,其中|C|是选举候选人的数目。实验结果表明该近似算法能够制定出接近最优的分配策略。2)针对选民服务资源分配,本文研究如何对具有分割异质性的资源集合进行最大化最小公平分配。首先提出了一个混合整数线性规划表达式来计算最优的分配策略。由于该问题是NP难的,本文基于增广流思想进一步提出了一个多项式时间的近似算法。实验结果表明该近似算法的平均性能达到最优算法性能的80%以上。3)针对选民服务资源分配,本文在上一部分工作基础上进一步研究如何在分配权重存在多样性的Agent群体中基于最大化最小公平分配准则进行合理的资源分配。本文考虑采用一般化的最大化最小公平分配准则,即最大化最小的分配效用与分配权重比。但是,该分配准则可能导致Agent所获效用之间的严重贫富差距,并使得部分Agent由于缺少资源无法高效完成交付给它的任务。基于上述考虑,本文提出了一种新的分配策略评价指标。该指标正比于Agent群体中最小的分配效用与分配权重比,同时反比于Agent群体的贫富差距。首先,本文提出了一个分支界定算法来计算能够最大化该评价指标的最优分配。其次,由于计算最优分配是NP难的,本文基于爬山搜索思想提出了一个多项式时间的启发式方法。实验结果表明该方法能够制定出接近最优的分配策略。4)针对投票站服务房间(岗位)资源分配,本文研究如何在满足预算约束的情况下将多个Agent合理的分配到容量具有多样性的房间中去。主要关注如何寻找社会福利最大的房间分配。首先证明了寻找社会福利最大的房间分配是NP难的。其次,针对每个房间的容量不超过常数c~*>0的情况,提出了一个(c~*+2)/2+ε(ε>0)因子的多项式时间近似算法。再次,证明了最大化社会福利问题不存在多项式时间的c~*/2因子近似算法除非P=NP。最后,针对单个房间容量不受限制的一般情况,基于局部搜索思想提出了一个启发式方法。实验结果表明该启发式方法能够制定出接近最优的分配策略。综上所述,本文针对社会选举中的资源分配问题,分别从选举保护资源分配、选民服务资源分配与投票站服务房间(岗位)资源分配三个角度进行了系统的研究,并提出了有针对性的资源分配方法,有效的满足了实际应用中的资源分配策略制定需求。