×

Forming \(k\) coalitions and facilitating relationships in social networks. (English) Zbl 1451.91155

Summary: In this paper we relax two common assumptions that are made when studying coalition formation. The first is that any number of coalitions can be formed; the second is that any possible coalition can be formed. We study a model of coalition formation where the value depends on a social network and exactly \(k\) coalitions must be formed. Additionally, in this context we present a new problem for an organizer that would like to introduce members of the social network to each other in order to increase the social welfare or to stabilize a coalition structure.
We show that, when the number of coalitions, \(k\), is fixed and there are not many negative edges, it is possible to find the coalition structure that maximizes the social welfare in polynomial time. Furthermore, an organizer can efficiently find the optimal set of edges to add to the network, and we experimentally demonstrate the effectiveness of this approach. In addition, we show that in our setting even when \(k\) is fixed and there are not many negative edges, finding a member of the core is intractable. However, we provide a heuristic for efficiently finding a member of the core that also guarantees a social welfare within a factor of 1/2 of the optimal social welfare. We also show that checking whether a given coalition structure is a member of the core can be done in polynomial time. Finally, we consider the problem faced by an organizer who would like to add edges to the network in order to stabilize a specific coalition structure core: we show that this problem is intractable.

MSC:

91D30 Social networks; opinion dynamics
91A12 Cooperative games
91A80 Applications of game theory

Software:

