Parallel algorithm to solving block-cyclic partitioned bimatrix games
Închide
Articolul precedent
Articolul urmator
114 5
Ultima descărcare din IBN:
2023-05-04 12:34
SM ISO690:2012
HANCU, Boris, CATARANCIUC, Emil. Parallel algorithm to solving block-cyclic partitioned bimatrix games. In: Conference on Applied and Industrial Mathematics: CAIM 2022, Ed. 29, 25-27 august 2022, Chişinău. Chișinău, Republica Moldova: Casa Editorial-Poligrafică „Bons Offices”, 2022, Ediţia a 29, pp. 108-109. ISBN 978-9975-81-074-6.
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Conference on Applied and Industrial Mathematics
Ediţia a 29, 2022
Conferința "Conference on Applied and Industrial Mathematics"
29, Chişinău, Moldova, 25-27 august 2022

Parallel algorithm to solving block-cyclic partitioned bimatrix games


Pag. 108-109

Hancu Boris, Cataranciuc Emil
 
Moldova State University
 
 
Disponibil în IBN: 21 decembrie 2022


Rezumat

]We consider the bimatrix game in the following strategic form Γ = ⟨I, J,A,B⟩ and denote by NE[Γ] the set of all equilibrium profiles in the game Γ. Matrices A and matrix B are divided into submatrices using one and the same algorithm. Thus we can obtain a series of pairs submatrices of the same size {(Ar,Br)}r=1,p where Ar =  ar ij  j∈Jr i∈Ir , Br =  br ij  j∈Jr i∈Ir and Ir1 ∩Ir2 = ⊘, Jr1 ∩Jr2 = ⊘ ∀r1 ̸= r2. Here the index r actually means ”processor” which, will obtain these submatrices. These submatrices will generate a series of games which are actually sub-games of the original game Γr = ⟨Ir,Jr,Ar,Br⟩ . We denote by NE[Γr] the set of Nash equilibrium profiles in the problem Γr and assume that the subgames are solved in parallel on an HPC system. If for any (i∗r , j∗r ) ∈ NE[Γr] we have that (i∗r , j∗r ) ∈ NE[Γ] then we will say that the algorithm of dividing the matrices into blocks of submatrices is perfect and will be called perfect matrix dividing and distribution (PMDD) algorithm. According to the two dimensional block cyclic data distribution algorithm [1] all process can be referenced by its row and column coordinates, (l, c) and must solve the Γ(c,l) =  I(c,l),J(c,l),A(c,l),B(c,l)  game. We can proof the folowing theorem. Theorem If 1. for fixed c and all l ̸= l such that (l, c) ∈ L×C the conditions ai∗( l,c) ,j∗(l,c) ≥ ai∗( l,c) j∗(l,c) are fulfilled;2. for fixed l and all c ̸= c such that (l, c) ∈ L×C the conditions bi∗( l,c) ,j∗(l,c) ≥ bi∗( l,c) j∗(l,c) are fulfilled. Then the two dimensional block cyclic data distribution algorithm is a PMDD algorithm. Here i∗( l,c) = arg max i (l,c)∈I (l,c) ai (l,c) j∗r and j∗(l,c) = arg max j(l,c)∈J(l,c) bi∗r j(l,c) .