%DVOUMATICE - kooperativní konflikt - nepřenosná výhra
close all, clear all, clc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Zadejte výplatní matice pro hráče 1 a 2 např. následovně:
% A=[-2 5 6; 3 1 -2; 1 4 2]
% B=[3 2 1; -1 4 -1; 5 4 2]

%Matice A a B musí nabývat stejných rozměrů.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Příklady vstupních parametrů:

%Příklad z [9]:
% A=[-2 3 -5 10; -4 8 9 7;2 4 2 -10]
% B=[-5 3 22 11;-4 8 4 -5; -11 3 10 7]

%Příklad z [9]:
% A=[-2 4 -5; 5 -3 7; -4 2 1]
% B=[0 6 -1; 5 -2 3; 1 2 -2]

%Příklad z [9]:
% A=[-2 5 6; 3 1 -2; 1 4 2]
% B=[3 2 1; -1 4 -1; 5 4 2]

% %Dva rovnovážné body, které se navzájem nedominují => zaručené výhry podle  maximin, 1 řešení
% A=[4 7 5;5 1 9;6 7 1]
% B=[9 5 3;2 0.97 5;4 8 1]

% % Matice 3x2, jeden rovnovážný bod => kooperace nemá přínos
% A=[15 5;6 4;4 7]
% B=[10 16;11 5;7 12]

% Zaručené výhry podle  maximin => 1 paretovská dvojice
% A=[4 8 7; 1 0 8; 3 6 7]
% B=[5 4 7; 1 0 3; 2 1 2]

% Příklad z diplomové práce:
% A=[6 9 -5 4; 2 -1 9 5; 3 5 6 8; 8 6 -1 3]
% B=[5 6 6 1; 5 2 7 -2; -4 -2 5 7; 3 5 7 -2]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Zadejte vstupní parametry:




%kód algoritmu:
size_check=0;
[m,n]=size(A);
[m_2,n_2]=size(B);
if (m>=2 && n>=2) && (m==m_2 && n==n_2)
    size_check=1;
end

