Достаточное условие элементарной разрешимости антагонистических матричных игр (nхn)
Международная
публикация
ART 53088
Автор:
О.
А. Колтуновский
О.
А. Колтуновский Библиографическое описание статьи для цитирования:
Колтуновский
О.
А. Достаточное условие элементарной разрешимости антагонистических матричных игр (nхn) // Научно-методический электронный журнал «Концепт». –
2013. – Т. 3. – С.
431–435. – URL:
http://e-koncept.ru/2013/53088.htm.
Аннотация. Введено новое понятие стабилизирующих стратегий в матричной игре (nхn), анонсированы условия их существования и оптимальности, приведены примеры, предложена новая трактовка решения матричных игр произвольной размерности как поиска стабилизирующих стратегий, по своему смыслу наиболее полно отражающих антагонизм ситуации.
Ключевые слова:
антагонистические матричные игры(nхn), элементарная
разрешимость, теорема фон неймана, стабилизирующие стратегии, стабильный выигрыш (проигрыш) игрока
Текст статьи
1Колтуновский Олег Александровичк.ф.м.н., зав. кафедрой естственнонаучных дисциплинНЧОУ ВПО ЮжноСахалинский институт экономики, права и информатикиªЮжноСахалинскkoltoleg@rambler.ru
Достаточное условиеэлементарной разрешимости антагонистическихматричныхигр (nхn)
Аннотация: введено новое понятие стабилизирующих стратегий в матричной игре (nхn), анонсированы условия их существования и оптимальности, приведены примеры, предложена новаятрактовка решения матричных игр произвольной размерности как поиска стабилизирующих стратегий, по своему смыслу наиболее полно отражающих антагонизм ситуации.
Ключевые слова: антагонистические матричные игры(nхn), элементарная разрешимость, теорема фон Неймана, стабилизирующие стратегии, стабильный выигрыш (проигрыш) игрока.
В данной работе платежной матрицей игры является квадратная матрица А порядка n. Смешанными стратегиями Xи Y первого и второго игроков, как обычно, будем называть векторстроку
размера (1хn) и векторстолбец (nх1) соответственно, состоящие из вероятностей применения игроками своих чистых стратегий. Определение 1. Стратегии Х или Y+
называются стабилизирующими, если существуют числа v и v+
такие, что для любых стратегий Xи Y XAY= v или XAY+= v+ . Смысл стабилизации: стратегии Х
или Y+обеспечивают первому или второму игрокам постоянные выигрыш или проигрыш независимо от выбираемой соперником стратегии. Справедлива следующая простая Лемма 1. Если значение v и v+
совпадают, то они равны цене игры v: v = v = v+ Напомним, что по известной теореме фон Неймана о минимаксе существуют оптимальные равновесные стратегии игроков X* и Y* такие, чтоmaxminXAY=minmaxXAY= v=X*AY* X Y Y X При выполнении условий леммы 1 в качестве стратегий
X* и Y* можновзятьстратегии Х
и Y+ соответственно. Очевидно, что в общем случаеv ≤v ≤ v+ Для формулировки основных результатов работы образуем из матрицы А две новые матрицы следующим образом. Вычтем последний столбец из каждого предыдущего (поэлементно), а элементы последнего столбца заменим единицами, получим матрицу В. Аналогичные преобразования проведем с последней и предыдущими строками матрицы А, получимматрицуС. Справедливы следующие теоремы. Теорема 1. Если алгебраические дополнения Вin(i=1,…,n) элементов последнего столбца матрицы В все неположительны или неотрицательны и в сумме не равны 2нулю, то существуют стабилизирующая стратегия Хпервого игрока и его стабильный выигрыш v, определяемые равенствамиХ= .Теорема 2. Если алгебраические дополнения Сnj(j1,…,n)элементов последней строки матрицы С все неположительныили неотрицательны и в сумме не равны нулю, то существуют стабилизирующаястратегия Y+ второго игрока и его стабильный проигрыш v+, определяемы равенствамиY+ = .Теорема 3. Если матрицы В и С удовлетворяют условиям теорем 1 и 2 соответственно, то1)равны определители и 2)одними из оптимальных стратегий X* и Y* в антагонистической игре с платежной матрицей А являются определенные в теоремах 1 и 2 стабилизирующие стратегии игроков Х
и Y+ соответственно:Х*Х, Y*=Y+ а цена игры vравна отношению определителей. Замечание 1. Теоремы13 обратимы в том смысле , что при наличии стабилизирующих стратегий у одного или обеих игроков соответствующие алгебраические дополнения матриц В и (или) С все неположительны, либо все неотрицательны. Замечание 2.Из теоремы 3 следует, что одинаковая знакоопределенность всех упомянутых дополнений элементов матриц В и С влечет активность (применяемость) каждой стратегии игроков в оптимальном решении (X*,Y*). Обратное не верно в общем случае активность каждой стратегии в одном (!) из оптимальных решений не влечет положительность или отрицательность всех дополнений, достаточно рассмотреть матрицы с одинаковыми элементами (!), когда любые стратегии оптимальны. Вышеcказанное проиллюстрируем примерами. Пример 1. Известно [1,c.69], что для платежной квадратной матрицы А, удовлетворяющей условию МинковскогоЛеонтьева,все стратегии игроков являются активными. Пусть A=, detB= detC= 205, detA= 606, ,
3 Пример 2. Показывающий, что для игры с платежной матрицей А, удовлетворяющей условиям теоремы 3, не все стратегии игроков обязаны быть активными. Пусть(a
любое число)
А , Х*=X =Y +T=Y *=(1/2;1/2;0),v=7. Пример 3. Показывающий, что для игры с доминируемой (строго) чистой стратегией одного игрока может существовать смешанная стратегия (активизирующая и доминируемую), делающая постоянным его выигрыш или проигрыш.Пусть А , Х= ), Пример 4. Показывающий, что для игры с возможностью последовательного исключения доминируемых стратегий игроковсуществуют стабилизирующие стратегииу каждогов исходной (!) игре. Пусть
A= , X*=X= (1/2;1/2;0), Y*T= YT= (1/2; 0;1/2), v= 3/2 В следующих примерах платежная матрица А имеет седловую точку. Стабилизирующих стратегий игроков может быть от двух до ни одной. Пример 5. (две стабилизирующие стратегии).Пусть (см. также пример 2) А
,Х*=X=Y+T=Y*T=(1/2; 1/2; 0) , v=2 Пример 6. (стабилизирующая стратегия только у одного игрока).Пусть А, Y*T= (0; 1/2;1/2) , v+ = 3,5 (v=0),
В13= 10, В23= 13, В33= 17. Пример 7. (у игроковнет стабилизирующих стратегий)
4 A=,
В13= 10, В23 7, В33= 3, С31= 4, С32 = 3, С33=1
Внимание авторак данной тематике было привлечено задачей 280 [2, с.184], когда элементарные методы рассматривались на занятиях по теории игр в некоторых сахалинских вузах. О новизне, целостности и полноте решения поставленной проблемы судить читателям. Другие элементарные алгебраические методы решения антагонистических матричных игр (nхn): Лагранжа (!), Крамера, обратной матрицы собраны и изложены в [3,с. 3952], Автор без ссылок употребляет основные понятия, определения и теоремы (теорему фон Неймана), очевидно, известные любому специалисту. Автор предлагает следующую трактовку решенияантагонистических игр: всегда можно выбрать неактивные стратегии игроков таким образом, что платежная матрица А произвольного размера (mхn) сократится до квадратной матрицы А* размера (n*хn*), обладающей следующими свойствами:1)совпадают цены игр : v(А) v(А*),2)оптимальные стратегии игроков в игре с матрицей А* являются стабилизирующими, т.е. каждый, применяя подобную стратегию, добивается цели, не учитывая поведение другого игрока это ли не прямое проявление антагонизма?! Наконец, заметим, что в игре (2х2) без седловой точки равновесное (на самом деле стабилизирующее) поведение игроков является по сложившейся терминологии и минимаксным, и максиминным (!) т.е., обычно трактуемое как лучшее поведение в худшей ситуацииªявляется и худшим в лучшей ситуацииª!
Ссылки на источники1.Карлин С. Математические методы в теории игр, программировании и экономике.М.: Мир,1964.2.
Калихман И.Р. Сборник задач по математическому программированию.М.: Высш.школа,1975.3.Колобашкина Л.В. Основы теории игр: учебное пособие. М.: БИНОМ. Лаборатория знаний,2011.
5Koltunovsky OlegPhD, Head. Department eststvennonauchnyh disciplinesNCHOU VPO "YuzhnoSakhalinsk Institute of Economics, Law and Informatics"YuzhnoSakhalinskkoltoleg@rambler.ru
A sufficient condition for the solvability of the elementaryzerosum matrix games (n×n)
Abstract:We introduce a new notion of stabilizing strategies in the matrix game (n×n), announced their conditions of existence and optimality, examples, offered a new interpretation of the solutions of matrix games of arbitrary dimension as a search stabilizing strategies inmeaning is perfectly reflected antagonism situation.
Keywords: antagonistic matrix game (n×n), elementary solvability, von Neumann theorem, stabilizing strategy, stable gain (loss) player.
Достаточное условиеэлементарной разрешимости антагонистическихматричныхигр (nхn)
Аннотация: введено новое понятие стабилизирующих стратегий в матричной игре (nхn), анонсированы условия их существования и оптимальности, приведены примеры, предложена новаятрактовка решения матричных игр произвольной размерности как поиска стабилизирующих стратегий, по своему смыслу наиболее полно отражающих антагонизм ситуации.
Ключевые слова: антагонистические матричные игры(nхn), элементарная разрешимость, теорема фон Неймана, стабилизирующие стратегии, стабильный выигрыш (проигрыш) игрока.
В данной работе платежной матрицей игры является квадратная матрица А порядка n. Смешанными стратегиями Xи Y первого и второго игроков, как обычно, будем называть векторстроку
размера (1хn) и векторстолбец (nх1) соответственно, состоящие из вероятностей применения игроками своих чистых стратегий. Определение 1. Стратегии Х или Y+
называются стабилизирующими, если существуют числа v и v+
такие, что для любых стратегий Xи Y XAY= v или XAY+= v+ . Смысл стабилизации: стратегии Х
или Y+обеспечивают первому или второму игрокам постоянные выигрыш или проигрыш независимо от выбираемой соперником стратегии. Справедлива следующая простая Лемма 1. Если значение v и v+
совпадают, то они равны цене игры v: v = v = v+ Напомним, что по известной теореме фон Неймана о минимаксе существуют оптимальные равновесные стратегии игроков X* и Y* такие, чтоmaxminXAY=minmaxXAY= v=X*AY* X Y Y X При выполнении условий леммы 1 в качестве стратегий
X* и Y* можновзятьстратегии Х
и Y+ соответственно. Очевидно, что в общем случаеv ≤v ≤ v+ Для формулировки основных результатов работы образуем из матрицы А две новые матрицы следующим образом. Вычтем последний столбец из каждого предыдущего (поэлементно), а элементы последнего столбца заменим единицами, получим матрицу В. Аналогичные преобразования проведем с последней и предыдущими строками матрицы А, получимматрицуС. Справедливы следующие теоремы. Теорема 1. Если алгебраические дополнения Вin(i=1,…,n) элементов последнего столбца матрицы В все неположительны или неотрицательны и в сумме не равны 2нулю, то существуют стабилизирующая стратегия Хпервого игрока и его стабильный выигрыш v, определяемые равенствамиХ= .Теорема 2. Если алгебраические дополнения Сnj(j1,…,n)элементов последней строки матрицы С все неположительныили неотрицательны и в сумме не равны нулю, то существуют стабилизирующаястратегия Y+ второго игрока и его стабильный проигрыш v+, определяемы равенствамиY+ = .Теорема 3. Если матрицы В и С удовлетворяют условиям теорем 1 и 2 соответственно, то1)равны определители и 2)одними из оптимальных стратегий X* и Y* в антагонистической игре с платежной матрицей А являются определенные в теоремах 1 и 2 стабилизирующие стратегии игроков Х
и Y+ соответственно:Х*Х, Y*=Y+ а цена игры vравна отношению определителей. Замечание 1. Теоремы13 обратимы в том смысле , что при наличии стабилизирующих стратегий у одного или обеих игроков соответствующие алгебраические дополнения матриц В и (или) С все неположительны, либо все неотрицательны. Замечание 2.Из теоремы 3 следует, что одинаковая знакоопределенность всех упомянутых дополнений элементов матриц В и С влечет активность (применяемость) каждой стратегии игроков в оптимальном решении (X*,Y*). Обратное не верно в общем случае активность каждой стратегии в одном (!) из оптимальных решений не влечет положительность или отрицательность всех дополнений, достаточно рассмотреть матрицы с одинаковыми элементами (!), когда любые стратегии оптимальны. Вышеcказанное проиллюстрируем примерами. Пример 1. Известно [1,c.69], что для платежной квадратной матрицы А, удовлетворяющей условию МинковскогоЛеонтьева,все стратегии игроков являются активными. Пусть A=, detB= detC= 205, detA= 606, ,
3 Пример 2. Показывающий, что для игры с платежной матрицей А, удовлетворяющей условиям теоремы 3, не все стратегии игроков обязаны быть активными. Пусть(a
любое число)
А , Х*=X =Y +T=Y *=(1/2;1/2;0),v=7. Пример 3. Показывающий, что для игры с доминируемой (строго) чистой стратегией одного игрока может существовать смешанная стратегия (активизирующая и доминируемую), делающая постоянным его выигрыш или проигрыш.Пусть А , Х= ), Пример 4. Показывающий, что для игры с возможностью последовательного исключения доминируемых стратегий игроковсуществуют стабилизирующие стратегииу каждогов исходной (!) игре. Пусть
A= , X*=X= (1/2;1/2;0), Y*T= YT= (1/2; 0;1/2), v= 3/2 В следующих примерах платежная матрица А имеет седловую точку. Стабилизирующих стратегий игроков может быть от двух до ни одной. Пример 5. (две стабилизирующие стратегии).Пусть (см. также пример 2) А
,Х*=X=Y+T=Y*T=(1/2; 1/2; 0) , v=2 Пример 6. (стабилизирующая стратегия только у одного игрока).Пусть А, Y*T= (0; 1/2;1/2) , v+ = 3,5 (v=0),
В13= 10, В23= 13, В33= 17. Пример 7. (у игроковнет стабилизирующих стратегий)
4 A=,
В13= 10, В23 7, В33= 3, С31= 4, С32 = 3, С33=1
Внимание авторак данной тематике было привлечено задачей 280 [2, с.184], когда элементарные методы рассматривались на занятиях по теории игр в некоторых сахалинских вузах. О новизне, целостности и полноте решения поставленной проблемы судить читателям. Другие элементарные алгебраические методы решения антагонистических матричных игр (nхn): Лагранжа (!), Крамера, обратной матрицы собраны и изложены в [3,с. 3952], Автор без ссылок употребляет основные понятия, определения и теоремы (теорему фон Неймана), очевидно, известные любому специалисту. Автор предлагает следующую трактовку решенияантагонистических игр: всегда можно выбрать неактивные стратегии игроков таким образом, что платежная матрица А произвольного размера (mхn) сократится до квадратной матрицы А* размера (n*хn*), обладающей следующими свойствами:1)совпадают цены игр : v(А) v(А*),2)оптимальные стратегии игроков в игре с матрицей А* являются стабилизирующими, т.е. каждый, применяя подобную стратегию, добивается цели, не учитывая поведение другого игрока это ли не прямое проявление антагонизма?! Наконец, заметим, что в игре (2х2) без седловой точки равновесное (на самом деле стабилизирующее) поведение игроков является по сложившейся терминологии и минимаксным, и максиминным (!) т.е., обычно трактуемое как лучшее поведение в худшей ситуацииªявляется и худшим в лучшей ситуацииª!
Ссылки на источники1.Карлин С. Математические методы в теории игр, программировании и экономике.М.: Мир,1964.2.
Калихман И.Р. Сборник задач по математическому программированию.М.: Высш.школа,1975.3.Колобашкина Л.В. Основы теории игр: учебное пособие. М.: БИНОМ. Лаборатория знаний,2011.
5Koltunovsky OlegPhD, Head. Department eststvennonauchnyh disciplinesNCHOU VPO "YuzhnoSakhalinsk Institute of Economics, Law and Informatics"YuzhnoSakhalinskkoltoleg@rambler.ru
A sufficient condition for the solvability of the elementaryzerosum matrix games (n×n)
Abstract:We introduce a new notion of stabilizing strategies in the matrix game (n×n), announced their conditions of existence and optimality, examples, offered a new interpretation of the solutions of matrix games of arbitrary dimension as a search stabilizing strategies inmeaning is perfectly reflected antagonism situation.
Keywords: antagonistic matrix game (n×n), elementary solvability, von Neumann theorem, stabilizing strategy, stable gain (loss) player.
