Элементы теории игр

Пример 1

 
 
 
Седловой  точкой является пара (iо = 3; jо = 1), при которой u = =  = 2. 
 
Заметим, что хотя выигрыш в ситуации (3;3) также равен 2 = = , она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца.

Пример 2

 
 
 
 
 
Из  анализа матрицы выигрышей видно, что  , т.е. данная матрица не имеет седловой точки. Если игрок 1 выбирает свою чистую максиминную стратегию i = 2, то игрок 2, выбрав свою минимаксную j = 2, проиграет только 20. В этом случае игроку 1 выгодно выбрать стратегию i = 1, т.е. отклониться от своей чистой максиминной стратегии и выиграть 30. Тогда игроку 2 будет выгодно выбрать стратегию j = 1, т.е. отклониться от своей чистой минимаксной стратегии и проиграть 10. В свою очередь игрок 1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а игрок 2 ответит выбором 2-й стратегии и т.д.

 

http://gendocs.ru/v1735/?cc=3

 

 

 

 

 

Матричные игры в смешанных стратегиях

Если  седловая точка отсутствует, решение  игры проводят в смешанных стратегиях и решают следующими методами:

1. Решение игры через систему уравнений.  
   Если задана квадратная матрица nxn (n=m), то вектор вероятностей можно найти, решив систему уравнений. Этот метод используется не всегда и применим только в отдельных случаях (если матрица 2x2, то решение игры получается практически всегда). Если в решении получаются отрицательные вероятности, то данную систему решают симплекс-методом.
2. Решение игры графическим методом.  
   В случаях, когда n=2 или m=2, матричную игру можно решить графически.
3. Решение матричной игры симплекс-методом.  
   В этом случае матричная игра сводится к задаче линейного программирования.

 

http://math.semestr.ru/games/index.php

 

 

Если  игра имеет седловую точку, то оптимальными для игроков будут соответственно максиминная и минимаксная стратегии, а чистой ценой игры – седловой элемент платежной матрицы. Если игра седловой точки не имеет, то решение  игры затрудняется. Проиллюстрируем  это на простом числовом примере  такой игры с двумя стратегиями  у каждого игрока и платежной  матрицей:

2 9

6 3

В данном случае  =3, а  =6. Таким образом, игрок А может выиграть не менее 3, а игрок В может ограничить свой проигрыш (выигрыш игрока А) шесть единицами. Область между 3 и 6 остается как бы нейтральной, и каждый игрок может попытаться улучшить свой результат за счет этой области. Но как это сделать? Если игроки применяют свои наиболее предпочтительные стратегии А2 и В1, то игрок А выигрывает, а игрок В проигрывает 6 единиц. Это, конечно, устраивает игрока А, но невыгодно игроку В. Поэтому, если игрок В заметит, что игрок А предпочтительно использует свою стратегию А2, то он может перейти на свою стратегию В2 и понизить выигрыш игрока А до 2 единиц. В свою очередь игрок А может в ответ перейти на свою первую стратегию и выиграть уже 9 единиц. В свою очередь, узнав об этом, игрок В может снова сменить стратегию и понизить выигрыш игрока А до 2 единиц.

Из  этих рассуждений ясно, что игрокам  надо так выбирать свои чистые стратегии  в очередной партии, чтобы партнер  не догадался об очередном выборе. Этого можно добиться, используя  случайный выбор, однако вероятности  выбора стратегий необходимо определить. Анализ игры без седловой точки показывает, что игрок А выигрывает больше максимина  , получаемого им при максиминной стратегии, если в ходе игрыбудет пользоваться случайным образом не одной, а несколькими чистыми стратегиями, т. е. будет случайным образом смешивать чистые стратегии или говорят применять смешанную стратегию. Аналогично игрок В проиграет меньше минимакса  , выплачиваемого им игроку А при минимаксной стратегии, если он будет использовать свою смешанную стратегию.

Обозначим через p1, …, pm вероятности, с которыми игрок А использует в ходе игры свои чистые стратегии А1, ….Am, а через q1, …, qn аналогичные величины для  игрока В. Очевидно, должны выполняться  условия неотрицательности:

И условия  нормировки:

Упорядоченные множества  P1, …, pm и  Q1, …, qn полностью определяют характер действий игроков и называются смешанными стратегиями игроков А и В соответственно. Очевидно, игроки располагают бесконечным множеством смешанных стратегий.

