Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по ТПР - файл Лекция№15-тпр.doc


Лекции по ТПР
скачать (681.7 kb.)

Доступные файлы (18):

Лекция№01-тпр.doc38kb.12.11.2008 13:15скачать
Лекция№02-тпр.doc97kb.12.11.2008 13:25скачать
Лекция№03-тпр.doc179kb.12.09.2004 22:30скачать
Лекция№04-тпр.doc146kb.12.09.2004 22:31скачать
Лекция№05-тпр.doc131kb.12.09.2004 22:32скачать
Лекция№06-тпр.doc248kb.12.09.2004 22:33скачать
Лекция№09.doc177kb.03.10.2006 21:09скачать
Лекция№10-тпр.doc179kb.12.09.2004 22:49скачать
Лекция№11-тпр.doc353kb.25.11.2005 11:46скачать
Лекция№12-тпр.doc205kb.12.09.2004 22:53скачать
Лекция№13-тпр.doc191kb.12.09.2004 22:54скачать
Лекция№14-тпр.doc83kb.14.12.2004 14:25скачать
Лекция№15-тпр.doc301kb.12.09.2004 23:02скачать
Лекция№16-тпр.doc131kb.12.09.2004 23:04скачать
Лекция№17-тпр.doc542kb.12.09.2004 23:03скачать
Лекция№7-тпр.doc142kb.12.09.2004 22:38скачать
Лекция№8-тпр.doc93kb.12.09.2004 22:44скачать
Лекция№9-тпр.doc142kb.12.09.2004 22:47скачать

Лекция№15-тпр.doc

Лекция №15.

Решение игры среди чистых стратегий.

Рассмотрим игру с платёжной матрицей:








...



...













...



...


































...



...

































...



...













...



...









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

Вначале найдём наилучшую чистую стратегию игрока . Пусть он использует чистую стратегию . Какой при этом у него будет гарантированный выигрыш? Очевидно, это будет зависеть от того, какую стратегию использует игрок . Он может применять самую невыгодную для игрока стратегию. Следовательно, гарантированный выигрыш игрока будет равен

.

Но, так как он сам выбирает какую чистую стратегию использовать, то он будет применять ту чистую стратегию, которая даёт ему наибольший гарантированный выигрыш. Для этого ему нужно среди значений найти наибольший выигрыш . Таким образом, гарантированный выигрыш игрока вычисляется как максимин на платёжной матрице:

(1)

Пусть максимум по в выражении (1) достигается при , то есть .

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

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

Теперь найдём наилучшую чистую стратегию игрока . Допустим он использует свою стратегию . Его проигрыш будет зависеть от действий игрока , который может применить стратегию, дающую ему наибольший выигрыш. Поэтому гарантированный проигрыш игрока будет равен



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

(2)

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

Можно показать, что для любой платёжной матрицы справедливо .








...



...



...



























































...


































































































Действительно, пусть имеется матрица , для которой вычислены



Элемент является минимальным элементом строки , поэтому имеет место неравенство .

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

или .

Последнее неравенство означает, что



Вычислим нижнюю и верхнюю цены игры для рассмотренных ранее примеров.

  1. Игра в прятки. Нижняя цена игры















-1

1





1

-1


.

Верхняя цена игры

.

Следовательно .





  1. Игра «вооружение и самолёты».














0,5

0,6

0,8

0,5



0,9

0,7

0,8

0,7



0,7

0,5

0,6

0,5



0,9

0,7

0,8



Нижняя цена игры

.

Верхняя цена игры

.

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

.

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

Во втором примере . Анализ игры показал, что наилучшими стратегиями будут чистые стратегии.

Если платёжная матрица игры обладает свойством , то такая игра называется с седловой точкой. На платёжной матрице такой игры существует элемент

.


Этот элемент называется седловой точкой, для которой справедливо неравенство

.

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

Теорема. Любая конечная парная игра с нулевой суммой и с полной информацией является игрой с седловой точкой.

Например, игры в шашки, шахматы являются конечными, парными играми с нулевой суммой и с полной информацией, поэтому они относятся к играм с седловой точкой.













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

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

В качестве примера приведем следующую игру с полной информацией. Два игрока поочередно кладут одинаковые монеты на круглый стол, выбирая произвольно положение монеты (взаимное перекрытие монет не допускается). Выигрывает тот, кто положит последнюю монету (когда места для других уже не останется). Нетрудно убедиться, что исход этой игры предрешен, и существует определенная стратегия, обеспечивающая достоверный выигрыш тому из игроков, кто кладет монету первым. А именно, он должен первый раз положить монету в центр стола, а далее на каждый ход противника отвечать симметричным ходом. Очевидно, как бы ни вел себя противник, ему не избежать проигрыша. Поэтому игра имеет смысл только для лиц, не знающих ее решения. Точно так же дело обстоит с шахматами и другими играми с полной информацией; любая из этих игр обладает седловой точкой и, значит, решением, указывающим каждому игроку его оптимальную стратегию, так что игра имеет смысл только до тех пор, пока неизвестно решение. Решение шахматной игры не найдено (и в обозримом будущем вряд ли будет найдено) только потому, что число стратегий (комбинаций ходов) в шахматах слишком велико, чтобы можно было построить платежную матрицу и найти в ней седловую точку.


Скачать файл (681.7 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации