Поделиться Поделиться

Геометрическое решение игр .

Игры с двумя стратегиями можно решить геометрически. Для этого начинаем решать игру со стороны игрока, у которого две стратегии.

Пусть этот игрок А.

Геометрическое решение игр . - Инвестирование - 58


Геометрическое решение игр . - Инвестирование - 59

Решается по принципу минимакса для игрока А.

Решение необязательно находится на пересечении линий.

Рассмотрим задачу со стороны игрока В.

Геометрическое решение игр . - Инвестирование - 60

Если у одного игрока 2 стороны, а у другого много, то игру также можно решить геометрически.

В результате упрощения, игра имеет вид:

  B1 Геометрическое решение игр . - Инвестирование - 61 B2 Геометрическое решение игр . - Инвестирование - 62 B3 B4
A1 -1 -3
A2 -1 -5

Решим игру относительно игрока А:

 
  Геометрическое решение игр . - Инвестирование - 63


Для решения необходимо решить совместное уравнение В4, В1.

Тангенс угла наклона Геометрическое решение игр . - Инвестирование - 64

Геометрическое решение игр . - Инвестирование - 65

Геометрическое решение игр . - Инвестирование - 66

Геометрическое решение игр . - Инвестирование - 67

Геометрическое решение игр . - Инвестирование - 68

Геометрическое решение игр . - Инвестирование - 69

 
  Геометрическое решение игр . - Инвестирование - 70


A1: Геометрическое решение игр . - Инвестирование - 71

A2: Геометрическое решение игр . - Инвестирование - 72

Геометрическое решение игр . - Инвестирование - 73

Геометрическое решение игр . - Инвестирование - 74

Геометрическое решение игр . - Инвестирование - 75

Решение игр m ´ n.

Пусть у игрока Геометрическое решение игр . - Инвестирование - 76 , Геометрическое решение игр . - Инвестирование - 77 стратегий, а у Геометрическое решение игр . - Инвестирование - 78 . В общем случае игра имеет решение в области смешан­ных стратегий. Таким образом, чтобы решить игру надо найти Геометрическое решение игр . - Инвестирование - 79 и Геометрическое решение игр . - Инвестирование - 80 . Пусть игрок Геометрическое решение игр . - Инвестирование - 76 применя­ет свою оптимальную смешанную стратегию, а игрок Геометрическое решение игр . - Инвестирование - 81 чистую. При этом поучится выиг­рыш:

Геометрическое решение игр . - Инвестирование - 82

По определению решения игры, отклонение игрока Геометрическое решение игр . - Инвестирование - 83 от своей оптимальной стратегии невыгод­но для него. Если бы все стратегии были активными, то можно было бы поставить “ = ” в выра­жение Геометрическое решение игр . - Инвестирование - 84 .

В дальнейшем будем считать, что величина цены игры Геометрическое решение игр . - Инвестирование - 85 . Этого можно добиться, если перво­начальную платёжную матрицу Геометрическое решение игр . - Инвестирование - 86 сместить вверх, т. е. прибавить величину Геометрическое решение игр . - Инвестирование - 87 к каждому элемен­ту матрицы. При этом решение игры не меняется.

Разделим левую и правую часть неравенств на величину Геометрическое решение игр . - Инвестирование - 88 , и обозначим величины Геометрическое решение игр . - Инвестирование - 89 . То­гда получим систему ограничений в следующем виде:

Геометрическое решение игр . - Инвестирование - 90

Так как Геометрическое решение игр . - Инвестирование - 91 то:

Геометрическое решение игр . - Инвестирование - 92

Так как необходимо выбрать такие вероятности Геометрическое решение игр . - Инвестирование - 93 , что бы цена игры была максимальной, то можно считать, что Геометрическое решение игр . - Инвестирование - 94 . Получили следующую задачу линейного программирования: найти такие неотрицательные величины Геометрическое решение игр . - Инвестирование - 95 которые бы удовлетворяли системе уравнений Геометрическое решение игр . - Инвестирование - 96 и при этом минимизировали линейную систему Геометрическое решение игр . - Инвестирование - 97 . Аналогично рассмотрим игру со стороны игрока Геометрическое решение игр . - Инвестирование - 83 .

Геометрическое решение игр . - Инвестирование - 98

Аналогично делим на Геометрическое решение игр . - Инвестирование - 88 и обозначим Геометрическое решение игр . - Инвестирование - 99 . Получим задачу:

Геометрическое решение игр . - Инвестирование - 100

Геометрическое решение игр . - Инвестирование - 101

Так как игрок Геометрическое решение игр . - Инвестирование - 83 стремится уменьшить выигрыш, то решение игры Геометрическое решение игр . - Инвестирование - 102 может быть сведено к решению пары задач линейного программирования.

Рассмотрим вопрос существования решения задач Геометрическое решение игр . - Инвестирование - 103 . Доказательство существования этого решения будет доказательством основной теоремы теории игр.

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

1) Нет допустимого решения, т. е. система ограничений несовместна.

2) Целевая функция не ограничена.

Покажем, что любая пара задач линейного программирования имеет решение: возьмём Геометрическое решение игр . - Инвестирование - 104 и Геометрическое решение игр . - Инвестирование - 97 . Рассмотрим самый маленький выигрыш матрицы Геометрическое решение игр . - Инвестирование - 86 : Геометрическое решение игр . - Инвестирование - 105 . Тогда в качестве решения можно взять следующее: Геометрическое решение игр . - Инвестирование - 106 . Подставим это решение во все строки линейных нера­венств Геометрическое решение игр . - Инвестирование - 96 . Так как Геометрическое решение игр . - Инвестирование - 107 , то, например, Геометрическое решение игр . - Инвестирование - 108 всегда, а остальные равны нулю, то у нас есть реше­ние всегда. Так как вероятности и цена игры больше нуля, поэтому Геометрическое решение игр . - Инвестирование - 109 . Так как Геометрическое решение игр . - Инвестирование - 94 , то мини­мальная величина ограничена по крайней мере нулём, таким образом мы доказали, что решение Геометрическое решение игр . - Инвестирование - 96 и Геометрическое решение игр . - Инвестирование - 97 всегда существуют. А если существует Геометрическое решение игр . - Инвестирование - 97 , то существует Геометрическое решение игр . - Инвестирование - 88 , и значит существует Геометрическое решение игр . - Инвестирование - 110 во второй задаче. Мы доказали основную теорему теории игр: любая матричная игра имеет решение в области смешанных стратегий.

← Предыдущая страница | Следующая страница →