Теория игр. Основные понятия: Текст лекций

ÌÈÍÈÑÒÅÐÑÒÂÎ ÎÁÐÀÇÎÂÀÍÈß ÐÎÑÑÈÉÑÊÎÉ ÔÅÄÅÐÀÖÈÈ

Ñàíêò-Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò àýðîêîñìè÷åñêîãî ïðèáîðîñòðîåíèÿ

Е. Р. Даниловцева, В. Г. Фарафонов, Г. Н. Дьякова

ТЕОРИЯ ИГР. ОСНОВНЫЕ ПОНЯТИЯ Текст лекций

Ñàíêò-Ïåòåðáóðã 2003

УДК 519.8 ББК 22.18 Д18 Даниловцева Е. Р., Фарафонов В. Г., Дьякова Г. Н. Д18 Теория игр. Основные понятия: Текст лекций/ СПбГУАП. СПб., 2003, 36 с.: ил. В тексте лекций излагаются основные понятия теории игр. Подробно рассмотрена теория антагонистических игр. Разобраны примеры решения матричных игр. Текст лекций предназначен для студентов, обучающихся по специальности “Математические методы в экономике”. Рецензенты: кафедра высшей математики Санкт-Петербургского государственного университета аэрокосмического приборостроения; доцент Ю. П. Данилов Утверждено редакционно-издательским советом университета в качестве текста лекций

© СПбГУАП, 2003 Учебное издание Даниловцева Елена Рафаиловна Фарафонов Виктор Георгиевич Дьякова Галина Николаевна ТЕОРИЯ ИГР. ОСНОВНЫЕ ПОНЯТИЯ Текст лекций Редактор А. В. Подчепаева Компьютерная верстка М. А. Даниловой Подписано к печати 26.09.03. Формат 60×84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 2,32. Уч. -изд. л. 2,13. Тираж 100 экз. Заказ № Редакционно-издательский отдел Отдел электронных публикаций и библиографии библиотеки Отдел оперативной полиграфии СПбГУАП 190000, Санкт-Петербург, ул. Б. Морская, 67

2

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

Наконец, примерами конфликтных ситуаций являются обычные игры: салонные, карточные, шахматные, морской бой и т. д. Для конфликта характерно следующее: ни один из его участников заранее не знает решений, принимаемых остальными участниками, т. е. вынужден действовать в условиях неопределенности; ход событий в конфликте зависит от решений, принимаемых каждой из сторон, поэтому поведение любого участника конфликта, если оно разумно, должно определяться с учетом возможного поведения всех его участников. Подводя итог сказанному, отметим, что общим, объединяющим все конфликты, независимо от их физической и социальной природы, является: 1) столкновение интересов нескольких (двух или более) сторон, в том числе сознательных индивидуумов или природы; 2) преследование сторонами различных целей; 3) наличие наборов альтернатив для достижения этих целей, каждая из которых приводит к одному (или к одному из нескольких) возможных исходов. 2. Понятие игры. Классификация игр. Формальное представление игр Игрой называется математическая модель конфликта. Математическая модель конфликта должна отражать присущие ему черты, а значит, должна описывать: множество заинтересованных сторон (игроков); возможные действия каждой из сторон (стратегии и ходы); интересы сторон, представленные функциями выигрыша ( платежа) для каждого из игроков. В теории игр предполагается, что функции выигрыша и множество стратегий, доступных каждому из игроков общеизвестны, т. е. каждый из игроков знает свою функцию выигрыша и набор имеющихся в его распоряжении стратегий, а так же функции выигрыша и стратегии всех остальных игроков. В соответствии с этой информацией каждый из игроков организует свое поведение. Различные виды игр можно классифицировать следующим образом: по числу игроков; по числу стратегий; 4

по свойствам функции выигрыша; по возможности предварительных переговоров и взаимодействия между игроками в ходе игры. По числу игроков различают игры с двумя, тремя и более участниками. В принципе возможны так же игры с бесконечным числом игроков. По числу стратегий различают конечные и бесконечные игры. В конечных играх игроки располагают конечным числом возможных стратегий. Например, в игре в орлянку у игроков по две стратегии – «орел» или «решка». В бесконечных играх игроки имеют бесконечное число возможных стратегий. Например, при взаимодействии продавца и покупателя каждый из игроков может назвать любую цену и любое количество продаваемого (покупаемого) товара. По свойствам функции выигрыша различают игры: с нулевой суммой, когда выигрыш одного игрока равен проигрышу другого, т. е. налицо прямой конфликт между игроками; с постоянной разностью, в которых игроки и выигрывают, и проигрывают одновременно, так что им выгодно действовать сообща; с ненулевой суммой, где есть и конфликты, и согласованные действия игроков. По возможности предварительных переговоров и взаимодействия между игроками в ходе игры различают кооперативные и некооперативные игры. Игра называется кооперативной, если до начала игры игроки образуют коалиции и принимают взаимообязывающие соглашения о своих стратегиях (например, образование коалиций в парламенте перед голосованием по некоторым вопросам). Игра, в которой игроки не могут координировать свои стратегии подобным образом, называется некооперативной (например, все игры с нулевой суммой). Рассмотрим примеры формального представления игр. Обозначим через I множество всех игроков, через Si – множество возможных действий игрока i (i∈I), называемое множеством стратегий. Например: а) игра в орлянку I = {1, 2}, Si = {Орел, Решка}; б) голосование в парламенте I = {1, 2, …, n}, где n – число голосующих, Si = {За, Против, Воздержался}; в) взаимодействие на рынке двух продавцов 5

I = {1, 2} Si = {Pi: Pi > 0}, где Pi – цена продаваемого товара. В партии игроки выбирают каждый свою стратегию si ∈ Si, в результате чего складывается набор стратегий s = (s1, s2,…,sn), называемый ситуацией. В рассмотренных выше примерах приведем возможные ситуации: а) (Орел, Орел), (Орел, Решка), (Решка, Орел), (Решка, Решка); б) (За, За, Против, За, Воздержался, …, Против); в) (5 рублей, 3 рубля), (5 рублей, 7 рублей). Заинтересованность игроков в конкретных ситуациях проявляется в том, что каждому игроку i в каждой ситуации s присваивается число, выражающее степень удовлетворения его интересов в данной ситуации. Это число называется выигрышем игрока i и обозначается H i(s). Вернемся к указанным выше примерам. В игре в орлянку: H1(Орел, Орел) = H1(Решка, Решка) = 1, H1(Орел, Решка ) = H1(Решка, Орел ) = –1, H2(Орел, Орел) = H2(Решка, Решка) = –1, H2(Орел, Решка) = H2(Решка, Орел) = 1. Видно, что в любой ситуации H1 + H2 = 0. Запишем это в виде матрицы выигрышей, где строки будут соответствовать стратегиям 1-го игрока, столбцы – стратегиям 2-го игрока. 1  1 −1   −1 H1 =  , H2 =   . 1  −1  1 −1  При этом или H1 + H2 = 0. Таким образом, орлянка является примером игры с нулевой суммой. При голосовании в парламенте: если проголосовавших “За” больше, чем проголосовав10, ших “Против” (вопрос прошел),   если проголосовавших “За” меньше, чем проголосовавHi =  7, − ших “Против” (вопрос не прошел),   для участников голосования i = 1, 2, …, k (членов одной коалиции);

6

если проголосовавших “За” больше, чем проголосовавших “Против” (вопрос прошел), если проголосовавших “За” меньше, чем проголосовавших “Против” (вопрос не прошел), для участников голосования i = k + 1, …, n (членов другой коалиции). В случае взаимодействия на рынке двух продавцов предположим, что потребитель приобретет товар у фирмы, объявившей меньшую цену, или распределит свой спрос поровну между фирмами в случае, если цены равны. Если d(p) – функция спроса в зависимости от цены на товар, то функция выигрыша:

10,   Hi =   5, 

