Состязательные задачи. Решение игры 2-х лиц

Моделируют ситуацию неопределенности, причем неопределенность обусловлена наличием конфликта. Конфликт имеет место, если в операции участвуют две и более оперирующих сторон, преследующих несовпадающие цели. Неопределенность у одной из сторон возникает в связи с неизвестностью линии поведения других сторон, в то время как результат зависит от поведения всех участников операции. Игра характеризуется известным количеством участников - игроками, правилами игры, множеством возможных ситуаций и соответсв. им выигрышами или проигрышами (платежами). По методу ведения различают дискретные игры (игроки совершают поочередные ходы) и непрерывные (игроки действуют непрерывно - преследования). По количеству ходов, по числу стратегий выделяют игры с конечным и бесконечным числом шагов/стратегий. По форме платы различают игры с нулевой суммой, когда выигрыши одних равны проигрышам других (цели противоположные - антагонистические), и игры с ненулевой суммой (выигрыши и проигрыши не совпадают). В зависимости от числа игроков говорят об играх . Дискретная игра 2 лиц с ненулевой суммой - биматричная, каждой ситуации соответствует два платежа (по 1 для каждого

игрока).

стратегии А	стратегии игрока

Простейшей является дискретная игра двух лиц с нулевой суммой. Представляется платежной матрицей, в которой отражены стратегии игроков и платежи, имеющие противоположный смысл для игроков:

u_ij - платеж, соответствующий ситуации A_iB_j. Будем считать, что u_ij имеет смысл выигрыша игрока A, для B это проигрыш. Решение игры – опр-е оптимального поведения каждого из игроков и соответст-го результата - цены игры. Метод решения основан на принципе гарант. результата, применяется обоими игроками. Каждый из игроков рассчитывает на наихудший для себя вариант. Игрок A - на основе максимина , B - на основе минимакса. - верхняя цена игры, игрок B проиграет не более этой величины, если будет вести себя оптимально, - гарантированный проигрыш игрока B, для A это макс возможный выигрыш. Нижняя цена игры есть гарантированный выигрыш игрока A, при оптимальном поведении он выиграет не меньше, для игрока B это минимально возможный проигрыш. , . Если , то игра имеет решение в области чистых стратегий - каждый из игроков будет придерживаться только одной своей стратегии, оптимальная стратегия будет применяться с вероятностью 1, а все остальные - с вероятностью 0. Такое решение соответствует седловой точке платежной матрицы. Когда u_ij - выигрыш игрока A, в седловой точке значение u_ij^*= иявляется наибольшим в столбце и наименьшим в строке. Т.о, при наличии седловой точки решение всегда находится в области чистых стратегий, а оптимальные стратегии - это стратегии, на пересечении которых лежит седловая точка. Пример: Находя максимум в последнем столбце, получаем нижнюю цену игры 4, 4. 4, а оптимальными стратегиями являются A ₃ и B ₂. На их пересечении находится седловая точка платежной матрицы. При этом A гарантирует себе выигрыш не меньше 4, а игрок B проиграет не более 4, и каждому из игроков невыгодно отклоняться от найденных стратегий.

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

Пример:

и, , а решение лежит в области смешанных стратегий. Платежная матрица не имеет седловой точки. Если один из игроков имеет только две стратегии, решение можно найти графически. Для этого проводятся две оси ординат на расстоянии, которое принимается за единицу. На этих осях откладываются платежи игрока, имеющего две стратегии. Зафиксируем стратегию B ₁. Если же применять стратегию A ₁ с вероятностью , а стратегию A ₂ с вероятностью , то ожидаемый выигрыш составит 6 x ₁ + 5(1- x ₁) = 5 +x ₁. Выигрыш зависит от вероятности линейно.

Аналогично строятся прямые, соответствующие выигрышам игрока А при фиксации других стратегий игрока B. Гарантированные выигрыши игрока A лежат на нижней грани, выделенной жирной линией. Игрок стремится к макс гарантированному выигрышу (т М). Оптимальное решение для игрока A состоит в применении стратегии A ₁ с вероятностью и стратегии A ₂ с вероятностью . Цена игры равна 49/11. растет от 0 до 1 справа налево, а - наоборот. Для игрока В активные стратегии определяются т M - это стратегии B ₂и B ₃. Вероятности применения этих стратегий находятся с помощью графика, аналогичного приведенному, но оси ординат должны соответствовать B ₂и B ₃. Оптимальное решение в области смешанных стратегий может быть реализовано только при многократном повторении игры, а цена игры есть соотв. оптимальному поведению мат. ожидание результата (на один розыгрыш).

М сократить число стратегий одного из игроков за счет отбрасывания доминируемых стратегий, стратегий, которые заведомо не будут активными в оптимальном решении-> попарные сравнения стратегий одного из игроков. Та стратегия, на которой платежи не лучше, чем на другой, для всех стратегий противника и хотя бы для одной хуже, является доминируемой и может быть отброшена. Если число стратегий у одного из игроков сократится до двух, игра решается графически. В общем случае решение в области смешанных стратегий находится методами линейного программирования.

Применяются модели коалиционных и кооперативных игр. Так, в игре лиц ( 2) с нулевой суммой в процессе игры могут образовываться объединения части игроков против остальных, если такая коалиция улучшает результаты всех объединившихся игроков, что обеспечивается побочными платежами со стороны инициатора объединения. Кооперативная игра может улучшать результаты всех игроков за счет предварительных договоренностей с заключением обязывающих соглашений (в играх с ненулевой суммой). Кооперация возможна и в игре двух лиц.

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