Лекция 6. Осторожное поведение

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

Пусть игрок г выберет стратегию s^. Тогда его выигрыш в самой плохой ситуации, то есть гарантированный выигрыш, равен

Mj(si) = minw^Si, s-i).

S-i

Руководствуясь такими ожиданиями, он должен выбрать стратегию с наи­большим гарантированным выигрышем

S j, S j S — j

Это число обозначается как щ. Стратегия s*^, дающая максимум функции щ(-), называется осторожной (prudent) стратегией игрока г а число - га­рантированным результатом (security level) или максимином.

Если все игроки ведут себя осторожно, мы получаем равновесие в осто­рожных стратегиях (s*n). Заметим, что в общем случае выигрыши в таком равновесии превосходят пессимистические ожидания, т.е. Wi(s*jv) > Щ-

Интерес гарантированных результатов (т.е. чисел с^) в том, что никакое разумное решение не может дать игроку меньший выигрыш. В самом деле, он всегда может перейти на осторожную стратегию и получить выигрыш, не меньший щ.

Наряду с числом щ полезно рассматривать другое число (минимакс)

(5i = minmax«i(si, s_0-

Его отличие от п/ в том, что "первыми" должны сходить противники, а игрок г уже на их ход делает свой s^. Отсюда совершенно ясно, что выполнено фундаментальное неравенство

maxmin«i(si, s_i) — ai < А — minmaxw^s^, s-i).

Sj, S — j S — j S j

Впрочем, это неравенство легко доказать и формально. В самом деле, пусть дана функ­ция и от двух переменных, х и у. Тогда, для любых х и у имеет место неравенство

тти(х,-) < и(х,у) < тахЦ-,у)