p1 < p2 ,  p1 × d ( p1 ),  1-й фирмы H1 ( p1 , p2 ) = 1/ 2 × p1 × d ( p1 ), p1 = p2 , 0, p1 > p2 ;  p1 < p2 , 0,  2-й фирмы H 2 ( p1 , p2 ) = 1/ 2 × p1 × d ( p1 ), p1 = p2 ,  p × d ( p ), p1 > p2 . 2  2

3. Определение бескоалиционной игры Бескоалиционной игрой будем называть такую игру, в которой целью каждого игрока является получение по возможности большего индивидуального выигрыша. Обозначим: I – множество всех игроков. Далее будем считать I конечным. Обычно принято различать игроков по номерам, т. е. считать I = {1, 2, …, n}; Si – множество стратегий игрока i ∈ I, т. е. множество возможных действий, имеющихся в распоряжении игрока i. Считается, что Si содержит не менее двух возможных стратегий, иначе его действия заранее определены. Процесс игры состоит в выборе каждым из игроков одной своей стратегии si ∈ S. Таким образом, в результате каждой партии игры складывается система стратегий s = (s1, s2,…,sn), которая называется ситуацией. Множество всех ситуаций S = S1 × S2 × ... × Sn , т. е. S является декартовым произведением множеств стратегий всех игроков. Обозначим: Hi(s) 7

– выигрыш игрока i в ситуации s. Функция Hi , определенная на множестве всех ситуаций, называется функцией выигрыша игрока i. Hi: S → R, т. е. каждой ситуации s ∈ S Hi – сопоставляет вещественное число. Определение 1. Бескоалиционной игрой называется система Г = < I , {Si }i∈ , {H i }i∈I >, в которой I и Si (i ∈ I) являются множеI ствами, а Hi – функции на множестве S = S1 × S2 × ... × Sn , , принимающие вещественные значения.

Определение 2. Бескоалиционная игра Г = < I , {Si } , {H i } >, i∈I i∈I называется игрой с постоянной суммой, если существует такое постоянное число C, что

∑ Hi ( s) =

C ∀ s ∈ S , т. е. сумма выигрышей игро-

i∈I

ков постоянна в любой ситуации. 4. Приемлемые ситуации и ситуации равновесия Ситуацию s в игре Г естественно считать приемлемой для игрока i, если этот игрок, изменяя в ситуации s свою стратегию на какую-либо другую, не может увеличить этим своего выигрыша. Пусть s = ( s1 , s2 , ..., si −1 , si , si +1 , ..., sn ) – произвольная ситуация в игре , а si – некоторая стратегия игрока i. Рассмотрим новую ситуацию s si′ = ( s1 , s2 , ..., si −1 , si′, si +1 ,..., sn ) , получившуюся из ситуации s заменой стратегии si игрока i на si′ . Очевидно,

что s si′ = s, если si′ совпадает с si ( si′ = si ). Определение 3. Ситуация s в игре Г называется приемлемой для игрока i, если H i ( s si′ ) ≤ H i ( s ) , ∀si′ ∈ Si . Смысл названия «приемлемая» состоит в том, что, если в некоторой ситуации s для игрока i найдется такая стратегия si′, что H i ( s si′ ) > H i ( s ) , то игрок i в случае складывающейся ситуации s может получить больший выигрыш, выбирая si′, вместо si. В этом смысле ситуация s для игрока может считаться неприемлемой. Определение 4. Ситуация s называется ситуацией равновесия (или равновесной ситуацией), если она приемлема для всех игроков, т. е. H i ( s si′ ) ≤ H i ( s ) , ∀i, ∀si′ ∈ Si . 8

Из определения видно, что в ситуациях равновесия и только в них ни один игрок не заинтересован в отклонении от своей стратегии. Определение 5. Равновесной стратегией игрока в бескоалиционной игре называется такая его стратегия, которая входит хотя бы в одну из равновесных ситуаций игры. Процесс нахождения ситуаций равновесия в бескоалиционной игре называется решением игры. 5. Пример «Дилемма заключенных» Предположим, игроками 1 и 2 являются преступники, находящиеся в предварительном заключении по подозрению в тяжком преступлении. Прямых улик против них нет, и возможность их обвинения в значительной мере зависит от того, сознаются ли преступники сами. Имеем I = {1, 2}, Si = {Признаться, Не признаться}. Определим заинтересованность игроков в различных ситуациях. Если оба признаются, то будут осуждены на длительный срок, но с учетом смягчающего обстоятельства (добровольного признания) каждый получит срок 5 лет (выигрыш (потери) каждого оценим в –5). Если оба не сознаются, то за отсутствием улик обвинение в тяжком преступлении будет снято, но следствие сможет доказать виновность игроков в менее тяжком преступлении, в результате чего оба получат срок в 1 год (выигрыш (потери) каждого оценим в –1). Если в участии в преступлении сознается один из игроков, то ему удается свалить всю вину на другого. В результате сознавшийся выходит на свободу (выигрыш (потери) 0), а его упорствующий соучастник получит полную меру возмездия – срок 10 лет (выигрыш (потери) –10). Запишем функции выигрышей (потерь) игроков в рассмотренной игре. Пусть П – признание, Н – непризнание, H1 – выигрыш 1-го игрока, H2 – выигрыш 2-го игрока. H1 (П, П) = H 2 (П, П) = –5 , H1 (П, П) = H 2 (П, П) = –1, H1 (П, Н) = H 2 (H, П) = 0, H1 (H, П) = H 2 (П, Н) = –10. В матричной записи, где строки соответствуют стратегиям 1-го, а столбцы стратегиям 2-го игрока, имеем 9

 −5 0  −5 −10  H1 =  , H2 =   .  −10 −1   0 −1  Ситуацией равновесия в данной игре оказывается ситуация (П, П), в которой каждый из игроков должен признаться. В этой ситуации каждый из игроков теряет 5, т. е. оказывается осужденным на 5 лет. В ситуации же (Н, Н), когда ни один не признался, потери каждого всего 1 (каждый осужден на 1 год). Однако данная ситуация явно неустойчива, так как каждый из игроков заинтересован отклониться от выбранной стратегии и признаться, рассчитывая свалить вину на другого и избежать наказания, сведя свои потери к 0 (при этом потери партнера составят 10). Таким образом разумной стратегией для каждого игрока является признание, так как оно гарантирует игроку неполучение максимального срока в 10 лет. Хотя более «выгодной» кажется тактика непризнания, дающая возможность получения незначительного наказания (срок в 1 год), однако чреватая неожиданностью в виде максимального срока в 10 лет в случае признания со стороны соучастника.

6. Стратегическая эквивалентность игр Разнообразие бескоалиционных игр делает желательным объединение их в такие классы, внутри которых игры обладают одними и теми же свойствами. В качестве таких классов можно взять классы стратегически эквивалентных игр. Определение 6. Пусть есть две бескоалиционной игры Г′ и Г′′ с одними и теми же множествами игроков и их стратегий, отличающиеся лишь функциями выигрыша: Г′ = < I , {Si }i∈I , {H i′}i∈I >

Г′′ = < I , {Si }i∈I , {H i′′}i∈I >

,

и пусть существует k > 0, а для каждого игрока существует вещественное Ci такое, что в любой ситуации s Н i′( s ) = k ⋅ H i′′( s ) + ci .

Тогда игры Г′ и Г′′ называются стратегически эквивалентными. Стратегическая эквивалентность игры Г′ игре Г′′ обозначается ′ Г ~ Г′′. 10