Так как каждый раз применение игроком  одной чистой стратегии исключает  применение другой, то чистые стратегии  являются несовместными событиями. Кроме того, они являются единственными возможными событиями.

Чистая  стратегия есть частный случай смешанной  стратегии. Действительно, если в смешанной  стратегии какая-либо I-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта I-Я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

 

http://matica.org.ua/teoriya-igr-issledovanie-operatsiy/1-3-2-reshenie-matrichnich-igr-v-smeshannich-strategiyach

 

 

 

Пример   

Задержание  подозреваемого.

Рассмотрим  дилемму оперативного работника, направляющегося  на задержание подозреваемого, с точки  зрения теории игр. Опишем конфликтную  ситуацию, несколько упростив ее. Оперуполномоченный может пойти на задержание один, а может вызвать группу захвата. Его противник, предварительного не зная  о силах и средствах милиции, в свою очередь, может оказывать или не оказывать сопротивление представителям правоохранительных органов.

Вариант, при котором оперативник пойдет один и своими силами сможет задержать  преступника, оценивается им как  выигрыш в 3 единицы (очень хорошо). Также оценивается и тот случай, когда преступник окажет сопротивление  и решение вызова группы захвата  окажется вполне своевременным. Если оперативник  предпримет попытку задержания в  одиночку, не расчитав свои силы, и данная попытка не увенчается успехом ввиду сопротивления задерживаемого, то оперуполномоченный проигрывает 1 единицу. Т.е. его выигрыш составит –1. При неэффективном вызове группы захвата оперативник выигрывает всего 1 единицу.

Заметим, что введенные платежи, на основании  которых будет получено решение  конфликта, оценены нами достаточно условно. При описании конкретного  случая нужно стремится задать их, обосновывая количественно, к примеру, с помощью теории вероятностей. Теория игр на этот счет никаких рецептов не дает. Она может лишь сказать, как поступить в случае с уже  заданной платежной матрицей, чтобы  выиграть как можно больше или  проиграть как можно меньше вне  зависимости от действий противника.

Платежная матрица в этом случае будет такова:

.

Наибольшее  значение минимумов строк равно 1. Это соответствует второй стратегии  оперативника. Наименьшее значение максимумов столбцов – 3 (впрочем, максимумы столбцов в этой матрице совпадают). Мы видим, что нижняя и верхняя цена игры не равны друг другу. Значит, платежная  матрица не имеет седловую точку и конфликт не может быть разрешен в чистых стратегиях. Рассмотренный выше способ решения игры уже не применим. Если оперуполномоченный применит вторую стратегию, то это гарантирует ему выигрыш в 1 единицу. Но взять эту стратегию в качестве чистой, т.е. всякий раз при задержании подозреваемого вызывать группу захвата, было бы, безусловно, неэффективно. Это означало бы «стрельбу из пушки по воробьям». Как интуитивно понятно, оперативник должен применять обе стратегии в зависимости от предполагаемой ситуации. Естественно, что в каждом конкретном случае он реализует какую-то одну из них. И теория игр не дает рецепта по поводу того, как поступать оперативнику в отдельном случае. Она, как мы увидим дальше, лишь определяет вероятности применения стратегий игроками. Эти вероятности зависят от условий задачи, т.е. тех платежей, которые были заданы изначально.

 

http://posobie-mii.narod.ru/Glava10.5.htm

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Связь между теорией игр и линейным программированием

Первоначально развитие теории стратегических матричных  игр осуществлялось параллельно  и независимо от линейного программирования. Позже было установлено, что стратегическая матричная игра может быть сведена к паре двойственных задач линейного программирования. Решив одну из них, получаем оптимальные стратегии игрока 1; решив другую, получаем оптимальные стратегии игрока 2. Математическое соответствие между стратегическими матричными играми и линейным программированием было установлено Дж. Б. Данцигом, сформулировавшим и доказавшим в 1951 г. основную теорему теории игр

http://rudocs.exdat.com/docs/index-59691.html?page=20

 

Теорема. Каждая матричная игра с нулевой суммой всегда имеет решение в смешанных стратегиях, т.е. существуют такое число v и такие стратегии U* и W* игроков 1 и 2 соответственно, что выполняются неравенства:

Поясним смысл доказываемых неравенств: если игрок 1 отклоняется от своей оптимальной стратегии, то его выигрыш не увеличивается по сравнению с ценой игры; если от своей оптимальной стратегии отклоняется игрок 2, то по сравнению с ценой игры его проигрыш не уменьшается.