40108

Функция выигрыша в матричных играх без седловой точки. Смешанные и оптимальные смешанные стратегии. Метод сведения решения матричных игр к задаче линейного программирования

Доклад

Менеджмент, консалтинг и предпринимательство

Функция выигрыша в матричных играх без седловой точки. Парная игра с нулевой суммой задается формально матрицей игры матрицей А = {ij} элементы которой определяют выигрыш первого игрока и проигрыш второго если первый игрок выберет iю стратегию а второй jю стратегию. Пара i0j0 называется седловой точкой матрицы решением игры если выполняются условия: mx по столбцу I игрок min по строке II игрок Значение функции выигрыша в седловой точке называется ценой игры. Тогда выигрыш первого игрока при условии что он выбирает...

Русский

2013-10-15

119.5 KB

24 чел.

23. Функция выигрыша в матричных играх без седловой точки. Смешанные и оптимальные смешанные стратегии. Метод сведения решения матричных игр к задаче линейного программирования.

Матричной называют парную игру с нулевой суммой при условии, что каждый игрок имеет конечное число чистых стратегий. Парная игра с нулевой суммой задается формально матрицей игры – матрицей А = {aij}, элементы которой определяют выигрыш первого игрока (и проигрыш второго), если первый игрок выберет i-ю стратегию, а второй - j-ю стратегию. Пара  (i0,j0) называется седловой точкой матрицы (решением игры), если выполняются условия:  (max по столбцу (I игрок), min по строке (II игрок))

Значение функции выигрыша в седловой точке называется ценой игры.

Седловая точка обеспечивает равновесие в игре, но она существует не всегда (н-р, в 2-х пальцевой игре Морра ее нет). В случае, когда нет седловой точки игрокам не выгодно пользоваться одной и той же стратегией, так как в этом случае противник будет выбирать наилучший для себя вариант. Тогда выбор стратегий должен быть вероятностным – выбор осуществляется случайным образом с определенными вероятностями.

Если обозначить через  вероятности выбора i-ой стратегии первым игроком. При этом:

Сумма равна 1, так как он обязан что-то выбрать, у него нет возможности не выбрать

А через  вероятности выбора j-ой стратегии вторым игроком:

то наборы  и  называются смешанными стратегиями первого и второго игроков соответственно. Смешанная стратегия – это набор вероятностей чистых стратегий.

Тогда выигрыш первого игрока при условии, что он выбирает i-ю стратегию, а второй – j-ю стратегию составит .

Функция выигрыша первого игрока  – мат. ожидание выигрыша первого игрока. Соответственно средний выигрыш второго игрока = –M(x, y)

Любая матричная игра имеет решение в смешанных стратегиях, т.е. существует   

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

Тогда  и  называются оптимальными смешанными стратегиями игроков. Задачи заключается в нахождении оптимальных смешанных стратегий игроков и цены игры

Метод сведения решения матричных игр к задаче линейного программирования. (II метод)

Пусть игра определена матрицей   и ценой игры V. По следствию теоремы об оптимальности смешанных стратегий:

Если для смешанных стратегий () и числа V одновременно выполняются (1) и (2), то

– оптимальные стратегии игроков   (m + n неравенств)       (*)

1) Рассмотрим левую часть:

Решение СЛАУ сводится к задаче ЛП.

(1)

2) Рассмотрим правую часть (аналогично):

V меняем на W, так как системы (1)-(2) независимы, поэтому они имеют разные переменные.

(2)

Допустим, решили задачи и получили:

Если в этих решениях последние координаты совпадали бы, то выполнялись бы неравенства:

 

Тогда для каких-то  выполнялось бы следствие теоремы оптимальности.

Покажем двойственность.

Необходимо получить двойственные задачи.

Обозначим

{неравенства (3)-(4) лучше написать в развернутом виде, чтобы была видна двойственность}

  (3)

ЗАМ:

Аналогично для второй задачи:

   (4)

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

Алгоритм решения:

  1.  по матрице А построить задачи (3) и (4)
  2.  найти решения задач

тогда  – цена игры, оптимальные стратегии игроков:

Преимущества и недостатки метода:

