Автор работы: Пользователь скрыл имя, 01 Марта 2013 в 15:21, доклад
Теория игр рассматривает ситуации, при которых сталкиваются интересы двух или более сторон, преследующих различные цели. Такие ситуации называют конфликтными. Сами эти стороны, участвующие в конфликте, называют игроками. Игроками могут быть как отдельные лица, так и группы лиц (партнёры в бизнесе, фирмы и т. д.). Последовательные действия каждого из игроков зависят от действий, предпринятых ранее другими игроками. Таким образом, теория игр – это математическая теория, изучающая конфликтные ситуации.
Заметим, что исключение вторым игроком третьей стратегии стало возможным только после исключения первым игроком третьей стратегии. В первоначальной матрице игры третья стратегия была недоминируема.
Нам удалось уменьшить размерность игры до за счёт последовательного исключения заведомо невыгодных для игроков (строго доминируемых) стратегий. В дальнейшем мы научимся решать такие игры, то есть находить оптимальные стратегии для каждого из игроков.
Будем полагать, что каждый игрок стремится обеспечить себе максимально возможный выигрыш при любых действиях противника, – максимальный гарантированный выигрыш. Оптимальная стратегия первого игрока – это такая стратегия, которая обеспечивает ему максимальный гарантированный выигрыш при наихудших для него действиях противника (так называемая "осторожная" стратегия):
При этом первый игрок рассуждает примерно так: "Если я выберу i – ю стратегию , что соответствует i – й строке платёжной матрицы, то мой противник, если бы он знал мой выбор (а он его не знает), выбрал бы такую стратегию, которая максимизировала его выигрыш, то есть минимизировала мой выигрыш. Правда, он не знает, каков мой выбор, но может его угадать. Поэтому, будучи осторожным игроком, я буду считать, что он угадал и выбрал такую стратегию , которая минимизирует мой выигрыш: . Таким образом, мой гарантированный выигрыш при выборе мной i – й стратегии будет равен . Понятно, что я выберу такую стратегию, при которой этот гарантированный выигрыш будет максимален, то есть ".
Величина называется нижней ценой игры.
Аналогичные рассуждения в поведении второго игрока приводят к его оптимальной стратегии, определяемой из условия:
Величина называется верхней ценой игры.
Минимаксная стратегия второго игрока гарантирует, что его проигрыш в игре не превысит верхнюю цену игры .
Докажем, что нижняя цена игры в общем случае не превышает верхнюю:
Имеем систему очевидных неравенств:
Поскольку в одном из этих неравенств в левой части достигается , то отсюда следует неравенство .
Максминная стратегия первого игрока и минимаксная стратегия второго игрока называются осторожными стратегиями.
Если верхняя и нижняя цены равны , то игроки получат свои гарантированные платежи. Платёжная матрица в этом случае имеет седловую точку – элемент, минимальный в строке и максимальный в столбце.
Пример 7. Рассмотрим матричную игру:
Справа в каждой строке запишем , а снизу в третьей строке запишем :
Очевидно, элемент второй строки, второго столбца является седловой точкой:
Здесь - цена игры. Оптимальными стратегиями игроков являются: вторая стратегия первого игрока и вторая стратегия второго игрока.
Удобно отмечать подчеркиванием минимальные элементы в каждой строке и надчеркиванием максимальные элементы в каждом столбце:
Тогда элемент, оказавшийся одновременно подчеркнутым и надчеркнутым (если таковой имеется) оказывается седловой точкой в игре, а пара стратегий, соответствующих этому элементу, является решением игры.
Игра двух участников с нулевой суммой, имеющая седловую точку, называется вполне определённой. Для вполне определённых игр имеем:
– нижняя цена игры равна верхней.
Однако не любая матричная игра имеет седловую точку.
Пример 8. Пусть имеется матрица игры:
Справа в каждой строке запишем , а снизу в третьей строке запишем :
Максминная стратегия первого игрока (игрока A) даст элемент , в то время как минимаксная стратегия второго игрока (игрока B) даст . В этом случае имеем строгое неравенство:
Такая игра относится к классу не полностью определённых игр. Пусть для определённости платёжная матрица задана в рублях. Придерживаясь первой стратегии, игрок A ожидает, что игрок B выберет стратегию 2, т. е. получит 1 рубль. Придерживаясь стратегии 3, игрок B ожидает, что игрок A выберет стратегию 2, т. е. игрок 2 проиграет 5 руб. В результате же при выборе игроком A стратегии 1 и игроком B стратегии 3, результат платежа равен 4, чего не ждал ни один из них.
Минимаксная и максиминная стратегии в не полностью определённых играх не устойчивы. Пусть игра повторяется многократно. Если игрок A выбирает стратегию 1, то игрок B, узнав об этом, скоро откажется от стратегии 3 и выберет стратегию 2. Игрок A, узнав об этом, откажется от стратегии 1 и выберет стратегию 2, и т. д. Положение, в котором игроки пользуются минимаксными стратегиями, оказывается в таких играх неустойчивым и может быть нарушено, как только одному из игроков становится известна стратегия соперника. Данный подход (выбор осторожных стратегий) неприемлем в неполностью определённых играх.
Напротив, вполне определённые игры устойчивы: если один из игроков придерживается своей минимаксной (максминной) стратегии, то другому не удастся увеличить свой выигрыш, отступая от своей максминной (минимаксной) стратегии.
Упражнения.
1) Составить матричную игру с несколькими седловыми точками.
2) Пусть матричная игра имеет две седловые точки и . Доказать, что точки и также будут седловыми и значения матрицы игры во всех четырех точках равны.
На следующем
примере покажем, как можно использовать
условие, при котором некоторые
из стратегий оказываются
Пример 9. Рассмотрим игру двух игроков с нулевой суммой и следующей платежной матрицей:
Пусть возможные стратегии первого игрока, а возможные стратегии второго игрока. Очевидно, что для второго игрока (для него это матрица проигрышей !!) стратегия строго доминирует , а стратегия строго доминирует . Поэтому стратегии и можно не рассматривать. Платежная матрица примет вид:
Теперь видно, что для первого игрока стратегия строго доминирует . Платёжная матрица поэтому примет вид:
В полученной игре нижняя цена игры равна 1, а верхняя цена равна 2. Поскольку 2>1, данную игру следует отнести к классу не полностью определённых игр. Их решение рассмотрим в следующем параграфе.
Описанная в предыдущем примере процедура исключения строго доминируемых стратегий не может привести к исключению из рассмотрения седловых точек. Если же ее заменить процедурой исключения доминируемых стратегий, то это может привести к исключению из рассмотрения седловых точек. Например, в матричной игре
четыре седловые точки: . Однако, процедура исключения доминируемых стратегий может привести к исключению двух из них. Действительно, стратегии второго игрока , и доминируемы стратегией . Исключая их, получим матрицу
Далее, исключая доминируемую третью стратегию первого игрока, получим
Две из четырех седловых точек оказались исключенными методом итерационного исключения доминируемых стратегий. Если ставить задачу отыскания какой-нибудь седловой точки, то этот метод приемлем. Если же требуется отыскать все седловые точки, то следует исключать только строго доминируемые стратегии.
Рассмотренные выше стратегии относились к классу чистых стратегий. При выборе чистой стратегии игрок не отклоняется от правил выбора хода, определяемых этой стратегией. Можно сказать, что чистая стратегия - это уверенный выбор игроком определенного действия.
Смешанная стратегия – случайная величина, значениями которой являются чистые стратегии игрока.
Поскольку случайная
величина задается своим распределением
вероятностей, то смешанную стратегию
можно отождествлять с вероятно
Смешанную стратегию первого игрока зададим с помощью вектора вероятностей
Смешанную стратегию второго игрока зададим с помощью вектора вероятностей
Игра с использованием чистых стратегий является частным случаем игры с использованием смешанных стратегий, когда для некоторого имеем , а все остальные стратегии имеют нулевую вероятность.
Если для всех i, то смешанная стратегия называется полностью смешанной.
Исходом игры, предусматривающей смешанные стратегии игроков, является пара векторов .
Заметим, что смешанная стратегия может строго доминировать чистую стратегию. Тогда последняя играться, очевидно, не будет и ее можно исключить, как мы это делали раньше.
Пример 11. Исключить все строго доминируемые стратегии в антогонистической игре двух игроков (допускается использование смешанных стратегий):
Решение. Поскольку в первой колонке максимальный элемент (10) в первой строке, то стратегия a не может быть строго доминируема. Поскольку во второй колонке максимальный элемент (12) во второй строке, то стратегия b также не может быть строго доминируема. Найдем смешанную стратегию первого игрока (смесь первых двух стратегий), строго доминирующую его третью стратегию: . Имеем:
Следовательно, стратегия c строго доминируема смешанной стратегией при всех и мы ее далее можем исключить из рассмотрения.
Упражнение. Дана антагонистическая игра
Найти все значения x, при которых стратегия c может быть строго доминируема.
Теорема о минимаксе. Любая конечная антагонистическая матричная игра имеет решение на множестве смешанных стратегий.
При выборе первым игроком i–й чистой стратегии и вторым игроком j–й чистой стратегии выигрыш первого игрока будет равен . Но поскольку это событие наступает с вероятностью, равной произведению вероятностей (в предположении независимости выбора стратегий игроками), то математическое ожидание выигрыша первого игрока будет равно , или в матричных обозначениях .
Решением игры называется пара оптимальных стратегий (в общем случае смешанных) обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии. Мы будем говорить тогда, что на таких стратегиях достигнуто положение равновесия. Если и – оптимальные стратегии соответственно первого и второго игроков, то для любых векторов вероятностей p и q (стратегий первого и второго игроков) имеем: .
Предположим, первый игрок избрал i–ю чистую стратегию. Второй игрок будет тогда строить свою смешанную стратегию q так, чтобы минимизировать выигрыш первого игрока или, что то же, максимизировать свой выигрыш: . Обозначим этот гарантированный для первого игрока выигрыш через . Если же теперь первый игрок выбирает i–ю чистую стратегию с вероятностью , то он заинтересован выбрать вероятности таким образом, чтобы максимизировать средний гарантированный выигрыш: . Иными словами, стратегия первого игрока заключается в выборе им максминной стратегии p:
Аналогичные рассуждения в отношении второго игрока приведут к его минимаксной стратегии:
Теорема о минимаксе утверждает, что существуют решения задач и и они совпадают – . Обозначим цену игры через . Очевидно, V удовлетворяет условиям:
В случае матричной игры 2x2
характер изменения платёжной функции , как функции от выбираемых стратегий p и q представлен на рис. 2:
Рис. 2
Цена игры V является и максимальным ожидаемым средним выигрышем первого игрока, и минимальным ожидаемым средним проигрышем второго игрока при проведении серии игр. Таким образом, любая конечная игра двух лиц с противоположными интересами имеет седловую точку в пространстве векторов вероятностей. Эта точка называется решением игры а сами стратегии и называются оптимальными стратегиями. Цена игры единственна, но достигаться она может либо в одной точке в пространстве , либо на некотором множестве точек. В последнем случае это множество представляет собой замкнутый выпуклый многогранник. Во всех его точках целевая функция постоянна.