https://m2.mtmt.hu/ hun 2026-10-23 16:50 JournalArticle 37353270 APPROVED true 0 false 2026-09-28T09:29:47.942+0000 2026-06-25T09:27:37.693+0000 2026-06-25T09:27:31.401+0000 true 10102336 Stossek Virág /api/admin/10102336 Admin Stossek Virág (SZTAKI admin4) true 2026-06-25T09:27:37.708+0000 2026-06-25T09:27:37.708+0000 true false true 24 24 /api/publicationtype/24 PublicationType Folyóiratcikk 1 true 24 JournalArticle true 10000059 Article true 24 24 /api/publicationtype/24 PublicationType Folyóiratcikk 1 true 24 JournalArticle /api/subtype/10000059 Szakcikk SubType Szakcikk (Folyóiratcikk) 101 true 10000059 true 1 /api/category/1 Category Tudományos true 1 Vu, Duc Nghia true true /api/journal/10057489 REVIEWED MATHEMATICS 2227-7390 true false 10057489 false 10057489 true 2227-7390 Journal FOREIGN 14 9 1 47 1 47 2026 This paper presents a theoretically grounded integration of deterministic Q-learning with relational game theory (QLRG) for efficiently identifying minimal winning coalitions in Online Social Networks (OSNs). We address the fundamental challenge that coalition formation is NP-hard under traditional approaches by leveraging structural properties of relational dependencies and Armstrong’s axioms to transform the problem into one solvable in polynomial time. Our framework reduces the state space from exponential O(2n) to O(n2) through a sufficient statistic representation based on coalition size, follower reach, and terminal status, while achieving O(n4) time complexity under deterministic, static, and sufficiently symmetric influence structures. The QLRG framework introduces three critical innovations: (1) a principled agent selection mechanism derived directly from the Q-function that eliminates heuristic weight tuning; (2) a formal Boost action defined through temporal closure operators that captures influence spread dynamics; and (3) a constrained MDP formulation that enforces relational consistency through action elimination rather than penalty terms. We prove that the Bellman optimality operator forms a contraction mapping, guaranteeing deterministic convergence to optimal policies with established rates of O(1/√k) for decreasing learning rates or linear convergence up to bias for constant rates. To bridge the gap between this idealized model and the asymmetry inherent in real OSNs, we further develop a cluster-based sufficient statistics approach. By partitioning the network into communities with bounded internal variation, we relax the global symmetry requirement while preserving polynomial state space complexity, and obtaining a single within-community swap changes the optimal Q-value by at most εi1−γ, which is a local Lipschitz continuity result. The implications of this are both theoretical and practical, and they form the bedrock for relaxing the global symmetry assumption in the QLRG framework. Empirical validation on synthetic networks satisfying the symmetry assumption demonstrates that QLRG consistently identifies minimal winning coalitions matching the optimal solutions found by exhaustive search, while operating with polynomial-time complexity. Unlike conventional approaches, our framework simultaneously satisfies four critical properties: deterministic convergence, policy optimality, minimal coalition identification, and computational tractability. The work bridges computational social science and operations research, providing a mathematically rigorous foundation for strategic decision-making in influencer marketing and coalition formation. While the framework requires symmetry assumptions that may only hold approximately in real-world OSNs, it establishes an idealized baseline for future extensions addressing stochasticity, dynamics, and partial observability. This research represents a paradigm shift from empirical improvements to theoretically grounded convergence guarantees for coalition formation problems, demonstrating how structural mathematical insights can transform intractable problems into efficiently solvable ones without sacrificing solution quality. true 2026 true true true false true false GOLD 2026-09-28 true https://doi.org/10.3390/math14091526 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Q2 492907 false false false false 2026-09-23T09:27:37.404+0000 Számítástudományi Kutatócsoport (HRN SZTAKI / IL) 1 18 1 2 0 true Language 10002 /api/language/10002 Angol Angol English true 2 true PersonAuthorship 139775640 /api/authorship/139775640 Vu, Duc Nghia 1 0.5 true false false Vu Duc Nghia true false false AuthorshipType 1 /api/authorshiptype/1 Szerző 0 true 0 true false true PersonAuthorship 139775641 /api/authorship/139775641 Demetrovics, Janos [Demetrovics, János (Informatika, szám...), szerző] Számítástudományi Kutatócsoport (HRN SZTAKI / IL) 2 0.5 false true false Author 10000952 /api/author/10000952 Demetrovics János (Informatika, számítástudomány) Demetrovics János true 10000952 true Demetrovics Janos true false false AuthorshipType 1 /api/authorshiptype/1 Szerző 0 true 0 true false true PublicationIdentifier 32547790 /api/publicationidentifier/32547790 DOI: 10.3390/math14091526 PlainSource 6 /api/publicationsource/6 DOI PublicationSourceType 10001 /api/publicationsourcetype/10001 DOI true true true DOI DOI https://doi.org/@@@ true true 6 true GOLD true IDENTICAL 10.3390/math14091526 https://doi.org/10.3390/math14091526 false true PublicationIdentifier 32547791 /api/publicationidentifier/32547791 WoS: 001763861700001 PlainSource 1 /api/publicationsource/1 WoS PublicationSourceType 10003 /api/publicationsourcetype/10003 Indexelő adatbázis false true true WoS WoS https://www.webofscience.com/wos/woscc/full-record/@@@ true true 1 true IDENTICAL 001763861700001 https://www.webofscience.com/wos/woscc/full-record/001763861700001 false true PublicationIdentifier 32547801 /api/publicationidentifier/32547801 SZTAKI: 11147 SwordSource 86 /api/publicationsource/86 SZTAKI PublicationSourceType 10007 /api/publicationsourcetype/10007 Repozitórium true true true SZTAKI SZTAKI https://eprints.sztaki.hu/@@@ true true 86 true GOLD true 11147 https://eprints.sztaki.hu/11147 false true PublicationIdentifier 32547792 /api/publicationidentifier/32547792 Scopus: 105038454232 PlainSource 3 /api/publicationsource/3 Scopus PublicationSourceType 10003 /api/publicationsourcetype/10003 Indexelő adatbázis false true true Scopus Scopus http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-@@@ true true 3 true IDENTICAL 105038454232 http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-105038454232 false true PredatorRating 11781858 /api/predatorrating/11781858 Norvég listás folyóirat:492907 MATHEMATICS 2227-7390 RatingType 10033 /api/ratingtype/10033 Norvég listás folyóirat norveg true true 492907 true true SjrRating 11676934 /api/sjrrating/11676934 sjr:Q2 (2026) Scopus - Computer Science (miscellaneous) MATHEMATICS 2227-7390 133 0.49 journal RatingType 10002 /api/ratingtype/10002 sjr sjr true true ClassificationExternal 1701 /api/classificationexternal/1701 Scopus - Computer Science (miscellaneous) true 1701 true Q2 FROM_LAST_YEAR true true Reference 76326363 /api/reference/76326363 1. Watkins 1992: Q-learning., Mach. Learn., 8, p. 279 1 false true Reference 76326364 /api/reference/76326364 2. Watkins, C.J.C.H. (1989). Learning from Delayed Rewards. [Ph.D. Thesis, University of Cambridge]. 2 false true Reference 76326365 /api/reference/76326365 3. Jang 2019: Q-Learning Algorithms: A Comprehensive Classification and Applications., IEEE Access, 7, p. 133653, DOI: 10.1109/ACCESS.2019.2941229 3 10.1109/ACCESS.2019.2941229 false true Reference 76326366 /api/reference/76326366 4. Zhang, Y., and Yang, Q. (2017). A survey on multi-task learning. arXiv., DOI: 10.1093/nsr/nwx105 4 10.1093/nsr/nwx105 false true Reference 76326367 /api/reference/76326367 5. Gu, S., Holly, E., Lillicrap, T., and Levine, S. (June, January 29). Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates. Proceedings of the 2017 IEEE International Conference on Robotics and Automation (ICRA), Singapore., DOI: 10.1109/ICRA.2017.7989385 5 10.1109/ICRA.2017.7989385 false true Reference 76326368 /api/reference/76326368 6. Ghavamzadeh 2015: Bayesian reinforcement learning: A survey., Found. Trends Mach. Learn., 8, p. 359, DOI: 10.1561/2200000049 6 10.1561/2200000049 false true Reference 76326369 /api/reference/76326369 7. Armstrong 1974: Dependency structures of data base relationships., IFIP Congr., 74, p. 580 7 false true Reference 76326370 /api/reference/76326370 8. Beeri 1979: Computational problems related to the design of normal form relational schemas., ACM Trans. Database Syst. (TODS), 4, p. 30, DOI: 10.1145/320064.320066 8 10.1145/320064.320066 false true Reference 76326371 /api/reference/76326371 9. Rashid, T., Samvelyan, M., Witt, C.S., Farquhar, G., Foerster, J., and Whiteson, S. (2018). QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. International Conference on Machine Learning, ACM. 9 false true Reference 76326372 /api/reference/76326372 10. Casgrain 2022: Deep Q-Learning for Nash Equilibria: Nash-DQN., Appl. Math. Financ., 29, p. 62, DOI: 10.1080/1350486X.2022.2136727 10 10.1080/1350486X.2022.2136727 false true Reference 76326373 /api/reference/76326373 11. von Neumann, J., and Morgenstern, O. (1944). Theory of Games and Economic Behavior, Princeton University Press. 11 false true Reference 76326374 /api/reference/76326374 12. Bowling, M., and Veloso, M. (2025, December 01). Scalable Learning in Stochastic Games. AAAI Technical Report WS-02-06. Available online: https://cdn.aaai.org/Workshops/2002/WS-02-06/WS02-06-002.pdf. 12 false true Reference 76326375 /api/reference/76326375 13. Hu 2003: Nash Q-learning for general-sum stochastic games., J. Mach. Learn. Res., 4, p. 1039 13 false true Reference 76326376 /api/reference/76326376 14. Littman, M.L. (2001). Friend-or-foe Q-learning in general-sum games. Proceedings of the Eighteenth International Conference on Machine Learning, ACM. 14 false true Reference 76326377 /api/reference/76326377 15. Phillips, P. (2021). Reinforcement Learning in Two Player Zero Sum Simultaneous Action Games. arXiv. 15 false true Reference 76326378 /api/reference/76326378 16. Li 2022: Off-policy Q-learning: Solving Nash equilibrium of multi-player games with network-induced delay and unmeasured state., Automatica, 136, p. 110076, DOI: 10.1016/j.automatica.2021.110076 16 10.1016/j.automatica.2021.110076 false true Reference 76326379 /api/reference/76326379 17. De La Fuente, N., Alonso, M.N.I., and Casadellà, G. (2024). Game Theory and Multi-Agent Reinforcement Learning: From Nash Equilibria to Evolutionary Dynamics. arXiv., DOI: 10.2139/ssrn.5052738 17 10.2139/ssrn.5052738 false true Reference 76326380 /api/reference/76326380 18. Wang 2026: A comprehensive survey of game-theoretic approaches for networked systems., Syst. Sci. Control. Eng., 14, p. 2622131, DOI: 10.1080/21642583.2026.2622131 18 10.1080/21642583.2026.2622131 false true Reference 76326381 /api/reference/76326381 19. Peleg, B., and Sudhölter, P. (2007). Introduction to the Theory of Cooperative Games, Springer Science & Business Media. 19 false true Reference 76326382 /api/reference/76326382 20. Ding, S., and Lin, D. (2020, January 14–17). A Coalitional Markov Decision Process Model for Dynamic Coalition Formation among Agents. Proceedings of the 2020 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT), Melbourne, Australia., DOI: 10.1109/WIIAT50758.2020.00044 20 10.1109/WIIAT50758.2020.00044 false true Reference 76326383 /api/reference/76326383 21. Chalkiadakis, G., Markakis, E., and Boutilier, C. (2007). Coalition formation under uncertainty: Bargaining equilibria and the Bayesian core stability concept. AAMAS ‘07: Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, ACM., DOI: 10.1145/1329125.1329203 21 10.1145/1329125.1329203 false true Reference 76326384 /api/reference/76326384 22. Lowe 2020: Multi-agent actor-critic for mixed cooperative-competitive environments., Adv. Neural Inf. Process. Syst., 33, p. 11203 22 false true Reference 76326385 /api/reference/76326385 23. Liu, T.Y., Qi, Q., and Ye, Y. (2014). Coalitional Games on Sparse Social Networks. Web and Internet Economics. WINE 2014, Springer. Lecture Notes in Computer Science., DOI: 10.1007/978-3-319-13129-0 23 10.1007/978-3-319-13129-0 false true Reference 76326386 /api/reference/76326386 24. Kempe, D., Kleinberg, J., and Tardos, É. (2003, January 24–27). Maximizing the spread of influence through a social network, 2003. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA., DOI: 10.1145/956750.956769 24 10.1145/956750.956769 false true Reference 76326387 /api/reference/76326387 25. Nghia 2024: On the Relational Dependency Coalitional Games., J. Comput. Sci. Cybern., 4, p. 127 25 false true Reference 76326388 /api/reference/76326388 26. Vu 2025: Approximate Relational Games for Green Influencer Marketing Optimization., IEEE Access, 13, p. 158967, DOI: 10.1109/ACCESS.2025.3605398 26 10.1109/ACCESS.2025.3605398 false true Reference 76326389 /api/reference/76326389 27. Vu 2026: Relational Games and Repeated Bayesian Relational Games with Decision Tables for Influencer Marketing., Soft Comput., 30, p. 1637, DOI: 10.1007/s00500-025-11043-7 27 10.1007/s00500-025-11043-7 false true Reference 76326390 /api/reference/76326390 28. Jaakkola 1994: On the convergence of stochastic iterative dynamic programming algorithms., Neural Comput., 6, p. 1185, DOI: 10.1162/neco.1994.6.6.1185 28 10.1162/neco.1994.6.6.1185 false true Reference 76326391 /api/reference/76326391 29. Osborne, M.J., and Rubinstein, A. (1994). A Course in Game Theory, MIT Press. 29 false true Reference 76326392 /api/reference/76326392 30. Papadimitriou, C.H. (1994). Computational Complexity, Addison-Wesley. 30 false true Reference 76326393 /api/reference/76326393 31. Taylor, A.D., and Zwicker, W.S. (1999). Simple Games: Desirability Relations, Trading, Pseudoweightings, Princeton University Press., DOI: 10.1515/9780691223896 31 10.1515/9780691223896 false true Reference 76326394 /api/reference/76326394 32. Shapley 1953: A value for n-person games., Contrib. Theory Games, 2, p. 307 32 false true Reference 76326395 /api/reference/76326395 33. Sutton, R.S., and Barto, A.G. (2018). Reinforcement Learning: An Introduction, MIT Press. 33 false true Reference 76326396 /api/reference/76326396 34. Tesauro 1995: Reinforcement learning with soft state aggregation., Advances in Neural Information Processing Systems, Volume 7, p. 361 34 false true Reference 76326397 /api/reference/76326397 35. Dayan 1994: TD(λ) converges with probability 1., Mach. Learn., 14, p. 5, DOI: 10.1023/A:1022657612745 35 10.1023/A:1022657612745 false true Reference 76326398 /api/reference/76326398 36. Deng 1994: On the complexity of cooperative solution concepts., Math. Oper. Res., 19, p. 257, DOI: 10.1287/moor.19.2.257 36 10.1287/moor.19.2.257 false true Reference 76326399 /api/reference/76326399 37. Puterman, M.L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons., DOI: 10.1002/9780470316887 37 10.1002/9780470316887 false true Reference 76326400 /api/reference/76326400 38. Jaakkola, T., Singh, S.P., and Jordan, M.I. (1994). Reinforcement learning algorithm for partially observable Markov decision problems. Proceedings of the 8th International Conference on Neural Information Processing Systems (NIPS’94), MIT Press. 38 false true Reference 76326401 /api/reference/76326401 39. Tsitsiklis 1994: Asynchronous Stochastic Approximation and Q-Learning., Mach. Learn., 16, p. 185, DOI: 10.1023/A:1022689125041 39 10.1023/A:1022689125041 false true Reference 76326402 /api/reference/76326402 40. Mansour 2003: Learning Rates for Q-learning., J. Mach. Learn. Res., 5, p. 1 40 false true Reference 76326403 /api/reference/76326403 41. Dimitri, P.B., and Tsitsiklis, J.N. (1996). Neuro-Dynamic Programming, Athena Scientific. Available online: https://web.mit.edu/dimitrib/www/NDP.pdf. 41 false true /api/publication/37353270 Vu Duc Nghia et al. Deterministic Q-Learning with Relational Game Theory: Polynomial-Time Convergence to Minimal Winning Coalitions in Symmetric Influence Networks and Extension. (2026) MATHEMATICS 2227-7390 14 9 1-47<div class="JournalArticle Publication long-list"> <div class="authors"> <img title="Forrásközlemény" style="float: left" src="/frontend/resources/grid/publication-core-icon.png"> <div class="autype autype0"> <span class="author-name" >Vu Duc Nghia </span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" mtid="10000952"><a href="/gui2/?type=authors&mode=browse&sel=10000952" target="_blank">Demetrovics Janos (<span class="authorship-author-name">Demetrovics János</span> <span class="authorAux-mtmt"> Informatika, számítástudomány</span>) </a> </span> <span class="author-affil"><span title="HUN-REN Számítástechnikai és Automatizálási Kutatóintézet">HRN SZTAKI</span>/<span title="Mesterséges Intelligencia Kutatólaboratórium">IL</span>/Számítástudományi Kutatócsoport</span> </div> </div> <div class="title"><a href="/gui2/?mode=browse&params=publication;37353270" target="_blank">Deterministic Q-Learning with Relational Game Theory: Polynomial-Time Convergence to Minimal Winning Coalitions in Symmetric Influence Networks and Extension</a></div> <div> <span class="journal-title">MATHEMATICS</span> <span class="journal-issn">( <a target="_blank" href="https://portal.issn.org/resource/ISSN/2227-7390">2227-7390</a>)</span>: <span class="journal-volume">14</span> <span class="journal-issue">9</span> <span class="page"> pp 1-47 </span> <span class="year">(2026)</span> </div> <div class="pub-footer"> <span class="language" xmlns="http://www.w3.org/1999/html">Nyelv: Angol | </span> <span class="identifiers"> <span class="id identifier oa_GOLD" title=" Gold "> <a style="color:blue" title="10.3390/math14091526" target="_blank" href="https://doi.org/10.3390/math14091526"> DOI </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:blue" title="001763861700001" target="_blank" href="https://www.webofscience.com/wos/woscc/full-record/001763861700001"> WoS </a> </span> <span class="id identifier oa_GOLD" title=" Gold "> <a style="color:black" title="11147" target="_blank" href="https://eprints.sztaki.hu/11147"> SZTAKI </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:blue" title="105038454232" target="_blank" href="http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-105038454232"> Scopus </a> </span> </span> <OnlyViewableByAuthor><div class="ratings"> <div class="journal-subject">Folyóirat szakterülete: Scopus - Computer Science (miscellaneous)&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;Q2</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Engineering (miscellaneous)&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;Q2</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Mathematics (miscellaneous)&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;Q2</div> <div class="journal-subject">Norvég listás folyóirat</div> </div></OnlyViewableByAuthor> <div class="mtid"><span class="long-pub-mtid">Közlemény: 37353270</span> | <span class="status-data status-APPROVED"> Nyilvános </span> Forrás | <span class="type-subtype">Folyóiratcikk ( Szakcikk ) </span> | <span class="pub-category">Tudományos</span> | <span class="publication-sourceOfData"></span> </div> <div class="lastModified">Utolsó módosítás: 2026.06.25. 11:27 Stossek Virág (SZTAKI admin4) </div> </div></div>