PARALLEL ALGORITHM TO FIND THE STACKELBERG EQUILIBRIUM PROFILES IN THE THREE STAGE DYNAMIC GAMES WITH DISCRETE PAYOFF FUNCTIONS

Boris HÂNCU Catedra Informatică şi Optimizare Discretă

Abstract

În articol este definit un joc dinamic cu trei jucători pe trei niveluri în informaţie completă. Ordinea de alegere a strategiilor este următoarea: jucătorul 1 alege primul strategia sa şi o transmite jucătorului 2 care, la rândul său, va alege strategia sa, după ce îşi alege strategia jucătorul 3. Aceste jocuri pot fi utilizate la modelarea proceselor decizionale în sisteme cu structuri ierarhice. În calitate de soluţie a acestui joc sunt considerate situaţiile Stackelberg de echilibru determinate în baza algoritmului inducţiei recursive. Este descris un algoritm paralel al metodei inducţiei recursive pentru determinarea situaţiilor Stackelberg de echilibru, când funcţiile-scop ale jucătorilor sunt reprezentate în forma unor matrici. Algoritmul paralel este elaborat pentru sisteme paralele de calcul cu memorie distribuită de tip clastere, în care schimbul de date între procesele (procesoarele) de calcul se realizează prin transmiterea de mesaje. Pentru implementarea soft a paralelizării la nivel de date şi la nivel de operaţii a algoritmului paralel se utilizează sistemul de funcţii standardizate Message Passing Interface (MPI). Este formulată şi demonstrată teorema despre corectituninea algoritmului. La fel sunt prezentaţi şi estimatorii unor caracteristici numerice care descriu timpul de calcul al algoritmului paralel.