|
Article information
2018 , Volume 23, ¹ 1, p.3-18
Kubica B.J.
Advanced interval tools for computing solutions of continuous games
Computing Nash equilibria in continuous games is a difficult problem, but interval methods have already been applied to its solution quite successfully. The purpose of this paper is to briefly survey previous efforts and achievements of the author related to the topic, and to consider some advanced tools for accelerating the interval branch-and-bound-type methods. In particular, we discuss computing eigenvalues of interval matrices, use of algorithmic (automatic) differentiation, memory management techniques as well as advanced parallelization in both shared-memory and distributedmemory environments.
[full text]
Keywords: Nash equilibria, continuous games, interval computations, eigenvalues, automatic differentiation, memory management, threads, MPI
doi: 10.5072/ICT.2018.1.11778
Author(s):
Kubica Bartlomiej Jacek
Office: Warsaw University of Life Sciences
Address: 02-776, Poland, Warsawa
References:
[1] Nash, J.F. Equilibrium points in 𝑛-person games. Proceedings of National Association of Science. 1950; 36(1):48–49.
[2] Aumann, R. J. Acceptable points in general cooperative games. Contributions to the Theory of Games IV. A. W. Tucker and R. D. Luce, eds. Princeton: Princeton University Press; 1959.
[3] Kubica, B.J. Wo’zniak, A. An interval method for seeking the Nash equilibria of noncooperative games // PPAM 2009 Proceedings. Lecture Notes in Computer Science. 2010; (6068):446–455.
[4] Kubica, B.J., Wo’zniak, A. Applying an interval method for a four agent economy analysis. PPAM 2011 Proceedings (9th International Conference on Parallel Processing and Applied Mathematics). Lecture Notes in Computer Science. 2012; (7204):477–483.
[5] Kubica, B.J., Wo’zniak, A. Interval methods for computing strong Nash equilibria of continuous games. Decision Making in Manufacturing and Services. 2015; 9(1):63–78.
[6] Kearfott, R.B., Nakao, M.T., Neumaier, A., Rump, S.M., Shary, S.P., van Hentenryck, P. Standardized notation in interval analysis. Computational Technologies. 2010; 15(1):7–13.
[7] Kubica, B.J. A class of problems that can be solved using interval algorithms. Computing. 2012; (94):271–280.
[8] Hansen, E., Walster, W. Global Optimization Using Interval Analysis. New York: Marcel Dekker; 2004: 515.
[9] Jaulin, L., Kieffer, M., Didrit, O.,Walter. E. Applied Interval Analysis. London: Springer; 2001: 378.
[10] Kearfott, R.B. Rigorous Global Search: Continuous Problems. Dordrecht: Kluwer; 1996: 278.
[11] Moore, R.E., Kearfott, R.B., Cloud, M.J. Introduction to Interval Analysis. SIAM, Philadelphia; 2009: 234.
[12] Shary, S.P. Finite-dimensional Interval Analysis. XYZ, 2017. Available at: http://www.nsc.ru/interval/Library/InteBooks/SharyBook.pdf (accessed 03.04.2017).
[13] Rohn, J., Deif, A. On the range of eigenvalues of an interval matrix. Computing. 1992; 47(3):373–377.
[14] Hlad’ık, M., Daney, D., Tsigaridas, E. A filtering method for the interval eigenvalue Problem. Applied Mathematics and Computation. 2011; 217(12):5236–5242.
[15] Hlad’ık, M. Bounds on eigenvalues of real and complex interval matrices. Applied Mathematics and Computation. 2013; 219(10):5584–5591.
[16] Mayer, G. Result verification for eigenvectors and eigenvalues. Topics in Validated Computations. Proceedings of the IMACS-GAMM International Workshop on Validated Computation, Oldenburg, Germany, 30 August–3 September, 1993. J. Herzberger, ed. Amsterdam: Elsevier; 1994: 209–276.
[17] VERSOFT. Verification software in MATLAB/ INTLAB. Available at: http://uivtx.cs.cas.cz/~rohn/matlab/.
[18] C-XSC. C++ eXtended Scientific Computing library. Available at: http://www.xsc.de, 2015.
[19] Alexandrescu, A. Modern C++ design: Generic programming and design patterns applied. Boston: Addison-Wesley; 2001: 352.
[20] Kramer, W., Zimmer, M., Hofschuster, W. Using C-XSC for high performance verified computing. Lecture Notes in Computer Science. 2012; (7134):168–178.
[21] ADHC. ADHC template library. Available at: https://www.researchgate.net/profile/Bartlomiej_Kubica/publications?category=data/, 2017.
[22] Loki. Loki C++ template library. Available at: http://loki-lib.sourceforge.net, 2015.
[23] Williams, A. C++ Concurrency in Action. New York: Manning Publications; 2012: 528.
[24] MPI. Message Passing Interface. Available at: http://www.mpi-forum.org, 2015.
[25] Intel Threading Building Blocks. Available at: http://www.threadingbuildingblocks.org, 2015.
[26] Gau, C.-Y., Stadtherr, M.A. Dynamic load balancing for parallel interval-Newton using message passing. Computers & chemical engineering. 2002; 26(6):811–825.
[27] Cannon, L. E. A cellular computer to implement the Kalman filter algorithm. Technical report, DTIC Document, 1969.
[28] CXSC-MPI. MPI extension for the use of C-XSC in parallel environments. Available at: http://www2.math.uniwuppertal.de/~xsc/xsc/cxsc_software.html#cxsc_mpi, 2015.
[29] Grimmer, M. An MPI extension for the use of C-XSC in parallel environments. Available at: http://www2.math.uniwuppertal.de/~xsc/preprints/prep_05_3.pdf, 2005.
[30] OpenBLAS. OpenBLAS library. Available at: http://xianyi.github.com/OpenBLAS/, 2015.
[31] OpenMPI. OpenMPI library. Available at: https://www.open-mpi.org, 2015.
[32] Hoffler, T. Advanced MPI: New features of MPI-3. Available at: http://htor.inf.ethz.ch/teaching/mpi_tutorials/speedup15/hoefler-advanced-mpi-speedup15.pdf, 2016.
[33] Brinsky, M. An introduction to MPI-3.0 shared memory programming. Available at: https://goparallel.sourceforge.net/wp-content/uploads/2015/06/PUM21-2-An_Introduction_to_MPI-3.pdf, 2016.
Bibliography link:
Kubica B.J. Advanced interval tools for computing solutions of continuous games // Computational technologies. 2018. V. 23. ¹ 1. P. 3-18
|
