Research On Coalition Formation Algorithms In Fractional Hedonic Games

With the development of artificial intelligence and distributed systems,multi-agent systems have gradually become a popular research area which can be applied to the fields of social network analysis,intelligent robots and data mining.In multi-agent systems,agents can interact,coordinate and cooperate with each other.Agents cooperating with each other form a coalition.The problem of coalition formation,a basic problem in multi-agent systems,studies cooperation and coalitions among agents.Nowadays,there have been a large number of research results in the field of coalition formation.Most of the research focuses on stable coalition structures.For example,some research has explored the complexity of forming core stable or Nash stable coalition structures and corresponding coalition formation algorithms.The research results on the problem of social welfare maximization are relatively few.The social welfare maximization problem aims to generate a coalition structure with the largest sum of value of all coalitions.Coalition formation generally uses game theory models in the field of game theory to specify the value of a coalition.Fractional Hedonic game has been extensively studied in the field of game theory after it was proposed in 2014.It defines the welfare of an agent in a coalition and the welfare of an agent in a coalition is its average preference value to all other members in this coalition.The value of a coalition is the sum of the welfare of members in the coalition.The fractional hedonic game is also a special game that can be represented by graphs.Nodes in the graph are regarded as agents and edges are regarded as preference values.It depicts the relationship between the welfare of agents and the topology of graphs.This thesis studies the social welfare maximization problem based on fractional hedonic games.However,there are only a handful of related researches and the existing algorithms have disadvantages that the social welfare of generated coalition structure is low or not in line with the reality or the complexity of these algorithms is too high.They need to be improved and optimized.Therefore,the thesis proposes three coalition formation algorithms for social welfare maximization based on the fractional hedonic games where optimality of algorithms has been theoretically proved on classic regular graphs and their superiority also has been experimentally verified.This research not only has theoretical significance in the field of coalition formation but also has application value in the field of social network analysis including network clustering and community detection.The content of this thesis is mainly divided in the following four aspects:(1)This thesis proposes a coalition formation mechanism,with which two coalition formation algorithms are proposed according to two different welfare distribution methods.First,this thesis proposes a coalition formation mechanism based on multi-agent systems.Each self-interested agent interacts with each other and chooses whether to join other coalitions according to the payoff.According to different distribution methods in coalition formation,two coalition formation algorithms are proposed.One is the coalition formation with fractional hedonic game-based welfare distribution(CFFHG)algorithm.However,with this mechanism,CFFHG has certain defects.In response to this shortcoming,this thesis adopts the Shapley value as a welfare distribution method,and proposes a coalition formation with Shapley value-based welfare distribution algorithm(CFSV).(2)Aiming at solving the high complexity of calculating the Shapley value,this thesis uses an approximation algorithm to effectively calculate Shapley value which forms coalition formation with the approximate Shapley value-based welfare distribution.In the normal process of calculating the Shapley value,the complexity of calculation is extremely high because it considers the marginal contribution in each permutation of all the agents in the coalition.Using the approximate algorithm,coalitions can be formed and coalition structures can be generated on large-scale networks.Therefore,the algorithm proposed in this thesis can be evaluated on larger networks.(3)This thesis proves that CFFHG algorithm and CFSV algorithm can generate a socially optimal coalition structure in fractional hedonic games.Although it has been proven that forming a socially optimal coalition structure in fractional hedonic games is an NP-hard problem.This thesis theoretically proves that the optimality of the proposed algorithms on some standard graphs such as complete graphs,star graphs,path graphs,cycles and balanced complete bipartite graphs.(4)This thesis demonstrates the superiority of the proposed algorithm through experimental results.This thesis uses multiple real-world social networks and synthetic networks to evaluate the proposed algorithm.In real-world social networks,the generated coalition structure has certain reference value to reality.In the part of synthetic networks,the ER model and the small-world model are used to generate networks for the evaluation of algorithms.Moreover,several existing coalition formation algorithms in fractional hedonic games are used as comparative algorithms in this thesis.Experimental results show that the social welfare of the coalition structure generated by the proposed algorithm is bigger than benchmark methods.Finally,the thesis has conducted an individual experiment to explore how people will cooperate to form coalitions in real life and compare it with algorithms proposed in thesis.