Теория игр. Оуэн (1971) (Теория игр. Оуэн (1971).djvu), страница 3
Описание файла
DJVU-файл из архива "Теория игр. Оуэн (1971).djvu", который расположен в категории "". Всё это находится в предмете "теория игр и исследование операций" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла, 3 - страница
Для того чтобы учесть этот динамический характер, необходимо конкретизировать понятие стратегии, рассматривая ее не просто как элемент абстрактного множества, а как объект, имеющий внутреннюю структуру и конструируемый в некотором процессе, причем результаты отдельных шагов этого процесса могут изменяться в зависимости от тех или иных обстоятельств, являясь тем самым функциями этих обстоятельств. Областью задания каждой такой функции является множество всех представлений принимающего решения субъекта (т. е. коалиции действия) об обстановке, в которой приходится принимать решения. Здесь важно отметить, что аргументом функции-стратегии является не истинное состояние субъекта, а его субъективное представление о нем (его и иф ор мац ио нное состояние).
Каждое информационное состояние субъекта можно понимать как некоторый класс его истинных состояний, в который объединяются состояния, не различаемые субьектом в момент принятия им решения. Возможными значениями функции на каждом из информационных состояний являются те частичные решения, которые субъект в состоянии привять в этот момент. Очевидно, область значений функции-решения в различных информационных состояниях определяется теми же внешними по отношению к субъекту обстоятельствами, что и сами информационные состояния. Описанное представление о стратегии как о функции, заданной на множестве информационных состояний субъекта, весьма характерно для большинства салонных и спортивных игр, а также для большинства конфликтов, моделями которых призваны быть игры.
Поэтому в ряде руководств по теории игр и в том числе в данной книге изложение начинается с описания игр именно такой динамической природы (см. $ 1.2). й 4. ОПТИМАЛЬНОСТЬ Понятие о п т и м а л ь н о с т и принимаемого решения значительно труднее поддается формализации, чем понятия конфликта н принятия решения. Эта задача является сейчас одной из основных в теории игр, При современном состоянии теории игр представляется наиболее естественным следующий подход к вопросам такого рода. Предмет и содержание 'теории игр 13 или х,+х, /,, х,>у„х,>у, Х2+ Х3 — /3~ Х2) У21 Х3) УЗ.
(2) (а) или, наконец, Наглядная интерпретация такого понимания предпочтения разбивается в $5 этого введения, а также в $ Ч111.4 книги. Отвлечемся на мгновение от теоретико-игровых сложностей и рассмотрим обычную задачу экстремального типа. Пусть мы хотим максимизировать значение интересующей нас функции /, которая задана на некотором множестве М и принимает вещественные значения. При этом будем предполагать, что в нашей власти выбрать любую точку или любые точки множества М. Поставленную задачу можно сформулировать нееколькими, как легко видеть, эквивалентными способами. Например: 1) найти точки х, в которых значение функции / не меньше ее значений в каких-либо других точках М: /(х) ~ /(у) (у ве М); 2) найти такие точки х, что любое отклонение от них в пределах множества М не увеличивает значения функции /; 3) найти такое множество точек /с, что для произвольных х, у е:-/1 не может быть /(х) > /(у), а для любой точки х'ф/с найдется такая точка х ~ /г, что /(х) > /(г).
Ясно, что если мы вместо максимизации значения функции будем заниматься поисками наиболее предпочтительной точки в множестве М в условиях линейного отношения предпочтения (см. й 2) на 'хз этом множестве, то эти формулировки Р останутся эквивалентными. Но если ! отношение предпочтения не линейно, а носит более сложный характер, то приведенные формулировки уже перестают быть эквивалентными.
0 Рассмотрим, например, трехмерное Р х2 евклидово пространство. Его точками 2 являются тройки вещественных чисел х = (х„х2, х,). Возьмем в качестве 1 множества М треугольник Р,Р,Р, с вершинами (1, О, 0), (О, 1, 0) и (О, 0,1) Рис. к (см. рис. 1). Пусть х = (х„х2, х,) и у = (уь у2, ут) — две точки этого треугольника. Положим х) у и будем говорить, что точка х п р е д п о ч т и т е л ь и е е, ч е м т о ч к а у, если выполняется хотя бы одна из следующих троек неравенств: Х1+ Х2 — /3, Х1) У11 К2) УЬ (1) предмет и содержание теории игр Рассмотрим теперь три задачи:- а) найти точки х, каждая из которых более предпочтительна, чем какая-либо другая точка у из М: х)у (уев М) (очевндно, одинаково предпочтительных точек в рассматриваемых условиях не бывает); б) найти такие точки х, что любое отклонение от х в пределах М не приводит к более предпочтительным точкам; в) найти такое множество точек /с, что для произвольных х, уев/с не может быть х ) у, а какова бы ни была точка гф/с, найдется такая точка х ~ /с, что х ) з.
Эти задачи в применении к исследованию предпочтительности точек в смысле своих формулировок полностью соответствуют приведенным выше трем задачам о нахождении экстремума функции /. Однако онн уже не являются эквивалентными. Действительно, задача а) вовсе не имеет решения. В самом деле, возьмем произвольную точку х = (хь хь хз). Пусть для определенности хз — отличная от нуля координата этой точки. Тогда у точки у = (х ~ + х,/2, х, + х,/2, О) две координаты больше соответствующих координат точки х, Поэтому не может быть х) у.
Решение задачи б) состоит из единственной точки ('/з, Чз, '/з). В самом деле, пусть у =(уьуьуз)) х. По определению отношения предпочтения это значит, что либо У~+Уз ~ /з У~> /з» Уз> /з либо У~+Уз~ /з У~> /з» Уз> /з либо Уз+Уз п /з Уз> /з. Уз> /з Но ни одна из этих троек неравенств, очевидно, не совместна. Эначит, (1/з,'/з,'/з) является искомой точкой. Покажем, что иных точек с этим свойством нет. Действительно, пусть х = (хь хь хз) Ф(Чз, 1/з» '/з).
Пусть для определенности хз — наибольшая нз координат этой точки. Тогда, очевидно, хз > '/з, так что х1 + хз < з/з Возьмем тепеРь столь малое е > О, что х1 + х, + 2е ~ '/з хз — 2е > О, и положим х~ + е = у„х, + е уз, хз — 2е = уз Мы получаем Уз+Уз~ /з» У~>х~ Уз>хз» т. е. У)х. Предмет и содереиииие теории игр рз Решим, наконец, задачу в), Возьмем для этого точку О ('/з, Чз, 1/з) и соединим ее с серединами всех трех сторон треугольника Р|Р«Рз, т, е.
с точками К =(!/з, '/з,О), Ь =('/з, О,'/з) и М (О,'/з,'/з), как это показано на рис. 2. Объединение трех отрезков ОК, ОЕ и ОМ обозначим через Я. Покажем, что множество Й является искомым. Возьмем некотоРУю точкУ х = (х!, хз, хз), дл Я котоРой хз+хззс'з/з. Это значит, что точка х находится в треугольнике АВРз. Отношение х~ > уз означает, что точка У = (Уь Уь Уз) расположена дальше от вершины Рь чем х, Е т. е. что она находится в трапеции СОРзРз. Точно так же хз > уз означает, что у находится в трапеции ЕРРзРь Таким образом, для всех у, лежа- М щих в параллелограмме СхРРз (считая, что стороны Сх и хР В параллелограмму не принадлежат), х)у.
Построив такие параллелограммы из всех точек, лежащих на отрезках /.О и ОМ, мы ' е ЭК «заметемз весь четырехугольник ОМРз/. Значит, для каж- Рис. 2. дой точки у из этого четырехугольника (за исключением точек на ломаной /.ОМ, т. е. точек, принадлежащих К) найдется такое хан/1, что х ) у. Ввиду симметрии всей картины, такое х ~ К найдется и вообще для каждой точки треугольника, не принадлежащей Я. Вместе с тем ни одна из точек /1 в такой параллелогрдмм не попадет. Следовательно, для х, у ен К отношение х ) у невозможно.
Мы видим, что незначительные различия в формулировках оптимальности для традиционных экстремальных задач превращаются в существенно разные концепции оптимальности для за"дач более широкого типа. Это показывает, в частности, что вопрос 'о формализации понятия оптимального решения ие может быть решен в рамках теории нгр однозначно. Более того, оказывается, что для одних классов нгр естественно принимать одни принципы оптимальности, а для других — совсем иные и даже противоречащие первым. Например, читатель может непосредственно обратиться к примеру Ъ'П.1.4 (дилемма заключенного).
В этой игре участвуют два игрока, которые одновременно являются как коалициями действия, тии н коалициями интересов. Стратегиями первого игрока Предмет и содержание теории игр 16 являются строки матрицы, а стратегиями второго — ее столбцы. Пара чисел, напнсаная в каждой из четырех клеток матрицы, представляет собой выигрыш первого и второго игроков. Здесь выбор игроками их первых стратегий оптимален в том смысле, что оба они получают достаточно большие выигрыши, Вместе с тем никакая взаимная договоренность игроков выбирать именно первые стратегии не может считаться устойчивой, так как каждый нарушивший ее игрок получает от этого нарушения больший выигрыш. Наоборот, выбор игроками своих вторых стратегий приводит к устойчивой ситуации, но выигрыши игроков в ней малы.