Resouce Allocation In Social Elections

Resource allocation is one of the hot issues in computing science.The application scenarios of resource allocation include computation resource sharing,border dispute resolution and so on.In the existing work on resource allocation,researchers usually set different allocation objectives according to different application scenarios and design pointed allocation methods.For example,in the allocation of computing resources,researchers usually focus on how to allocate the resources to efficiently execute tasks;in border dispute resolution,researchers usually focus on how to allocate the resources to guarantee fairness.With the development of democratic politics,democratic elections have become an important part of modern society.Meanwhile,democratic elections have also become one of the important application scenarios that the research field of multiagent system focuses on,where the agents are usually used to model the voters or candidates.In a social election,the election organizer(e.g.,the government)usually needs to establish many polling stations to serve the voters in different electoral districts.Moreover,the election organizer usually needs to deploy protection resources(e.g.,security resources)and provide voter service resources(e.g.,computing resources for electronic vote service and worker resources for voter services)to ensure the security and efficiency of election process.Because the processes and results of social elections have extensive concern and influence,this makes the resource allocation in social elections have more diverse demands and raises new challenges for the research of resource allocation.First,the election organizer needs to consider how to allocate protection resources to ensure the security of election process and protect election outcome from control.However,the existing work on the allocation of protection resources only focuses on how to allocate the given protection resources.However,if protection resources are not sufficient,the election outcome still may be successfully controlled even if the organizer adopts the optimal allocation strategy.Second,the election organizer usually needs to consider how to fairly allocate the voter service resources among different polling stations.The service resources usually include both indivisible resources and divisible resources.For example,in an electronic vote service system,there are both the indivisible CPU resources and the divisible storage resource.This dissertation mainly focuses on max-min fairness,i.e.,maximizing the utility of the minimum utility of any agent(e.g.,polling station).However,when money transfer is forbidden,the existing work on max-min fair allocation only focuses on the fair allocation of indivisible resources.Third,because the vicinities of different polling stations usually have different amounts of voters,we should assign different allocation entitlements to different polling stations.Then,the election organizer usually needs to consider how to allocate resources among the agents who have different entitlements fairly.Nevertheless,when money transfer is forbidden,the existing work on max-min fair allocation usually assumes that each agent has the same allocation entitlement.Fourth,the election organizer also needs to consider how to allocate the workers in each polling station to service rooms(e.g.,vote-counting rooms),i.e.,allocating the posts of service rooms.Moreover,the post capacity of each service room usually has diversity and a worker can only be allocated to the rooms whose ability requirements of the posts are not beyond its ability.However,the existing work on room allocation usually assumes that each room has the same capacity and each agent can be allocated to any room.To achieve better resource allocation in social elections,aiming at the above problems,this dissertation respectively proposes the corresponding resource allocation algorithms.The main work and contributions are summarized as follows.1)For the allocation of election protection resources,this dissertation investigates how to protect election outcome from control using minimal protection resources.First,we show that finding a minimal resource-consumption strategy that can protect the election outcome from control is NP-hard.Second,we present an integer linear programming formulation to compute the optimal allocation strategy.Third,we propose a(|C|-1)-factor approximation algorithm for the problem,where|C|is the number of candidates.Experimental results show that the proposed approximation algorithm produces near-optimal solutions.2)For the allocation of voter service resources,this dissertation investigates how to allocate the resource set which consists of both indivisible resources and divisible resources based on max-min fairness.First,this dissertation presents an integer linear programming formulation to compute the optimal allocation strategy.Because the problem is NP-hard, this dissertation further proposes an approximation algorithm based on the augmented flow idea.Experimental results show that the average performance of the proposed approximation algorithm reaches above 80%of the performance of the optimal algorithm.3)For the allocation of voter service resources,this dissertation further investigates how to allocate resources among the agents who have different entitlements based on max-min fairness.This dissertation considers adopting the generalized max-min fairness criterion,i.e.,maximizing the minimum utility entitlement ratio,to allocate the resources.The utility entitlement ratio of an agent is the ratio between the utility of the acquired resources of the agent and its entitlement value.Nevertheless,the generalized max-min fairness may lead to a serious wealth gap,which usually makes some agents unable to finish their tasks efficiently due to the lack of resources.Based on the above consideration,this dissertation proposes an evaluation indicator of allocation that is positively related to the minimum utility entitlement ratio of the agents and that is inversely related to the wealth gap.First,this dissertation proposes a branch and bound algorithm to compute the optimal allocation that maximizes the evaluation indicator.Second,because finding the optimal allocation is NP-hard,we propose a heuristic algorithm based on hill-climbing search.Experimental results show that the heuristic algorithm produces near-optimal solutions.4)For the allocation of service room resources(posts)of a polling station,this dissertation investigates how to allocate agents to rooms with diverse capacities under the budget constraints.This dissertation mainly focuses on how to find a room allocation that maximizes the social welfare.First,this dissertation shows that finding a room allocation that maximizes the social welfare is NP-hard.Second,this dissertation presents a polynomial-time(c~*+2)/2+ε-factor approximation algorithm(withε>0)for the case where the capacity of each room is not larger than a constant c~*>0.Third,this dissertation demonstrates that there is no polynomial-time c~*/2-factor approximation algorithm for the social welfare maximization problem unless P=NP.Finally,this dissertation proposes a heuristic algorithm based on local search for the general case where the capacity of each room is not bounded by a constant.Experimental results show that the proposed algorithm produces near-optimal solutions.Overall,this dissertation mainly investigates the allocation of election protection resources,the allocation of voter service resources and the allocation of service room resources(posts)of a polling station in social elections and proposes the pointed methods of resource allocation,which efficiently satisfy the demands of developing resource allocation strategies in real applications.