Принцип Оптимальности

Принцип оптимальности – это понятие определяющее

решение игры.

Решением игры является множество ,или , если мы изучаем конфликт с точки зрения выделенного игрока (оперирующая сторона).

Пример 1. Задача оптимизации

В этом случае I= {1}- изучается поведение единственного игрока, максимизирующего свою функцию выигрыша.

Пусть, например,

Из необходимого условия оптимальности

=-2( -1)=0

получим

, то есть

П усть теперь функция выигрыша имеет вид:

то есть прежнюю функцию мы «срезали» прямой.

. (см. рис. 1)

В этом случае, очевидно, при

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

Замечание. Везде далее будет использовано обозначение Argmax - множество точек таких, что

Тогда в рассматриваемом выше примере имеем:

= Argmax

М1
						Х1
0	0,50	1	1,50	2
	Рис.1

Пример2.Многокритериальная задача.

В этом случае имеем одного игрока

I={1}, но m функций , которые он желает максимизировать

Как показано в лекции №4 для многокритериальной задачи принцип оптимальности и понятие оптимального решения определяются следующим образом. Сначала из неформальных соображений конструируется свертка критериев:

F( ), а затем как в предыдущем примере определяем = Argmax .

Пример. 3. Антагонистическая игра.

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

Итак, пусть

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

,

которая по определению удовлетворяет условию

Седловая точка удовлетворяет принципу устойчивости (равновесия интересов).Если один из игроков выбрал свое управление , соответствующее седловой точке, то противнику не целесообразно отклоняться от неё.

Например, для матричной игры

,

не трудно проверить, что элемент =3-наименьший во второй строке и наибольший в третьем столбце, то есть =3 соответствует седловой точке в этой игре.

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

Пример.4. Максимально гарантированный результат(МГР)

Пусть

-управление игрока, а -неконтролируемые им факторы.

Тогда игрок гарантированно может рассчитывать на получение результата

Управление , удовлетворяющее условию

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

Пусть -управление партнера и игрок 1 знает его принцип оптимальности, что позволяет ему оценить его «отклик» на свое управление , то есть знать, что игрок 2 выберет .

Например, если мы знаем , то

= Argmax

Тогда МГР игрока1 оценивается величиной

Отметим, что в следствие получаем неравенство .

Пример.5. Бескоалиционная игра n лиц.

Эта игра общего вида

Г=

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

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

Самым распространенным принципом оптимальности для этой игры является ситуация равновесия по Нэшу

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

Такая совокупность стратегий выбранных участниками и их выигрыши называются равновесием Нэша.

Концепция равновесия Нэша впервые использована не Нэшем; Антуан Огюст Курно показал, как найти то, что мы называем равновесием Нэша, в игре Курно. Соответственно, некоторые авторы называют его равновесием Нэша-Курно.

Однако Нэш первым показал в своей диссертации Некооперативные игры (1950), что равновесия Нэша должны существовать для всех конечных игр с любым числом игроков. До Нэша это было доказано только для игр с 2 участниками с нулевой суммой Джоном фон Нейманом и Оскаром Моргенштерном (1947).

Игра может иметь равновесие Нэша в чистых стратегиях или в смешанных. Нэш доказал, что если разрешить смешанные стратегии, тогда в каждой игре n игроков будет хотя бы одно равновесие Нэша.