Справедливы три свойства стратегической эквивалентности – рефлексивность, симметрия и транзитивность. 1. Рефлексивность. Каждая игра Г стратегически эквивалентна самой себе: Г ~ Г . Д о к а з а т е л ь с т в о. Положим k = 1 и Ci = 0, для всех i в любой ситуации s имеем H i ( s ) = 1 ⋅ H i ( s ) + 0, что и требовалось доказать. 2. Симметрия. Если Г~ Г′ , то Г′~ Г. Д о к а з а т е л ь с т в о. Пусть Г~ Г′ , тогда эти игры имеют одни и те же множества игроков и их стратегий, а функции выигрыша связаны следующим образом: H i ( s ) = k ⋅ H i′( s ) + ci , k > 0, ci ∈ R ⇒ H i′( s ) = 1/ k ⋅ H i ( s ) − ci / k ,

1 > 0, ci / k ∈ R k

⇒ Г′~ Г,

что и требовалось доказать. 3. Транзитивность. Если Г ~ Г ′ и Г′~ Г′′, то Г~ Г′′. Д о к а з а т е л ь с т в о. Пусть Г ~ Г ′ и Г′~ Г′′ , тогда Г, Г′, Г′′ имеют одни и те же множества игроков и их стратегий, а функции выигрыша связаны следующим образом: H i ( s ) = k ⋅ H i′( s ) + ci , H i′( s ) = p ⋅ H i′′( s ) + bi , k > 0, p > 0, ci ∈ R, bi ∈ R.

Тогда H i и H i′′ связаны соотношением H i ( s ) = kpH i′′( s ) + (kbi + ci ) , kp > 0, (kbi + ci ) ∈ R,

что по определению 6 означает эквивалентность Г~ Г′′. Таким образом, отношение стратегической эквивалентности действительно обладает всеми свойствами эквивалентного отношения, и, значит, разбивает множество всех бескоалиционных игр на попарно не пересекающиеся классы эквивалентных друг другу игр. Данное обстоятельство позволяет изучать свойства игр одного класса эквивалентности на примере одной игры из этого класса. Различие между двумя стратегически эквивалентными играми по сути состоит лишь в различии начальных капиталов игроков ci и единиц измерения выигрышей, определяемых коэффициентом k. 11

Поэтому естественно, что разумное поведение игроков в стратегически эквивалентных играх должно быть одинаковым. Теорема 1. Стратегически эквивалентные игры имеют одни и те же ситуации равновесия. Д о к а з а т е л ь с т в о. Пусть Г~ Г′, а s* – ситуация равновесия в игре Г. Докажем, что s* – ситуация равновесия в игре Г′ . Из определения ситуации равновесия s* в игре Г следует, что для всех i ∈ I и si ∈ Si верно следующее: H i ( s * si ) ≤ H i ( s*).

(6.1)

А стратегическая эквивалентность Г и Г′ означает H i ( s*) = kH i′( s*) + ci , H i ( s * si ) = kH i′( s * si ) + ci ;

(6.2) (6.3)

из (6.1), (6.2), (6.3) получаем kH i′ ( s* si ) + ci ≤ kH i′ ( s* ) + ci , откуда (с учетом k > 0) получаем H i′( s * si ) ≤ H i′( s*) ∀ i ∈ I и si ∈ Si ,

что и означает равновесность стратегии s* в игре Г′. Определение 7. Бескоалиционная игра Г = < I , {Si }i∈I , {H i }i∈I > такая, что в любой ситуации s ∈ S суммарный выигрыш игроков равен нулю, называется игрой с нулевой суммой. Теорема 2. Всякая бескоалиционная игра с постоянной суммой стратегически эквивалентна некоторой игре с нулевой суммой. Д о к а з а т е л ь с т в о. Пусть Г = {I , {Si }i∈I , {H i }i∈I } – игра с постоянной

∑ H i ( s) = c, c = const. i∈I Выберем произвольные ci (i ∈ I ), , для которых ∑ c = c, и рассмот-

суммой, т. е. для всех ситуаций s ∈ S верно

i

i∈I

рим игру Г′ = {I ,{Si }i∈I , {H i′}i∈I } с функциями выигрышей Н i′( s ) = H i ( s ) − ci . Видно, что, с одной стороны, Г и Г′ эквивалентны, а, с другой стороны, Г′ – является игрой с нулевой суммой, так как

∑ H i′( s) = ∑ H i ( s) − ∑ ci = c − c = 0 i∈I

12

i∈I

i∈I

∀ s ∈ S.

7. Антагонистические игры Антагонистическая игра является частным случаем бескоалиционной игры. Определение 8. Игра Г = < I , {Si }i∈I , {H i }i∈I > называется антагонистической, если число игроков в ней равно двум, а значения функций выигрыша этих игроков в каждой ситуации равны по величине и (7.1) противоположны по знаку, т. е. H1 ( s ) = − H 2 ( s ), ∀s ∈ S . Из определения следует, что в любой ситуации антагонистической игры H 1 ( s ) + H 2 ( s ) = 0 . Иначе говоря, антагонистическая игра – это игра двух лиц с нулевой суммой. Ясно, что при задании антагонистической игры достаточно задать только одну функцию выигрыша, вторая однозначно определяется из выражения (7.1). Поэтому под антагонистической игрой обычно понимают тройку: Г = < A, B, H >, где А и В – множества стратегий игроков 1 и 2, а Н – функция выигрыша игрока 1, заданная на S = {(a , b): a ∈ A, b ∈ B}. Из теоремы 2 следует, что бескоалиционная игра двух лиц с постоянной суммой стратегически эквивалентна некоторой антагонистической игре. 8. Седловые точки Пусть Г = < A, B, H > – антагонистическая игра. Для ситуации равновесия (a, b) должно быть верно (8.1) H1 ( a , b) ≥ H1 ( a ′, b), a ′ ∈ A; H 2 ( a, b) ≥ H 2 ( a , b′), b′ ∈ B.

(8.2)

Учитывая, что H 2 ( a , b) = − H1 ( a , b), запишем выражение (8.2) как − H1 ( a , b) ≥ − H1 ( a , b′), b′ ∈ B или H1 ( a , b) ≤ H1 ( a , b′), b′ ∈ B. Вместе с (8.1) запишем это в виде двойного неравенства (переходя от обозначения H 1 к обозначению Н для функции выигрыша 1-го игрока) H ( a ′, b) ≤ H ( a , b) ≤ H ( a , b′), a ′ ∈ A, b′ ∈ B.

Это неравенство выражает следующее свойство функции Н в точке (a, b): при любом изменении переменной a значение Н может только уменьшиться, а при изменении значения переменной b – только увеличиться, т. е. по переменной a функция Н невозрастающая, а по переменной b – неубывающая. Таким образом, на поверхности, описывае13

мой функцией Н, в координатах a и b ситуациям равновесия будут соответствовать седлообразные точки поверхности. Замечание. Следует иметь в виду, что понятие седловой точки в теории игр отличается от аналогичного понятия в геометрии. Первое отличие состоит в том, что в теории игр для седлообразной точки необходимо, чтобы в ней достигался максимум именно по первой переменной, а минимум – по второй. В геометрии же от порядка переменных седлообразность точки не зависит. Второе отличие в том, что в геометрии седлообразность точки связана с аналитичностью функции и обращением в ноль соответствующих производных. В теории игр аналитичность экстремумов не обязательна. Кроме того, седловая точка нередко оказывается на границе области задания функции. 9. Отступление в теорию функций Определение 9. Пусть f – функция, заданная на множестве D. Ее супремумом на этом множестве называется наименьшее из всех чисел p таких, что f ( x ) ≤ p при любом x ∈ D. Обозначение супремума: sup f ( x ) или sup f ( x ), если есть ясность x∈D

относительно области задания f(x). Определение 10. Инфимумом функции f на D называется наибольшее из чисел p таких, что p ≤ f ( x ), ∀x ∈ D. Обозначение: inf f ( x ) или inf f ( x ). x∈D

