Игры двух лиц с нулевой суммой

2. Игроки используют случайную смесь чистых стратегий с заданными вероятностями. 3. Игра повторяется многократно в сходных условиях. 4. При любом ходе ни один из игроков не информирован о стратегии другого игрока. 5. Допускается усреднение результатов игр.Свойства антагонистических игрДж. фон Нейманом была доказана основная теорема теорииигр, утверждающая, что каждая игра имеет, по крайней мере, одно решение,возможно, в области смешанных стратегий:Для матричной игры с любой матрицейА величины и существуют и равны между собой. Из основной теоремы теории игр следует1. Любая игра имеет цену.2. Цена игры удовлетворяет неравенству .3. Средний выигрыш остается равным цене игры, если один из игроков придерживается своей оптимальной стратегии, а другой игрок применяет свои полезные стратегии с любыми частотами.Кроме того, для игр с нулевой суммой выполняются следующие утверждения:1. Если в игре с нулевой суммой последовательно удалить все строго доминируемые стратегии, то множество оставшихся стратегий не зависит от последовательности удаления.Описание алгоритма решения игры с нулевой суммойРассмотрим игру двух лиц с нулевой суммой, заданную платежной матрицей.Сначала проводится последовательное удаление доминирующих стратегий, если таковые имеются в игре.Затем в получившейся матрице производится поиск седловой точки. Для этого находится максиминная стратегия.Затем находится минимаксная стратегия.Если они совпали, то имеется седловая точка – решение игры найдено и равно элементу платежной матрицы в седловой точке.В случае отсутствия седловой точки вплатежной матрицы, решение игры ищется в смешанных стратегиях.Если после удаления доминирующих стратегий мы получили матрицу 22, то можно применить графический метод решения, либо решить задачу по готовым формулам.Если матрица имеет размерность большую, чем 22, то решение в смешанных стратегиях производится методами линейного программирования (симлекс-метод).Если в платежной матрице имеется хотя бы один неположительныйэлемент, то перед сведением игры к задаче линейного программирования еёнужно преобразовать в матрицу, все элементы которой строго положительны.Для этого достаточно увеличить все элементы платежной матрицы на одно и тоже числогде . При таком преобразовании матрицы оптимальные стратегии игроков не изменяются.После составления задач линейного программирования, эта задачи решаются методами линейного программирования, в частности, симплекс-методом и применяя свойства двойственных задач линейного программирования.Получив оптимальное решениепостроенной задачи линейного программирования, находят цену игры (оптимальную стратегию первого игрока): Если в процессе приведения игры к задаче линейного программирования матрица увеличивалась наd,то для получения цены первоначальной игрыv*нужно уменьшить на d.Графически алгоритм можно представить следующей блок-схемой (рисунок 2).Рисунок 2 – Блок-схема алгоритма решения игры с нулевой суммойПримеры решения задачПример 1Найти функцию выигрыша для игрока A для всех чистых стратегий, если игрок B придерживается смешанной стратегии (0.15, 0.25, 0.35, 0.25).B1B2B3B4A134-33A2433-3A36-340А4-4713A555-1-1Решение:Решение проводим в среде Scilab:clcA=[34-33;433-3;6-340;-4713;55-1-1]Y=[0.15;0.25;0.35;0.25]W=A*Y[nr,nc]=size(W)answ=max(W)k=0fori=1:1:nrifW(i)==answthenk=iendenddisp('Максимальный выигрыш принесет стратегия ')disp(k)Пример 2Решение игры 22Игра не имеет седловой точкиРешение проводим в среде Scilab:clcA=[85;46]p=ones(2)q=ones(2)p(1)=(A(2,2)-A(2,1))/(A(1,1)+A(2,2)-A(1,2)-A(2,1))p(2)=(A(1,1)-A(1,2))/(A(1,1)+A(2,2)-A(1,2)-A(2,1))q(1)=(A(2,2)-A(1,2))/(A(1,1)+A(2,2)-A(1,2)-A(2,1))q(2)=(A(1,1)-A(2,1))/(A(1,1)+A(2,2)-A(1,2)-A(2,1))v=det(A)/(A(1,1)+A(2,2)-A(1,2)-A(2,1))disp('Вектор P')disp(p)disp('Вектор Q')disp(q)disp('Ценаигры v')disp(v)Найти решение игры22clcA=[31;02]b=max(A,'c')beta=min(b)dispbeta=disp(beta)a=min(A,'r')alfa=max(a)dispalfa=disp(alfa)ifalfa<>betathendisp('Седловая точка отсутствует, цена игры больше ')disp(alfa)disp('и меньше ')disp(beta)p=zeros(2)q=zeros(2)p(1)=(A(2,2)-A(2,1))/(A(1,1)+A(2,2)-A(1,2)-A(2,1))p(2)=(A(1,1)-A(1,2))/(A(1,1)+A(2,2)-A(1,2)-A(2,1))q(1)=(A(2,2)-A(1,2))/(A(1,1)+A(2,2)-A(1,2)-A(2,1))q(2)=(A(1,1)-A(2,1))/(A(1,1)+A(2,2)-A(1,2)-A(2,1))v=det(A)/(A(1,1)+A(2,2)-A(1,2)-A(2,1))disp('Вектор P')disp(p)disp('Вектор Q')disp(q)disp('Ценаигры v')disp(v)elsedisp('Решениенайдено: v=',alfa)endПример 3Найти решение игры графическим методом:Решение проводим в среде Scilab:clcA=[2230;4324];dispA=disp(A)[nr,nc]=size(A)n=ncb=max(A,'c')beta=min(b)dispbeta=disp(beta)a=min(A,'r')alfa=max(a)dispalfa=disp(alfa)ifalfa<>betathendisp('Седловая точка отсутствует, цена игры больше ')disp(alfa)disp('и меньше ')disp(beta)x=0:1:1w1=(A(1,1)-A(2,1))*x+A(2,1)w2=(A(1,2)-A(2,2))*x+A(2,2)w3=(A(1,3)-A(2,3))*x+A(2,3)w4=(A(1,4)-A(2,4))*x+A(2,4)plot(x,[w1;w2;w3;w4])legend('w1','w2','w3','w4')W=zeros(2,2)W(1,1)=A(1,3)-A(2,3)W(1,2)=-1W(2,1)=A(1,4)-A(2,4)W(2,2)=-1b=[A(2,3);A(2,4)]Z=linsolve(W,b);P=zeros(1,2)P(1)=Z(1)P(2)=1-Z(1)disp('Вектор P')disp(P)v=Z(2)Q=zeros(1,4)Q(3)=(v-A(1,4))/(A(1,3)-A(1,4))Q(4)=1-Q(3)disp('Вектор Q')disp(Q)disp('Ценаигры v')disp(v)elsedisp('Решениенайдено: v=',alfa)endПример 4Найти решение игры графическим методом:Решение проводим в среде Scilab:clcC=[15;23;32;-26];dispC=disp(C)[nr,nc]=size(C)n=ncb=max(C,'c')beta=min(b)dispbeta=disp(beta)a=min(C,'r')alfa=max(a)dispalfa=disp(alfa)ifalfa<>betathendisp('Седловая точка отсутствует, цена игры больше ')disp(alfa)disp('и меньше ')disp(beta)y=0:1:1x=0:1:1w1=(C(1,1)-C(1,2))*y+C(1,2)w2=(C(2,1)-C(2,2))*y+C(2,2)w3=(C(3,1)-C(3,2))*y+C(3,2)w4=(C(4,1)-C(4,2))*y+C(4,2)plot(x,[w1;w2;w3;w4])legend('w1','w2','w3','w4')P=zeros(1,4)Q=zeros(1,2)Q(1)=(C(3,2)-C(1,2))/(C(1,1)-C(1,2)-C(3,1)+C(3,2))Q(2)=1-Q(1)P(1)=(v-C(3,1))/(C(1,1)-C(3,1))P(3)=1-P(1)disp('Вектор P')disp(P)v=C(1,1)*Q(1)+C(1,2)*Q(2)disp('Вектор Q')disp(Q)disp('Цена игры v')disp(v)elsedisp('Решение найдено: v=',alfa)endПример 5Найти нижнюю и верхнюю цену игры, заданной матрицей: Определить седловую точку, если она существует, и найти минимаксные стратегии.Решение проводим в среде Scilab:clcA=[3-21;34-1;1-52];Aeq=A+abs(min(A))disp(A)disp(Aeq)beq=[1;1;1];c=-[1;1;1];ci=[0;0;0];[xopt,fopt,exitflag,iter,yopt]=karmarkar([],[],c,[],[0.5],[1],[],[],Aeq,beq,ci)v=1/sum(xopt)W=[1Aeq(1,2)Aeq(1,3);0Aeq(2,2)Aeq(2,3);0Aeq(3,2)Aeq(3,3)]D=inv(W)X=[011]*Ddisp('Вектор P:')disp(v*X)disp('Вектор Q:')disp(v*xopt')disp('ценаигры:')disp(v-abs(min(A)))Ответ: , оптимальные стратегии игроков , Пример 6Вывод седловой точки:functiony=get_saddle_mask(A)AR_min=min(A,'r');AC_max=max(A,'c');fori=1:size(A,1)y(i,:)=(A(i,:)==min(AC_max(i)));endfori=1:size(A,2)y(:,i)=y(:,i).*(A(:,i)==max(AR_min(i)));endendfunctionclcA=[2352;2462;-2720];disp('A=')disp(A)b=max(A,'c')beta=min(b)dispbeta=disp(beta)a=min(A,'r')alfa=max(a)dispalfa=disp(alfa)ifalfa<>betathendisp('Седловая точка отсутствует, цена игры больше ')disp(alfa)disp('и меньше ')disp(beta)elsedisp('Решениенайдено: v=',alfa)A_Saddle=get_saddle_mask(A);disp(A_Saddle)[i_saddle,j_saddle]=find(A_Saddle==1);disp('Седловаяточка')disp(i_saddle);disp(j_saddle);endЗаключениеТеория игр является достаточно сложной областью знания, применение которой и толкование полученных результатов нужно проводить с известной осторожностью. В данной курсовой работе мы рассмотрели основные понятия теории игр, и в частности класс игр двух лиц с нулевой суммой.Игры двух лиц с нулевой суммойявляются важной частью теории игр, позволяя рассматривать класс задач, в которых определяющим принципом является рациональность игроков.Для таких игр существует несколько способов решения: в чистых стратегиях, графический, в смешанных стратегиях по формулам для игр 22 и универсальный способ – сведением игры к задаче линейного программирования.Были решены примеры на игры с нулевой суммой при помощи программы scilab.Список использованной литературы1. Блекуэлл Д. Теория игр и статистических решений / Д. Блекуэлл, М. А. Гиршик ; пер. с англ. И. В. Соловьева ; под ред. Б. А. Севастьянова. – М.: Иностранная литература, 1958. – 374 с.2. Губко М.В., Новиков Д.А. Теория игр в управлении организационными системами[Текст]. 2-е издание. – М.: Институт проблем управления им. В.А. Трапезникова, 2005. – 138 с.3. Захаров, А. В. Теория игр в общественных науках: учебник для вузов / А. В. Захаров ; Нац. исслед. ун-т «Высшая школа экономики». – М. : Изд. дом Высшей школы экономики, 2015. – 304 с. ISBN 978-5-7598-1180-0.4. Матвеев В. А.Конечные бескоалиционные игры и равновесия:Учебное пособие – Псков, 2005. – 176с.ISBN 5-87854-335-45. Сигал А.В. Применение теории антагонистических игр для принятия решений в экономике // Ученые записки Крымского федерального университета имени В. И. Вернадского. Экономика и управление. 2013. №1. URL: https://cyberleninka.ru/article/n/primenenie-teorii-antagonisticheskih-igr-dlya-prinyatiya-resheniy-v-ekonomike (дата обращения: 30.05.2023).