Visible to the public Maximizing Social Welfare in Fractional Hedonic Games using Shapley Value

TitleMaximizing Social Welfare in Fractional Hedonic Games using Shapley Value
Publication TypeConference Paper
Year of Publication2019
AuthorsChen, Siyuan, Liu, Wei, Liu, Jiamou, Soo, Khí-Uí, Chen, Wu
Conference Name2019 IEEE International Conference on Agents (ICA)
Date Publishedoct
Keywords3G mobile communication, 5G mobile communication, agent-based methods, Approximation algorithms, Benchmark testing, CFSV, coalition formation, coalition generation problem, decision rules, fractional hedonic games, game theory, Games, graph theory, human factors, multi-agent systems, optimal coalition structure, player payoffs, pubcrawl, Scalability, Shapley value, Shapley value-based welfare distribution scheme, Social Agents, Social network services, social sciences, social welfare, Stability analysis
AbstractFractional hedonic games (FHGs) are extensively studied in game theory and explain the formation of coalitions among individuals in a group. This paper investigates the coalition generation problem, namely, finding a coalition structure whose social welfare, i.e., the sum of the players' payoffs, is maximized. We focus on agent-based methods which set the decision rules for each player in the game. Through repeated interactions the players arrive at a coalition structure. In particular, we propose CFSV, namely, coalition formation with Shapley value-based welfare distribution scheme. To evaluate CFSV, we theoretically demonstrate that this algorithm achieves optimal coalition structure over certain standard graph classes and empirically compare the algorithm against other existing benchmarks on real-world and synthetic graphs. The results show that CFSV is able to achieve superior performance.
Citation Keychen_maximizing_2019