Определение 11. Если супремум функции f на D достигается, т. е. если существует x∗ ∈ D, такое что f ( x )∗ = sup f ( x ), то он называется максимумом. Обозначение: max f ( x ). Определение 12. Если инфимум функции f на D достигается, т. е. если существует x∗ ∈ D такое что f ( x*) = inf f ( x ), то он называется минимумом. Обозначение: min f ( x ). Утверждение 1. Если существует некоторая постоянная c такая, что f ( x ) ≤ c, ∀x ∈ D, то и sup f ( x ) ≤ c; x∈D

14

если некоторая постоянная d такова, что f ( x ) ≥ d , ∀x ∈ D, то и inf f ( x ) ≥ d .

x∈D

Данное утверждение следует непосредственно из определений 9 и 10. Утверждение 2. Если f ( x ) и g ( x ) заданы на D и при любом x ∈ D

верно f ( x ) ≤ g ( x ) , то верно и sup f ( x ) ≤ sup g ( x ) , inf f ( x ) ≤ inf g ( x ). Д о к а з а т е л ь с т в о. Из условия и определение супремума имеем f ( x ) ≤ g ( x ) ≤ sup g ( x ) = const ⇒ с учетом утверждения 1 sup f ( x ) ≤

≤ sup g ( x ). Аналогично доказывается неравенство для инфимумов. Теорема 3. Если x изменяется в области D , y изменяется в области E , f (x, y ) определена на D × E , то supinf f ( x, y ) ≤ inf sup f ( x, y ). x

y

y

(9.1)

x

Д о к а з а т е л ь с т в о. Имеем при любом x и y f ( x, y ) ≤ sup f ( x, y ). x

Учитывая утверждение 2, получим: inf f ( x, y ) ≤ inf sup f ( x, y ) = const. y

y

x

Справа здесь стоит постоянная. Поэтому в соответствии с утверждением 1 имеем: supinf f ( x, y ) ≤ inf sup f ( x, y ). x

y

y

x

Следствие (Утверждение 3): Если в выражении (9.1) экстремумы достигаются, то max inf f ( x, y ) ≤ min sup f ( x, y ). x

y

y

(9.2)

x

Если, кроме того, достигаются и все внутренние экстремумы, т. е. если ∀ x ∃ min f ( x, y ) и ∀y ∃ max f ( x, y ) , то x

y

max min f ( x, y ) ≤ min max f ( x, y ). x

y

y

(9.3)

x

Неравенства (9.1), (9.2), (9.3) называют иногда неравенствами минимаксов. Они имеют большое значение в теории игр. 15

10. Равенство минимаксов и седловые точки Теорема 4. Для того чтобы функция f ( x, y ) , заданная на множестве D × E , имела седловые точки, необходимо и достаточно, чтобы существовали (т. е. достигались) минимаксы max inf f ( x, y ) , min sup f ( x, y ) y

y

x

(10.1)

x

и выполнялось равенство max inf f ( x, y ) = min sup f ( x, y ). y

x

y

(10.2)

x

Замечание. Подразумевается седлообразность точки в смысле теории игр. Д о к а з а т е л ь с т в о. 1. Необходимость. Пусть f(x, y) имеет седловые точки и (x*, y*) – одна из них. Это означает, что

(

) (

) (

)

f x, y * ≤ f x* , y * ≤ f x* , y .

(10.3)

Применяя к левой части выражения (10.3) утверждение 1 п. 9, получим

(

) (

)

sup f x, y * ≤ f x* , y* . x

(10.4)

Далее, используя определение инфимума применительно к функции g ( y ) = sup f ( x, y ) , получаем x

( )

(

) (

)

inf sup f ( x, y ) = inf g ( y ) ≤ g y * = sup f x, y * ≤ f x* , y* . (10.5) y

y

x

x

Аналогично, применяя к правой части выражения (10.3) утверждение 1 п. 9 и используя определение супремума применительно к функции z ( x ) = inf f ( x, y ) , получим y

( )

(

) (

)

supinf f ( x, y ) = sup z ( x ) ≥ z x* = inf f x* , y ≥ f x* , y * . 10.6) y

x

x

y

Объединяя выражения (10.5) и (10.6), имеем: inf sup f ( x, y ) ≤ sup f ( x, y* ) ≤ f ( x* , y* ) ≤ inf f ( x* , y ) ≤ supinf f ( x, y ) (10.7) y

x

y

x

⇒ inf sup f ( x, y ) ≤ sup inf f ( x, y ). y

16

x

x

y

x

y

Но, согласно теореме 3, справедливо и противоположное неравенство supinf f ( x, y ) ≤ inf sup f ( x, y ). x

y

y

x

Поэтому inf sup f ( x, y ) = supinf f ( x, y ). y

x

x

(10.8)

y

Значит, в выражении (10.7) крайние части равны. Следовательно, равны друг другу все части этого неравенства. В частности, inf sup f ( x , y ) = sup f ( x , y * ). y

x

x

Таким образом в выражении inf sup f ( x, y ) инфимум достигается y

x

(именно при y = y*) и оно может быть записано как min sup f ( x, y ). y

x

Точно так же из равенства всех частей в выражении (10.7) вытекает, что inf f ( x* , y ) = supinf f ( x, y ), т. е. супремум достигается в точке x* y

y

x

и поэтому вместо sup inf f ( x, y ) мы можем писать max inf f ( x, y ). y x y x В итоге равенство (10.8) может быть переписано следующим образом max inf f ( x, y ) = min sup f ( x, y ), что и требовалось доказать. x

y

y

x

2. Достаточность. Предположим теперь, что минимаксы (10.1) существуют и равны, а внешние экстремумы на них достигаются соответственно в точках x* и y* Это значит, что max inf f ( x, y ) = inf f ( x* , y ). x

y

y

Но, кроме того, по определению инфимума inf f ( x* , y ) ≤ f ( x* , y ), y

так что max inf f ( x, y ) = inf f ( x , y ) ≤ f ( x , y ). *

x

y

*

*

y

(10.9)

Аналогично рассуждая, получаем f ( x* , y * ) ≤ sup f ( x, y * ) = min sup f ( x, y ). x

y

(10.10)

x

По предположению минимаксы (10.1) равны, а значит равны друг другу и все сравниваемые в неравенствах (10.9) и (10.10) выражения. В частности, sup f ( x, y * ) = f ( x* , y * ). x

17

Учитывая, что f ( x, y * ) ≤ sup f ( x, y * ) ∀x, получим x

(10.11) f ( x, y* ) ≤ f ( x* , y * ), ∀x. Точно так же из равенства частей выражения (10.9) имеем inf f ( x* , y ) = f ( x* , y * ). y

С учетом inf f ( x* , y ) ≤ f ( x* , y ) ∀y получаем y

f ( x * , y * ) ≤ f ( x * , y ) ∀y .

(10.12)

Выражения (10.1) и (10.2) вместе дают f ( x, y* ) ≤ f ( x* , y * ) ≤ f ( x* , y ), т. е. (x*, y*) – седловая точка функции f(x, y). Замечание 1. В ходе доказательства этой теоремы (достаточности) было установлено, что в качестве компонент седловой точки могут быть независимо друг от друга взяты любые x и y, на которых достигаются внешние экстремумы в минимаксах (10.1). Поэтому, если (a, b) и (c, d) – седловые точки функции f(x, y), то точки (a, d) и (c, b) так же будут седловыми для этой функции. Это свойство множества всех седловых точек функции называется обычно прямоугольностью множества. Замечание 2. Из выражения (10.9), (10.10), (10.2) вытекает, что значение функции в седловой точке равно общему значению минимаксов (10.1), являющемуся некой константой. Следовательно, значения функции во всех ее седловых точках равны друг другу. 11. Матричные игры Определение 13. Антагонистические игры, в которых каждый игрок имеет конечное множество стратегий, называются матричными играми. Такая игра полностью определяется некоторой матрицей, в которой строки соответствуют стратегиям первого игрока, столбцы – стратегиям второго игрока, а на их пересечении стоит выигрыш первого игрока в соответствующей ситуации H (i, j ) = aij . Эта матрица называется матрицей игры, или матрицей выигрышей. Приняты следующие обозначения. Пусть A
– матрица некоторой игры. 18

 a11 a12 
