Графический метод решения игры.

Основные понятия теории игр.

Теория игр – математическая теория конфликтных ситуаций. Исследуются задачи о принятии решений в условиях неопределённости, обусловленной наличием мыслящего противника (или многих противников)

Игра – математическая модель конфликтной ситуации.

Игроки – стороны, участвующие в конфликте, а выигрыш – исход конфликта.

Общая постановка задачи теории игр.

1. Принимают решения n конфликтующих сторон – игроков, интересы которых не совпадают.

2. Определены правила выбора допустимых стратегий, известных игрокам.

3. Известен набор возможных конечных состояний игры (выигрыш, ничья, проигрыш и тд.)

4. Всем участникам игры заранее известны платежи, соответствующие каждому возможному конечному состоянию.

Парная антагонистическая игра – игра, с нулевой суммой, в которую играют 2 игрока (игра, в которой выигрыш первого игрока равен проигрышу другого).

Стратегия игрока - совокупность возможных действий игрока, определяющая результат игры.

Чистая стратегия – действие игрока, определяющее результат игры.

Пусть игрок А располагает n личными чистыми стратегиями – А₁, А₂,….А_n,

а игрок В имеет m личных стратегий B₁, B₂,….B_m. Тогда игра имеет размерность n ∙ m.

Результаты игры задаём платёжной матрицей, в которой каждой i – той стратегии игрока А и j – той стратегии игрока В ставится в соответствии число а_ij., равное выигрышу игрока А и проигрышу игрока В.

Платёжная матрица – таблица, в которой каждой i-той стратегии игрока А и j-той стратегии игрока В ставится в соответствие число , равное выигрышу игрока А и проигрышу игрока В при применении ими соответствующих стратегий.

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

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

Этот элемент – седловая точка платёжной матрицы, чистая цена игры. -

Наибольший из наименьших выигрышей игрока А– максимин – нижняя цена игры –

– наихудший из выигрышей для k –той стратегии.

) – наилучший из наихудших выигрышей

Наименьший из наибольших проигрышей игрока В - минимакс - верхняя цена игры -

– наихудший (самый большой) проигрыш игрока В при использовании им стратегии В_k

– наилучший из наихудших проигрышей.

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

Теорема Неймана.

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

Активная стратегия –чистая стратегия, входящая в оптимальную смешанную с ненулевой вероятностью.

Теорема об активных стратегиях. Если один игрок придерживается своей оптимальной смешанной стратегии, то его выигрыш остаётся неизменным и равным цене игры V,если второй игрок не выходит за пределы своих активных стратегий.

Графический метод решения игры.

Если в результате вычёркивания доминирующих столбцов и доминируемых строк остаётся платёжная матрица размером два на два, игру можно решить графическим методом. Вычеркнутые стратегии считаем не активными. Они входят в оптимальную смешанную стратегию с нулевыми вероятностями. Чтобы найти вероятности оставшихся стратегий, строим оси стратегий первого игрока, откладываем на них соответствующие стратегиям выигрыши, затем соединяем точки, соответствующие проигрышам второго игрока. Из получившихся отрезков формируем «нижнюю ломаную», находим на ней максимум. Координаты найденной точки – вероятность правой стратегии и цена игры. Координаты точки пересечения осей можно найти решив систему из двух уравнений прямых. Каждое уравнение прямой удобно получить в виде уравнения прямой, проходящей через дdе точки ( и

Чтобы найти оптимальную смешанную стратегию второго игрока, совершаем аналогичные действия и ищем координаты минимума верхней ломаной. Её ордината – цена игры, а абсцисса – вероятность одной из стратегий. Вероятность второй определяем вычитая из единицы известную.

Не нашли, что искали? Воспользуйтесь поиском по сайту: