Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Смешанные стратегии. Оптимальные смешанные стратегии, цена игры, доминирующие стратегии, методы упрощения платежных матриц

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

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

Платежная матрица

Рассмотрим игру, в которой игрок А имеет М стратегий, а игрок Б – Н стратегий. Такая игра называется М на Н.

Наши стратегии будем обозначать А1, А2, …, противника – Б1,Б2,…. Предположим, что каждая сторона выбрала определенную стратегию: мы – Аi, противник –Бj.

Выбор стратегии однозначно определяет исход игры. Обозначим выигрыш аij.

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

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

li=mina_ij- минимально возможный выигрыш игрока А при стратегии

Ai(i=1,n)

gi=maxa_{ij –} макс возможный проигрыш игрока Б при стратегии

Bj(j=1,n)

g=min max a_ij

jI

l=maxmina_ij – нижняя чистая цена игры

Ij

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

Число g показывает, какой минимальный гарантированный проигрыш может быть у игрока Б, при правильном выборе своих чистых стратегий независимо от действий игрока А.

l<=g

Если l=g, то игра имеет седловую точку и чистую цену игры.

(А*,Б*, v) – решения игры.

Для игр без седловых точек оптимальные стратегии игроков находятся в области смешенных стратегий. Смешенной стратегиейигрока А называют вектор р=(р1,р2…), где рi>=0 (i=1,n)

Сумма pi =1.

Смешенная стратегия игрока Б называется q=(q1,q2…), qi>=0 (j=1,n).

Вероятности, с которыми игроки А и Б выбирают свои чистые стратегии Аiи Бj в ходе игры.

При использовании смешенных стратегий игра приобретает случайный характер. Случайной так же становиться величина выигрыша игрока А(проигрыша Б). Эта величина является функцией смешанных стратегий вектора pиq и определяется по формуле:

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

Если в платежной матрице элементы К-ой строки не меньше соответствующих S-ой строки.

Доминирует – Аkj>=Asj ->Ak dominir As

Частным случаем доминирование стратегий является дублирование стратегий(если стратегии одинаковы, то доминирует любая из них).