Abstract
We formulate and solve the problem of optimizing the structure of an information propagation network between multiple agents. In a given space of interests (e.g., information on certain targets), each agent is defined by a vector of their desirable information, called filter, and a vector of available information, called source. The agents seek to build a directed network that maximizes the value of the desirable source-information that reaches each agent having been filtered en route, less the expense that each agent incurs in filtering any information of no interest to them. We frame this optimization problem as a game of common interest, where the Nash equilibria can be attained as limit points of Sampled Fictitious Play (SFP), offering a method that turns out computationally effective in traversing the huge space of feasible networks on a given node set. Our key idea lies in the creative use of history in SFP, leading to the new History Value-Weighted SFP method. To our knowledge, this is the first successful application of FP for network structure optimization. The appeal of our work is supported by the outcomes of the computational experiments that compare the performance of several algorithms in two settings: centralized (full information) and decentralized (local information).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adamic, L.A., Glance, N.: The political blogosphere and the 2004 U.S. election: divided they blog. In: Proceedings of the 3rd International Workshop on Link Discovery, LinkKDD 2005, pp. 36–43. ACM, New York (2005). https://doi.org/10.1145/1134271.1134277
Brown, G.W.: Iterative solution of games by fictitious play (1951)
Dolinskaya, I.S., Epelman, M.A., Şişikoğlu Sir, E., Smith, R.L.: Parameter-free sampled fictitious play for solving deterministic dynamic programming problems. J. Optim. Theory Appl. 169(2), 631–655 (2016). https://doi.org/10.1007/s10957-015-0798-5
Epelman, M., Ghate, A., Smith, R.L.: Sampled fictitious play for approximate dynamic programming. Comput. Oper. Res. 38(12), 1705–1718 (2011). https://doi.org/10.1016/j.cor.2011.01.023. http://www.sciencedirect.com/science/article/pii/S0305054811000451
Ghate, A., Cheng, S.F., Baumert, S., Reaume, D., Sharma, D., Smith, R.L.: Sampled fictitious play for multi-action stochastic dynamic programs. IIE Trans. 46(7), 742–756 (2014)
Horn, R.A.: The hadamard product. In: Proceedings of Symposium in Applied Mathematics, vol. 40, pp. 87–169 (1990)
Lambert, T.J., Epelman, M.A., Smith, R.L.: A fictitious play approach to large-scale optimization. Oper. Res. 53(3), 477–489 (2005). https://doi.org/10.1287/opre.1040.0178. http://dx.doi.org/10.1287/opre.1040.0178
Monderer, D., Shapley, L.S.: Fictitious play property for games with identical interests. J. Econ. Theory 68(1), 258–265 (1996). https://doi.org/10.1006/jeth.1996.0014. http://www.sciencedirect.com/science/article/pii/S0022053196900149
Robinson, J.: An iterative method of solving a game. Ann. Math. 54, 296–301 (1951)
Acknowledgements
Work of A. Semenov was funded in part by the AFRL European Office of Aerospace Research and Development (grant no. FA9550-17-1-0030). This material is based upon work supported by the AFRL Mathematical Modeling and Optimization Institute.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Nikolaev, A., Semenov, A., Pasiliao, E.L. (2019). Sampled Fictitious Play on Networks. In: Tagarelli, A., Tong, H. (eds) Computational Data and Social Networks. CSoNet 2019. Lecture Notes in Computer Science(), vol 11917. Springer, Cham. https://doi.org/10.1007/978-3-030-34980-6_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-34980-6_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-34979-0
Online ISBN: 978-3-030-34980-6
eBook Packages: Computer ScienceComputer Science (R0)