+ сразу получаем решение игры, т.е. не надо переобозначать

+ можно решать игры с любой ценой игры

– больше на 2 переменные

– надо вводить дополнительные переменные, так как


 

А также другие работы, которые могут Вас заинтересовать

75877. Методи викладання іноземної мови. Комунікативно-спрямований підхід 36.5 KB
  В період післявоєнних десятиліть формується характерна тенденція до і посилення комунікативної спрямованості навчального процесу — його наближення до реального процесу спілкування. Розробкою комунікативного методу в тій чи іншій мірі займалось багато наукових колективів та методистів у різних країнах
75878. Методи викладання іноземної мови. Комунікативно спрямований підхід 32.22 KB
  Перекладні методи: Граматикоперекладний навчання граматики у ході читання тексту та його дослівного перекладу. Мета навчання спілкування. Переважає усне мовлення на основі комунікативних ситуацій навчання фонетики лексики. Переваги:розробка методики навчання усного мовлення системи фонетичних вправ використання різних безперекладних способів семантизації лексики.
75879. Проблеми перекладу в аспекті семантики. Види відношень одиниць вихідної мови та мови перекладу (повна та часткова відповідальність, пересічення, включення) 54.5 KB
  В первую очередь, понятие уровня перевода связано с распространенным в теории перевода понятиями “эквивалентного” (иначе - “адекватного”), “буквального” и вольного перевода. Вообще говоря, понятие переводческой эквивалентности, также как и буквализма и переводческой вольности, не сводиться видимо
75880. Структурні та мовні особливості словникових статей словників-тезаурусів, двомовних, асоціативних, частотних словників 48 KB
  Идеографические словари. Словари-тезаурусы сделанные по конкретным проблемным областям например по электронике геологии торговле политике широко используются в системах автоматического поиска. Переводные словари. Франкорусские словари представлены в частности словарем К.
75881. Структурні та мовні особливості словникових статей словників історичних та етимологічних, словників мовних форм (орфографічних, орфоепічних, морфемних), словників мовленнєвого використання, ономастиконів 47 KB
  Щербой в статье Опыт общей теории лексикографии: Историческим в полном смысле этого термина был бы такой словарь который давал бы историю всех слов на протяжении определенного отрезка времени начиная с той или иной определенной даты или эпохи причем указывалось бы не только возникновение новых слов и новых значений но и их отмирание а также их видоизменение. С 1984 издается Словарь русского языка XVIII в. К числу наиболее полных словарей такого типа для русского языка принадлежит четырехтомный Этимологический словарь русского языка М. Не...
75883. Проблеми створення комп’ютерних систем розпізнавання усного мовлення. Методи виділення й упізнавання елементів мови при обробці усного мовлення 29.83 KB
  Задача распознавания речи состоит в автоматическом восстановлении текста произносимых человеком слов фраз или предложений на естественном языке. Только в последние десятилетия компьютерная техника достигла такого уровня когда стала осмысленной задача распознавания слитной или даже спонтанной устной речи. На этом этапе выяснилось что для решения задачи распознавания речи недостаточно уметь распознавать отдельные звуки и слова команды с надежностью сравнимой с надежностью распознавания отдельных команд человеком. Поэтому задачу...
75884. Структурні компоненти словників. Особливості словникових статей нетрадиційних лінгвістичних словників 282.5 KB
  Каждая зона содержит особый тип словарной информации. Первая зона лексический вход словарной статьи вокабула или лемма. Лексический вход обычно выделяют полужирным шрифтом и поэтому в жаргоне лексикографов и редакторов эта зона часто называется черным словом. В толковом словаре после лексического входа чаще всего следуют зона грамматической информации и зона стилистических помет.
75885. Структурні компоненти словників. Особливості словникових статей нетрадиційних лінгвістичних словників. Основные структурные компоненты словаря 37.09 KB
  Каждая зона содержит особый тип словарной информации. Первая зона лексический вход словарной статьи вокабула заголовок словарной статьи или лемма син. Поэтому в жаргоне лексикографов и редакторов эта зона часто называется черное слово. В толковом словаре после лексического входа чаще всего следует зона грамматической информации и зона стилистических помет.