Gliwice, 07.04.2014
Laboratorium
Komputerowe wspomaganie podejmowania decyzji
Ćw. 2 – Gry macierzowe o sumie niezerowej, strategie czyste
Walentek Adrian
Olberek Kamil
AiR, sem. 6, TI-2, sekcja 1
Gra macierzowa o wymiarach 4x4
A
|
B
|
|---|
Powyższy przykład ma 2 położenia równowagi Nasha:
(3,3)=(-25,-19)
(4,4)=(16,7)
Z czego tylko jedno jest rozwiązaniem dopuszczalnym: (3,3)=(-25,-19), ponieważ daje mniejsze wartości funkcji kosztów tj. nie istnieje para strategii od niej lepszej. Otrzymane rozwiązania nie są parami wymienialne, ponieważ jesteśmy w stanie bez problemu wybrać parę dającą lepszy wynik dla obu graczy. Wymienialność miałaby miejsce gdyby istniała para dająca wynik np. (-19,-25) czy np. (-24,-20).
W wymyślonym przez nas przykładzie znajduje się punkt minimaksowy, jednak nie stanowi on dopuszczalnego punktu równowagi Nasha, gdyż dopuszczalnym rozwiązaniem jest tylko para (3,3) dająca wynik (-25,-19), a obliczony punkt minimaksowy to: (4,4)=(16,7). Jednak punkt ten należy do rozwiązań strategii Nasha.
Wprowadzenie hierarchii w grze
Gracz D1 jako leader
Zbiór racjonalnych reakcji followera:
B
| D1\D2 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 28 | 47 | 39 | 10 |
| 2 | -6 | -17 | -20 | -25 |
| 3 | -16 | -4 | -19 | -15 |
| 4 | 13 | 14 | 32 | 7 |
Strategie równowagi Stackelberga dla leadera:
A
| D1\D2 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | -13 | 21 | 18 | 23 |
| 2 | 0 | -33 | -5 | 37 |
| 3 | 49 | 9 | -25 | 24 |
| 4 | -38 | -6 | 3 | 16 |
Optymalną strategią leadera jest strategia (3,3) z wynikiem (-25,-19).
Gracz D2 jako leader
Zbiór racjonalnych reakcji followera:
A
| D1\D2 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | -13 | 21 | 18 | 23 |
| 2 | 0 | -33 | -5 | 37 |
| 3 | 49 | 9 | -25 | 24 |
| 4 | -38 | -6 | 3 | 16 |
Strategie równowagi Stackelberga dla leadera:
B
| D1\D2 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 28 | 47 | 39 | 10 |
| 2 | -6 | -17 | -20 | -25 |
| 3 | -16 | -4 | -19 | -15 |
| 4 | 13 | 14 | 32 | 7 |
Optymalną strategią leadera jest strategia (3,3) z wynikiem (-19,-25).
Porównując rezultat gry przed i po wprowadzeniu hierarchii, dla naszej gry macierzowej otrzymaliśmy taką samą parę zagrań tj. (3,3). W zależności od tego, który gracz jest leaderem ten otrzymuje lepszy wynik. Jeśli gracz zaczyna, czyli jest leaderem to otrzymuje wynik -25, z kolei follower otrzymuje rezultat -19. W naszym przykładzie zbiór racjonalnych relacji followera na i-te zagranie leadera jest zbiorem jednoelementowym, dlatego leader dostaje lepszy wynik niż przy zagraniu strategią Nasha.
Kod programu
Równowaga Nasha
function nash(A,B)
[Nx,Ny] = size(A);
wybory_A=zeros(Ny);
wybory_B=zeros(Ny);
row_nasha=zeros(4,Ny);
%wybory gracza A
for j=1:Ny
[minimum,index]=min(A(:,j));
wybory_A(1,j)=index;
wybory_A(2,j)=j;
wybory_A(3,j)=minimum;
end
%wybory gracza B
for i=1:Nx
[minimum,index]=min(B(i,:));
wybory_B(1,i)=i;
wybory_B(2,i)=index;
wybory_B(3,i)=minimum;
end
%szukanie rownowagi Nasha
k=1;
for j=1:Ny
if wybory_A(1,j) == wybory_B(1,j)
if wybory_A(2,j) == wybory_B(2,j)
row_nasha(1,k)=wybory_A(1,j);
row_nasha(2,k)=wybory_A(2,j);
row_nasha(3,k)=wybory_A(3,j);
row_nasha(4,k)=wybory_B(3,j);
k=k+1;
end
end
end
%wyswietlanie wyników
for i=1:k-1
disp(['Row. Nasha ' num2str(i) ': (' num2str(row_nasha(1,i)) ',' num2str(row_nasha(2,i)) ')=(' num2str(row_nasha(3,i)) ',' num2str(row_nasha(4,i)) ')']);
end
%szukanie dopuszczalnej
Suma = sum(row_nasha(3:4,:));
minimum=min(Suma);
for j=1:Ny
if Suma(j)==minimum
disp(['Dopuszczalne: (' num2str(row_nasha(1,j)) ',' num2str(row_nasha(2,j)) ')=(' num2str(row_nasha(3,j)) ',' num2str(row_nasha(4,j)) ')']);
end
end
%rownowaga minimaksowa
k=1;
for i=1:Nx
[maksimum,j]=max(A(i,:));
[minimum,index] = min(A(:,j));
if maksimum <= minimum
minmaks1(1,k)=index;
minmaks1(2,k)=j;
minmaks1(3,k)=A(index,j);
k=k+1;
end
end
if k==1
disp('Brak minimaksowych rozwiazan w macierzy A');
else
k=1;
for j=1:Ny
[maksimum,i]=max(B(:,j));
[minimum,index] = min(B(i,:));
if maksimum <= minimum
minmaks2(1,k)=index;
minmaks2(2,k)=j;
minmaks2(3,k)=B(index,j);
k=k+1;
end
end
end
if k==1
disp('Brak minimaksowych rozwiazan w macierzy B');
else
minmaks1
minmaks2
for i=1:k-1;
if minmaks1(1,i)==minmaks2(1,i) && minmaks1(2,i)==minmaks2(2,i)
znalezione=1;
disp(['Rozwiazanie minimaksowe: (' num2str(minmaks2(1,i)) ',' num2str(minmaks2(2,i)) ')=(' num2str(minmaks1(3,i)) ',' num2str(minmaks2(3,i)) ')']);
end
end
end
end
Równowaga von Stackelberga
function stackelberg(A,B,rola_A)
%rola_A podajemy: leader albo follower
[Nx,Ny] = size(A);
if strcmp(rola_A,'follower') == 1
temp_A=A;
A=B;
B=temp_A;
A=A';
B=B';
end
k=1;
for i=1:Nx
minimum=min(B(i,:));
for j=1:Ny
if B(i,j)==minimum
tablica_follower(1,k)=i;
tablica_follower(2,k)=j;
tablica_follower(3,k)=A(i,j);
k=k+1;
end
end
end
tablica_follower;
k=1;
m=1;
liczba_wystapien=0;
poprzednia_liczba_wystapien=1;
for i=1:Nx
while k <= size(tablica_follower,2) && i == tablica_follower(1,k)
liczba_wystapien=liczba_wystapien+1;
k=k+1;
end
maksimum_wiersz = max(tablica_follower(3,poprzednia_liczba_wystapien:poprzednia_liczba_wystapien+liczba_wystapien-1));
for j=poprzednia_liczba_wystapien:poprzednia_liczba_wystapien+liczba_wystapien-1
if maksimum_wiersz == tablica_follower(3,j);
tablica_follower1(1,m)=i;
tablica_follower1(2,m)=tablica_follower(2,j);
tablica_follower1(3,m)=maksimum_wiersz;
m=m+1;
end
end
poprzednia_liczba_wystapien=poprzednia_liczba_wystapien+liczba_wystapien;
liczba_wystapien=0;
j=1;
end
tablica_follower1;
k=1;
minimum = min(tablica_follower1(3,:));
for i=1:size(tablica_follower1,2)
if tablica_follower1(3,i)==minimum
tablica_wynik(1,k)=tablica_follower1(1,i);
tablica_wynik(2,k)=tablica_follower1(2,i);
tablica_wynik(3,k)=tablica_follower1(3,i);
tablica_wynik(4,k)=B(tablica_follower1(1,i),tablica_follower1(2,i));
disp(['Row. Stackelberga ' num2str(i) ': (' num2str(tablica_wynik(1,k)) ',' num2str(tablica_wynik(2,k)) ')=(' num2str(tablica_wynik(3,k)) ',' num2str(tablica_wynik(4,k)) ')']);
k=k+1;
end
end
tablica_wynik;