Исследование операций. Линейное, динамическое программирование


Исследование операций - часть 154


Рассмотрим пример игры без седловой точки и приведем (без доказательства) ее решение. Игра состоит в следующем: два игрока А и В одновременно и не сговариваясь показывают один, два или три пальца. Выигрыш решает общее количество пальцев: если оно четное, выигрывает А и получает у В сумму, равную этому числу; если нечетное, то, наоборот, А

платит В сумму, равную этому числу. Как поступать игрокам?

Составим матрицу игры. В одной партии у каждого игрока три стратегии: показать один, два или три пальца. Матрица 3×3 дана в таблице 26.5; в дополнительном правом столбце приведены минимумы строк, а в дополнительной нижней строке — максимумы столбцов.

Нижняя цена игры ? = — 3 и соответствует стратегии A1. Это значит, что при разумном, осторожном поведении мы гарантируем, что не проиграем больше, чем 3. Слабое утешение, но все же лучше, чем, скажем, выигрыш — 5, встречающийся в некоторых клетках матрицы. Плохо нам, игроку А...

Но утешимся:

положение противника, кажется, еще хуже: нижняя цена игры ? = 4, т. е. при разумном поведении он отдаст нам минимум 4. В общем, положение не слишком хорошее — ни для той, ни для другой стороны. Но посмотрим: нельзя ли его улучшить? Оказывается, можно. Если каждая сторона будет применять не одну какую-то чистую стратегию, а смешанную, в которую

 

 

Таблица 26.5

Bj

 

Ai

 

B1

 

B2

 

B3

 

?i

A1

A2

A3

 

2

-3

4

-3

4

-5

4

-5

6

-3

-5

-5

?j

4

4

6

 

первая и третья входят с вероятностями 1/4, а вторая — с вероятностью 1/2, т. е.

 

то средний выигрыш будет устойчиво равен нулю (значит, игра «справедлива» и одинаково выгодна той и другой стороне). Стратегии

 образуют решение игры, а ее цена v = 0. Как мы это решение нашли? Это вопрос другой. В следующем параграфе мы покажем, как вообще решаются конечные игры.

§ 27. Методы решения конечных игр

Перед тем, как решать игру m×n, нужно, прежде всего, попытаться ее упростить, избавившись от лишних стратегий.


Начало  Назад  Вперед



Книжный магазин