Динамические игры

Теорией игр называют теорию математических моделей принятия оптимальных решений в условиях соперников. Игровая ситуация, естественно, получается из модели исследования операции в предположении, что неконтролируемые факторы связаны с действиями других активных участников операции. Конфликтом называется операция, в которой участвуют несколько сторон (по крайней мере, две), преследующих свои интересы и обладающих определенными возможностями действия. Участников игры называют игроками. Часто в игре выделяют оперирующую сторону, а всех игроков считают равноправными и определяют оптимальные решения для всех участников. В некоторых играх игрокам имеет смысл объединиться и действовать совместно. Такие объединения называются коалициями. Очевидно, без такого объединения отдельный игрок образует коалицию действия. Выбор всеми коалициями действия определенных стратегий определяет исход конфликта или игровую ситуацию. Не все ситуации, складывающиеся при произвольном выборе стратегий коалициями действий, могут быть допустимыми, т.е. разрешаемыми правилами игры. Недопустимые ситуации называются запрещенными. Таким образом, множество допустимых ситуаций является подмножеством прямого произведения пространств стратегий всех коалиций действия. Среди исходов игры один является более предпочтительным, а другие менее предпочтительными для участников, под которыми можно понимать как отдельных игроков, так и их объединения-коалиции. Чтобы подчеркнуть, что эти объединения могут, вообще говоря, не совпадать с коалициями действия, их называют коалициями интересов. Коалиции интересов либо совпадают с коалициями действия (тогда их называют просто коалициями) либо представляют собой отдельных игроков. Численная оценка каждого исхода, т.е. критерий эффективности, называется функцией выигрыша. Если общая позиционная игра развивается в древовидно упорядоченном множестве, то она называется позиционной игрой. В динамической игре игроки управляют движением точки в пространстве состояний j. Динамическая игра, у которой переходная функция распределения не зависит от предыстории игры, называется стохастической игрой. Антагонистическая динамическая игра, в которой выигрыш в каждый момент времени может принимать лишь значения 0 или 1, называется игрой на выживание. Стохастическая игра в теории игр - повторяющаяся игра со случайными переходами состояний, разыгрываемая одним и более игроками. Стохастические игры были изобретены Л.Шепли в начале 1950-х годов. Наиболее полным их описанием является сборник статей под редакцией А.Ноймана и С.Сорина. Более элементарная книга Дж. Филар и К. Вриз содержит общее изложение теории марковских процессов принятия решений и стохастических игр двух лиц. Ими был использован термин конкурентные марковские процессы принятия решений для обозначения стохастических игр одного и двух лиц. Игра разыгрывается в течение ряда этапов. В начале каждого этапа игра находится в некотором состоянии. Игроки выбирают свои действия и получают выигрыши, зависящие от текущего состояния и действий. После этого система переходит случайным образом в другое состояние, распределение вероятности переходов зависит от предшествующего состояния и действий игроков. Эта процедура повторяется в течение конечного или бесконечного числа шагов. Общий выигрыш игроков часто определяется как дисконтированная сумма выигрышей на каждом этапе или нижний предел средних выигрышей за конечное число шагов. При конечном числе игроков, конечных множествах действий и состояний игра с конечным числом повторений всегда имеет равновесие Нэша. Это справедливо также для игр с бесконечным числом повторений, если выигрыши участников представляют собой дисконтированную сумму. Н. Вайель показал, что все стохастические игры двух лиц с конечными множествами состояний и действий имеют приближенные равновесия Нэша, если функции выигрыша представляют собой нижний предел средних значений выигрыша за конечное число шагов. Вопрос о существовании таких равновесий в играх с большим количеством участников остается открытым. Стохастические игры находят применение в экономике и эволюционной биологии. Они представляют собой обобщение повторяющихся игр, которые соответствуют ситуации, когда имеется только одно состояние. Игра на выживание - антагонистическая динамическая игра с терминальным выигрышем, принимающим лишь значения 0 и 1. Таким образом, терминальное множество Х^T разбивается на два подмножества Х^T+ и Х^T-, при этом, если игра попадает в состояние , то выигрывает игрок I, а если в состояние , то выигрывает игрок II. В случае, если игра никогда не заканчивается, игрок I выигрывает, а игрок II проигрывает нек-рое число . Если , то имеем дело с И. на в. игрока II, а если , то - с И. на в. игрока I. Исторически понятие И. на в. восходит к классической задаче "о разорении игрока". Прямым обобщением этой задачи является игра, в к-рой на каждом шаге разыгрывается одна и та же матричная подигра, а изменения состояний выражаются в изменениях капиталов участников. Игрок I выигрывает, если разоряется противник (т.е. капитал противника становится отрицательным), и проигрывает, если разоряется сам. Такая игра обладает значением, не зависящим от , и оба игрока имеют стационарные e-оптимальные стратегии, если все элементы матрицы повторяемой подигры отличны от нуля. В этом случае игра почти наверное заканчивается за конечное число шагов. Другой вариант И. на в. (с многокомпонентными капиталами) представляют так наз. "игры на истощение". Дифференциальные И. на в. могут рассматриваться как обобщение описанных игр на случай непрерывного времени.

1. Определить корень уравнения sin(x+1)-0,5x=0 с точностью ε =0,01 методом половинного деления.

Определим интервал для дальнейшего решения задачи.

У(0)>0

У(1)>0

У(2)<0

Значит, интервал для нахождения корня уравнения [1;2]

Метод половинного деления предполагает собой разделение графика решений пополам и определение знака на концах отрезка.

Находим новый интервал для дальнейшего решения.

(1+2)/2=1,5

У(1,5)<0

У(1)>0

У(2)<0

Значит, новый интервал для нахождения корня уравнения [1;1,5]

У(1,5)<0

У(1)>0

У((1+1,5)/2)= У(1,25)>0

Значит, новый интервал для нахождения корня уравнения [1.25;1,5]

У(1,5)<0

У(1,25)>0

У((1.25+1,5)/2)= У(1,38)>0

Значит, новый интервал для нахождения корня уравнения [1.38;1,5]

У(1,5)<0

У(1,38)>0

У((1.38+1,5)/2)= У(1,44)>0

Значит, новый интервал для нахождения корня уравнения [1.44;1,5]