A comparative analysis of the calculation time for the data parallelization in bimatrix games
Close
Articolul precedent
Articolul urmator
312 7
Ultima descărcare din IBN:
2024-01-03 15:05
SM ISO690:2012
HANCU, Boris, ANTOHI, Ion. A comparative analysis of the calculation time for the data parallelization in bimatrix games. In: Mathematics and IT: Research and Education, 1-3 iulie 2021, Chişinău. Chișinău, Republica Moldova: 2021, pp. 41-42.
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Mathematics and IT: Research and Education 2021
Conferința "Mathematics and IT: Research and Education "
Chişinău, Moldova, 1-3 iulie 2021

A comparative analysis of the calculation time for the data parallelization in bimatrix games


Pag. 41-42

Hancu Boris, Antohi Ion
 
Moldova State University
 
 
Disponibil în IBN: 30 iunie 2021


Rezumat

We consider the bimatrix game in the following strategic form ¡ = hI; J; A;Bi, where A = jjaij jjj2J i2I ; B = jjbij jjj2J i2I are the payoff matrices of the players and denote by NE[¡] the set of all equilibrium profiles in the game. Based on the definition, it is easy to develop the following algorithm for determining the Nash equilibrium profiles in bimatrix games. 1. For any fixed column j 2 J; i¤(j) = Arg max i2I aij is determined. Under algorithmic aspect it can be as follows: for any column j of the matrix A all maximum elements of this column are highlighted. 2. For any fixed row i 2 I; j¤(i) = Arg max j2J bij is determined. Under algorithmic aspect it can be as follows: for any row i of the matrix B all maximum elements on this row are highlighted. 3. The function graph of the application i¤ from step 1) is built: gr_i¤ = f(i; j) : i = i¤ (j) ; 8j 2 Jg and of the application j¤ from step 2) is built as well: gr_j¤ = f(i; j) : j = j¤(i); 8i 2 Ig. The equilibrium profiles are all the profiles belonging to the intersection of the two given function graphs: NE = gr_i¤ \gr_j¤: From an algorithmic point of view it can be done as follows: we look for all highlighted elements in the matrices A and B and the indices of the elements whose positions coincide both in matrix A and in matrix B will be the equilibrium profiles. We make an analysis of the possibilities of the symbolic calculation system Mathematics for the elaboration of parallel programs on the DMM type parallel system. A parallel algorithm is developed for determining Nash equilibrium profiles in pure strategies for bimatrix games. For this algorithm, parallel programs are developed using the Wolfram Mathematica system and MPI programming models, in which different ways of distributing the calculations on cores (for Mathematica system), process (for MPI programing) and different ways of parallelization at the data level are performed. A comparative analysis of the calculation time for the developed programs is performed.