A =  a21 a22  ... ...   am1 am 2

... a1n  ... a2 n  . ... ...   ... amn 

Такая игра называется m × n –игрой. Стратегии первого игрока – номера соответствующих строк, стратегии второго игрока – номера соответствующих столбцов. Ai . – i-я строка матрицы A
. A. j – j-й столбец матрицы A
. (i, j) – ситуация, где i – номер строки, j – номер столбца. Ситуация (i, j) в матричной игре является равновесной, если aij* ≤ ai* j* ≤ ai* j

∀ i = 1,..., m, ∀ j = 1, ..., n.

В соответствии с теоремой 4 для существования в матричной игре седловых точек (ситуаций равновесия) необходимо и достаточно, чтобы были равны минимаксы: max min aij = min max aij . j j i i Существование этих минимаксов очевидно, так как множества стратегий каждого игрока конечны, а значит экстремумы на них достигаются. Схема нахождения седловых точек матрицы A
:

 a11 a  21  ...   am1 ↓ max ai1 i

→ min a1 j  j  → min a 2 j  j  → max min aij j i → ...   → min a mj  j 

a12 a22 ... am 2

... ... ... ...

a1n  a2n  ...   amn 

↓

↓

↓

...

max ain

max ai 2 i

i

min max aij j

i

Определение 14. Стратегии i

и

j , на которых достигаются

max min aij и min max aij ; называются соответственно максиминной и j i j i минимаксной.

19

Если максимин и минимакс равны друг другу, то их общее значение называется значением матричной игры с матрицей выигрышей A
и обозначается V ( A
). П р и м е р 1. Пусть задана матрица выигрышей −3 5 3

1 A
=  0 2 

−2 4 2

→ min a1 j j   → min a 2j  j   → min a ij j

↓ max ai1

↓ max ai 2

i

=2

  = 0  → max min aij = 2 j i   = 2

↓ max ai 3

i

i

=5 min max aij = 2 j

= −3

=4

i

Максимин и минимакс равны и V ( A
) = 2. Седловой точкой является ситуация (3, 1), образованная 3-й стратегией первого игрока и 1-й стратегией второго игрока. Замечание. Хотя выигрыш в ситуации (3,3) тоже равен 2, но эта точка не является седловой, так как для второго игрока данная ситуация приемлема (проигрыш минимален среди проигрышей третьей строки), а вот для первого игрока – не приемлема (выигрыш не является максимальным среди выигрышей третьего столбца). П р и м е р 2. Пусть задана матрица выигрышей
=  10 30  → 10  → max min a = 20. A ij  40 20  → 20 j i    ↓ ↓ 40

30

⇓ min max aij = 30 j

i

Максимин равен 20 и достигается при i = 2, а минимакс равен 30 и достигается при j = 2. Значит игра не имеет ситуации равновесия в чистых стратегиях. 20

Пусть первый игрок выбрал свою максиминную стратегию i = 2 , тогда второму выгодно выбрать свою стратегию j = 2 и проиграть 20. Но в этом случае первому выгоднее отклониться от своей максиминной стратегии и выбрать i = 1 , выигрывая при этом 30. Тогда второму выгодно выбрать j = 1 и проиграть всего 10. Но в этом случае первый выберет i = 2 и выиграет 40, на что второй ответит выбором j = 2 и проигрышем 20 и т.д. Видно, что ни одна из ситуаций не является приемлемой одновременно для обоих игроков. 12. Смешанные стратегии Если в игре с матрицей A
максимин и минимакс не равны друг другу, то по теореме 4, игра с такой матрицей не имеет ситуации равновесия. В этом случае игрок 1 может обеспечить себе выигрыш max min aij j i (имеет гарантированный выигрыш), а игрок 2 может не дать ему больше, чем min max aij (имеет гарантированный проигрыш). Вопрос о раздеj i ле между игроками разности (эта разность всегда неотрицательна) остается открытым. Поэтому естественно желание игроков получить дополнительные стратегические возможности для уверенного получения в свою пользу возможно большей доли этой разности. Оказывается, игрокам целесообразно выбирать свои стратегии случайно, т. е. определять распределение вероятностей на множестве чистых (первоначальных) стратегий, а затем предоставить выбор конкретной чистой стратегии случайному механизму. Выбор игроками своих чистых стратегий с некоторыми наперед заданными вероятностями – по существу один из планов проведения игры и, таким образом, тоже является некоторой стратегией. В отличие от первоначально заданных (чистых) стратегий, такие стратегии называются смешанными. Определение 15. Распределение вероятностей на множестве чистых стратегий игрока называется его смешанной стратегией. Смешанную стратегию игрока можно представить в виде вектора X = ( x1 , x2 , ..., xn ) ,

(12.1)

где x1 ≥ 0, x2 ≥ 0, ..., xn ≥ 0,

(12.2)

n

∑ xi = 1,

i =1

(12.3) 21

здесь xi – вероятность выбора игроком его i-й стратегии. Таким образом, задание смешанной стратегии игрока состоит в указании тех вероятностей, с которыми выбираются его первоначальные стратегии. Выбор игроком одной первоначальной (чистой) стратегии равносилен заданию смешанной стратегии, в которой выбранная чистая стратегия имеет вероятность 1, а все остальные – 0. Поэтому каждая первоначальная стратегия также может рассматриваться как смешанная. Все чистые стратегии игрока являются ортами в n -мерном евклидовом пространстве векторов вида (12.1): l1 = (1, 0, ..., 0 ) ,

l2 = (0, 1, ..., 0 ) , ..................... ln = (0, 0, ..., 1).

(12.4)

Множество всех векторов (12.1), подчиненных условиям (12.2) и (12.3), составляет (n − 1) -мерный симплекс, натянутый на орты l1, l2, …, ln чистых стратегий. Этот симплекс будем называть фундаментальным и обозначать через S n . В случае n = 2 симплекс является отрезком, в случае n = 3 – треугольником, в случае n = 4 – тетраэдром. (рис. 1). x3

x2 n=2

e2

e3 n =3

S2 S3 e1

x1

e2 e1 x1

Рис. 1

22

x2

13. Смешанное расширение матричной игры Пусть в игре с матрицей выигрышей  a11 a12 ... a1n  a a22 ... a2 n  A
=  21  ... ... ... ...   a   m1 am 2 ... amn  игроки 1 и 2 независимо выбирают свои смешанные стратегии X = ( x1 , ..., xm ) , Y = ( y1 , ..., yn ).

Определение 16. Пара (X, Y) смешанных стратегий игроков в матричной игре называется ситуацией в смешанных стратегиях в этой игре. В условиях ситуации в смешанных стратегиях каждая обычная ситуация (i, j) (в чистых стратегиях) реализуется с вероятностью xi yj. Таким образом, первый игрок получает выигрыш aij с вероятностью xiyj, а математическое ожидание его выигрыша равно m n

∑ ∑ aij xi y j .

i =1 j =1

Это число принимается за выигрыш игрока 1 в ситуации (X, Y) в смешанных стратегиях и обозначается через H ( X , Y ). Определение 17. Смешанным расширением матричной игры называется антагонистическая игра < Sm , Sn , Н >, в которой стратегиями игроков являются их смешанные стратегии в исходной игре, а функция выигрыша игрока 1 определяется как m

n

H ( X , Y ) = ∑ ∑ aij xi y j . i =1 j =1

(13.1)

В обозначениях скалярных произведений (13.1) можно переписать m

n

m

i =1

j =1

i =1


T, H ( X , Y ) = ∑ xi ∑ aij y j = ∑ xi Ai ⋅Y T = XAY

(13.2)

где использованы обозначения:

W T = ( w1 , w2 ,..., wn )

