Modeling the Optimal Coalition Structure Using the Core Solution Concept

Document Type : Original Article

Authors

1 Professor, University of Tehran .

2 Professor, University of Tehran.

3 Ph.D Student, University of Tehran.

Abstract

Coalition formation is an important step towards developing the social welfare by improving the performance. This is pursued in two main research streams: (i) algorithmic approaches to achieve the optimal coalition structure and (ii) cooperative game theory to distribute the coalition payoff based on fairness and stability criteria. The aim of this paper is to integrate the strengths of the two approaches in order to achieve an optimal and stable coalition structure. The main innovation of the paper is using mathematical modeling to incorporates stability condition in a set partitioning problem through core solution concept to overcome decentralized procedures of coalition formation and payoff distribution. A numerical example is used to investigate the performance of overlapping and non-overlapping optimal coalition structure models. The results show that cooperation leads to improve social welfare. This improvement has an ascending trend with a decreasing slope and does not change after increasing the upper limit of players allowed to join the coalition to the certain extent. This is due to several reasons which prevent players to form grand coalition and suggests that, to form large coalitions, one should compare achieved gains with the managerial complexities and the increased costs of coordination and communication between players.

Keywords

References

  1. Alberola, J. M., Del Val, E., Costa, A., Novais, P., & Julian, V. (2018). A genetic algorithm for group formation in elderly communities. AI Communications, 31(5), 409–425.
  2. Amoozad Mahdiraji, H., Jafarnezhad, A., Mohaghar, A., Moddares Yazdi, M. (2013). Coalition or independence? Determining the appropriate decision for different levels of three- tier supply chain. Journal of Industrial Management Perspective, 3(9), 9-34. (In Persian)
  3. Ansink, E., Weikard, H. P., & Withagen, C. (2019). International environmental agreements with support. Journal of Environmental Economics and Management, 97, 241–252.
  4. Aumann, R. J., & Dreze, J. H. (1974). Cooperative games with coalition structures. International Journal of Game Theory, 3(4), 217–237.
  5. Aumann, R. J., & Myerson, R. B. (2003). Endogenous formation of links between players and of coalitions: An application of the Shapley value. In Networks and Groups, Springer, 207-220.
  6. Aziz, H., & De Keijzer, B. (2011). Complexity of coalition structure generation. In 10th International Conference on Autonomous Agents and Multiagent Systems, 1, 191–197.
  7. Bartholdi, J., & Kemahlioglu-Ziya, E. (2005). Using Shapley value to allocate savings in a supply chain. In Supply chain optimization, Springer, 169-208.
  8. Bitar, E. Y., Baeyens, E., Khargonekar, P., Poolla, K., & Varaiya, P. (2012). Optimal sharing of quantity risk for a coalition of wind power producers facing nodal prices. IEEE American Control Conference, 4438–4445.
  9. Björklund, A., Husfeldt, T., Koivisto, M., Lin, F., Xu, L., & Zhang, P. (2009). Set partitioning via inclusion- exclusion. SIAM Journal on Computing, 39(2), 546–563.
  10. Chalkiadakis, G., & Boutilier, C. (2012). Sequentially optimal repeated coalition formation under uncertainty, Autonomous Agents and Multi-Agent Systems, 24(3), 441–484.
  11. Chalkiadakis, G., Elkind, E., Markakis, E., Polukarov, M., & Jennings, N. R. (2010). Cooperative games with overlapping coalitions. Journal of Artificial Intelligence Research, 39, 179–216.
  12. Chalkiadakis, G., Elkind, E., & Wooldridge, M. (2011). Computational aspects of cooperative game theory. Synthesis Lectures on Artificial Intelligence and Machine Learning, 5(6), 1–168.
  13. Chalkiadakis, G., Greco, G., & Markakis, E. (2016). Characteristic function games with restricted agent interactions: Core-stability and coalition structures. Artificial Intelligence, 232, 76–113.
  14. Cruz, F., Espinosa, A., Moure, J. C., Cerquides, J., Rodriguez-Aguilar, J. A., Svensson, K., & Ramchurn, S. D. (2017). Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems. Concurrency and Computation: Practice and Experience, 29(5), e3969.
  15. Dang, V. D., & Jennings, N. R. (2006). Coalition structure generation in task-based settings. In Proceedings of 17th European Conference on Artificial Intelligence, 141, 210–214.
  16. Dicheva, D., & Dochev, D. (2010). Artificial intelligence: methodology, systems, and applications. Springer.
  17. Di Mauro, N., Basile, T. M., Ferilli, S., & Esposito, F. (2010). Coalition structure generation with GRASP. In International Conference on Artificial Intelligence: Methodology, Systems, and Applications, 111–120.
  18. Drechsel, J., & Kimms, A. (2010). Computing core allocations in cooperative games with an application to cooperative procurement. International Journal of Production Economics, 128(1), 310–321.
  19. Elkind, E., Rahwan, T., Jennings, N. R. (2013). Computational coalition formation. Multiagent systems. MIT press, 329–380.
  20. Farinelli, A., Bicego, M., Bistaffa, F., & Ramchurn, S. D. (2017). A hierarchical clustering approach to large- scale near-optimal coalition formation with quality guarantees. Engineering Applications of Artificial Intelligence, 59, 170–185.
  21. Farinelli, A., Bicego, M., Ramchurn, S., & Zucchelli, M. (2013). C-Link: A hierarchical clustering approach to large-scale near-optimal coalition formation. In 23th International Joint Conference on Artificial Intelligence, 106–112.
  22. Frisk, M., Göthe-Lundgren, M., Jörnsten, K., & Rönnqvist, M., (2010). Cost allocation in collaborative forest transportation. European Journal of Operational Research, 205(2), 448–458.
  23. Gamson, W. A. (1964). Experimental studies of coalition formation. Advances in Experimental Social Psychology, 1, 81–110.
  24. Gao, J., Yang, X., & Liu, D. (2017). Uncertain shapley value of coalitional game with application to supply chain alliance. Applied Soft Computing, 56, 551-556.
  25. Guajardo, M., Rönnqvist, M., Flisberg, P., & Frisk, M. (2018). Collaborative transportation with overlapping coalitions. European Journal of Operational Research, 271(1), 238–249.
  26. Han, Z., & Poor, H.V. (2009). Coalition games with cooperative transmission: a cure for the curse of boundary nodes in selfish packet-forwarding wireless networks. IEEE Transactions on Communications, 57(1), 203–213.
  27. Jonnalagadda, A., & Kuppusamy, L. (2018). A cooperative game framework for detecting overlapping communities in social networks. Physica A: Statistical Mechanics and its Applications, 491, 498–515.
  28. Khalilzadeh, J., & Wang, Y. (2018). The economics of attitudes: A different approach to utility functions of players in tourism marketing coalitional networks. Tourism Management, 65, 14–25.
  29. Lamarche-Perrin, R., Demazeau, Y., & Vincent, J. M. (2014). A generic algorithmic framework to solve special versions of the set partitioning problem. In the 26th International Conference on Tools with Artificial Intelligence, 891–897.
  30. Li, C., Sycara, K., & Scheller-Wolf, A. (2010). Combinatorial Coalition Formation for multi-item group-buying with heterogeneous customers. Decision Support Systems, 49(1), 1–13.
  31. Liao, S. S., Zhang, J.D., Lau, R., & Wu, T. (2014). Coalition formation based on marginal contributions and the Markov process. Decision Support Systems, 57, 355–363.
  32. Lozano, S., Moreno, P., Adenso-Díaz, B., & Algaba, E. (2013). Cooperative game theory approach to allocating benefits of horizontal cooperation. European Journal of Operational Research, 229(2), 444–452.
  33. Michalak, T. P., Rahwan, T., Elkind, E., Wooldridge, M., & Jennings, N. R. (2016). A hybrid exact algorithm for complete set partitioning. Artificial Intelligence, 230, 14–50.
  34. Michalak, T. P., Sroka, J., Rahwan, T., Wooldridge, M., McBurney, P., & Jennings, N. R. (2010). A distributed algorithm for anytime coalition structure generation. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, 1, 1007–1014.
  35. Nomoto, K., Sakurai, Y., & Yokoo, M. (2017). Coalition structure generation utilizing graphical representation of partition function games. In Proceedings of the 31th AAAI Conference on Artificial Intelligence.
  36. Rahwan, T., & Jennings, N. R. (2007). An algorithm for distributing coalitional value calculations among cooperating agents. Artificial Intelligence, 171(8–9), 535–567.
  37. Rahwan, T., & Jennings, N. R. (2008). An improved dynamic programming algorithm for coalition structure generation. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, 3, 1417–1420.
  38. Rahwan, T., Michalak, T., & Jennings, N. R. (2011). Minimum search to establish worst-case guarantees in coalition structure generation. In 22th International Joint Conference on Artificial Intelligence, 338–342.
  39. Rahwan, T., Michalak, T. P., Wooldridge, M., & Jennings, N. R. (2012). Anytime coalition structure generation in multi-agent systems with positive or negative externalities. Artificial Intelligence, 186, 95–122.
  40. Rahwan, T., Michalak, T. P., Wooldridge, M., & Jennings, N. R. (2015). Coalition structure generation: A survey. Artificial Intelligence, 229, 139–174.
  41. Rahwan, T., Ramchurn, S. D., Dang, V. D., Giovannucci, A., & Jennings, N. R. (2007). Anytime optimal coalition struture generation. In the Proceeding of 22th National Conference on Artificial Intelligence, 1184–1190.
  42. Rahwan, T., Ramchurn, S. D., Jennings, N. R., & Giovannucci, A. (2009). An anytime algorithm for optimal coalition structure generation. Journal of Artificial Intelligence Research, 34, 521–567.
  43. Ramchurn, S.D., Polukarov, M., Farinelli, A., Truong, C., & Jennings, N.R. (2010). Coalition formation with spatial and temporal constraints. In Proceedings of AAMAS, 1181–1188.
  44. Ramos, G. D., Rial, J. C. B., & Bazzan, A. L. (2013). Self-adapting coalition formation among electric vehicles in smart grids. In the 7th International Conference on Self-Adaptive and Self-Organizing Systems, 11–20.
  45. Ray, D. (2007). A game-theoretic perspective on coalition formation. Oxford University Press.
  46. Sabar, M., Montreuil, B., & Frayret, J. M. (2009). A multi-agent-based approach for personnel scheduling in assembly centers. Engineering Applications of Artificial Intelligence, 22(7), 1080–1088.
  47. Sandholm, T., Larson, K., Andersson, M., Shehory, O., & Tohmé, F. (1999). Coalition structure generation with worst case guarantees. Artificial Intelligence, 111 (1), 209–238.
  48. Schulz, A. S., & Uhan, N. A. (2013). Approximating the least core value and least core of cooperative games with supermodular costs. Discrete Optimization, 10 (2), 163–180.
  49. Sen, S., & Dutta, P. S. (2000). Searching for optimal coalition structures. In Proceedings of the 4th International Conference on Multi Agent Systems, 287–292.
  50. Service, T., & Adams, J. (2011). Randomized coalition structure generation. Artificial Intelligence, 175 (16–17), 2061–2074.
  51. Shahriari Nia, A., Olfat, L., Amiri, M., Kazazi, A. (2020). A combined approach to develop a structural model of factors affecting cooperation in the supply chain of the home appliance industry. Journal of Industrial Management Perspective, 10(1), 89-119. (In Persian)
  52. Sharma, S., & Singh, B. (2019). Overlapping coalition-based resource and power allocation for enhanced performance of underlaying D2D communication. Arabian Journal for Science and Engineering, 44(3), 2379–2388.
  53. Shehory, O., & Kraus, S. (1998). Methods for task allocation via agent coalition formation. Artificial Intelligence, 101(1–2), 165–200.
  54. Shoham, Y., & Leyton-Brown, K. (2008). Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press.
  55. Sless, L., Hazon, N., Kraus, S., & Wooldridge, M. (2018). Forming k coalitions and facilitating relationships in social networks. Artificial Intelligence, 259, 217–245.
  56. Taleizadeh, A., Samadi, R. (2015). Optimization of sale price and advertising cost in a two-level supply chain includes one manufacturer and two retailers. Journal of Industrial Management Perspective, 5(2), 107-127. (In Persian)
  57. Ueda, S., Hasegawa, T., Hashimoto, N., Ohta, N., Iwasaki, A., & Yokoo, M. (2012). Handling negative value rules in MC-net-based coalition structure generation. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, 12, 795–804.
  58. Ueda, S., Iwasaki, A., Conitzer, V., Ohta, N., Sakurai, Y., & Yokoo, M. (2018). Coalition structure generation in cooperative games with compact representations. Autonomous Agents and Multi-Agent Systems, 32(4), 503–533.
  59. Von Neumann, J., & Morgenstern, O. (1944). Theory of games and economic behavior. Princeton University Press.
  60. Xu, S., Xia, C., & Kwak, K. S. (2016). Overlapping coalition formation games based interference coordination for D2D underlaying LTE-A networks. AEU - International Journal of Electronics and Communications, 70(2), 204–209.
  61. Yeh, D., & Yun Yeh, D. (1986). A dynamic programming approach to the complete set partitioning problem. BIT Computer Science and Numerical Mathematics, 26(4), 467–474.

Files

Share

How to cite

Statistics