(здесь гшп2 означает минимум по второму аргументу, а тахх - максимум по первому). Пусть А означает множество "левых" чисел (то есть чисел вида ишь и(.г. •). при всевоз­можных х. Аналогично В означает множество "правых" чисел. Предыдущее неравенство говорит, что любое левое число < любого правого. Но тогда и максимум (или супремум) левых чисел < минимума (инфимума) правых.

Ситуацию с (\ и о' в игре удобно понимать с помощью следующей картинки.

за счет интеллекта

и.

с помощью партнеров

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

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

Антагонистические игры. Понятие гарантированного результата щ представляет интерес для любой игры, так как никакая разумная стратегия не может дать игроку меньше, чем щ. Осторожные же стратегии представля­ют меньший интерес. Тем не менее имеется класс игр (исторически игравший большую роль), где осторожные стратегии также представляют интерес. Это так называемые антагонистические игры. Под антагонистической игрой мы будем понимать игру двух лиц с нулевой суммой, когда выигрыш одного игрока в точности равен проигрышу второго, и\ = —«2- По этой причине часто указывают только выигрыш первого игрока и называют такие игры матричными (а не биматричными). Под и мы понимаем и\.

Пусть а = сх\ = тахй1 тшй2 м(в1, вг) - гарантированный выигрыш 1-го. Тогда

«2 = тахтти2(й1, вг) = тахтт(—вг)) =

= тах(— тахи(в1, вг)) = — П1ттахм(в1, вг) = —А = —0­82 8± 82 8±

Напомним, что а < (3. Смысл его мы уже объясняли: при "правильной" игре игрок 1 никогда не получит меньше а, при "правильной" игре второ­го игрок 1 никогда не получит больше (3. Особый интерес представляет тот случай, когда а и (3 совпадают. В этом случае при "правильной" игре (более точно, при использовании осторожных стратегий обоими игроками) первый игрок получает ровно а (а второй получает —а). В этом случае говорят, что игра имеет цену а.

Можно дать другую формулировку. Вообще, пусть есть (числовая) функция и на про­изведении X х У двух множеств. Седловой точкой (или седловой парой) для функции и называется пара (ж*, у*), такая что

и(х,У*) < и{х*,у*) < и(х*,у)

для любых х е X и у е У.

Предложение. Антагонистическая игра имеет цену тогда и только тогда, когда функция, и имеет седловую точку.

Доказательство. Пусть 81* - осторожная стратегия первого игрока. Тогда, по опреде­лению, а < а (-V | *. .-V.). Аналогично для второго имеем /3 > и (-V |. -V-.*). Если игра имеет цену, т.е. а = /3, то

и(ви, 82) > а = /3 > и(б1, 82*),

для любых ,31 и ,32, что и значит, что (,зи,,32*) - седловая пара.

Обратно, пусть есть седловая пара (з1*,32*); тогда выполняется неравенство

и($1*,$2) > и(зЬ32*)

для любых ,31 и ,з2. Значит и(,31*, ,з2) > ,з2*) для любых ,з2, и, в частности, тт2 и(,31*, ■) >

и(зи,82*). Тем более а, как максимум левых чисел, больше или равно правого,

а > и(зи,82*).

Симметрично, /3 < и(,зи, ,32*). Получаем, что а > /3. С другой стороны, всегда а < [3, значит, а = [3. □

Разумеется, седловая точка вполне может не существовать (т.е. игра может оказаться существенной). Вот простой пример (орлянка)

1,

-1Д

1,1

1,-1

Здесь нет седловой точки, как нет и цены игры.

Выпуклый случай. Покажем, что в одном важном случае седловая точ­ка существует. А именно, мы будем считать, что

1) Множества стратегий X и У суть А(5х) и А(5г) - симплексы смешанных стратегий;

2) функция выигрыша и(х:у) аффинна по х £ X (при фиксированном у) и аффинна по у £ У (при фиксированном х).

Именно такая ситуация возникает при смешанном расширении игры.

Теорема (фон Нейман). В этом случае существует седловая точка.

Приводимое ниже рассуждение дает не только существование седловой точки, но и способ ее нахождения. Для этого полезно геометрически предста­вить данные задачи. Как мы увидим далее, такое представление полезно не только при анализе антагонистических игр.

Геометрическое представление задачи игрока. Будем представлять стратегии игрока (в данном случае - первого) как векторы в пространстве К^2. А именно, стратегии 51 £ Б\ сопоставляет вектор м(в1,-) £ К52. (Особенно удобно это, когда у второго игрока всего две стратегии; тогда все рисуется на плоскости.) В результате множество Б\ реализуется как подмножество в К*52.

Выпустим теперь из точки 51 "отрицательный ортант" в! — К+2. Важную роль играет пересечение его с "биссектрисой", или правильнее - с диагональю, в К52. Диагональю мы называем множество векторов с равными координата­ми, А = {(х, ...,х)} С М52. Так вот, пересечение нашего ортанта (точнее, его границы) с А в точности указывает гарантированный выигрыш при исполь­зовании стратегии 51.

Отсюда вывод. Рассмотрим объединение Л множеств в! — К+2 по всем э\ £ Бх] я буду называть его "внутренней оболочкой" множества $1. Смысл его такой: пересечение его границы дЛ с диагональю А - это в точности точка (а, ...,а).

Аналогично мы можем изобразить /?, только для этого нам придется рас­смотреть "внешнюю оболочку" В нашего множества $1. Она задается системой линейных неравенств

ж(вг) < тахм(-, вг), 52 £ бг-

И снова небольшое размышление делает понятным, что (3 соответствует точ­ке пересечения диагонали А с границей дВ. Неравенство а < (3 видно из очевидного включения Л С В.

Чтобы все это не выглядело слишком абстрактным, рассмотрим конкрет­ный пример

 

г

а

 

1

4

з'

2

2

 

9

0

Соответствующая картинка выглядит так:

 

Представление смешанных стратегий. Посмотрим теперь, что проис­ходит, когда мы добавляем смешанные стратегии. Начнем с первого игрока. Как изобразить на этом рисунке смесь 0.5 (8)5 + 0.5 (8)5"?. Ясно, что эта страте­гия дает ожидаемый выигрыш 0.5-1 + 0.5-9 = 5, если второй применяет и 2, если второй применяет Но это как раз середина отрезка, соединяющего точки в и б". Точно так же обстоит дело и в общем случае. И если мы добавим все смешанные стратегии первого участника, мы получим новое множество Лт = со (Л) = со(51) — К+2. Здесь и далее со(Х) означает выпуклую оболоч­ку множества X. Видно, что ат - а для смешанного расширения - будучи точкой пересечения диагонали А с большим множеством Лт7 тоже выросло.

Теперь подумаем, как представлять смешанные стратегии второго игро­ка. Его чистые стратегии соответствовали координатным функциям на К*52; и(в1, вг) - это по определению 52-ая координата вектора «(въ ')• Рассмотрим смесь (72 = 0.5 ® 52 + 0.5 ® 5;2. Ясно, что

и(в1, 02) = 0.5м(51, 5г) + 0.5м(51, 5'2).

Так что м(51,(72) - это не что иное, как значение линейного функционала 0.552+0.552 в точке 51. И это верно в общем случае. Таким образом мы видим,что смешанные стратегии второго игрока изображаются (неотрицательными) линейными функционалами на К*52.

Теперь уже ясно, как построить "внешнюю оболочку" Вт для смешанного расширения: она задается аналогичной системой линейных неравенств, толь­ко наряду с координатными функциями мы должны рассмотреть все неотри­цательные:

1(х) < тахДвх),

где I пробегает все (неотрицательные) линейные функционалы на К52. Гео­метрически - Вт есть пересечение всех полупространств, содержащих Бг (точ­нее, содержащих Л). И (Зт - (3 для смешанного расширения - соответствует пересечению диагонали А с Вт.

Итак, мы видим, что Лт - это выпуклая оболочка соЛ7 а Вт - это пере­сечение полупространств, содержащих Л. Но основная теорема о выпуклых множествах утверждает, что эти два множества СОВПАДАЮТ! В частности, ат = /?т, то есть смешанное расширение имеет цену.

На самом деле мы получаем сразу и осторожные смешанные стратегии игроков. Для первого - это точка х* пересечения диагонали с границей мно­жества Лт = Вт. А для второго - это функционал /*. опорный к Лт = Вт в точке х*.

В нашем примере картина такая:

 

Точка х* = (3,3); нужно только представить ее как смесь точек из $1. В данном случае это делается однозначно: х% = (3/4) ® в + (1/4) ^в". В качестве 1^ нужно взять функционал (1/3)£+ (2/3)£;.

Теорема об отделении выпуклых множеств. Выше, когда мы заявляли, что Л"'и В"' совпадают, мы пользовались следующим фундаментальным утверждением, которое установил Минковский, Пусть К - выпуклое замкнутое подмножество в пространстве К". Тогда К совпадает с пересечением (замкнутых) полупространств в К", содержащих К.

Иначе говоря, если точка х НЕ принадлежит К, то ее можно отделить от К гипер­плоскостью. Проще всего в этом убедиться так. Рассмотрим на пространстве К" евкли­дову метрику. Пусть теперь у - ближайшая к х точка из /\'. В качестве гиперплоскости Н, отделяющей х от К, можно взять гиперлоскость, проходящую через середину отрезка [х.у] и перпендикулярную к этому отрезку.

Доминирование. В общем случае две стратегии игрока несравнимы - в од­них ситуациях лучше одна, в других - другая. Однако встречаются ситуации, когда одна стратегия несомненно лучше другой.

Определение. Стратегия Si игрока г сильно доминирует стратегию если щ^^^в^) > щ^'^в^) для любой       £ Б^. Если всюду стоят >, то говорят о слабом доминировании.

Контрольный вопрос: может ли доминироваться осторожная стратегия?