Abstract
From a perspective of designing or engineering for opinion formation games in social networks, the opinion maximization (or minimization) problem has been studied mainly for designing subset selecting algorithms. We define a two-player zero-sum Stackelberg game of competitive opinion optimization by letting the player under study as the leader minimize the sum of expressed opinions by doing so-called “internal opinion design”, knowing that the other adversarial player as the follower is to maximize the same objective by also conducting her own internal opinion design. We furthermore consider multiagent learning, specifically using the Optimistic Gradient Descent Ascent, and analyze its convergence to equilibria in the simultaneous version of competitive opinion optimization.
P.-A. Chen—Supported in part by MOST 110-2410-H-A49-011.
C.-C. Lin—Supported in part by MOST 110-2222-E-032-002-MY2.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
For a player maximizing her total reward given a sequence of reward vectors, the regret can also be defined accordingly.
- 2.
In particular, for a node i, after its internal opinion is affected by the min player and the max player, without clipping its modified internal opinion value \(s_i+x_i+y_i\) clipped to the range \([-1,1]\) every node’s equilibrium strategy would result in a dominant strategy solution, which is a special Nash equilibrium and less interesting to look for since the strategies of both players would not be mutually entangled.
- 3.
The whose proof is detailed in the full version.
- 4.
This part is deferred to the full version.
References
Abernethy, J., Bartlett, P.L., Hazan, E.: Blackwell approachability and no-regret learning are equivalent. In: Proceedings of Conference on Learning Theory (2011)
Ahmadinejad, A., Mahini, H.: How effectively can we form opinions? In: Proceedings of International World Wide Web Conference (2014)
Bindel, D., Kleinberg, J., Oren, S.: How bad is forming your own opinion? In: Proceedings of 52nd Annual IEEE Symposium on Foundations of Computer Science (2011)
Cesa-Bianchi, N., Lugosi, G.: Combinatorial bandits. In: Proceedings of 22nd Annual Conference on Learning Theory (2009)
Chen, P.-A., Chen, Y.-L., Lu, C.-J.: Bounds on the price of anarchy for a more general class of directed graphs in opinion formation games. Oper. Res. Lett. 44, 808–811 (2016)
Chiang, C.-K., Yang, T., Lee, C.-J., Mahdavi, M., Lu, C.-J., Zhu, S.: Online optimization with gradual variations. In: Proceedings of Conference on Learning Theory (2012)
Freund, Y., Schapire, R.E.: A decision theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci. 55(1), 119–139 (1997)
Freund, Y., Schapire, R.E.: Adaptive game playing using multiplicative weights. Games Econ. Behav. 29, 79–103 (1999)
Gionis, A., Terzi, E., Tsaparas, P.: Opinion maximization in social networks. In: Proceedings of 13th SIAM International Conference on Data Mining (2013)
Golowich, N., Pattathil, S., Daskalakis, C.: Tight last-iterate convergence rates for no-regret learning in multi-player games. In: Proceedings of the 34th Conference on Neural Information Processing Systems (2020)
Kalai, A., Vempala, S.: Efficient algorithms for online decision problems. J. Comput. Syst. Sci. 71, 291–307 (2005)
Koolen, W., Warmuth, M., Kivinen, J.: Hedging structured concepts. In: Proceedings of 23rd Annual Conference on Learning Theory (2010)
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Proceedings of 17th Annual Symposium on Theoretical Aspects of Computer Science (1999)
Lee, C.: Analysis of perturbation techniques in online learning. Doctoral Dissertation, the Department of Computer Science and Engineering, the University of Michigan (2018)
Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V. (eds.): Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)
Wei, C.-Y., Lee, C.-W., Zhang, M., Luo, H.: Linear last-iterate convergence in constrained saddle-point optimization. In: Proceedings of 9th International Conference on Learning Representations (2021)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Chen, PA., Lu, CJ., Lin, CC., Fu, KW. (2022). Multiagent Learning for Competitive Opinion Optimization (Extended Abstract). In: Hsieh, SY., Hung, LJ., Klasing, R., Lee, CW., Peng, SL. (eds) New Trends in Computer Technologies and Applications. ICS 2022. Communications in Computer and Information Science, vol 1723. Springer, Singapore. https://doi.org/10.1007/978-981-19-9582-8_6
Download citation
DOI: https://doi.org/10.1007/978-981-19-9582-8_6
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-19-9581-1
Online ISBN: 978-981-19-9582-8
eBook Packages: Computer ScienceComputer Science (R0)