if (size_check==1)
    %radkova maxima v B
    for i=1:m
        Bi=B(i,:);
        mx_B=max(Bi);
        [~,p{i}]=find(Bi==mx_B); %[m,n]=find(max) <--zajima me jen index sloupce n
        k1(i)=numel(p{i}); %pocitani, kolikrat je maximum na radku
    end
    
    %sloupcova maxima v A
    for i=1:n
        Ai=A(:,i);
        mx_A=max(Ai);
        [q{i},~]=find(Ai==mx_A); %[m,n]=find(max) <--zajima me jen index radku m
        k2(i)=numel(q{i}); %pocitani, kolikrat je maximum ve sloupci
        
    end
    
    %indexovani radkovych maxim v B
    X= [0,0];
    for i=1:numel(k1)
        for j=1:k1(i)
            C1(j,:)=[i,p{i}(j)]; %v ramci i-teho p-cka najdi j-tou hodnotu C1(1,1)=[]
        end
        X=[X;C1];
        C1=[];
    end
    
    %indexovani sloupcovych maxim v A
    Y=[0,0];
    for i=1:numel(k2)
        for j=1:k2(i)
            C2(j,:)=[i,q{i}(j)]; %v ramci iteho q-cka najdi jtou hodnotu
        end
        Y=[Y;C2];
        C2=[];
    end
    
    %odstraneni prvnich nul
    X=X(2:end,:);
    Y=Y(2:end,:);
    
    %prohozeni indexu ve sloupcovych maximech v A
    swap = [1 2];
    Y(:, swap) = Y(:, flip(swap));
    
    %nalezeni spolecnych oznacenych strategii
    C = intersect(X,Y,'rows');
    
    disp('Nalezená sloupcová maxima v matici A:')
    [length_U,~] = size(Y); %kolik ma matice sloupcovych maxim radku(tzn, zaznamu)
    for i=1:length_U
        fprintf('a(i=%g,j=%g)=%g\n',Y(i,1),Y(i,2),A(Y(i,1),Y(i,2)));
    end
    disp('............................')
    
    disp('Nalezená řádková maxima v matici B:')
    [length_Z,~] = size(X); %kolik ma matice radkovych maxim radku(tzn, zaznamu)
    for i=1:length_Z
        fprintf('b(i=%g,j=%g)=%g\n',X(i,1),X(i,2),B(X(i,1),X(i,2)));
    end
    
    [length_C,~] = size(C);
    v1_v2_check=0;
    if (length_C>0)
        disp('............................');
        
        if(length_C>1)
            disp('Nalezené rovnovážné body:')
        else
            disp('Nalezený rovnovážný bod:')
        end
        for i=1:length_C
            fprintf('a(i=%g,j=%g)=%g \n',C(i,1),C(i,2),A(C(i,1),C(i,2)));
            fprintf('b(i=%g,j=%g)=%g \n',C(i,1),C(i,2),B(C(i,1),C(i,2)));
            disp('...');
        end
        disp('............................');
        disp('Hledání a odstranění dominovaných rovnovážných bodů:');
        [length_C,~] = size(C);
        D=[0 0];
        for j=1:length_C
            for i=1:length_C
                if (A(C(j,1),C(j,2)) > A(C(i,1),C(i,2))) && (B(C(j,1),C(j,2)) > B(C(i,1),C(i,2)))
                    fprintf('a(i=%g,j=%g)=%g > a(i=%g,j=%g)=%g , b(i=%g,j=%g)=%g > b(i=%g,j=%g)=%g \n',C(j,1),C(j,2),A(C(j,1),C(j,2)),C(i,1),C(i,2),A(C(i,1),C(i,2)),C(j,1),C(j,2),B(C(j,1),C(j,2)),C(i,1),C(i,2),B(C(i,1),C(i,2)));
                    disp('...');
                    D(i,:)=[C(i,1),C(i,2)]; %radkove indexy dominovanych strategii
                end
                
            end
        end
        C=setdiff(C,D,'rows');
        %odstraneni nulovych radku
        C(C(:,1)==0,:) = [] ;
        disp('............................');
        [length_C,~] = size(C);
        %jediny rovnovazny bod
        if length_C==1
            disp('Nalezen jediný nedominovaný rovnovážný bod:');
            fprintf('a(i=%g,j=%g)=%g \n',C(1,1),C(1,2),A(C(1,1),C(1,2)));
            fprintf('b(i=%g,j=%g)=%g \n',C(1,1),C(1,2),B(C(1,1),C(1,2)));
            v1_v2_check=1;
        else
            %eq_check overuje rovnost funkcnich hodnot rovnovaznych bodu
            eq_check=1;
            disp('Kontrola rovnosti funkčních hodnot nedominovaných rovnovážných bodů:');
            for j=1:length_C
                for i=1:length_C
                     if (A(C(j,1),C(j,2)) ~= A(C(i,1),C(i,2))) || (B(C(j,1),C(j,2)) ~= B(C(i,1),C(i,2)))
                        fprintf('a(i=%g,j=%g)=%g ~= a(i=%g,j=%g)=%g nebo b(i=%g,j=%g)=%g ~= b(i=%g,j=%g)=%g \n',C(j,1),C(j,2),A(C(j,1),C(j,2)),C(i,1),C(i,2),A(C(i,1),C(i,2)),C(j,1),C(j,2),B(C(j,1),C(j,2)),C(i,1),C(i,2),B(C(i,1),C(i,2)));
                        disp('...');
                        eq_check=0;
                    end
                end
            end
            %exchangable_check_count>0 znamena, ze nektery z rovnovaznych bodu je nezamenitelny
            exchangable_check_count=0;
            disp('............................');
            %rovnovazne body jsou si rovny, kontrola zamenitelnosti - resitelny pripad
            if eq_check==1
                disp('Kontrola zaměnitelnosti nedominovaných rovnovážných bodů:');
                member_check=inf;
                for j=1:length_C
                    for i=1:length_C
                        exchangable=intersect(C,[C(j,1) C(i,2)],'rows');
                        [member_check,~]=size(exchangable);
                        if (member_check==0)
                            exchangable_check_count=exchangable_check_count+1;
                        end
                    end
                end
            end
            % rovnovazne body jsou stejne (a zamenitelne)
            if (exchangable_check_count==0 && eq_check==1)
                disp('Nalezené nedominované rovnovážné body mají stejnou funkční hodnotu a jsou zaměnitelné.');
                disp('............................');
                v1_v2_check=1;
            else
                %rovnovazne body nejsou stejne nebo nejsou zamenitelne
                disp('Nalezené nedominované rovnovážné body nemají stejnou funkční hodnotu, nebo nejsou zaměnitelné.');
                disp('............................');
                disp('Hledání zaručených výher podle maximinu:');
            end
        end
    else
        
        disp('............................');
        disp('Matice nemá žádný rovnovážný bod.');
        disp('Hledání zaručených výher podle maximinu:');
        
    end
    %zarucene vyhry:
    %jestlize je v matici nedominovany rovnovazny bod, pak je znama zarucena vyhra obou hracu
    if (v1_v2_check==1)
        v_1=A(C(1,1),C(1,2));
        v_2=B(C(1,1),C(1,2));
        disp('............................')
        disp('Zaručené výhry dle rovnovážného bodu jsou:');
        fprintf('Rovnovážná zaručená výhra prvního hráče v(1)=%g \n',v_1);
        fprintf('Rovnovážná zaručená výhra druhého hráče v(2)=%g \n',v_2);
    else
        %jestlize v matici nedominovany rovnovazny bod neni, pak se zjisti
        %zarucena vyhra podle maximiminu v radcich A, a sloupcich B
        disp('Nalezená řádková minima v matici A:');
        v1_min=min(A,[],2);
        for i=1:m
            fprintf('řádek %g: %g \n',i,v1_min(i));
        end
        
        disp('Nalezená sloupcová minima v matici B:');
        v2_min=min(B);
        for i=1:n
            fprintf('sloupec %g: %g \n',i,v2_min(i));
        end
        v_1=max(v1_min);
        v_2=max(v2_min);
        disp('Zaručené výhry dle maximinu jsou:');
        fprintf('Zaručená výhra prvního hráče v(1)=%g \n',v_1);
        fprintf('Zaručená výhra druhého hráče v(2)=%g \n',v_2);
    end
    disp('............................')
    
    %naplneni mnoziny pripustnych dvojic vyher P:
    %v maticich takove prvky, pro ktere plati: a(i,j) >= v_1 a soucasne b(i,j)>=v_2
    %soucasne musi platit: a(i,j)+b(i,j)>v(1)+v(2)
    [m_a,n_a]=find(A>=v_1);
    [m_b,n_b]=find(B>=v_2);
    X=[m_a n_a];
    Y=[m_b n_b];
    P=intersect(X,Y,'rows');
    [length_P,~] = size(P);
    disp('Ověření, zda má kooperace pro hráče přínos:');
    disp('...');
    coop_check=0;
    for i=1:length_P
        if (A(P(i,1),P(i,2))+B(P(i,1),P(i,2)))>v_1+v_2
            coop_check=1;
        end
    end
    
    %pokud pro zadnou z dvojic vyher z mnoziny P neplati: a(i,j)+b(i,j)>v(1)+v(2), pak konec> kooperace nema smysl!
    if coop_check==0
        disp('Kooperace nemá přínos, neboť pro žádnou dvojici výher neplatí v(1,2)>v(1)+v(2) a současně a(i,j)>=v(1),b(i,j)>=v(2).');
        disp('Hráči by tudíž kooperací nenabyli žádného zisku. Pro řešení hry je nutno využít metod nekooperativní teorie her.');
        return;
    end
    
    if length_P>0
        %pokud je v mnozine prave 1 prvek, pak je resenim hry
        if length_P==1
            fprintf('Množina přípustných dvojic výher P obsahuje jeden prvek, který je řešením hry:\n');
            fprintf('a(i=%g,j=%g)=%g, b(i=%g,j=%g)=%g\n',P(1,1),P(1,2),A(P(1,1),P(1,2)),P(1,1),P(1,2),B(P(1,1),P(1,2)));
        else
            %pokud je v mnozine P vice jak 1 prvek:
            fprintf('Množina přípustných dvojic výher P obsahuje %g prvky:\n',length_P);
            for i=1:length_P
                fprintf('a(i=%g,j=%g)=%g, b(i=%g,j=%g)=%g\n',P(i,1),P(i,2),A(P(i,1),P(i,2)),P(i,1),P(i,2),B(P(i,1),P(i,2)));
            end
            disp('............................');
            %naplneni mnoziny nedominovanych dvojic vyher P':
            %v mnozine P takove prvky, pro ktere plati a(i',j')>=a(i,j) a soucasne b(i',j')>b(i,j)
            %nebo a(i',j')>a(i,j) a soucasne b(i',j')>= b(i,j). 
            D=[0 0];
            disp('Naplnění množiny nedominovaných přípustných dvojic výher (tzv. množiny paretovských dvojic):');
            for j=1:length_P
                for i=1:length_P
                    if (A(P(j,1),P(j,2)) >= A(P(i,1),P(i,2))) && (B(P(j,1),P(j,2)) > B(P(i,1),P(i,2)))
                        fprintf('a(i=%g,j=%g)=%g >= a(i=%g,j=%g)=%g , b(i=%g,j=%g)=%g > b(i=%g,j=%g)=%g \n',P(j,1),P(j,2),A(P(j,1),P(j,2)),P(i,1),P(i,2),A(P(i,1),P(i,2)),P(j,1),P(j,2),B(P(j,1),P(j,2)),P(i,1),P(i,2),B(P(i,1),P(i,2)));
                        D(i,:)=[P(i,1),P(i,2)]; %radkove indexy dominovanych dvojic
                    end
                    
                    if (A(P(j,1),P(j,2)) > A(P(i,1),P(i,2))) && (B(P(j,1),P(j,2)) >= B(P(i,1),P(i,2)))
                        fprintf('a(i=%g,j=%g)=%g > a(i=%g,j=%g)=%g , b(i=%g,j=%g)=%g >= b(i=%g,j=%g)=%g \n',P(j,1),P(j,2),A(P(j,1),P(j,2)),P(i,1),P(i,2),A(P(i,1),P(i,2)),P(j,1),P(j,2),B(P(j,1),P(j,2)),P(i,1),P(i,2),B(P(i,1),P(i,2)));
                        disp('...');
                        D(i,:)=[P(i,1),P(i,2)]; %radkove indexy dominovanych dvojic
                    end
                    
                end
            end
            
            P_paret=setdiff(P,D,'rows');
            %odstraneni nulovych radku
            P_paret(P(:,1)==0,:) = [] ;
            [length_P_paret,~] = size(P_paret);
            disp('............................');
            if length_P_paret==0
                disp('Hráči nemají důvod kooperovat. K nalezení řešení hry je třeba užít metod nekooperativní teorie her.');
                return
            end
             
            %pokud je v mnozine P' vice jak 1 prvek:
            if length_P_paret>1
                disp('Množina nedominovaných přípustných dvojic výher (tzv. množina paretovských dvojic) je tvořena prvky:');
                for i=1:length_P_paret
                    fprintf('a(i=%g,j=%g)=%g, b(i=%g,j=%g)=%g\n',P_paret(i,1),P_paret(i,2),A(P_paret(i,1),P_paret(i,2)),P_paret(i,1),P_paret(i,2),B(P_paret(i,1),P_paret(i,2)));
                end
                disp('............................');
                
                %hledani stredni hodnoty N
                sum_A=0;
                sum_B=0;
                disp('Hledaní střední hodnoty výher v množine paretovských dvojic:');
                for i=1:length_P_paret
                    sum_A=sum_A+A(P_paret(i,1),P_paret(i,2));
                    sum_B=sum_B+B(P_paret(i,1),P_paret(i,2));
                end
                N=[sum_A/length_P_paret sum_B/length_P_paret];
                fprintf('Střední hodnota výher prvního hráče: %g/%g=%g \n',sum_A,length_P_paret,N(1));
                fprintf('Střední hodnota výher druhého hráče: %g/%g=%g \n',sum_B,length_P_paret,N(2));
                fprintf('N=[%g %g]\n',N(1),N(2));
                disp('............................');
                
                disp('Hledaní dvojice výher s nejkratší euklidovskou vzáleností od střední hodnoty výher N:');
                %hledani nejkratsi euklidovske vzdalenosti vzhledem ke stredni hodnote N
                min_distance=inf;
                for i=1:length_P_paret
                    distance(i)=abs(A(P_paret(i,1),P_paret(i,2))-N(1))+abs(B(P_paret(i,1),P_paret(i,2))-N(2));
                    if distance(i)<=min_distance
                        min_distance=distance(i);
                    end
                end
                %nalezeni dvojice vyher v množině P s nejkratsi euklidovskou vzdalenosti vzhledem ke stredni hodnote N
                j=1;
                for i=1:length_P_paret
                    if abs(A(P_paret(i,1),P_paret(i,2))-N(1))+abs(B(P_paret(i,1),P_paret(i,2))-N(2))==min_distance
                        min_distance_index(j)=i;
                        j=j+1;
                    end
                end

                for i=1:length(min_distance_index)
                    fprintf('a(i=%g,j=%g)=%g, b(i=%g,j=%g)=%g s euklidovskou vzáleností:%g\n',P_paret(min_distance_index(i),1),P_paret(min_distance_index(i),2),A(P_paret(min_distance_index(i),1),P_paret(min_distance_index(i),2)),P_paret(min_distance_index(i),1),P_paret(min_distance_index(i),2),B(P_paret(min_distance_index(i),1),P_paret(min_distance_index(i),2)),min_distance);
                end
                
                %v mnozine P' je prave jeden prvek:
            else
                disp('Množina nedominovaných přípustných dvojic výher (tzv. množina paretovských dvojic) obsahuje')
                disp('jeden prvek, který je řešením hry:');
                fprintf('a(i=%g,j=%g)=%g, b(i=%g,j=%g)=%g\n',P_paret(1,1),P_paret(1,2),A(P_paret(1,1),P_paret(1,2)),P_paret(1,1),P_paret(1,2),B(P_paret(1,1),P_paret(1,2)));
            end
        end
        %v mnozine P neni zadny prvek > neni duvod kooperovat
    else
        disp('Hráči nemají důvod kooperovat. K nalezení řešení hry je třeba užít metod nekooperativní teorie her.');
    end
else
    disp('Chyba: Obě matice A, B musí mít tototžné rozměry o rozměrech alespoň 2x2.');
end