T

 w1  w  =  2  – вектор-столбец,  ...   w   n

23

 w1  n Z W = ( z1 , ..., zn )  ...  = ∑ zi wi – скалярное произведение векто w  i =1  n ров Z и W. Таким образом, T


T. H ( X , Y ) = X AY

(13.3)

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

(X

*

, Y*

)

является седловой точкой (ситуацией равновесия), если выполняется двойное неравенство
*T ≤ X * AY
*T ≤ X * AY
T X AY

(

)

(

∀X ∈ S m , ∀Y ∈ S n ,

)

(

)

H X , Y * ≤ H X *, Y * ≤ H X *, Y .

(13.4)

Лемма 1 (о переходе к смешанным стратегиям). Пусть Y – произвольная стратегия игрока 2, a – некоторое число: T AY ≤ a , i = 1, ..., m, i

(13.5)

тогда для любой смешанной стратегии X = ( x1 , ..., xn ), X ∈ Sm верно
T ≤a. XAY Д о к а з а т е л ь с т в о. Умножим каждое из неравенств (13.5) на xi (знак неравенства не изменится, так как xi ≥ 0 ). Получим T xi AY ≤ xi a , i = 1, ..., m. i Сложим все полученные неравенства: m

m

m

i =1

i =1

i =1


T = ∑ x AY T ≤ ∑ x a = a ∑ x = a ⋅ 1 = a , XAY i i i i

что и требовалось доказать. Замечание. Точно так же осуществляются переходы к смешанным стратегиям в неравенствах вида T
T ≥ a ∀X ∈ S , AY ≥ a i = 1, ..., m ⇒ XAY i m T
XA j ≤ a j = 1, ..., n ⇒ XAY ≤ a ∀Y ∈ Sn ,

XA j ≥ a

24

j = 1, ..., n ⇒ XAY T ≥ a ∀Y ∈ Sn .

Теорема 5. Для того чтобы ситуация

( X *, Y * ) была равновесной,

необходимо и достаточно, чтобы при всех i = 1, ..., m и j = 1, ..., n выполнялись неравенства *T
*T ≤ X * A . ≤ X * AY AY i j

Д о к а з а т е л ь с т в о. 1. Необходимость. Пусть

(13.6)

( X *, Y * )

–

ситуация равновесия. ⇒ верны неравенства (13.4) при всех X ∈ Sn и Y ∈ Sn ⇒ верны неравенства (13.6), так как они получаются из неравенств (13.4) как частный случай при X = li , Y T = l j T . 2. Достаточность. Пусть верны неравенства (13.6) при всех i = 1, ..., m и j = 1, ..., n. Применим к обеим сторонам неравенств (13.6) лемму о переходе к смешанным стратегиям. Это даст нам неравенства (13.4).

(

)

* * Теорема 6. Если ситуация i , j в чистых стратегиях является рав-

новесной для матричной игры с матрицей A
, то она является равновесной и для ее смешанного расширения. Д о к а з а т е л ь с т в о. ной игре с матрицей A
,

(i , j ) – равновесная ситуация в матрич*

⇔ aij* ≤ ai* j* ≤ ai* j

*

∀i = 1, ..., m, ∀i = 1, ..., n.

(13.7)

Но неравенства (13.6) превращаются в (13.7), если подставить X = i* , Y * = j*. Значит, неравенства (13.6) справедливы для таких *

X * , Y * и ситуация ( X * = i* , Y * = j* ) – равновесная ситуация для смешанного расширения игры. Оказывается, что ситуации равновесия в смешанном расширении существуют для любой матричной игры. Замечание. Далее удобно обозначать смешанную стратегию, соответствующую чистой стратегии i , тем же символом i. Тогда, i ⋅ A
= Ai⋅ , A
⋅ j T = A⋅ j .

(13.8)

25

14. Существование минимаксов в смешанных стратегиях. Равенство минимаксов


T. Лемма 2. 1. При любом Y0 ∈ Sn существует максимум max XAY 0 X


T. 2. При любом X 0 ∈ Sm существует минимум min X 0 AY Y

Д о к а з а т е л ь с т в о.

1. Рассмотрим функцию


T = ∑ x AY T . Эта функция линейна по x , ..., x , F ( x1 , ..., xm ) = XAY 0 i i 0 1 m i

а потому является непрерывной функцией от x1 , ..., xm . Множество Sm – замкнутое, ограниченное. ⇒ Функция F ( x1 , ..., xm ) достигает на Sm (в силу непрерывности) своего максимума. 2. Второе утверждение леммы доказывается аналогично.
T – непрерывная функция Y. Лемма 3. 1. max XAY X


T – непрерывная функция X. 2. min XAY Y

Данная лемма приводится без доказательств.
T и min max XAY
T существуют. Теорема 7. Минимаксы max min XAY X

Y

Y

X

Д о к а з а т е л ь с т в о. 1. Sn – замкнутое ограниченное множество
T достигает на S (в силу непрерывности) сво⇒ функция max XAY n X


T max XAY его минимума, т. е. min существует. Y X
T. Аналогично доказывается существование max min XAY X

Y

Теорема 8. (теорема о минимаксах) Какова бы ни была матрица A
:
T = min max XAY
T. max min XAY X

Y

Y

X

(14.1)

Или, другими словами, равновесные смешанные стратегии игроков существуют. Без доказательства. 26

Определение 18. Общее значение минимаксов (14.1) называется значением матричной игры с матрицей выигрышей A
. Это значение игры обозначается V ( A
). Соответствие между матричной игрой и ее значением можно понимать как функцию, заданную на множестве всех матричных игр (или, что то же самое, на множестве всех матриц). Выбор игроком 1 стратегии X 0 , по которой достигается внешний максимум в (14.1) – наилучшее из всего того, что он может предпринять, так как этот максимум будет получен им, как бы ни складывались обстоятельства. Выбор игроком 2 стратегии Y0 , по которой достигается внешний минимум в (14.1) – наиболее целесообразное из его действий, так как при этом он не даст игроку 1 больше этого минимакса, как бы ни складывались обстоятельства. Таким образом, игроки 1 и 2 должны выбирать такие свои стратегии, которые в игре составляют седловую точку. Определение 19. Равновесные стратегии игроков в антагонистической игре называются их оптимальными стратегиями. Определение седловой точки ( X * , Y * ) можно переписать теперь в виде
*T ≤ V ≤ X * AY
T при всех X ∈ Sm , Y ∈ Sn . XAY

(14.2)

Мы видим, что выбор игроком 1 оптимальной стратегии дает ему выигрыш не меньший, чем значение игры, что бы ни делал при этом игрок 2. Выбор игроком 2 его оптимальной стратегии всегда причиняет ему ущерб не больший, чем значение игры, что бы ни делал при этом игрок 1. Следовательно, выбор каждым из игроков своей оптимальной стратегии не имеет смысла скрывать от противника. Это дает основание называть матричную игру вполне определенной. Определенность игры понимается в том смысле, что в условиях применения игроками смешанных стратегий однозначно устанавливается математическое ожидание выигрыша игрока 1. Фактические же значения выигрыша игрока 1 в отдельных партиях могут быть различными.

27

15. Три свойства значения игры Теорема 9. В матричной игре с матрицей выигрышей A
V ( A
) = max min XA⋅ j = min max Ai⋅Y T , j

X

Y

(15.1)

i

причем внешние экстремумы достигаются на оптимальных стратегиях игроков. Приводится без доказательства. Теорема 10. Для любой матрицы A
верно max min aij ≤ V ( A
) ≤ min max aij , i

j

j

(15.2)

i

Д о к а з а т е л ь с т в о. 1. Докажем левое неравенство. Из выражения (15.1) следует, что V ( A
) = max min XA⋅ j . X

j

Но max min XA⋅ j ≥ max min iA⋅ j = max min aij , так как переход от проX

j

j

i

j

i

