183752 (743626), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

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

Из всех значений находят минимальное:

,

которое дает минимаксный выигрыш или минимакс.

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

Если , то число С называют чистой ценой игры или седловой точкой.

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

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

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

Из этого определения следует, что сумма компонент этого вектора равна единице, а сами компоненты не отрицательны.

Обычно смешанную стратегию первого игрока обо­значают как вектор

, а второго игрока - как вектор , где . (5.1.1).

Если u° - оптимальная стратегия первого игрока, z° - оптимальная стратегия второго игрока, то число - называют ценой игры.

Для того чтобы число - было ценой игры, а u° и z° — оптимальными стратегиями, необходимо и до­статочно выполнение неравенств:

, (5.1.2)

. (5.1.3)

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

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

Однако, не следует забывать, что:

1) применение смешанных стратегий рисковано, когда игра не повторяется;
2) если игра повторяется, надо иметь уверенность, что у про­тивника нет информации о конкретных решениях другого игрока;
3) противник не обязан применять смешанные стратегии, равно как и стремиться к цели, противоположной цели другого игрока.

Обозначим смешанную стратегию первого игрока p = {p_i}, где p_i - вероятность применения i-й стратегии, , . Пусть смешан­ная стратегия второго игрока , , q_j - вероятность при­менения j-й стратегии, , . Р и Q определяют матема­тическое ожидание платежа:

.

Теорема фон Неймана. Любая матричная игра имеет седловую точ­ку в смешанных стратегиях.

Доказательство. Множества M и N ограничены и замкнуты, так как , , а функция W непрерывна по P и Q . W линейна по P при фиксированных Q, следовательно, вогнута по P при фиксированных Q. Аналогично W выпукла по Q при фиксированных P. M и N выпуклы.

Действительно, рассмотрим такие и , что , , тогда , .

Складывая, получим .

Кроме того, .

Следовательно, при и

тоже смешанная стратегия.

Применяя фундаментальную теорему, получим то, что требуется доказать:

.

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

Пусть P^o и Q^o оптимальные смешанные стратегии, v - цена игры, тогда

.

Из теорема следует, что

.

Обозначим .

Поделим (4) на v , получим

.

Из этой задачи линейного программирования можно получить оптимальные стратегии первого игрока (оперирующей стороны).

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

Игры с природой. Оптимальная стратегия в игре с природой при известном распределении её состояний. Максиминный критерий Вальда выбора стратегии в игре с природой при неизвестном распределении её состояний. Критерий минимаксного риска Сэвиджа выбора стратегии в игре с природой при неизвестном распределении её состояний. Критерий пессимизма-оптимизма Гурвица выбора стратегии в игре с природой при неизвестном распределении её состояний.

В случае, когда между сторонами (участниками) от­сутствует «антагонизм» (например, в процессе работы предприятий и торговых посредников), такие ситуации называют «играми с природой».

Здесь первая сторона принимает решение, а вторая сторона — «природа» не оказывает первой стороне со­знательного, агрессивного противодействия, но ее ре­альное поведение неизвестно.

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

По платежной матрице можно принять ряд решений. Например, оценить возможные исходы: минимальный выигрыш

то есть наименьшая из величин в каждой i-й строке как пессимистическая оценка; максимальный выиг­рыш – то наилучшее, что дает выбор i-го варианта

При анализе «игры с природой» вводится показатель, по которому оценивают, насколько то или иное состо­яние «природы» влияет на исход ситуации. Этот по­казатель называют риском.

Риск при пользовании стратегией и состоянии «природы» оценивается разностью между максималь­но возможным выигрышем при данном состоянии «при­роды» и выигрышем при выбранной стратегии .

.

Исходя из этого определения можно оценить мак­симальный риск каждого решения:

.

Решения могут приниматься по результатам анализа ряда критериев.

Критерий, основанный на известных вероятност­ных состояниях «природы».

Если известны вероятности состояний «природы» (на­пример, спроса по данным анализа за прошлые годы):

где ,

то в качестве показателя эффективности (рацио­нальности, обоснованности) стратегии берется средний (математическое ожидание) - выигрыш применения этой стратегии:

,

а оптимальной считают стратегию, для которой этот показатель эффективности имеет максимальное значе­ние, то есть

.

Если каждому решению соответствует множество возможных результатов с вероятностями , то сред­нее значение выигрыша можно определить по формуле

,

а оптимальная стратегия выбирается по условию

.

В этом случае можно воспользоваться и стратегией минимального среднего риска для каждого i-го состо­яния «природы»

.

Максиминный критерий Вальда предполагает выбор решения, при котором гарантируется максимальный выигрыш в наихудших условиях внешней среды (состояния «при­роды»):

.

Согласно критерия пессимизма-оптимизма Гурвица при выборе решения вместо двух крайностей в оценке ситуации (оптимум-пессимизм) придерживаются некоторого ком­промисса, учитывающего возможность как наихудшего, так и наилучшего поведения «природы»:

,

где x - показатель пессимизма-оптимизма (чаще всего 0,5).

Если х = 1 критерий слишком пессимистичный, если х = 0 – слишком отптимистичный.

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

Характеристики

Список файлов реферата