В антагонистической игре произвольной размерности выигрыш первого. Антагонистические матричные игры. Платёжная матрица, чистые стратегии, цена игры
Рассмотрим конечную парную игру с нулевой суммой. Обозначим через a выигрыш игрока A , а через b – выигрыш игрока B . Так как a = –b , то при анализе такой игры нет необходимости рассматривать оба этих числа – достаточно рассматривать выигрыш одного из игроков. Пусть это будет, например, A . В дальнейшем для удобства изложения сторону A будем условно именовать "мы ", а сторону B – "противник ".
Пусть у нас имеется m возможных стратегийA 1 , A 2 , …, A m , а у противника n возможных стратегий B 1 , B 2 , …, B n (такая игра называется игрой m×n ). Предположим, что каждая сторона выбрала определенную стратегию: мы выбрали A i , противник B j . Если игра состоит только из личных ходов, то выбор стратегий A i и B j однозначно определяет исход игры – наш выигрыш (положительный или отрицательный). Обозначим этот выигрыш через a ij (выигрыш при выборе нами стратегии A i , а противником – стратегии B j ).
Если игра содержит кроме личных случайные ходы, то выигрыш при паре стратегий A i , B j есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае естественной оценкой ожидаемого выигрыша является математическое ожидание случайного выигрыша . Для удобства будем обозначать через a ij как сам выигрыш (в игре без случайных ходов), так и его математическое ожидание (в игре со случайными ходами).
Предположим, что нам известны значения a ij при каждой паре стратегий. Эти значения можно записать в виде матрицы, строки которой соответствуют нашим стратегиями (A i ), а столбцы – стратегиям противника (B j ):
| B j A i | B 1 | B 2 | … | B n |
| A 1 | a 11 | a 12 | … | a 1n |
| A 2 | a 21 | a 22 | … | a 2n |
| … | … | … | … | … |
| A m | a m 1 | a m 2 | … | a mn |
Такая матрица называется платежной матрицей игры или просто матрицей игры .
Заметим, что построение платежной матрицы для игр с большим количеством стратегий может представлять непростую задачу. Например, для шахматной игры число возможных стратегий так велико, что построение платежной матрицы является практически неосуществимым. Однако, в принципе любая конечная игра может быть приведена к матричной форме.
Рассмотрим пример 1 антагонистической игры 4×5. В нашем распоряжении есть четыре стратегии, у противника – пять стратегий. Матрица игры следующая:
| B j A i | B 1 | B 2 | B 3 | B 4 | B 5 |
| A 1 | |||||
| A 2 | |||||
| A 3 | |||||
| A 4 |
Какой стратегией нам (т.е. игроку A ) воспользоваться? Какую бы мы ни выбрали стратегию, разумный противник ответит на нее той стратегией, для которой наш выигрыш будет минимальным. Например, если мы выберем стратегию A 3 (соблазнившись выигрышем 10), противник в ответ выберет стратегию B 1 , и наш выигрыш будет всего лишь 1. Очевидно, исходя из принципа осторожности (а он – основной принцип теории игр), надо выбирать ту стратегию, при которой наш минимальный выигрыш максимален .
Обозначим через α i минимальное значение выигрыша для стратегии A i :
и добавим к матрице игры столбец, содержащий эти значения:
| B j A i | B 1 | B 2 | B 3 | B 4 | B 5 | минимум в строках α i | |
| A 1 | |||||||
| A 2 | |||||||
| A 3 | |||||||
| A 4 | максимин |
Выбирая стратегию, мы должны предпочесть ту, для которой значение α i максимально. Обозначим это максимальное значение через α :
Величина α называется нижней ценой игры или максимином (максимум минимального выигрыша). Стратегия игрока A , соответствующая максимину α , называется максиминной стратегией .
В данном примере максимин α равен 3 (соответствующая клетка в таблице выделена серым цветом), а максиминная стратегия –A 4 . Выбрав эту стратегию, можем быть уверены, что при любом поведении противника выиграем не меньше, чем 3 (а может быть и больше при "неразумном" поведении противника"). Эта величина – наш гарантированный минимум, который мы можем себе обеспечить, придерживаясь наиболее осторожной ("перестраховочной") стратегии.
Теперь проведем аналогичные рассуждения за противника B B A B 2 – мы ему ответим A .
Обозначим через β j A B ) для стратегии A i :
β j β :
7.ЧТО НАЗЫВАЕТСЯ ВЕРХНЕЙ ЦЕННОЙ ИГРЫТеперь проведем аналогичные рассуждения за противника B . Он заинтересован в том, чтобы обратить наш выигрыш в минимум, то есть отдать нам поменьше, но должен рассчитывать на наше, наихудшее для него, поведение. Например, если он выберет стратегию B 1 , то мы ответим ему стратегией A 3 , и он отдаст нам 10. Если выберет B 2 – мы ему ответим A 2 , и он отдаст 8 и т. д. Очевидно, осторожный противник должен выбрать ту стратегию, при которой наш максимальный выигрыш будет минимален .
Обозначим через β j максимальные значения в столбцах платежной матрицы (максимальный выигрыш игрока A , или, что то же самое, максимальный проигрыш игрока B ) для стратегии A i :
и добавим к матрице игры строку, содержащую эти значения:
Выбирая стратегию, противник предпочтет ту, для которой значение β j минимально. Обозначим его через β :
Величина β называется верхней ценой игры или минимаксом (минимум максимального выигрыша). Соответствующая минимаксу стратегия противника (игрока B ), называется минимаксной стратегией .
Минимакс – это значение выигрыша, больше которого заведомо не отдаст нам разумный противник (иначе говоря, разумный противник проиграет не больше, чем β ). В данном примере минимакс β равен 5 (соответствующая клетка в таблице выделена серым цветом) и достигается он при стратегии противника B 3 .
Итак, исходя из принципа осторожности («всегда рассчитывай на худшее!»), мы должны выбрать стратегию A 4 , а противник – стратегию B 3 . Принцип осторожности является в теории игр основным и называется принципом минимакса .
Рассмотрим пример 2 . Пусть игроки A и В одновременно и независимо друг от друга записывают одно из трех чисел: либо «1», либо «2», либо «3». Если сумма записанных чисел оказывается четной, то игрок B платит игроку A эту сумму. Если сумма нечетная, то эту сумму выплачивает игрок A игроку В .
Запишем платежную матрицу игры, и найдем нижнюю и верхнюю цены игры (номер стратегии соответствует записанному числу):
Игрок A должен придерживаться максиминной стратегии A 1 , чтобы выиграть не меньше –3 (то есть чтобы проиграть не больше 3). Минимаксная стратегия игрока B – любая из стратегий B 1 и B 2 , гарантирующая, что он отдаст не более 4.
Тот же самый результат мы получим, если будем записывать платежную матрицу с точки зрения игрока В . Фактически, эта матрица получается путем транспонирования матрицы, построенной с точки зрения игрока A , и изменения знаков элементов на противоположный (так как выигрыш игрока A – это проигрыш игрока В ):
Исходя из этой матрицы следует, что игрок B должен придерживаться любой из стратегий B 1 и B 2 (и тогда он проиграет не более 4), а игрок A – стратегии A 1 (и тогда он проиграет не более 3). Как видно, результат в точности совпадает с полученным выше, поэтому при анализе не важно, с точки зрения какого игрока мы его проводим.
8 ЧТО НАЗЫВАЕТСЯ ЦЕННОВОЙ ИГРОЙ.
9.В ЧЕМ СОСТОЙТ ПРИНЦЕП МИНИМАКСА.2. Нижняя и верхняя цена игры. Принцип минимакса
Рассмотрим матричную игру типа с платежной матрицей
Если игрок А выберет стратегию А i , то все его возможные выигрыши будут элементами i -й строки матрицы С . В наихудшем для игрока А случае, когда игрокВ применяет стратегию, соответствующую минимальному элементу этой строки, выигрыш игрока А будет равен числу .
Следовательно, для получения наибольшего выигрыша, игроку А нужно выбирать ту из стратегий, для которой число максимально .
Задача принятия решения, рассматриваемая в рамках системного подхода, содержит три основные компоненты: в ней выделены система, управляющая подсистема и среда. Теперь мы переходим к изучению задач принятия решения, в которых на систему воздействует не одна, а несколько управляющих подсистем, каждая из которых имеет свои цели и возможности действий. Такой подход к принятию решений называется теоретико-игровым, а математические модели соответствующих взаимодействий называются играми . Ввиду различия целей управляющих подсистем, а также определенных ограничений на возможности обмена информацией между ними, указанные взаимодействия носят конфликтный характер. Поэтому всякая игра представляет собой математическую модель конфликта. Ограничимся случаем, когда управляющих подсистем две. Если цели систем противоположны, конфликт называется антагонистическим, а математическая модель такого конфликта называется антагонистической игрой ..
В теоретико-игровой терминологии 1-я управляющая подсистема называется игроком 1 , 2-я управляющая подсистема - игроком 2 , множества
их альтернативных действий называются множествами стратегий этих игроков. Пусть Х - множество стратегий игрока 1, Y - множество стратегий
игрока 2. Состояние системы однозначно определяется выбором управляющих воздействий подсистемами 1 и 2, то есть выбором стратегий
x ∈X и y ∈Y . Пусть F (x ,y )- оценка полезности для игрока 1 того состояния
системы, в которое она переходит при выборе игроком 1 стратегии х и
игроком 2 стратегии у . Число F (x ,y ) называется выигрышем игрока 1 в ситуации (x ,y ), а функция F - функцией выигрыша игрока 1 . Выигрыш игрока
1 одновременно является проигрышем игрока 2 , то есть величиной, которую первый игрок стремится увеличить, а второй – уменьшить. Это и есть
проявление антагонистического характера конфликта: интересы игроков полностью противоположны (то, что выигрывает один, проигрывает другой).
Антагонистическую игру естественно задать системой Г= (Х, Y, F ).
Заметим, что формально антагонистическая игра задается фактически так же, как и задача принятия решения в условиях неопределенности - если
отождествить управляющую подсистему 2 со средой. Содержательное различие между управляющей подсистемой и средой состоит в том, что
поведение первой носит целенаправленный характер. Если при составлении математической модели реального конфликта у нас есть основание (или намерение) рассматривать среду как противника, цель которого - принести
нам максимальный вред, то такую ситуацию можно представить в виде антагонистической игры. Другими словами, антагонистическую игру можно трактовать как крайний случай ЗПР в условиях неопределенности,
характеризуемый тем, что среда рассматривается как противник, имеющий цель. При этом мы должны ограничить виды гипотез о поведении среды.
Наиболее обоснованной здесь является гипотеза крайней осторожности, когда, принимая решение, мы рассчитываем на самый худший для нас возможный вариант действий среды.
Определение. Если Х и Y конечны, то антагонистическая игра называется матричной. В матричной игре можно считать, что X ={1,…,n },
Y ={1,…,m } и положить aij=F (i,j ). Таким образом, матричная игра полностью определяется матрицей A= (aij ), i =1,…,n, j =1,…,m .
Пример 3.1. Игра с двумя пальцами.
Два человека одновременно показывают один или два пальца и называют число 1 или 2, означающее, по мнению говорящего, количество
пальцев, показанное другим. После того, как пальцы показаны и числа названы, происходит распределение выигрыша по следующим правилам:
если оба угадали или оба не угадали, сколько пальцев показал их соперник, выигрыш каждого равен нулю; если угадал только один, то противник платит угадавшему сумму денег, пропорциональную общему числу показанных
Это антагонистическая матричная игра. Каждый игрок имеет четыре стратегии: 1- показать 1 палец и назвать 1, 2- показать 1 палец и назвать 2, 3-
показать 2 пальца и назвать 1, 4 - показать 2 пальца и назвать 2. Тогда матрица выигрышей A=(aij), i= 1,…, 4, j= 1,…, 4 определяется следующим образом:
a12= 2, a21 = – 2, a13=a42= –3, a24=a31= 3, a34 = – 4, a43= 4,aij= 0 в остальных случаях.
Пример 3.2. Дискретная игра типа дуэли.
Задачами дуэльного типа описывается, например, борьба двух игроков,
каждый из которых желает совершить некое единовременное действие (выброс на рынок партии товара, заявка о покупке на аукционе) и выбирает для этого время. Пусть игроки продвигаются навстречу друг другу на n шагов. После каждого сделанного шага игрок может выстрелить или не выстрелить в противника. Выстрел может быть у каждого только один. Считается, что вероятность попасть в противника, если продвинуться на k n =5 имеет вид
Теория игр - это теория математических моделей принятия решений в условиях конфликта или неопределенности. Предполагается, что действия сторон в игре характеризуются определенными стратегиями - наборами правил действий. Если выигрыш одной стороны неизбежно проводит к проигрышу другой стороны, то говорят об антагонистических играх . Если набор стратегий ограничен, то игра называется матричной и решение можно получить очень просто. Решения, получаемые с помощью теории игр, полезны при составлении планов в условиях возможного противодействия конкурентов или неопределенности во внешней среде.
Если биматричная игра является антагонистической, то матрица выигрышей игрока 2 полностью определяется матрицей выигрышей игрока 1 (соответствующие элементы этих двух матриц отличаются только знаками). Поэтому биматричная антагонистическая игра полностью описывается единственной матрицей (матрицей выигрышей игрока 1) и в соответствии с этим называется матричной.
Эта игра - антагонистическая. В ней j = х2 - О, Р, а Я (О, О] = Н(Р, Р) = -I и Я (О, Р) = Я (Р, О) = 1, или в матричной форме о р
Пусть некоторый класс игр Ж является "зеркально-замкнутым", т.е. вместе с каждой своей игрой содержит зеркально изоморфную ей (так как все игры, зеркально изоморфные данной, изоморфны друг другу , мы, в соответствии с только что сказанным, можем говорить об одной зеркально изоморфной игре). Таким классом является, например, класс всех антагонистических игр или класс всех матричных игр.
Вспоминая определение приемлемых ситуаций в антагонистической игре , получаем, что ситуация (X, Y) в смешанном расширении матричной игры является приемлемой для игрока 1 тогда и только тогда когда при любом х G х выполняется неравенство
Процесс переработки игр в симметричные им называется симметризацией. Мы опишем здесь один прием симметризации. Другой, принципиально иной вариант симметризации будет приведен в п. 26.7. Оба эти варианта симметризации в действительности применимы к произвольным антагонистическим играм , но будут сформулированы и доказаны только для матричных игр.
Таким образом, исходные термины и обозначения теории общих антагонистических игр совпадают с соответствующими терминами и обозначениями теории матричных игр.
Для конечных антагонистических (матричных) игр существование этих экстремумов было нами доказано в 10 гл. 1, и все дело заключалось в установлении их равенства или хотя бы в нахождении путей преодоления их неравенства.
Уже рассмотрение матричных игр показывает, что существуют антагонистические игры без ситуаций равновесия (и даже без ситуаций е-равно-весия при достаточно малых е > 0) в первоначально заданных стратегиях игроков.
Но каждую конечную (матричную) игру можно дополнить до бесконечной игры , например, путем предоставления в распоряжение каждого игрока любого числа доминируемых стратегий (см. 22 гл. 1). Очевидно, такое расширение множества стратегий игрока в действительности не будет означать расширения его возможностей, и фактическое его поведение в расширенной игре не должно будет отличаться от его поведения в первоначальной игре. Тем самым мы получили сразу достаточное количество примеров бесконечных антагонистических игр, не имеющих седловых точек . Имеются и примеров такого рода.
Таким образом, для реализации в бесконечной антагонистической игре принципа максимина необходимо, как и в случае конечной (матричной) игры, некоторое расширение стратегических возможностей игроков. Для 96
Как и в случае матричных игр (см. 17 гл. 1), для общих антагонистических игр важную роль играет понятие спектра смешанной стратегии , которому здесь, однако, приходится дать более общее определение.
Заметим, наконец, что множество всех смешанных стратегий игрока 1 в произвольной антагонистической игре является, как и в матричной
Уже рассмотрение антагонистических игр показывает, что большое число таких игр, и в том числе конечных, матричных игр имеет ситуации равновесия не в исходных, чистых стратегиях , а лишь в обобщенных, смешанных стратегиях . Поэтому и для общих, неантагонистических бескоалиционных игр естественно искать ситуации равновесия именно в смешанных стратегиях.
Так, например (см. рис. 3.1), мы уже отмечали, что "Исполнителю" почти не приходится сталкиваться с поведенческой неопределенностью. А вот если взять концептуальный уровень типа "Администратор", то здесь все как раз наоборот. Как правило, главный тип неопределенности, с которым приходится сталкиваться такому "нашему ЛПР" - это "Конфликт". Теперь можем уточнить, что обычно это нестрогое соперничество. Несколько реже "Администратор" принимает решения в условиях "природной неопределенности", и еще реже он сталкивается со строгим, антагонистическим конфликтом. Кроме того, столкновение интересов при принятии решений "Администратором" происходит, так сказать, "однократно", т. е. в нашей классификации он чаще разыгрывает только одну (иногда весьма небольшое количество) партий игры. Шкалы для оценки последствий чаще качественные, чем количественные. Стратегическая самостоятельность у "Администратора" довольно ограничена. Принимая во внимание сказанное, можно утверждать, что проблемные ситуации подобного масштаба чаще всего приходится анализировать с помощью бескоалиционных неантагонистических би-матричных игр, причем, в чистых стратегиях .
Принципы решения матричных антагонистических игр
В итоге будет разумно ожидать, что в описанной выше игре противники будут придерживаться избранных стратегий. Матричная антагонистическая игра , для которой max min fiv = min max Aiy>
Однако далеко не все матричные антагонистические игры являются вполне определенными, и в общем случае
Таким образом, в общем случае для решения матричной антагонистической игры размерностью /ихл необходимо решить пару двойственных задач линейного программирования , в результате чего находится набор оптимальных стратегий , / и цена игры v.
Как определяется матричная антагонистическая игра двух лиц
Какие есть методы упрощения и решения матричных антагонистических игр
В случае игры двух лиц естественно считать их интересы прямо противоположными - игра антагонистическая . Таким образом, выигрыш одного игрока равен проигрышу другого (сумма выигрышей обоих игроков равна нулю, отсюда и название - игра с нулевой суммой). Будем рассматривать игры, в которых у каждого игрока имеется конечное число альтернатив. Функция выигрыша для такой игры двух лиц с нулевой суммой может быть задана в матричной форме (в виде платежной матрицы).
Как уже отмечалось, конечная антагонистическая игра называется матричной.
МАТРИЧНЫЕ ИГРЫ - класс антагонистических игр, в которых участвуют два игрока, причем каждый игрок располагает конечным числом стратегий. Если один игрок имеет т стратегий, а второй - п, то можно построить матрицу игры размерностью тхп. М.и. могут иметь седловую точку , но могут и не иметь ее. В последнем случае
В качестве основного допущения в теории игр предполагается, что каждый игрок стремится обеспечить себе максимально возможный выигрыш при любых действиях партнера. Предположим, что имеется конечная антагонистическая игра с матрицей выигрышей первого игрока и соответственно матрицей выигрышей второго игрока . Пусть Игрок 1 считает, что какую бы стратегию он ни выбрал, Игрок 2 выберет стратегию, максимизирующую его выигрыш, и тем самым минимизирующую выигрыш Игрока 1.
Таким образом, Игрок 1 выбирает i
Игрок 2 точно также стремится обеспечить себе наивысшую величину выигрыша (или, что эквивалентно, наименьшую величину проигрыша) вне зависимости от выбранной стратегии противника. Его оптимальной стратегией будет столбец Н 0 с наименьшим максимальным платежом. Таким образом, Игрок 2 выберет j -ю стратегию, которая является решением задачи
В итоге, если Игрок 1 придерживается избранной стратегией (называемой максиминнной стратегией ), его выигрыш в любом случае будет меньше максиминного значения (называемого «нижней ценой игры» ), т.е.
Соответственно, если Игрок 2 придерживается своей минимаксной стратегии, то его проигрыш будет не больше максиминного значения (называемого «верхней ценой игры» ), т.е.
В случае, когда верхняя цена игры равна нижней, т.е. = , оба игрока получают свои гарантированные платежи, а значение h ij * называется ценой игры .
Элемент матрицы h ij матрицы выигрышей, соответствующей стратегиям, называется седловой точкой матрицы Н .
В случае, если цена антагонистической игры равна 0, игра называется справедливой .
Рассмотрим игру, в которой Игрок 1 располагает двумя стратегиями, а Игрок 2 – тремя. Матрица выигрышей Игрока 1 имеет вид:
Замечание . Поскольку мы рассматриваем пример антагонистической игры, то матрица выигрышей Игрока 2 будет Н 2 =-Н 1 .
Игрок 1 рассчитывает, что если он выберет первую стратегию (т.е. первую строку матрицы Н 1 ), то противник выберет свою вторую стратегию (т.е. второй столбец) так, что выигрыш будет равен 1 . Если же он выбирает вторую стратегию, то противник может выбрать первую стратегию, так что выигрыш будет равен -1.
Проанализировав полученные значения: Игрок 1 останавливается на своей первой стратегии, которая обеспечивает ему максимальный гарантированный выигрыш, равный 1.
Точно также Игрок 2 рассматривает свои наихудшие варианты, когда противник выбирает первую или вторую стратегии, или когда противник выбирает вторую стратегию, когда Игроком 2 выбран третий столбец. Этим варианты соответствуют максимальным значениям столбцов 2, 1 и 6.
Взяв минимальные значения этих максимумов, Игрок 2 останавливается на своей второй стратегии, при которой его проигрыш минимален и равен :
Следовательно, в этой игре существуют совместные выборы стратегий, те. Е
Следовательно в этой игре разумно ожидать, что противники будут придерживаться избранных стратегий. Матричная антагонистическая игра, для которой 
- называется вполне определенной, или игрой имеющей решение в чистых стратегиях.
Однако не все матричные антагонистические игры являются вполне определенными.
Игры, в которых выполняется строгое неравенство, называется не полностью определенными играми (или играми, не имеющими решения в чистых стратегиях).
Рассмотрим пример такой игры:
Для этой игры .
В итоге если игроки будут следовать предложенным выше правилам, то Игрок 1 выберет стратегию 1 и будет ожидать, что Игрок 2 выберет стратегию 2, при которой проигрыш равен -2, в то время как Игрок 2 изберет стратегию 3 и будет ожидать что Игрок 1 выберет стратегию 2 с выигрышем равным 4.
Однако если Игрок 2 выберет свою третью стратегию, то Игрок 1 поступит правильнее, выбирая вторую стратегию, а не первую стратегию. Аналогично, если Игрок 1 выберет первую стратегию, Игроку 2 выгоднее выбрать вторую стратегию, а не третью. По всей видимости, в играх подлобного типа принцип решения в чистых стратегиях оказывается непригодным.
В описанной ситуации игрокам становится важно, чтобы противник не угадал, какую стратегию он будет использовать. Для осуществления этого плана игрокам следует пользоваться так называемой смешанной стратегией.
По существу, смешанная стратегия игрока представляет собой схему случайного выбора чистой стратегии. Математически ее можно представить как вероятностное распределение на множестве чистых стратегий данного игрока. В итоге вектор , где соответствует вероятности применения Игроком 1 -той стратегии и , задает смешанную стратегию этого игрока. Аналогично определяется смешанная стратегия у Игрока 2 
.
Мы будем предполагать использование игроками их смешанных стратегий независимым, так что вероятность, с которой Игрок 1 выбирает тую стратегию, а Игрок 2 - - ю, равна . В этом случае платеж . Суммируя по и , найдем математическое ожидание выигрыша Игрока 1:
или матричных обозначениях
На множестве смешанных стратегий Игрок 1, стремящийся достичь наибольшего из гарантированных выигрышей, выбирает вектор вероятностей так, чтобы получить максимум минимальных значений ожидаемых выигрышей, т.е. он решает задачу:
.
Аналогично целью Игрока 2 является достижение минимума максимальных значений своих проигрышей, т.е. он решает задачу
.
Фундаментальным результатом теории игр является так называемая Теорема о минимаксе, которая утверждает, что сформулированные задачи Игрока 1 и Игрока 2 всегда имеют решение для любой матрицы выигрышей , и кроме того, .
Как и для вполне определенных игр, стратегия Игрока 1 называется Максиминной стратегией , стратегия Игрока 2 - минимаксной стратегией, значение - ценой игры; в случае, когда игра называется справедливой.
Очевидным следствием из Теоремы о минимаксе является соотношение:
.
которое означает, что никакая стратегия Игрока 1 не позволит выиграть ему сумму большую, чем цена игры, если Игрок 2 применит свою минимаксную стратегию, и никакая стратегия Игрока 2 не даст возможности проиграть ему суму меньшую, чем цена игры, если Игрок 1 применяет свою максиминную стратегию.
Это верно также и для чистых стратегий, как для частного случая смешанных стратегий. (Т.к. чистая стратегия – это стратегия, используемая с вероятностью 1): Использование любой чистой стратегии, в случае если противник использует свою оптимальную стратегию, не позволяет выиграть больше (проиграть меньше) цены игры.
Это факт часто используют для разработки конкретных алгоритмов решения антагонистических матричных игр.
Вычисление оптимальных стратегий значительно усложняется с ростом числа стратегий. Для поиска оптимальных стратегий можно использовать несколько подходов.
Для уменьшения размерности игры используется доминирование строк и столбцов. Обычно говорят, что -я стока матрицы доминирует -ю строку (т. е. одна чистая строка доминирует другую), если для всех , хотя бы для одного .
Аналогично -й столбец доминирует -й столбец, если для всех , хотя бы для одного .
Смысл этого определения состоит в том, что доминирующая стратегия никогда не хуже, а в некоторых случаях даже лучше, чем доминируемая стратегия. Отсюда, важный вывод – игроку нет необходимости использовать доминируемую стратегию. Это позволяет на практике все доминируемые строки и столбцы отбросить, что позволит уменьшить размеры матрицы (заметим, что этот подход может использоваться также при поиске решения в чистых стратегиях).
Пример. Рассмотрим игру со следующей матрицей:
|
Исключение второй строки приводит к матрице: третий столбец в этой урезанной матрице доминирует второй, и исключение второго столбца дает: .
В итоге, если можно найти решение для полученной игры, то его легко использовать для решения исходной игры, просто прописав исключенным строкам и столбцам нулевые вероятности.
Другой метод упрощения матрицы основан на свойстве, согласно которому аффинное преобразование матрицы платежей (т.е. преобразование всех элементов матрицы по правилу , где ) не изменяет решения игры; кроме того, цена преобразованной игры может быть получена из цены первоначальной игры по такому же правилу: . Это означает, что для задания игры в принципе безразлично, в каких единицах измеряются выигрыши (в рублях или долларах) прибавление (вычитание) некоторой фиксированной суммы изменит на такую же сумму выигрыш (проигрыш) каждого из игроков не меняя решение игры.
Это свойство может быть использовано для упрощения и придания наглядности матрице выигрышей (использовано по аналогии с операциями над матрицами – умножение матрицы на постоянное число, сложение и вычитание строк, кроме того, это свойство позволяет любую матричную антагонистическую игру сделать справедливой, для этого необходимо вычислить цену игры из всех элементов матрицы выигрышей).
Кроме того может быть использован графический способ для решения игры (и вообще игр или ).
Например, матрица выигрышей имеет вид: .
Пусть Игрок 1 выбирает свою первую стратегию с вероятностью , а вторую с вероятностью . Если Игрок 2 выбирает свою первую стратегию, то (из первого столбца матрицы) математическое ожидание для Игрока 1 будет равно . Если Игрок 2 выбирает свою вторую стратегию, то в соответствии со вторым столбцом матрицы: .
Каждое из этих уравнений может быть изображено графически отрезком прямой линии в области на графике с координатами и .
Тесты для итогового контроля
1. Антагонистическая игра может быть задана:
а) множеством стратегий обоих игроков и седловой точкой.
б) множеством стратегий обоих игроков и функцией выигрыша первого игрока.
2. Цена игры существует для матричных игр в смешанных стратегиях всегда.
а) да.
3.Если в матрице выигрышей все столбцы одинаковы и имеют вид (4 5 0 1), то какая стратегия оптимальна для 1-го игрока?
а) первая.
б)вторая.
в)любая из четырех.
4.Пусть в матричной игре одна из смешанных стратегий 1-го игрока имеет вид (0.3, 0.7), а одна из смешанных стратегий 2-го игрока имеет вид (0.4, 0, 0.6). Какова размерность этой матрицы?
а) 2*3.
в) другая размерность.
5. Принцип доминирования позволяет удалять из матрицы за один шаг:
а) целиком строки.
б) отдельные числа.
6.В графическом методе решения игр 2*m непосредственно из графика находят:
а) оптимальные стратегии обоих игроков.
б) цену игры и оптимальные стратегии 2-го игрока.
в) цену игры и оптимальные стратегии 1-го игрока.
7.График нижней огибающей для графического метода решения игр 2*m представляет собой в общем случае:
а) ломаную.
б) прямую.
в) параболу.
8. В матричной игре 2*2 две компоненты смешанной стратегии игрока:
а) определяют значения друг друга.
б) независимы.
9. В матричной игре элемент aij представляет собой:
а) выигрыш 1-го игрока при использовании им i-й стратегии, а 2-м – j-й стратегии.
б) оптимальную стратегию 1-го игрока при использовании противником i-й или j-й стратегии.
в) проигрыш 1-го игрока при использовании им j-й стратегии, а 2-м – i-й стратегии.
10.Элемент матрицы aij соответствует седловой точке. Возможны следующие ситуации:
а) этот элемент строго меньше всех в строке.
б) этот элемент второй по порядку в строке.
11. В методе Брауна-Робинсон каждый игрок при выборе стратегии на следующем шаге руководствуется:
а) стратегиями противника на предыдущих шагах.
б) своими стратегиями на предыдущих шагах.
в) чем-то еще.
12. По критерию математического ожидания каждый игрок исходит из того, что:
а) случится наихудшая для него ситуация.
в) все или некоторые ситуации возможны с некоторыми заданными вероятностями.
13. Пусть матричная игра задана матрицей, в которой все элементы отрицательны. Цена игры положительна:
б) нет.
в) нет однозначного ответа.
14. Цена игры - это:
а) число.
б) вектор.
в) матрица.
15.Какое максимальное число седловых точек может быть в игре размерности 5*5 (матрица может содержать любые числа) :
16. Пусть в матричной игре размерности 2*3 одна из смешанных стратегий 1-го игрока имеет вид (0.3, 0.7), а одна из смешанных стратегий 2-го игрока имеет вид (0.3, x, 0.5). Чему равно число x?
в) другому числу.
17. Для какой размерности игровой матрицы критерий Вальда обращается в критерий Лапласа?
в)только в других случаях.
18. Верхняя цена игры всегда меньше нижней цены игры.
б) нет.
б) вопрос некорректен.
19. Какие стратегии бывают в матричной игре:
а) чистые.
б) смешанные.
в) и те, и те.
20. Могут ли в какой-то антагонистической игре значения функции выигрыша обоих игроков для некоторых значений переменных равняться 1?
а) всегда.
б) иногда.
в) никогда.
21.Пусть в матричной игре одна из смешанных стратегий 1-го игрока имеет вид (0.3, 0.7), а одна из смешанных стратегий 2-го игрока имеет вид (0.4, 0.1,0.1,0.4). Какова размерность этой матрицы?
в) иная размерность.
22. Принцип доминирования позволяет удалять из матрицы за один шаг:
а) целиком столбцы,
б) отдельные числа.
в) подматрицы меньших размеров.
23. В матричной игре 3*3 две компоненты смешанной стратегии игрока:
а) определяют третью.
б) не определяют.
24. В матричной игре элемент aij представляет собой:
а) проигрыш 2-го игрока при использовании им j-й стратегии, а 2-м – i-й стратегии .
б) оптимальную стратегию 2-го игрока при использовании противником i-й или j-й стратегии,
в) выигрыш 1-го игрока при использовании им j-й стратегии, а 2-м – i-й стратегии,
25. Элемент матрицы aij соответствует седловой точке. Возможны следующие ситуации:
а) этот элемент больше всех в столбце.
б) этот элемент строго больше всех по порядку в строке.
в) в строке есть элементы и больше, и меньше, чем этот элемент.
26. По критерию Вальда каждый игрок исходит из того, что:
а) случится наиболее плохая для него ситуация.
б) все ситуации равновозможны.
в) все ситуации возможны с некоторыми заданными вероятностями.
27. Нижняя цена меньше верхней цены игры:
б) не всегда.
в) никогда.
28. Сумма компонент смешанной стратегия для матричной игры всегда:
а) равна 1.
б) неотрицательна.
в) положительна.
г) не всегда.
29. Пусть в матричной игре размерности 2*3 одна из смешанных стратегий 1-го игрока имеет вид (0.3, 0.7), а одна из смешанных стратегий 2-го игрока имеет вид (0.2, x, x). Чему равно число x?