извольных смешанных стратегий к частным лишь сужает область максимизации и может лишь уменьшить внешний максимум. ⇒ V ( A
) ≥ max min aij , что и требовалось доказать. j

i

2. Правая часть неравенства доказывается аналогично. Теорема 11. 1. Если игрок 1 имеет чистую оптимальную стратегию i0, то V = max min aij = min a i0 j . j

i

(15.3)

j

2. Если игрок 2 имеет чистую оптимальную стратегию j0, то V = min max aij = max aij0 . j

i

(15.4)

i

Д о к а з а т е л ь с т в о. 1. Согласно (15.1) V = max min XA⋅ j . Из X

условия теоремы максимум достигается на

j

X = i0 ,

max min XA⋅ j = min i0 A⋅ j = min a i0 j , что и требовалось доказать. X

j

j

j

2. Доказывается аналогично.

28

т. е.

16. Доминирование стратегий Определение 20. 1. Стратегия X ′ игрока 1 строго доминирует стратегию X ′′, ( X ′′ – строго доминируется X ′ ), если X ′A⋅ j > X ′′A⋅ j при любом j = 1, ..., n. 2. Стратегия Y ′ игрока 2 строго доминирует стратегию Y ′′ , ( Y ′′ строго доминируется стратегией Y ′ ), если Ai⋅Y ′T < Ai⋅Y ′′T при любом i = 1, ..., m. Определение 21. 1. Стратегия X ′ игрока 1 доминирует стратегию X ′′, ( X ′′ доминируется X ′ ), если X ′A⋅ j ≥ X ′′A⋅ j при любом j = 1, ..., n. 2. Стратегия Y ′ игрока 2 доминирует стратегию Y ′′, ( Y ′′

доминируется Y ′ ), если Ai⋅Y ′T ≤ Ai⋅Y ′′T при любом i = 1, ..., m. В частности: 1. Чистая стратегия i ′ игрока 1 строго доминирует (доминирует) чистую стратегию i ′′ , если ai′j > ai′′j при всех j, ( ai′j ≥ ai′′j при всех j ). 2. Чистая стратегия j ′ игрока 2 строго доминирует (доминирует) чистую стратегию j ′′, если aij′ < aij′′ при всех i , ( aij′ ≤ aij′′ при всех i ). Определение 22. Спектром смешанной стратегии игрока называется множество всех его чистых стратегий, вероятность применения которых согласно этой стратегии положительна. Чистые стратегии, входящие в спектр данной смешанной стратегии, называются существенными для нее. Теорема 12. Если чистая стратегия одного из игроков содержится в спектре некоторой его оптимальной стратегии, то выигрыш этого игрока в ситуации, образованной данной чистой стратегией и любой оптимальной стратегией другого игрока, равен значению игры. * Д о к а з а т е л ь с т в о. Пусть i0 содержится в спектре X – оптимальной стратегии игрока 1. Тогда вероятность применения i0 в смешанной стратегии X * положительна xi0 > 0 . *

(

)

Пусть Y – оптимальная стратегия игрока 2. X * ,Y * – ситуация равновесия, а значит *


*T = V ( A
) X * AY

(16.1) 29

Тогда по теореме 5 для любого i верно Ai 0Y *T < V .

(16.2)

Предположим, что утверждение теоремы 12 неверно. Это значит, что Ai 0⋅Y *T < V .

(16.3)

Суммируя по i неравенства (16.2), умноженные каждое на xi , и *

учитывая неравенство (16.3), получим
*T = ∑ x A Y *T < ∑ x V = V ∑ x = V . X * AY i i⋅ i i *

i

*

i

*

i


*T < V , что противоречит раТаким образом, получено X * AY венству (16.1). Значит, наше предположение неверно и утверждение теоремы 12 *T

справедливо, т. е. Ai0 Y = V . Что и требовалось доказать. Утверждение теоремы 12 можно записать следующим образом: если * X , Y * – оптимальные стратегии игроков 1 и 2, то n

Ai0 ⋅Y *T = ∑ ai0 j y j = V , для i таких, что xi * > 0, 0 0 *

j =1

m

X * A⋅ j0 = ∑ aij0 xi = V , для j таких, что 0 *

i =1

y j0 > 0. *

(16.4) (16.5)

Теорема 13. Ни одна строго доминируемая чистая стратегия игрока не содержится в спектре его оптимальной стратегии. Д о к а з а т е л ь с т в о. Пусть Y 0 строго доминирует чистую j0, а X* – некоторая оптимальная стратегия игрока 1. Тогда Ai⋅ j0 > Ai⋅Y 0 при всех i. Домножая эти неравенства на xi * каждое и суммируя по i, получим
0. (16.6) X * Ai⋅ j0 > X * AY Предположим, j0 содержится в спектре некоторой оптимальной стратегии игрока 2. Тогда по теореме 12 X * Ai⋅ j0 = X * A⋅ j0 = V .

(16.7)


< V , а это проСравнивая выражения (16.6) и (16.7), имеем X AY * тиворечит оптимальности стратегии X (см. (14.2)). 30 *

0

Таким образом, наше предположение неверно, и j0 не может содержаться в спектре оптимальной стратегии игрока 2. Определение 23. Пусть Г = < A, B, H >, Г′ =< A0 , B0 , H ′ >, где A, B – множества чистых стратегий игроков 1 и 2; A0 ⊂ A, B0 ⊂ B, H ′ – сужение H на A0 × B0 . Тогда Г′ называют подыгрой Г. Из определения следует, что множество смешанных стратегий в смешанном расширении Г′ содержится в множестве смешанных стратегий игры Г. Теорема 14. 1. Г = < A, B, H > – конечная антагонистическая игра. Г′ =< A \ i0 , B, H > – подыгра игры Г. 2. i0 – чистая стратегия игрока 1 в игре Г, доминируемая некоторой

X 0 , в спектре которой она не содержится. Тогда всякое решение ( X * , Y * , V ) игры Г′ является решением Г. Без доказательства. Теорема 15. 1. Г = < A, B, H > Г′ =< A, B \ j0 , H > – подыгра игры Г. 2. j0 – чистая стратегия игрока 2, доминируемая некоторой Y0 , в спектре которой она не содержится. Тогда всякое решение Г′ является решением Г. Без доказательства. Теорема 16. 1. i0– чистая стратегия игрока 1 в игре Г, доминируемая некоторой смешанной стратегией X0, не содержащей i0 в своем спектре. 2. j0– чистая стратегия игрока 2 в игре Г, доминируемая некоторой смешанной стратегией Y0, не содержащей j0 в своем спектре. 3. Г′′ =< A \ i0 , B \ j0 , H > – подыгра Г. Тогда всякое решение Г′′ является решением Г. Без доказательства. Теорема 17 (теорема об афинных преобразованиях). Пусть ( X * , Y * , V ) – решение игры Г =< A, B, H > . Тогда ( X * , Y * , kV + C ) – решение игры Г′ =< A, B, kH + C >, где k > 0, C ∈ R .

( )

(

)

(

)

(16.8) Д о к а з а т е л ь с т в о. H i, Y * ≤ H X * , Y * ≤ H X * , j при всех i ∈ A, j ∈ B . * Это условие оптимальности X и Y * (см. теорему 5) в игре Г. Двойное неравенство (16.8) равносильно двойному неравенству

( )

(

)

(

)

kH i, Y * + C ≤ kH X * , Y * + C ≤ kH X * , j + C

(16.9)

при всех i ∈ A, j ∈ B . 31

А это неравенство является условием оптимальности X* и Y* игре Г′ . Кроме того из выражений (16.8) и (16.9) видно, что если

(

)

(

)

V = H X * ,Y * – значение игры Г, то V ′ = kH X * , Y * + C = kV + C – значение игры . 17. Множества оптимальных стратегий игроков в матричных играх Пусть T1 (A) – множество всех оптимальных стратегий игрока 1 в матричной игре с матрицей выигрышей A
. T (A) – множество всех 2