KronFit
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmadian, S.; Hosseinzadeh, H.; Sanità, L., Stabilizing network bargaining games by blocking players, (International Conference on Integer Programming and Combinatorial Optimization, (2016)), 164-177 · Zbl 1422.91142
[2] Anagnostopoulos, A.; Becchetti, L.; Castillo, C.; Gionis, A.; Leonardi, S., Online team formation in social networks, (Proceedings of the 21st International Conference on World Wide Web, WWW-12, (2012)), 839-848
[3] Aziz, H.; Brandt, F.; Seedig, H. G., Computing desirable partitions in additively separable hedonic games, Artif. Intell., 195, 316-334, (2013) · Zbl 1270.91010
[4] Aziz, H.; Brandt, F.; Harrenstein, P., Fractional hedonic games, (Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS-2014, (2014)), 5-12
[5] Bachrach, Y.; Rosenschein, J. S., Coalitional skill games, (Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS-2008, (2008)), 1023-1030
[6] Bachrach, Y.; Elkind, E.; Meir, R.; Pasechnik, D.; Zuckerman, M.; Rothe, J.; Rosenschein, J. S., The cost of stability in coalitional games, (Algorithmic Game Theory, Lecture Notes in Computer Science, vol. 5814, (2009), Springer), 122-134 · Zbl 1262.91021
[7] Bachrach, Y.; Kohli, P.; Kolmogorov, V.; Zadimoghaddam, M., Optimal coalition structure generation in cooperative graph games, (Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, AAAI-2013, (2013)), 81-87
[8] Brânzei, S.; Larson, K., Coalitional affinity games, (Proceedings of the 8th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS-2009, (2009)), 1319-1320
[9] Brânzei, S.; Larson, K., Social distance games, (Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI-2011, (2011)), 91-96
[10] Chalkiadakis, G.; Elkind, E.; Wooldridge, M., Computational aspects of cooperative game theory, (2011), Morgan-Claypool
[11] Chalkiadakis, G.; Markakis, E.; Jennings, N. R., Coalitional stability in structured environments, (Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, AAMAS-2012, (2012)), 779-786
[12] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to algorithms, (1990), The MIT Press Cambridge, MA · Zbl 1158.68538
[13] De Dreu, C. K.W.; Weingart, L. R., Task versus relationship conflict, team performance, and team member satisfaction: a meta-analysis, J. Appl. Psychol., 88, 4, 741-749, (2003)
[14] de Weerdt, M. M.; Zhang, Y.; Klos, T., Multiagent task allocation in social networks, Auton. Agents Multi-Agent Syst., 25, 1, 46-86, (2012)
[15] Downey, R. G.; Fellows, M. R., Parameterized complexity, (2012), Springer Science & Business Media · Zbl 0914.68076
[16] Downey, R. G.; Estivill-Castro, V.; Fellows, M.; Prieto, E.; Rosamond, F. A., Cutting up is hard to do: the parameterized complexity of k-cut and related problems, Electron. Notes Theor. Comput. Sci., 78, 209-222, (2003) · Zbl 1270.68112
[17] Dunne, P. E.; Kraus, S.; Manisterski, E.; Wooldridge, M., Solving coalitional resource games, Artif. Intell., 174, 1, 20-50, (2010) · Zbl 1185.68752
[18] Elkind, E.; Wooldridge, M., Hedonic coalition nets, (Proceedings of the 8th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS-2009, (2009)), 417-424
[19] Fire, M.; Puzis, R., Organization mining using online social networks, Netw. Spat. Econ., 1-34, (2015)
[20] Rodriguez, M. G.; Leskovec, J.; Schölkopf, B., Structure and dynamics of information pathways in online media, (Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, (2013)), 23-32
[21] Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman · Zbl 0411.68039
[22] Gaston, M. E.; desJardins, M., Agent-organized networks for dynamic team formation, (Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS-2005, (2005)), 230-237
[23] Goldschmidt, O.; Hochbaum, D. S., A polynomial algorithm for the k-cut problem for fixed k, Math. Oper. Res., 19, 1, 24-37, (1994) · Zbl 0809.90125
[24] Hoefer, M.; Vaz, D.; Wagner, L., Hedonic coalition formation in networks, (Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI-2015, (2015)), 929-935
[25] Karp, R. M., Reducibility among combinatorial problems, (1972), Springer · Zbl 1187.90014
[26] Kleinberg, J.; Tardos, É., Balanced outcomes in social exchange networks, (Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, (2008)), 295-304 · Zbl 1231.91120
[27] Könemann, J.; Larson, K.; Steiner, D., Network bargaining: using approximate blocking sets to stabilize unstable instances, Theory Comput. Syst., 57, 3, 655-672, (2015) · Zbl 1327.91019
[28] Leiserson, C. E.; Rivest, R. L.; Stein, C.; Cormen, T. H., Introduction to algorithms, (2001), The MIT Press · Zbl 1047.68161
[29] Leskovec, J.; Chakrabarti, D.; Kleinberg, J.; Faloutsos, C.; Ghahramani, Z., Kronecker graphs: an approach to modeling networks, J. Mach. Learn. Res., 11, 985-1042, (2010) · Zbl 1242.05256
[30] McCormick, S. T.; Rao, M. R.; Rinaldi, G., Easy and difficult objective functions for MAX cut, Math. Program., 94, 2-3, 459-466, (2003) · Zbl 1030.90130
[31] Meir, R.; Rosenschein, J. S.; Malizia, E., Subsidies, stability, and restricted cooperation in coalitional games, (Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI-2011, (2011)), 301-306
[32] Milchtaich, I.; Winter, E., Stability and segregation in group formation, Games Econ. Behav., 38, 2, 318-346, (2002) · Zbl 1013.91010
[33] Rodriguez, M. G.; Balduzzi, D.; Schölkopf, B., Uncovering the temporal dynamics of diffusion networks, (2011), preprint
[34] Saad, W.; Han, Z.; Basar, T.; Debbah, M.; Hjorungnes, A., A selfish approach to coalition formation among unmanned air vehicles in wireless networks, (Proceedings of the 1st International Conference on Game Theory for Networks, GameNets-2009, (2009)), 259-267
[35] Sandholm, T.; Larson, K.; Andersson, M.; Shehory, O.; Tohmé, F., Coalition structure generation with worst case guarantees, Artif. Intell., 111, 1-2, 209-238, (1999) · Zbl 0997.91004
[36] Sless, L.; Hazon, N.; Kraus, S.; Wooldridge, M., Forming coalitions and facilitating relationships for completing tasks in social networks, (Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS-2014, (2014)), 261-268
[37] Stanton, I.; Kliot, G., Streaming graph partitioning for large distributed graphs, (Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2012), ACM), 1222-1230
[38] Sung, S. C.; Dimitrov, D., On core membership testing for hedonic coalition formation games, Oper. Res. Lett., 35, 2, 155-158, (2007) · Zbl 1303.91035
[39] Voice, T.; Polukarov, M.; Jennings, N. R., Coalition structure generation over graphs, J. Artif. Intell. Res., 45, 1, 165-196, (2012) · Zbl 1253.68183
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.