Студопедия — Теорема о минимаксе
Студопедия Главная Случайная страница Обратная связь

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

Теорема о минимаксе






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

Обозначим через

матрицу-столбец, состоящую из вероятностей xi, выбора i-й стра­тегии игрока А, и через

соответственно матрицу-столбец (вектор) вероятностей появления стратегий игрока B. В приведенных формулах

Теперь можно ставить вопрос об оптимальном выборе стратегии.

В этом случае векторы х и у называются смешанными стратегиями игроков А и В соответственно. Если в векторе х или у (или обоих вместе) все составляющие равны нулю, за исключением одной, то такую стратегию называют чистой. Чистая стратегия может быть оптимальной только при наличии седловой точки. В противном случае следует говорить об оптимальных смешанных стратегиях. При наличии смешанных стратегий следует оперировать не платежами, а средним значением (математическим ожиданием) платежей. Допустим, что игрок А выбирает чистую стратегию i, а игрок В – смешанную стратегию у. Тогда средний платеж игроку А равен:

.

Величина ui представляет собой i-ю составляющую вектора-столбца u:

.

Если игрок В применяет чистую стратегию j, а игрок А – сме­шанную стратегию х, то средний платеж игроку А равен:

Величина lj представляет собой j-ю составляющую матрицы-строки lt:

.

Если игроки А и В применяют смешанные стратегии х и у соответственно, то средний платеж игроку А

.

Основная теорема теории игр, теорема о минимаксе, утверждает, что максимин среднего платежа равен минимаксу среднего платежа, т.е.

.

Из этого равенства следует, что существует такая пара стратегий , что

для всех x и y.

В этом случае пара векторов (х*, у*) называется решением игры, оптимальными стратегиями, a v – ценой игры, т. е. всегда сущест­вует решение игры в классе чистых или смешанных стратегий.

В оптимальную смешанную стратегию не обязательно входят все чистые стратегии. Поэтому для тех чистых стратегий, которые входят в оптимальную смешанную стратегию, вводят специальный термин – активные стратегии. С активными стратегиями связано очень важное положение. Оказывается, что оптимальная смешан­ная стратегия, примененная против любой активной стратегии, дает цену игры. И, наоборот, любая активная стратегия, применен­ная против оптимальной смешанной стратегии, также дает цену игры. Это значит, что если один из игроков применяет оптимальную смешанную стратегию, то выигрыш (платеж) остается неизменным и равным цене игры v, независимо от стратегии другого игрока, если тот применяет одну из своих активных стратегий, их оптималь­ную и неоптимальную комбинацию (т. е. не выходит из класса ак­тивных стратегий).

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







Дата добавления: 2015-08-17; просмотров: 2540. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Гидравлический расчёт трубопроводов Пример 3.4. Вентиляционная труба d=0,1м (100 мм) имеет длину l=100 м. Определить давление, которое должен развивать вентилятор, если расход воздуха, подаваемый по трубе, . Давление на выходе . Местных сопротивлений по пути не имеется. Температура...

Огоньки» в основной период В основной период смены могут проводиться три вида «огоньков»: «огонек-анализ», тематический «огонек» и «конфликтный» огонек...

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

Методика обучения письму и письменной речи на иностранном языке в средней школе. Различают письмо и письменную речь. Письмо – объект овладения графической и орфографической системами иностранного языка для фиксации языкового и речевого материала...

Классификация холодных блюд и закусок. Урок №2 Тема: Холодные блюда и закуски. Значение холодных блюд и закусок. Классификация холодных блюд и закусок. Кулинарная обработка продуктов...

ТЕРМОДИНАМИКА БИОЛОГИЧЕСКИХ СИСТЕМ. 1. Особенности термодинамического метода изучения биологических систем. Основные понятия термодинамики. Термодинамикой называется раздел физики...

Studopedia.info - Студопедия - 2014-2024 год . (0.009 сек.) русская версия | украинская версия