оптимальных стратегий игрока 2.

Теорема 19. Во всякой матричной игре с матрицей выигрышей A
каждое из множеств, является: 1) непустым; 2) выпуклым; 3) замкнутым; 4) ограниченным. Д о к а з а т е л ь с т в о. Проведем только для T1 (A) . 1. Непустота следует из существования оптимальных стратегий, доказательство в п. 14. 2. Для доказательства выпуклости T1 (A) возьмем две оптимальные стратегии игрока 1: X ′ и X ′′ . Имеем для всех j = 1, …, n X ′A⋅ j ≥ V , X ′′A⋅ j ≥ V . Составим стратегию X = λ X ′ + (1 − λ ) X ′′, где λ ∈ [0; 1]. Тогда при любом j = 1, …, n XA⋅ j = (λ X ′ + (1 − λ ) X ′′) A⋅ j = λ X ′A⋅ j + (1 − λ ) X ′′A⋅ j ≥ λ V + (1 − λ )V = V ,

т. е. XA⋅ j ≥ V при всех j, а это есть условие оптимальности стратегии X. 3. Замкнутость. Пусть X1, X2, …, Xe – последовательность оптимальных стратегий игрока 1, сходящихся к X0. Из оптимальности этих стратегий имеем V ≤ X e A⋅ j при всех j = 1, …, n, e = 1, 2, …

32

(17.1)

Тогда, переходя к пределу в неравенстве (17.1), получим

V ≤ lim X e A⋅ j . e →∞

Учитывая непрерывность функции XA⋅ j , по X (так как она линейная),

(

)

имеем V ≤ lim X e A⋅ j = X 0 A⋅ j , а это есть условие оптимальности X0. e→∞

Таким образом, предел последовательности также содержится в множестве T1 (A) . 4. Ограниченность. T (A) ⊂ S m , S m – фундаментальный симплекс

стратегий игрока 1, являющийся ограниченным множеством ⇒ T1 (A) – ограниченное множество. 18. Бескоалиционные игры (общий случай). Смешанное расширение бескоалиционных игр. Теорема Нэша Пусть Г = < I , {Si }i∈I , {H i }i∈I > – произвольная бескоалиционная игра. И пусть Г игра конечная, т. е. множество Si чистых стратегий каждого игрока конечно. Пусть σi – произвольная смешанная стратегия игрока i, т. е. некоторое вероятностное распределение на множестве чистых стратегий Si; σi ( si ) – вероятность реализации чистой стратегии si в смешанной стратегии σi ;

∑

i

– множество всех смешанных стратегий игрока i.

Пусть каждый из игроков применяет свою стратегию σi , т. е. выбирает свои чистые стратегии с вероятностью σi ( si ) . Пусть смешанные стратегии всех игроков i = 1, 2, …, n как вероятностные распределения независимы в совокупности, т. е. вероятность появления ситуации s = (s1 , s2 , ..., sn ) равна σ

(s1 )⋅ σ 2(s2 )⋅ ....... ⋅ σ n (sn ) .

1

Таким образом, имеем вероятностное распределение σ на множестве всех ситуаций σ ( s ) = σ ( s1 , s2 , ..., sn ) = σ1 ( s1 ) ⋅ σ2 ( s2 ) ⋅ ... ⋅ σn ( sn ).

Определение 24. Такое вероятностное распределение σ называется ситуацией игры Г в смешанных стратегиях. Значение функции выигрыша каждого из игроков в ситуации σ оказывается случайной величиной. 33

Определение 25. Значение функции выигрыша Hi на ситуации σ в смешанных стратегиях есть математическое ожидание этой случайной величины H i (σ ) = ∑ H i ( s ) σ ( s ) = s∈S

n

∑ .... ∑ H ( s , ..., s ) ⋅ П σ ( s ) . i

s1∈S1

Определение 26. Игра Г* = < I ,

n

1

i =1

sn ∈Sn

{∑ }

i i∈I

i

i

(25.1)

, {H i }i∈I > , в которой мно-

жество всех игроков есть I, множество стратегий каждого игрока i есть ∑ i , а функции выигрыша Hi определяются равенством (25.1), называется смешанным расширением игры Г. * Напомним, что в бескоалиционной игре Г = < I , {Si }i∈I , {H i }i∈I > s

(

)

* * является ситуацией равновесия, если H i s si ≤ H i ( s ) для всех

i ∈ I и si ∈ Si . Определение 27. Ситуации равновесия смешанного расширения Г* игры Г называются ситуациями равновесия игры Г в смешанных стратегиях. * Таким образом, σ ситуация равновесия в Г, если при всех i и σi выполняется

(

)

H i σ* σi ≤ H i (σ* ).

(25.2)

Теорема 20. Для того чтобы ситуация σ* в игре Г была ситуацией равновесия этой игры (в смешанных стратегиях), необходимо и достаточно, чтобы для любого игрока i и любой его чистой стратегии si выполнялось H i (σ* || si ) ≤ H i (σ* ) .

(25.3)

Д о к а з а т е л ь с т в о. 1. Необходимость этого вытекает из (25.2), так как si – частный случай σi . 2. Для доказательства достаточности возьмем произвольную смешанную стратегию σi игрока i, умножим выражение (25.3) на σi ( si ) и просуммируем по si ∈ Si . 34

Получим

∑ H (σ

*

i

si ∈Si

|| si ) ⋅ σi ( si ) ≤

∑ σ ( s ) ⋅ H (σ ) = *

i

i

i

si ∈Si

= H i ( σ ) ⋅ ∑ σi ( si ) = H i (σ* ) ⋅ 1 = H i (σ* ) , *

si ∈Si

а левая часть неравенства равна H i (σ* || σi ). Таким образом, H i (σ* || σi ) ≤ H i (σ* ) , что и требовалось доказать. Оказывается, что ситуации равновесия в смешанных стратегиях существуют в любой конечной бескоалиционной игре. Теорема 21 (теорема Нэша): В каждой бескоалиционной игре Г = < I , {Si }i∈I , {H i }i∈I > существует хотя бы одна ситуация равновесия в смешанных стратегиях. Приводится без доказательства.

Библиографический список 1. Воробьев Н. Н. Теория игр. Лекции для экономистов-кибернетиков. Л., 1974. 2. Громова Н. Б., Минько Э. В., Прохоров В. И. Методы исследования операций в моделировании организационно-экономических задач: Учеб. пособие. М., 1992. 3. Дюбин Г. Н., Суздаль В. Г. Введение в прикладную теорию игр. М., 1981. 4. Замков О. О. Математические методы для экономистов. МоскваУфа, 1995. 5. Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр. М., 1998.

35

ОГЛАВЛЕНИЕ 1. Конфликт – предмет рассмотрения теории игр ................................ 2. Понятие игры. Классификация игр. Формальное представление игр ......................................................................................................... 3. Определение бескоалиционной игры ................................................ 4. Приемлемые ситуации и ситуации равновесия ............................... 5. Пример «Дилемма заключенных» ...................................................... 7. Антагонистические игры ..................................................................... 8. Седловые точки .................................................................................... 9. Отступление в теорию функций ........................................................ 10. Равенство минимаксов и седловые точки ...................................... 11. Матричные игры ................................................................................. 12. Смешанные стратегии ....................................................................... 13. Смешанное расширение матричной игры ....................................... 14. Существование минимаксов в смешанных стратегиях. Равенство минимаксов .................................................................................... 15. Три свойства значения игры ............................................................. 16. Доминирование стратегий ................................................................ 17. Множества оптимальных стратегий игроков в матричных играх 18. Бескоалиционные игры (общий случай). Смешанное расширение бескоалиционных игр. Теорема Нэша ...................................... Библиографический список ....................................................................

36

3 4 7 8 9 13 13 14 15 18 21 23 26 28 29 32 33 35