close

Вход

Забыли?

вход по аккаунту

?

961.Введение в теорию игр учебное пособие.

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Федеральное агентство по образованию
УДК 519.8
Р 69
Омский государственный университет
им. Ф.М. Достоевского
Рекомендовано к изданию редакционно-издательским советом
ОмГУ
Рецензенты:
доктор физико-математических наук,
профессор А.А. Колоколов,
кандидат физико-математических наук,
доцент В.В. Сервах
В.А. Романьков
Р 69 Романьков В.А. Введение в теорию игр: учебное пособие:
.
для студентов факультета международного бизнеса. – Омск:
.
Изд-во ОмГУ, 2005. – 54 с.
ВВЕДЕНИЕ В ТЕОРИЮ ИГР
ISBN 5-7779-0616-8
Учебное пособие
для студентов факультета международного бизнеса
В пособие включены материалы шести лекций, отражающие основные разделы дисциплины "Теория игр". Содержатся интересные иллюстративные материалы и задачи, решение которых будет способствовать усвоению теории.
Для студентов факультета международного бизнеса (специальности
061500 "Маркетинг" и 060600 "Мировая экономика").
УДК 519.8
Изд-во ОмГУ
Омск 2005
ISBN 5-7779-0616-8
c Омск. госуниверситет, 2005
°
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
.
ОГЛАВЛЕНИЕ
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1. Предмет, происхождение, классификация игр . . . . . . . . . . . . 5
2. Матричные игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1. Конечные игры двух участников . . . . . . . . . . . . . . . . . . . . . .
2.2. Конечные игры двух участников с нулевой суммой . . .
2.3. Максиминная и минимаксная стратегии игроков . . . . . .
2.4. Матричные игры, определенные в чистых стратегиях .
2.5. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
10
11
12
13
18
3. Смешанные стратегии. Теорема Неймана-Нэша . . . . . . . . . 22
3.1. Теорема Неймана-Нэша . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4. Непрерывные игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.1. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5. Кооперативные игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.1. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6. Открытый аукцион . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.1. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3
Предисловие
Теория игр широко используется при планировании и анализе экономических процессов, в управлении, прогнозировании, военном деле и во многих других областях. В современном мире
резко растут издержки от неправильно принятых решений. Данная теория не только моделирует многочисленные ситуации, но
и дает методы поиска оптимального решения, в том числе в случае неопределенности. В последнее время важность этой теории
возрастает, так как стремительное развитие общества приводит
к быстрому изменению ситуации, когда необходимо найти решение и применить его в условиях неопределенности и достаточно
быстро.
К сожалению, в настоящее время практически отсутствуют
учебные пособия и задачники, представляющие теорию игр. Все
это создает дополнительные трудности при изучении предмета.
Данное учебное пособие написано на основе материалов части
курса "Исследование операций и теория игр", читаемого автором
на протяжении нескольких лет студентам факультета международного бизнеса ОмГУ. В него включены выборочный лекционный материал, ряд задач и упражнений.
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. Предмет, происхождение,
классификация игр
Теория игр – это математическая дисциплина, устанавливающая правила поведения в конфликтных ситуациях, обеспечивающие достижение лучших (в некотором заранее заданном смысле)
результатов.
Рассмотренные ранее линейное программирование, динамическое программирование и некоторые другие методы исследования
операций можно рассматривать как "игры против природы". При
этом линейное программирование имеет дело с рядом неполно заданных обстоятельств, а динамическое программирование – с меняющейся обстановкой. Вместе с тем теорию игр, как и линейное
и динамическое программирование, следует считать частью исследования операций.
История. Современный математический подход к изучению
ситуаций, связанных с конфликтами интересов, что составляет
предмет теории игр, обычно приписывают фон Нейману, изложившему его в статьях 1928 и 1937 гг. Хотя следует отметить,
что еще Борель в статьях 1921, 1924 и 1937 гг. дал ясную формулировку важного класса теоретико-игровых задач, ввел понятие
чистых и смешанных стратегий.
Таким образом, у теории игр две родины – Германия (фон
Нейман) и Франция (Борель). В 1944 г. фон Нейман и Моргенштерн издали свою знаменитую книгу "Теория игр и экономическое поведение". Книга вызвала большой интерес и восхищение.
По-видимому, последующему быстрому развитию теории способствовал тот факт, что благодаря ей многие прикладные задачи
военного времени были успешно решены. В дальнейшем влияние
теории игр на другие науки и практическую деятельность продолжало возрастать. В настоящее время появилась потребность
в применении теоретико-игровых методов в сфере электронных
аукционов и некоторых других совершенно новых и порой неожиданных областях.
5
Примеры
Укажем области, в которых теория игр имеет наиболее эффективное приложение.
1. Экономика. Борьбу между фирмами, корпорациями, другими объединениями за рынки, потребителя (например, борьбу
телевизионных компаний за зрителя), льготы и т.п. можно трактовать как "экономические игры".
2. Военное дело. Столкновение интересов, в которых каждая
из сторон не может полностью определять значения переменных,
а исход решается рядом "битв", можно рассматривать как "военные игры". В этой области разрабатываются специфические методы, позволяющие вырабатывать оптимальные или допустимые
стратегии.
3. Политика. В настоящее время известны различные технологии политической борьбы, имеющие большое значение, например, при проведении выборов.
Политические и экономические конфликты, впрочем, наводят
на мысль о существовании "общественного арбитра". Часто признают, что столкновения интересов не должны переходить, например, в открытые угрозы. По-видимому, само цивилизованное существование предполагает оперирование такими понятиями, как
"справедливость"и т. п.
4. Салонные игры. К ним относятся карточные игры типа
бриджа и покера, имеющие свои собственные развивающиеся теории.
По ходу изложения мы будем формировать словарь специальных теоретико-игровых терминов. Приведем важнейшие из них.
Игра – конфликтная ситуация, допускающая математическую
формализацию. Должно быть известно ее описание, т.е. что имеется, что можно делать (какие "ходы"), каковы возможные результаты – исходы игры.
Игроки – участники игры.
Платежная функция – функция, определяющая выигрыши
игроков при различных исходах игры.
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Партия – определенная совокупность ходов в игре, приведшая
к некоторому исходу.
Стратегия – набор правил, формулируемых до игры, которые
определяют выбор хода в любой возможной ситуации.
Чистая стратегия – стратегия, не включающая вероятностный выбор. Обычно в этом случае говорят просто "стратегия".
Смешанная стратегия – стратегия, включающая вероятностный выбор.
Сформулируем основные условия того, когда конфликтная ситуация может считаться игрой в смысле теории игр.
1. Игра должна быть полностью описана. Должны быть указаны каким-нибудь способом ее правила, платежная функция. При
этом не должно возникать неопределенных ситуаций, когда либо не полностью ясны возможности игроков в выборе ходов, либо
не определен или допускает различную трактовку метод вычисления платежной функции. Вместе с тем описание игры и стратегии могут включать в себя вероятности. При этом вероятности
должны быть полностью определены или через функцию плотности, или через дискретную случайную величину, или еще какимнибудь адекватным способом.
2. Игра предполагает участие "разумных"игроков, т.е. предполагается, что игрок из всех возможных рассматриваемых им вариантов выбирает наилучший, то есть дающий ему наибольший
выигрыш, вариант. Предполагается, что игроки не только понимают, что для них лучше, но и знают о предпочтениях других
игроков.
остальных случаях. Рассматриваются игры с нулевой суммой, когда суммарный выигрыш всех игроков равен нулю, игры с постоянной суммой, которые легко сводятся к рассмотрению игр с
нулевой суммой, но также исследуются более сложные игры, когда сумма выигрышей не постоянна. Важный класс составляют
выпуклые игры, в которых выпукла платежная функция. Особое
место в теории занимают кооперативные игры, в принципе допускающие образование коалиций, т.е. объединений игроков с целью
получения максимального совокупного выигрыша.
Примеры игр
Пример 1.1. Игра Морра.
Игра Морра известна еще с античных времен. Иногда ее называют также средневековой каторжной игрой Морра. Существуют
различные ее варианты. Приведем один из них.
Каждый из двух игроков показывает 1 или 2 пальца на правой
руке и 1 или 2 пальца на левой. Если первый покажет на левой
руке столько же пальцев, что и противник, то он получит сумму,
равную числу пальцев, показанных им и противником на правой
руке. В противном случае он проигрывает ту же сумму.
Классификация игр
Игры классифицируют по количеству игроков, количеству стратегий, характеру взаимодействия игроков, характеру выигрыша,
свойствам платежной функции, состоянию информации и т. п.
Так рассматривают игры 2, 3, ... игроков, конечные игры, когда игроков и стратегий конечное число, и бесконечные игры в
Пример 1.2. Простейший вариант покера.
Допустим, что в колоде имеется всего два вида карт – "старшая" и "младшая".
Вначале каждый из игроков кладет в "банк" по 5 долларов. Затем второй из игроков раздает по одной карте – себе и сопернику
(первому игроку).
Первый игрок принимает решение. Либо он пасует, тогда его
выигрыш составит (-5) долларов при любом раскладе карт, либо
он продолжает игру, но при этом он должен добавить в банк 5
долларов. В последнем случае очередное право на решение переходит ко второму игроку.
Второй игрок может пасовать, тогда он при любом раскладе
проигрывает 5 долларов. Либо он может уравнять игру, т.е. добавить в банк 5 долларов.
7
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Мы рассматриваем самый простой из возможных случаев, поэтому предполагаем, что после этого возможного добавления карты автоматически раскрываются. Выигрыш составит 10 долларов
при СМ, (-10) долларов при раскладе МС, 0 долларов при любом
из двух других раскладов.
Мы дали полное описание игры. В таких случаях говорят, что
игра задана в развернутой форме. Нетрудно перечислить все возможные стратегии.
Для первого игрока существует 4 выбора: пасовать при С, пасовать при М, продолжать игру при С, продолжать игру при М.
Для выбора стратегии нужно определить, что он делает при С и
что – при М. Получается 4 варианта. Итого стратегий 4.
Для второго игрока тоже имеется только 4 стратегии, поскольку у него в каждом случае (С или М) всего 2 выбора.
Заметим, что стратегия определяется для данных, доступных
игроку при честной игре.
Обратим внимание также на то, что выигрыши первого игрока
записываются либо со знаком "плюс", либо со знаком "минус", в
последнем случае мы имеем дело с выигрышем второго игрока.
В теории игр часто не говорят "проигрыш", поэтому подобной
терминологии мы будем придерживаться и в дальнейшем.
9
2. Матричные игры
2.1. Конечные игры двух участников
Мы рассмотрим класс игр, в которых участвуют два игрока
с конечными множествами возможных стратегий. Для таких игр
платежную функцию удобно записывать в виде матрицы, поэтому
такие игры принято называть матричными.
Итак, первый игрок имеет возможные стратегии: S1 , S2 , ..., Sm ,
а второй игрок – стратегии: T1 , T2 , ..., Tn . Если первый игрок выбирает стратегию Si , а второй – Tj , то выигрыш первого игрока
составит aij , а выигрыш второго игрока – bij . Для определения
выигрышей необходимо знать пару матриц: A = (aij ), B = (bij ),
имеющих одинаковые порядки – m × n. Заметим, что в теории
игр обычно избегают термин "проигрыш", заменяя его отрицательным выигрышем.
Можно считать, что игра задана матрицей C размера m × n,
строки которой соответствуют стратегиям первого игрока: S1 , S2 ,
..., Sm , а столбцы – стратегиям второго игрока: T1 , T2 , ..., Tn . При
таком соответствии можно заменить слова "первый игрок выбирает стратегию Si " на слова: "первый игрок выбирает строку i".
Соответственно говорим, что "второй игрок выбирает столбец j."
При этом мы, конечно, допускаем вольность речи, но зато выигрываем в образности – строку можно "видеть", и упрощаем рассуждения.
Мы считаем, что на пересечении i-й строки и j-го столбца матрицы C стоит пара соответствующих выигрышей: (aij , bij ). Все это
позволяет называть матрицу C матрицей игры, или платежной
матрицей игры. Напомним все же, что матрица соответствует паре платежных функций aij , bij , аргументы которых i, j пробегают
конечные множества стратегий.
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2.2. Конечные игры двух участников с нулевой суммой
Рассмотрим наиболее хорошо разработанный класс игр. Мы
предполагаем, что в рассматриваемой матричной игре выигрыш
первого игрока всегда равен проигрышу второго. Другими словами, сумма выигрышей игроков равна нулю. Более точно, мы
предполагаем выполнение равенства
A = −B,
(2.1)
что, конечно, означает выполнение равенств
aij = −bij , i = 1, ..., m; j = 1, ..., n.
(2.2)
В таких матричных играх достаточно вместо платежной матрицы C задать матрицу выигрышей первого игрока A. Обычно
именно она называется в данном случае "матрицей игры", или
"платежной матрицей". Матричные игры с нулевой суммой называют антагонистическими, так как интересы игроков в них
прямо противоположны.
Поскольку мы фиксируем матрицу выигрышей первого игрока
в качестве матрицы игры, то и соответственно меняем терминологию, говоря о выигрышах первого игрока и проигрышах второго.
В подобной игре первый игрок стремится максимизировать свой
выигрыш, а второй игрок – минимизировать свой проигрыш. Однако возможности игроков ограничены, ведь они выбирают не выигрыши, а стратегии. Выигрыш определяется по взаимному выбору. При этом один игрок не знает, что выбирает другой.
Основная задача – оптимальный выбор стратегии. Но при этом
нужно еще определить, что в данном случае означает оптимальность.
Кроме стратегий, выбираемых игроком, есть еще стратегия самого выбора, связанная с выбором критерия оптимальности. Та11
ким образом, термин "стратегия" имеет два возможных смысла,
которые не следует путать.
2.3. Максиминная и минимаксная стратегии игроков
Основное допущение: каждый из игроков стремится обеспечить
себе максимальный возможный выигрыш при любых действиях
противника. Таким образом, речь идет о максимальном выигрыше, который может гарантировать себе игрок. Наибольший гарантированный выигрыш определяется при условии, что избранная
данным игроком стратегия как бы становится известной противнику, и тот делает наилучший в данной ситуации выбор. Пусть
первый игрок считает, что какую бы строку он не выбрал, второй
выберет столбец, минимизирующий выигрыш первого.
Тогда для определения оптимального выбора первого игрока
нужно вычислить в каждой строке минимальное значение его выигрыша, а затем выбрать ту строку, в которой данный минимум
максимален. Таким образом, первый игрок выбирает i-ю стратегию, являющуюся решением следующей задачи:
maxi minj aij .
(2.3)
Второй игрок стремится сделать так, чтобы его проигрыш был
минимален. Опять же он заботится о своем гарантированно минимальном проигрыше. Поэтому он должен предполагать, что первый игрок как бы знает выбор им столбца и соответственно принять наилучшее для себя ответное решение. Если второй игрок
выберет j-й столбец, то первый выберет ту строку i, для которой
соответствующий выигрыш aij максимален. Значит, нужно определить в каждом столбце максимальное значение, а затем выбрать
тот столбец, где это значение минимально. Таким образом, второй
игрок вычисляет значение
minj maxi aij .
12
(2.4)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Затем он выбирает ту стратегию j, которая является решением
(2.4).
Стратегия выбора, используемая первым игроком и описанная выше, называется максиминной стратегией. Соответственно,
стратегия второго игрока называется минимаксной.
В общем случае мы не можем сказать, что максиминная и минимаксная стратегии оптимальны в смысле максимизации гарантированного выигрыша. Такой вывод можно сделать только для
следующего подкласса матричных игр.
2.4. Матричные игры, определенные в чистых стратегиях
Допустим, игра с нулевой суммой, заданная матрицей A, такова, что
Сформулируем важные для понимания теоретические утверждения.
Теорема 2.1. (Основное неравенство для максимина и минимакса).
Пусть дана функция двух переменных f (x, y). Тогда имеет место неравенство
maxx miny f (x, y) ≤ miny maxx f (x, y).
(2.6)
В формулировке неявно предполагается, что все указанные максимумы и минимумы существуют. Они заведомо существуют, если
области определения переменных x, y конечны. Отсюда получаем
Следствие. Для любой платежной матрицы A матричной
игры выполнено неравенство
c(1) = maxi minj aij ≤ c(2) = minj maxi aij .
c = maxi minj aij = minj maxi aij .
(2.5)
В этом случае первый игрок может гарантировать себе максимальный выигрыш, равный c, и не может гарантировать больший
выигрыш. В то же время второй игрок не может гарантировать,
что его проигрыш будет меньше, чем c, однако он может гарантировать проигрыш c. Итак, возможности в гарантиях у игроков
сходятся к определенной сумме, равной c. При этом достаточно
использовать максиминную и минимаксную стратегии. Если один
из игроков использует соответствующую из указанных стратегий,
то у другого нет лучшего выбора, чем также использовать соответствующую стратегию. По этой причине максиминная и минимаксная стратегии являются оптимальными. Число c называется
ценой игры в чистых стратегиях. Игры, для которых выполнено равенство (2.5) и существует цена игры в чистых стратегиях
c, называются определенными в чистых стратегиях или просто
определенными играми. Часто также используется термин "игра,
разрешимая в чистых стратегиях".
13
(2.7)
По этой причине c(2) называют верхней, а c(1) – нижней ценой
игры. Мы видим, что игра определена тогда и только тогда, когда
нижняя и верхняя цены совпадают и равны цене игры.
Будем говорить, что точка (x0 , y0 ) является седловой точкой
функции f (x, y), если
f (x0 , y0 ) = maxx f (x, y0 )
и
f (x0 , y0 ) = miny f (x0 , y).
В частном случае платежной матрицы это означает, что
ai0 ,j0 = maxi ai,j0 ,
ai0 ,j0 = minj ai0 ,j .
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Следующее утверждение дает критерий определенности игры.
Теорема 2.2. Матричная игра с матрицей A определена тогда
и только тогда, когда матрица A имеет седловую точку E(i0 , j0 ).
При этом стратегии i0 , j0 как раз будут соответственно максиминной и минимаксной, а значение ai0 ,j0 будет ценой игры c.
Пример 2.1
Какие из следующих матриц имеют седловые

 
µ
¶
3
2 0 3
0 1 3 5
,  −1 1 2  ,  2
1 2 4 6
4
1 0 3
точки?

1
4 .
3
Решение
Для ответа на поставленный вопрос вычислим максимины и
минимаксы.
Возьмем первую матрицу и в каждой из строк найдем минимальное число. Получится набор (0, 1). Значит, maxi minj aij = 1.
Наоборот, выпишем набор максимальных чисел по столбцам. Получится (1, 2, 4, 6). Значит, minj maxi aij = 1. Мы видим, что максимин равен минимаксу, значит, игра имеет седловую точку, и
это точка 21. Можно говорить также, что это точка a21 , хотя это
не совсем точно. Значение a21 не превосходит других значений в
строке, и в то же время оно не меньше, чем другие значения в
столбце.
Во второй матрице наборы выглядят как (0, −1, 0) и (2, 1, 3).
Имеем: maxi minj aij = 0, minj maxi aij = 1, следовательно, игра
не определена и седловой точки у матрицы нет.
В третьей матрице наборы выглядят как (1, 2, 3) и (4, 4). Здесь
также нет седловой точки.
Игра, заданная первой матрицей, определена (в чистых стратегиях), и соответствующие максиминную и минимаксную стратегии игроков можно считать оптимальными. Игры, соответствующие двум другим матрицам, не определены. Соответствующие
стратегии нельзя считать оптимальными, их применение может
приводить к неожиданным результатам.
15
Методы теории матричных игр применяются в различных практических ситуациях. Рассмотрим, например, следующую задачу.
Пример 2.2. Допустим, ожидается эпидемия гриппа, причем
существует как опасность заразиться вирусом А, так и опасность
заразиться вирусом Б. Допустим, что мы не знаем, в каких пропорциях распространятся эти вирусы. В распоряжении правительства имеются два вида противогриппозной вакцины - α и β. Вакцина α гарантирует, что в 70 процентах случаев она обеспечивает защиту от вируса А и в 80 процентах случаев - от вируса
Б. Для вакцины β эти проценты 65 и 85 соответственно. Спрашивается, как организовать процесс прививки, чтобы обеспечить
максимально возможную в среднем защиту? При этом прививать
одному человеку сразу две вакцины нельзя.
Чтобы ответить на поставленный вопрос, запишем матрицу
"платежей" (кстати, мы видим, что "платеж" – понятие условное).
µ
70 80
65 85
¶
.
Что означает эта матрица? Строки соответствуют стратегиям
правительства – типу вакцин α и β. Столбцы соответствуют стратегиям природы – типу вируса А или Б. Мы видим, что иногда
абстрактная игра трактуется как игра против природы. Вычислим максимин – нижнюю цену игры. Он равен 70 и соответствует
стратегии выбора вакцины α. В то же время минимакс также равен 70. Он соответствует вирусу А. Мы видим, что игра определена в чистых стратегиях. Оптимальное поведение правительства
– прививка всем гражданам вакцины α. Природу, которую мы
считаем в данной модели злонамеренной, стремящейся принести
наибольший вред человеку, должна выбирать вирус А.
Возникает вопрос, какой вывод можно сделать, если игра не
будет определена в чистых стратегиях? Пусть, например, матрица
имеет вид
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
µ
90 80
65 85
¶
.
Тогда нижняя цена игры равна 80, а верхняя - 85. В этом случае нельзя рекомендовать правительству прививать всем один и
тот же вид вакцины. Необходимо соблюдать некоторые пропорции, реально прививая одним тип α, а другим – β. Точный смысл
сказанного проявится в следующем разделе.
Мы говорим, в основном, об играх с нулевой суммой. Приведенные методы исследования на самом деле применимы к более
широкому классу игр с постоянной суммой. Мы говорим, что задана матричная игра с постоянной суммой d, если для любых
i, j выполнено равенство aij + bij = d. В этом случае мы можем рассмотреть матричную игру с соответствующими значениями a′ij = aij − d/2, b′ij = bij − d/2. Новая игра будет иметь нулевую
сумму. В то же время все понятия, связанные с оптимальностью
выбора, для нее те же самые, что и для исходной игры. Мы ведем рассуждения на языке "больше-меньше", от сдвига выводы
не меняются.
Пример 2.3
Вспомним пример 1.1 об игре Морра. Запишем матрицу выигрышей первого игрока. Он имеет, так же, как и второй игрок, 4
возможные стратегии. Пронумеруем их следующим образом: S1 1 палец на левой руке и 1 на правой, S2 - 1 и 2 соответственно,
S3 - 2 и 1, S4 - 2 и 2. Для второго игрока нумеруем стратегии
Tj , j = 1, ..., 4, таким же способом. Матрица имеет вид:


2
3 −2 −3
 3
4 −3 −4 

.
 −2 −3 2
3 
−3 −4 3
4
Максимин равен −3, а минимакс 3. Игра не определена в чистых стратегиях. Это не удивительно. Если бы существовали оп17
тимальные чистые стратегии, то при небольшом числе всех возможных стратегий их легко вычислить или нащупать опытным
путем. Игра в этом случае потеряла бы практический интерес.
Есть известные игры, которые по сути своей конечны. Например, шахматы. Мы можем пренебречь повторениями, циклами,
учитывать только возможные позиции, которых конечное число
даже с учетом динамики (для знатоков: в одной статической позиции возможна рокировка или "взятие на проходе", а в другой
нет - динамически это разные позиции). Игры такого типа резко отличаются от игр типа матричных и многих других. В таких
играх выбор хода осуществляется в условиях полной определенности. Если игроки выбрали стратегии, то результат определен.
Если варьировать выбор в соответствии с заданным набором вероятностей для каждой возможной ситуации, то по существу это
мало что добавляет. Всегда есть наилучший чистый выбор по отношению к данной позиции. Банк всех возможных шахматных
партий с реальным доступом к нему погубил бы игру. Спасение
игры в том, что даже сейчас его создание практически не осуществимо.
Задачи
Задача 2.1. Дана матрица игры с нулевой суммой. Определить, существует ли у нее седловая точка. Выяснить, каковы верхняя и нижняя цены игры. Существует ли в данном случае цена
игры в чистых стратегиях?
а)


−8 −17 11 −13
 −14 −25 −10 −10  .
−16 −26 −17 −11
б)


10 −16 −10 13
 −9 11 −13 17  .
13 16
15 −9
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задача 2.2. Дана матрица игры с нулевой суммой. Определить, существует ли у нее седловая точка. Выяснить, каковы верхняя и нижняя цены игры. Существует ли в данном случае цена
игры в чистых стратегиях?
а)


−18 −7
10 −13
 −14
5
−10 −11  .
−16 −16 −17 −11
б)

15 −16 −10 13
 −9 11 −15 17  .
13 −16 15 −11

Задача 2.3. Дана матрица игры с нулевой суммой. Определить, существует ли у нее седловая точка. Выяснить, каковы верхняя и нижняя цены игры. Существует ли в данном случае цена
игры в чистых стратегиях?
а)


7
−6 −10 13
 −14 13 −15 17  .
13 −16 −17 −11
б)
µ
4 2
−3 1
¶

3
1 −5 −6
20 −60 −30
 2
4
8 −3 

,  50 110 75  , 
 4 −3 9 10  .
31 40 −30
12 −3 −4 15



Задача 2.5. Каждый из двух игроков независимо и одновременно называет любое целое число от 1 до 5. Если числа равны,
то первый выигрывает 3 рубля; если числа отличаются на 1, то
второй выигрывает 2 рубля; в остальных случаях выигрывает 1
рубль тот, у которого число больше.
Записать игру в виде матричной. Вычислить нижнюю и верхнюю цены игры. Является ли игра определенной в чистых стратегиях? Если "да", то в каких?
Задача 2.6. Пусть матрицы A, B одинакового размера m × n
имеют седловые точки.
Верно ли в общем случае, что матрица A + B имеет седловую
точку? Другими словами, верно ли, что сумма двух определенных
матричных игр определена?
Задача 2.7. Показать, что если каждая подматрица размера
2 × 2 матрицы A произвольного размера m × n имеет седловую
точку, то и матрица A также имеет седловую точку.
Задача 2.4. Выяснить, какие из следующих матриц соответствуют играм, определенным в чистых стратегиях, а какие - нет.
Для определенных случаев указать оптимальные стратегии игроков и цену игры. Для неопределенных указать нижнюю и верхние
цены игры.
Задача 2.8. Две конкурирующие телевизионные компании R
и Q объявляют одночасовую программу в одно и то же время.
Телевизионная компания R располагает тремя возможными программами r1 , r2 , r3 , а компания Q - четырьмя возможными программами q1 , q2 , q3 , q4 . Телевизионные компании, не зная о намерениях другой стороны, обращаются к экспертам, оценивающим
возможные пары программ.
Эта оценка выглядит следующим образом. Если R заявит свою
1-ю программу, а Q - свою первую, то 60 процентов будут смотреть программу телекомпании R, а 40 процентов - компании Q.
19
20


5
−6 −11 13
 −14 12 −15 17  .
13 −16 14 −11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Соответственно, если Q меняет программы на 2, 3, 4, то получаются проценты: 20 и 80, 30 и 70, 55 и 45; если R выбирает 2-ю
программу, а Q варьирует программы, то получаем проценты 50,
75, 45, 60 для R (проценты для Q легко восстанавливаются); наконец, при выборе R 3-ей программы получаем проценты 70, 45,
35, 30.
Какую программу следует заявить каждой телекомпании? Можно ли на этот вопрос ответить определенно?
Можно ли записать игру как матричную?
21
3. Смешанные стратегии.
Теорема Неймана-Нэша
Пусть задана матричная игра с нулевой суммой, матрица A =
(aij ), i = 1, 2, ..., m; j = 1, 2, ..., n, как и раньше, обозначает матрицу выигрышей первого игрока. До сих пор мы рассматривали
чистые стратегии, особо выделяя из них максиминную стратегию
первого игрока и минимаксную стратегию второго игрока.
Мы уже знаем, что эти стратегии можно считать оптимальными только в случае, если игра определена в чистых стратегиях. Для этого необходимо и достаточно, чтобы матрица A имела
седловую точку. Тогда нижняя и верхняя цены игры совпадают,
и данное значение называется ценой игры в чистых стратегиях.
Цена игры, с одной стороны, – есть гарантированный выигрыш
первого игрока, а с другой – гарантированный проигрыш второго
игрока.
Чистые стратегии представляют собой правила поведения, сформулированные до игры и предусматривающие все возможные игровые ситуации. Однако, если игра не определена в чистых стратегиях, то такое поведение может привести к нежелательным для
игроков последствиям.
Существует ли все-таки оптимальное поведение игроков? Ответ положительный: такие стратегии существуют, только формулируются они с использованием вероятностей. Правила поведения
не являются детерминированными, каждый раз они формируются заново на основе выбранного вероятностного распределения.
Такие стратегии называются смешанными.
Смешанная стратегия представляет собой вероятностную комбинацию чистых стратегий, то есть чистые стратегии, взятые с
определенными вероятностями.
Смешанная стратегия первого игрока задается вектором вероятностей p = (p1 , p2 , ..., pm ), где pi - вероятность
выбора i-й страP
тегии (строки). Ясно, что 0 ≤ pi ≤ 1, m
p
=
1.
i=1 i
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Средний выигрыш первого игрока при условии, что второй игрок выберет чистую стратегию j, равен математическому ожиданию случайной величины, значения которой стоят в j-м столбце
матрицы, а соответствующие вероятности задаются вектором p :
Mj (p) = p1 a1j + p2j a2j + ... + pm amj .
Пусть первый игрок использует максиминную стратегию, то
есть выбирает вектор p с таким условием, что достигается
maxp minj Mj (p).
Рассуждение здесь такое же, как и в случае чистых стратегий:
первый игрок выясняет, чему равен его гарантированный средний выигрыш независимо от действий второго игрока. Чтобы это
определить, он предполагает, что второй игрок при любом выборе
вектора p возьмет такую стратегию j, которая обеспечит ему наименьший средний проигрыш (minj Mj (p)). Еще раз заметим, что
игроки осуществляют свой выбор независимо друг от друга, не
зная выбора соперника. Приведенное рассуждение является абстракцией, позволяющей судить о гарантированном выигрыше.
Закончим рассуждение. Максимальный гарантированный выигрыш первого игрока равен приведенному выше значению
maxp minj Mj (p).
Пусть второй игрок также использует смешанную стратегию,
заданную стохастическим вектором q = (q1 , q2 , ..., qn ), где qj обозначает вероятность выбора им j-й стратегии (столбца). Средний
проигрыш второго игрока при выборе первым чистой стратегии i
вычисляется как математическое ожидание случайной величины,
значения которой стоят в i-й строке матрицы, а соответствующие
вероятности заданы вектором q :
Mi (q) = q1 ai1 + q2 ai2 + ...qn ain .
Можно доказать, что максимин всегда не больше минимакса и
в рассматриваемом случае
maxp minj Mj (p) ≤ minq maxi Mi (q).
Можно также называть значение максимина нижней ценой игры, а значение минимакса - верхней ценой игры. Все это не имеет
существенного значения ввиду следующей знаменитой теоремы основной теоремы теории матричных игр.
Теорема Неймана-Нэша.
Произвольная матричная игра с нулевой суммой определена в
смешанных стратегиях. Это означает, что для любой матрицы
A выигрышей первого игрока выполнено равенство:
c = maxp minj Mj (p) = minq maxi Mi (q).
Векторы p и q, обеспечивающие это равенство, являются оптимальными смешанными стратегиями игроков. Значение c называется ценой игры.
Если один из игроков использует свою оптимальную смешанную (максиминную или минимаксную) стратегию, то лучшим поведением другого игрока будет использование своей оптимальной
смешанной стратегии.
Мы приведем доказательство этой теоремы, использующее основную теорему двойственности из линейного программирования.
Это делается не только потому, что доказательство интересно и
остроумно, но также потому, что доказательство показывает, как
находить оптимальные векторы p и q.
Доказательство.
Второй игрок использует минимаксную стратегию, то есть выбирает вектор q таким образом, чтобы достичь minq maxi Mi (q)).
Будем рассматривать переменные p1 , p2 , ..., pm как переменные
прямой задачи линейного программирования, добавим к ним формальную переменную v. Аналогично, к переменным q1 , q2 , ..., qn
23
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
двойственной задачи добавляется переменная u. Смысл переменных объясним далее. А пока мы по всем правилам строим прямую
и двойственную задачи линейного программирования.
Каждая переменная прямой задачи соответствует одному из
ограничений двойственной задачи, причем переменной v, на которую не накладывается условие неотрицательности, соответствует
равенство, а остальным переменным - неравенства. Левые части
ограничений двойственной задачи записываются по транспонированной матрице ограничений прямой задачи, правые части - коэффициенты целевой функции прямой задачи, неравенства противоположные, коэффициенты целевой функции двойственной задачи
- правые части ограничений прямой задачи. Наконец, так как прямая задача - на максимум, двойственная - на минимум.
Прямая задача
Двойственная задача
переменные:
p1 , p2 , ..., pm , v
переменные
q1 , q2 , ..., qn , u
ограничения на переменные:
pi ≥ 0
ограничения на переменные:
qj ≥ 0
ограничения:
ограничения:
p1 + p2 + ...pm = 1
q1 + q2 + ... + qn = 1
p1 a11 + p2 a21 + ... + pm am1 − v ≥ 0 q1 a11 + q2 a12 + ... + qn a1n − u ≤ 0
p1 a12 + p2 a22 + ... + pm am2 − v ≥ 0 q1 a21 + q2 a22 + ... + qn a2n − u ≤ 0
...........................
........................
p1 a1n +p2 a2n +...+pm amn −v ≥ 0 q1 am1 +q2 am2 +...+qn amn −u ≤ 0
целевая функция: v
целевая функция: u
для переменной v, чтобы выполнялись неравенства в ограничениях прямой задачи, и достаточно большое значение переменной
u для выполнения неравенств в ограничениях двойственной задачи. Вспомним, что согласно основной теореме двойственности,
если прямая и двойственная задачи имеют допустимые решения,
то они обладают оптимальными решениями, причем оптимальные
значения целевых функций совпадают.
Итак, мы получили следующее равенство:
max(v) = min(u).
Перейдем теперь к интерпретации полученного утверждения
для рассматриваемой матричной игры. Ясно, что векторы p, q –
стохастические; можно считать, что они задают смешанные стратегии игроков. Для того, чтобы понять, что означают значения
переменных v, u, перепишем неравенства из ограничений прямой
и двойственной задач в следующем виде:
v ≤ Mj (p) (j = 1, 2, ..., n)
u ≥ Mi (q) (i = 1, 2, ..., m)
Отсюда видно, что максимальное значение v при любом выборе p равно minj Mj (p); значит, оптимум прямой задачи, обозначенный нами как max(v), есть на самом деле maxp minj Mj (p).
Аналогично можно объяснить, что min(u) - это на самом деле
minq maxi Mi (q)). Значит, мы доказали равенство из условия теоремы.
Теорема доказана.
Очевидно, что как прямая, так и двойственная задачи имеют
допустимые решения. Чтобы убедиться в этом, достаточно взять
значения: p1 = p2 = ...pm = 1/m, q1 = q2 = ... = qn = 1/n, удовлетворив тем самым ограничения на переменные и равенства в
ограничениях. А затем нужно выбрать достаточно малое значение
Из доказательства теоремы мы видим, что в общем случае для
того, чтобы найти оптимальные смешанные стратегии игроков в
матричной игре, достаточно решить прямую и двойственную задачи линейного программирования. Мы знаем из теории линейного программирования, что некоторые задачи допускают сравнительно простое графическое решение. Для матричных игр это
задачи с матрицами выигрышей порядка 2 × n или m × 2. Рассмотрим такие задачи.
25
26
оптимум: max(v)
оптимум: min(u)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример 3.1. Используя графический метод, найти оптимальную стратегию первого игрока для матричной игры с матрицей
¶
µ
4 −2 4 −7
.
A=
−7 3 6 −1
A=
µ
5
6 −4 −9
−8 13 −6 10
A=
Решение.
Пусть x = p1 - вероятность выбора первым игроком 1-й стратегии (строки), тогда 1 − x = p2 - вероятность выбора им 2-й
стратегии (строки). Вектор, определяющий смешанную стратегию первого игрока, есть p = (x, 1 − x). Проведем вычисления
средних выигрышей:
M1 (p) = 4x − 7(1 − x) = 11x − 7, M2 (p) = −2x + 3(1 − x) = −5x + 3,
M3 (p) = 4x + 6(1 − x) = 6 − 2x, M4 (p) = −7x − (1 − x) = −6x − 1.
Построим графики четырех полученных выражений Mi (p) как
функций от x. Учитываем, что x изменяется в пределах от 0 до 1.
Затем определим функцию min{M1 (p), ..., M4 (p), по определению
принимающую при каждом x наименьшее из четырех значений
рассматриваемых функций.
Легко видеть, что график этой функции совпадает вначале с
графиком функции M1 (p), а затем после ее пересечения с графиком функции M4 (p) совпадает с графиком M4 (p). Остальные графики проходят выше. Значит, искомое значение c = maxp minj Mj (p)
соответствует точке пересечения графиков функций M1 (p), M4 (p).
Приравнивая 11x − 7 = −6x − 1, получаем x = 6/17. Оптимальная
максиминная смешанная стратегия первого игрока задается вектором вероятностей p = (6/17, 11/17). Цена игры c = 11(6.17)−7 =
−53/17.
Задачи
Задача 3.1. Найти, используя графический метод, оптимальные стратегии первого игрока для матричных игр, заданных следующими матрицами:
27
µ
¶
,A =
µ
0 −7 14 −7
2 −3 −6 9
3 −8 6
11
−9 13 16 −10
¶
¶
,
.
Задача 3.2. Найти, используя графический метод, оптимальные стратегии второго игрока для матричных игр, заданных следующими матрицами:


4 −2

 4 −7 


A=
 −7 3  , A = 
6 −1




3 −5
3
−12

4
8 
−3 
,A =  5
.


−6 6
−10 13 
6 −1
6
−7
Задача 3.3. Дана матрица игры с нулевой суммой:


7
−6 −10 13
 −14 13 −15 17  .
13 −16 15 −11
1-й игрок выбрал стратегию p = (1/3, 1/12, 7/12),
2-й игрок - стратегию q = (2/7, 2/7, 0, 3/7).
Найти средний выигрыш 1-го игрока.
Задача 3.4. Дана матрица игры с

3
−5 −3
 15 −12 12
−7 −3 14
нулевой суммой:

2
11  .
9
1-й игрок выбрал стратегию p = (1/8, 3/8, 1/2),
2-й игрок - стратегию q = (2/9, 1/9, 2/3, 0).
Найти средний выигрыш 1-го игрока.
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задача 3.5. Дана матрица игры с нулевой суммой:


2 3 1 4
 5 −2 2 1  .
4 −3 2 −1
1-й игрок выбрал стратегию p = (1/11, 1/11, 9/11),
2-й игрок - стратегию q = (1/5, 1/5, 0, 3/5).
Найти средний выигрыш 1-го игрока.
Задача 3.6. Дана матрица игры с

3
−5 −3
 15 −12 12
−7 −3 14
нулевой суммой:

2
11  .
9
1-й игрок выбрал стратегию p = (1/8, 3/8, 1/2),
2-й игрок - стратегию q = (2/9, 1/9, 2/3, 0).
Найти средний выигрыш 1-го игрока.
Задача 3.7. Дана матрица игры с нулевой суммой:


5 −2 −3 −4
 6
4 −7
4 .
−5 13 7 −10
1-й игрок выбрал стратегию p = (1/5, 1/5, 3/5),
2-й игрок - стратегию q = (3/5, 1/5, 0, 1/5).
Найти средний выигрыш 1-го игрока.
Задача 3.8. Дана матрица игры с нулевой суммой:


−8
7
 4
−7 


 −9 13  .
9 −10
1-й игрок использует стратегию p = (1/12, 5/12, 1/4, 1/4).
29
Какую стратегию должен выбрать 2-й игрок, чтобы минимизировать свой проигрыш?
Задача 3.9. Дана матрица игры

4 −7
 −5 5

 −7 6
3 −4
с нулевой суммой:


.

1-й игрок использует стратегию p = (1/12, 1/3, 1/6, 5/12).
Какую стратегию должен выбрать 2-й игрок, чтобы минимизировать свой проигрыш?
Задача 3.10. Определить максиминную и минимаксную смешанные стратегии игроков в матричной игре с платежной матрицей:
¶
µ
6 −7 −9 12
.
−6 8 11 −9
Какова цена игры?
Задача 3.11. Определить максиминную и минимаксную смешанные стратегии игроков в матричной игре с платежной матрицей:
µ
¶
6
−5 7 −10
.
−4 −10 12 13
Какова цена игры?
Задача 3.12.
Определить максиминную и минимаксную смешанные стратегии игроков в матричной игре с платежной матрицей:
¶
µ
6
−5 7 −10
.
−4 −10 12 13
Какова цена игры?
30
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задача 3.13.
Определить максиминную и минимаксную смешанные стратегии игроков в матричной игре с платежной матрицей:
µ
¶
−7 −2 9 10
.
−4 8 5 −4
Какова цена игры?
Задача 3.14. Определить максиминную и минимаксную смешанные стратегии игроков в матричной игре с платежной матрицей:
µ
¶
9 −4 6 4
.
4 −6 3 −3
Какова цена игры?
Задача 3.15. Определить максиминную и минимаксную смешанные стратегии игроков в матричной игре с платежной матрицей:
µ
¶
−5 −2 11 10
.
4 −1 −12 −8
Какова цена игры?
Задача 3.18. Найти оптимальные стратегии игроков в неопределенной матричной игре из примера 2.2.
Задача 3.19. Вычислить цену неопределенных игр из задач
2.2, 2.3.
Задача 3.20. Найти оптимальные стратегии игроков для матричной игры из задачи 2.5.
Задача 3.21. Нападающая сторона, располагающая k войсковыми частями, должна осуществить прорыв через n пунктов обороны защищающейся стороны. Та, в свою очередь, располагает s
войсковыми частями. Нападение и оборона располагают свои силы по n пунктам, не имея информации о распределении сил противником. В один пункт разрешается направлять сразу несколько частей, можно не направлять ни одной. Каждая часть обороны, расположенная на любом из пунктов, уничтожает точно одну
часть нападения, направленную в этот пункт. Не уничтоженная
часть нападения прорывается через этот пункт.
Составить и решить матричную игру, считая выигрышем нападения (и проигрышем обороны) число прорвавшихся через оборону частей.
Решить задачу при следующих конкретных данных: k = 4, n =
2, s = 6; k = 4, n = 2, s = 7; k = 5, n = 2, s = 8; k = 3, n = 2, s =
6; k = 40, n = 2, s = 65; k = 14, n = 3, s = 26.
Задача 3.16. Дана матричная игра с платежной матрицей
A = (aij ) порядка m × m, элементы которой определяются равенствами: aij = 1, если i 6= j, aii = 0.
Докажите, что оптимальными стратегиями игроков будет выбор строк или столбцов с равными вероятностями. Чему равна
цена игры?
Задача 3.17. Дана матричная игра с платежной матрицей A =
(aij ) порядка m × m, элементы которой удовлетворяют тождеству
aij = −aji . Такие матрицы называются кососимметрическими.
Докажите, что цена игры равна 0.
31
32
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4. Непрерывные игры
maxα (minβ H(α, β)) = c(1).
До сих пор рассматривались конечные игры, в которых по
определению каждый игрок имел конечное множество стратегий.
Основным результатом являлась теорема Неймана-Нэша об определенности матричных игр в смешанных стратегиях.
Основным примером бесконечных игр для нас будут так называемые непрерывные игры на квадрате.
Рассмотрим единичный (для простоты) квадрат. Пусть первый
игрок выбирает число 0 ≤ α ≤ 1 на левой стороне квадрата – "номер" строки, а второй игрок выбирает число 0 ≤ β ≤ 1 на основании квадрата – "номер" столбца. Таким образом, мы рассматриваем ситуацию, при которой стратегии каждого игрока занумерованы числами интервала [0, 1]. Квадрат удобно использовать для
наглядности. Пусть выигрыш первого игрока равен проигрышу
второго и определяется значением платежной функции H(α, β),
заданной на рассматриваемом квадрате. Функция H(α, β) предполагается непрерывной.
Из курса математического анализа известно, что любая непрерывная функция H(α, β) достигает на квадрате (как и на любом
другом ограниченном замкнутом множестве) своих максимума и
минимума.
Фиксируя одну из переменных: α = α0 , или β = β0 , мы получим непрерывную функцию от одной переменной, заданную на
интервале [0, 1]. Это будет H(α0 , β) или H(α, β0 ), также достигающих своих экстремальных значений.
Пусть первый игрок использует стратегию α. Рассматривая,
какой максимальный выигрыш ему при этом гарантирован, он
должен учитывать наихудший для себя выбор противника – второго игрока. Он должен предполагать, что второй игрок выберет
β таким образом, что минимизирует свой проигрыш
minβ H(α, β).
Задача первого игрока – выбрать α так, чтобы получить
33
Число c(1) называется нижней ценой игры.
Наоборот, задача второго игрока – выбрать β таким образом,
чтобы получить
minβ (maxα H(α, β)) = c(2).
Число c(2) называется верхней ценой игры.
По основному неравенству для максимина и минимакса (см.
теорему 2.1)
c(1) ≤ c(2).
Если
c(1) = c(2) = c,
то игра, как и в матричном случае, называется определенной, а
величина c называется ценой игры.
Если игра определена, то при использовании одним из игроков
максиминной (для первого игрока) или минимаксной (для второго игрока) стратегии другой игрок не может улучшить свой результат, который он получит, используя свою из перечисленных
стратегий. Таким образом, в случае определенной игры данные
стратегии можно считать оптимальными. Однако в непрерывных
играх определенность встречается редко.
По этой причине вводится непрерывный аналог понятия смешанной стратегии. Соответствующие вероятности выбора чистых
стратегий задаются обычно через функции плотности вероятности: p(α) для первого игрока и q(β) для второго. При этом естественно предположить, что эти функции определены на интервале [0, 1], непрерывны, неотрицательны, а интегралы по ним равны
1.
Заметим, что условие непрерывности, конечно, не является обязательным.
34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Посмотрим, чему равен средний выигрыш при использовании
первым игроком смешанной стратегии p(α), а вторым игроком –
чистой стратегии β :
H1 (p(α), β) =
Z
1
p(α)H(α, β)dα.
0
Наоборот, средний выигрыш при использовании первым игроком чистой стратегии α и вторым - смешанной стратегии q(β)
равен
H2 (α, q(β)) =
Z
1
q(β)H(α, β)dβ.
0
Следующая теорема является непрерывным вариантом теоремы Неймана-Нэша о матричных играх.
Теорема 4.1. (Основная теорема теории непрерывных игр на
квадрате).
Непрерывная игра на квадрате определена в смешанных стратегиях, то есть выполнимо равенство
maxp(α) (minβ H1 (p(α), β) = minq(β) (maxα H2 (α, q(β)) = c.
Величина c называется ценой игры.
Если первый игрок использует максиминную стратегию p(α),
при которой ему гарантируется средний выигрыш c, то второй игрок вынужден использовать свою минимаксную стратегию q(β),
если он хочет гарантировать, что в среднем он не проиграет больше, чем c. То же самое можно сказать об игроках в обратном порядке. По этой причине максиминная и минимаксная смешанные
стратегии считаются оптимальными.
Заметим, что общих методов нахождения максиминной и минимаксной смешанных стратегий стратегий не существует. Однако есть очень важный класс таких игр, в которых оптимальные
стратегии эффективно определимы – это класс так называемых
выпуклых игр.
35
Напомним, что функция одной или нескольких переменных f
называется выпуклой, если для любого числа 0 ≤ λ ≤ 1 любых
аргументов X1 , X2 выполнено неравенство
f (λX1 + (1 − λ)X2 ) ≤ λf (X1 ) + (1 − λ)f (X2 ).
Функция называется строго выпуклой , если приведенные в
определении неравенства строгие. Напомним также, что о выпуклости функции имеет смысл говорить только в том случае, если
ее область определения – выпуклое множество, то есть оно содержит вместе с любой парой точек весь интервал, соединяющий эти
точки.
Часто на практике, когда мы имеем дело с дифференцируемыми функциями, удобно пользоваться следующим критерием выпуклости функции f (x1 , ..., xn ).
Факт 4.2. (Критерий выпуклости функции). Если функция
f (x1 , ..., xn ) определена на выпуклом множестве пространства
Rn и дважды непрерывно дифференцируема, то ее выпуклость
равносильна тому, что все левые угловые (главные) миноры матрицы Якоби
¢
¡
J(f (x1 , ..., xn )) = ∂ 2 f (x1 , ..., xn )/∂xi ∂xj
неотрицательны (для строгой выпуклости последнее условие необходимо заменить на "положительны").
Теорема 4.3. (Основная теорема о выпуклых играх).
Пусть функция H(α, β) выпукла по β для любого фиксированного α (такие игры называют выпуклыми). Тогда второй игрок имеет чистую оптимальную стратегию. Это значит,
что существует число β. такое, что выполнено равенство
maxp(α) H1 (p(α), β. ) = minq(β) (maxα H2 (α, q(β)) =
= minβ (maxα H2 (α, β)) = c.
Теорема 4.4. (Об алгоритме нахождения оптимальных стратегий выпуклых игр).
36
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Стратегия β. второго игрока находится непосредственно. Для
нахождения оптимальной стратегии первого игрока используются
следующие соображения.
Стратегия α называется существенной, если minβ maxα H(α, β)
достигается при заданном значении α и значении βопт. .
1) Если βопт. = 1, то существует чистая оптимальная существенная стратегия α1 первого игрока такая, что Hβ′ (α1 , 1) ≤ 0.
2) Если βопт. = 0, то существует чистая оптимальная существенная стратегия α2 первого игрока такая, что Hβ′ (α2 , 0) ≥ 0.
3) Если βопт. 6= 0, 1, то существуют чистые оптимальные существенные стратегии первого игрока α1 , α2 такие, что Hβ′ (α1 , 1) ≤
0, Hβ′ (α2 , 0) ≥ 0. Оптимальной стратегией первого игрока является смесь стратегий α1 , α2 с вероятностями p и 1 − p, где p определяется из равенства
Как уже объяснялось выше, оптимальной стратегией первого
игрока является смесь стратегий α1 , α2 с вероятностями p и 1 − p.
Пример 4.1.
Пусть задана непрерывная игра на единичном квадрате с платежной функцией H(α, β) = (α − β)2 . Найти оптимальные стратегии игроков.
Решение.
1)
∂ 2 H(α, β)/∂β 2 = 2 > 0,
т. е. игра (строго) выпукла.
2) Цена игры
c = minβ maxα (α − β)2 =
pHβ′ (α1 , βопт. ) + (1 − p)Hβ′ (α2 , β. ) = 0.
Схема алгоритма
1) Проверка того, что функция H(α, β) выпукла по β.
2) Нахождение β. из равенства
c = minβ maxα H(α, β).
3) Нахождение существенных стратегий α1 , α2 из равенства
c = H(α, βопт. ).
4) Определение индексов существенных стратегий из неравенств:
Hβ′ (α1 , βопт. ) ≤ 0, Hβ′ (α2 , 0) ≥ 0.
5) Вычисление p из равенства
pHβ′ (α1 , βопт. ) + (1 − p)Hβ′ (α2 , βопт. ) = 0.
6) Определение оптимальной стратегии первого игрока.
37
= minβ
½
(1 − β)2 , еслиβ ≤ 1/2, = 1/4приβ = 1/2;
(0 − β)2 = β 2 , еслиβ ≥ 1/2, = 1/4приβ = 1/2
Значит, β. = 1/2, c = 1/4.
Пример 4.2. (Борьба за рынки.)
Допустим, фирма A стремится вытеснить фирму B с одного из
двух рынков. Рынки имеют коэффициенты значимости k1 , k2 > 0,
соответственно. Каждая из фирм располагает капиталом, равным
1, расходуемым фирмой A на захват, а B - на защиту рынков.
Пусть фирма A вкладывает капитал α в первый рынок, а капитал 1 − α во второй, в то время как фирма B вкладывает капитал
β в первый рынок, а капитал 1 − β во второй. Тогда платежная
функция фирмы A задается формулой:
H(α, β) =
½
k1 (α − β), если α ≥ β
k2 ((1 − α) − (1 − β) = k2 (β − α), если β ≥ α
По смыслу задачи k1 , k2 ≥ 0. Легко проверить, что мы можем
трактовать ситуцию как игру двух игроков на квадрате, причем
38
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
эта игра относится к категории выпуклых игр. Можно считать ее
антагонистической. Согласно основной теореме о выпуклых играх второй игрок имеет оптимальную чистую стратегию. Для ее
нахождения вычислим minβ maxα H(α, β).
Вначале вычисляем:
k1 (α − k1 /(k1 + k2 )) = k1 k2 /(k1 + k2 ).
Тогда α = 1.
В случае α ≤ β0 получаем равенство
k2 (k1 /(k1 + k2 ) − α) = k1 k2 /(k1 + k2 ).
maxα H(α, β) = max{maxα≥β k1 (α − β), maxα≤β k2 (β − α)} =
= max{k1 (1 − β), k2 β}.
Мы использовали простые рассуждения. Во-первых, максимальное значение функции, заданной на двух интервалах разными
формулами, удобно находить, вычисляя максимальные значения
для каждого интервала в отдельности, а затем выбирая большее
значение. Во-вторых, так как функции на интервалах линейны по
рассматриваемой переменной α (β выступает как параметр), то их
максимальные значения находятся на одном из концов интервала.
Вычислим теперь
Тогда α = 0.
Вычислим значения частных производных, чтобы определить
номера существенных стратегий.
Hβ′ (0, β0 ) = (k2 β)′β (0, β0 ) = k2 > 0,
Hβ′ (1, β0 ) = (k1 (1 − β))′β (1, β0 ) = −k1 < 0,
из чего следует, что α1 = 1, α2 = 0.
Определим вероятности, с которыми первый игрок должен выбирать существенные стратегии α1 , α2 . Для этого составим уравнение
minβ maxα H(α, β).
Для этого построим графики функций k1 (1 − β), k2 β на интервале 0 ≤ β ≤ 1. Точка их пересечения как раз соответствует
искомому минимаксу. Решая уравнение
k1 (1 − β) = k2 β,
получаем оптимальное значение β0 = k1 /(k1 + k2 ) и цену игры
c = k1 k2 /(k1 + k2 ).
Определим теперь существенные стратегии первого игрока из
равенства
c = k1 k2 /(k1 + k2 ) = H(α, β0 ).
В случае α ≥ β0 получаем равенство
39
pHβ′ (1, β0 ) + (1 − p)Hβ′ (0, β0 ) = −pk1 + (1 − p)k2 = 0.
Получаем
p = k2 /(k1 + k2 ), 1 − p = k1 /(k1 + k2 ).
Мы видим, что оптимальной стратегией первого игрока является концентрация всех его сил на одном из рынков с вероятностью, обратно пропорциональной ценности рынка.
Задачи
Задача 4.1. Исследовать на выпуклость функции:
y = 5 − x21 − x22 ; y = 2/x приx > 0.
40
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задача 4.2. Всегда ли сумма выпуклых функций сама выпукла?
Задача 4.3. "О магазинах". Допустим, две фирмы хотят
открыть на одной улице по магазину. Первая собирается открыть
дорогой магазин, а вторая - дешевый. Решения о месте открытия
принимаются независимо и одновременно, после чего их изменить
уже нельзя. Как действовать первой и второй фирмам, если первая заинтересована в том, чтобы магазины были как можно дальше друг от друга, а у второй интересы прямо противоположны?
Задача 4.4. Как поступить фирмам в условиях предыдущей
задачи, если место для магазинов выбирается на круглой площади?
Задача 4.5. Платежная функция непрерывной игры на квадрате равна H(α, β) = 3α2 − 2αβ + 4β 2 . Определить оптимальные
стратегии игроков и цену игры.
Задача 4.6. Платежная функция непрерывной игры на квадрате равна H(α, β) = αβ + α − β + 1. Первый игрок использует смешанную стратегию, заданную функцией плотности вероятности f (t) = 2t, а второй игрок использует функцию плотности
вероятности g(s) = es /(e − 1). Найти средний выигрыш первого
игрока.
Задача 4.7. Непрерывная игра имеет платежную функцию
H(α, β) = αβ − 1/3α − 1/2β. Показать, что точка A(1/2, 1/3) седловая. Есть ли другие седловые точки? Какова цена игры? Имеет
ли игра решение в чистых стратегиях? Если "да", то в каких?
Функция f называется вогнутой, если функция −f выпукла.
Задача 4.10. Допустим, задана непрерывная игра на прямоугольнике со сторонами [0, a], [0, b] с платежной функцией K(α, β).
Доказать, что игра равносильна некоторой игре на единичном
квадрате. Какова платежная функция H(α, β) в равносильном
варианте?
Задача 4.11. Пусть арендатор земли общей площадью 100 гектаров может посеять кукурузу или сою. Пусть y1 – средняя урожайность с гектара (в некоторых единицах) кукурузы, y2 – сои.
Пусть p, 1 − p – доли всей площади, засеянной арендатором кукурузой и соей соответственно. Пусть f1 (t) = 1/t – цена единицы
урожая кукурузы, f2 (s) = 1/s2 – сои соответственно, где t, s –
доли посева кукурузы и сои соответственно для всех производителей. Пусть случайные величины t, s распределены равномерно.
Записать условие задачи в виде непрерывной игры. Определить
понятие оптимальности. Решить задачу при y1 = 10, y2 = 10.
Задача 4.12. Две конкурирующие фирмы ведут борьбу за n
рынков сбыта продукции путем затрат на рекламу. Фонды рекламных расходов фирм составляют a, b денежных единиц соответственно. Прибыль, которую можно получить от i-го рынка,
равна ci > 0. Она распределяется равномерно между фирмами,
пропорционально их затратам на рекламу на этом рынке. Выигрыш фирмы – ее суммарная прибыль.
Найти ситуации равновесия (оптимальные стратегии).
Задача 4.9. Верно ли, что в игре с вогнутой функцией платежей по первой переменной H(α, β) первый игрок имеет оптимальную чистую стратегию?
Задача 4.13. Пусть первый игрок (Центр) заинтересован в
увеличении выпуска продукции вторым игроком (Производителем). Центр управляет назначением цены x на продукцию y, цена
c продажи продукции на внешний рынок постоянна.
Критерий Производителя: прибыль = G(x, y) = xy − bln(a/(a −
y)), где 0 ≤ y < a; 0 < a, b; ac ≥ b, bln(a/(a − y)) − − функция
затрат. Критерий Центра: F (x, y) = cy −xy – прибыль от продажи
продукции y на внешний рынок.
Определить оптимальную стратегию Центра.
41
42
Задача 4.8. Показать, что непрерывная игра на единичном
квадрате с платежной функцией H(α, β) = αβ−aα−bβ+c, (a, b, c ≥
0), имеет седловую точку (которая может, впрочем, лежать на
границе квадрата).
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
5. Кооперативные игры
Обыкновенная матричная игра – игра двух участников. Поскольку мы рассматриваем игры с нулевой суммой, их интересы
противоположны, поэтому о совместном определении стратегий,
образовании коалиций не может быть и речи.
Рассмотрим игру n игроков, где n ≥ 3. Даже если попарно игроки имеют противоположные интересы, в принципе постановка
вопроса о коалициях уместна. Напомню в связи с этим, что коалицией называется объединение игроков (мыслимое или реальное)
с целью максимизации суммарного выигрыша. В случае образования коалиций возникает вопрос о дележе. Мы раcсмотрим его
далее. Игры, в которых допустимы коалиции, называются кооперативными.
Пусть игра конечна, то есть каждый из игроков имеет только
конечное множество стратегий. Пусть Xi – множество стратегий
i-го игрока. При выборе i-м игроком стратегии xi ∈ Xi по всем i
получаем вектор стратегий x = (x1 , ..., xn ), являющийся элементом пространства X = X1 × ...Xn .
Пусть Hi (x) – платежная функция i-го игрока. В качестве суммарной рассматривается платежная функция H(x) = (H1 (x),
..., Hn (x)), показывающая выигрыши всех игроков при выборе стратегии x. Игра n игроков называется игрой с нулевой суммой, если
H1 (x) + ... + Hn (x) = 0 для любого x.
Теорема 5.1. (Обобщение теоремы Неймана-Нэша на случай
игры n лиц).
Игра n игроков определена в смешанных стратегиях.
Hi+1 (x) + ... + Hn (x) = −Hi (x). Таким образом, с точки зрения
i-го игрока получается матричная игра двух лиц – его самого и
суммарного игрока, состоящего из всех остальных лиц. Причем
это – игра с нулевой суммой. По теореме Неймана-Нэша i-й игрок имеет оптимальную смешанную максиминную стратегию по
отношению к платежной функции Hi (x). Используя эту стратегию, он гарантирует себе выигрыш ci . Для остальных игроков
это – игра с постоянной суммой, которая, как мы знаем, с точки
зрения определения оптимальных стратегий эквивалентна игре с
нулевой суммой. Поскольку игроков стало меньше, по индукции
заключаем, что они имеют оптимальные смещанные стратегии.
При этом использование такой стратегии определенным игроком
является как бы вынужденным, если все остальные игроки используют свои оптимальные стратегии. В противном случае он
может только ухудшить свой результат. Цену игры представляет
вектор c = (c1 , ..., cn ). Заметим, что c1 + ... + cn = 0.
Пусть I – множество всех игроков. Тогда коалиция – это подмножество K в I.
PЗадача коалиции – максимизация суммарного
дохода HK (x) = i∈K Hi (x). Если K ⊆ I – коалиция, то K̄ = I \K
– противоположная коалиция, рассматриваемая как игрок с противоположным интересом.
По теореме Неймана-Нэша существуют оптимальные смешанные стратегии для K и для K̄, а также цена игры cK . Возникает
так называемая характеристическая функция γ : 2I −→ R. Здесь
2I обозначает множество всех подмножеств (коалиций) в I, число
которых, как известно, 2|I| , |I| – число элементов в множестве I.
Требуется выполнение следующих условий:
1)γ(∅) = 0;
Приведем схему доказательства теоремы, заодно объясняющую
ее точный смысл.
Рассмотрим игру с точки зрения i-го игрока. Для него все
остальные игроки выступают как одно лицо с конечным множеством стратегий X1 × ... × Xi−1 × Xi+1 × ...Xn . Платежная функция для этого суммарного лица равна H1 (x) + ... + Hi−1 (x) +
(5.1)
если K ∩ L = ∅. Последнее означает, что объединение в коалицию
не уменьшает суммарный доход.
43
44
2)γ(K) + γ(L) ≤ γ(K ∪ L),
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Болваном называется такой игрок i , который при вхождении
в любую коалицию не увеличивает ее суммарный доход более чем
на γ(i). Если игрок i болван, то для любой коалиции K, i 6∈ K
имеем γ(K ∪i) = γ(K)+γ(i). Носителем игры называется дополнение к множеству всех болванов. Игроки из носителя называются существенными. Для любого существенного игрока i найдется
такая коалиция K, что γ(K ∪ i) > γ(K) + γ(i).
Как правило, задание игры осуществляется через задание характеристической функции. При этом возникает вопрос о дележе суммарного дохода между игроками, входящими в коалицию.
Есть еще очень важный вопрос о "справедливом" дележе между
всеми игроками с учетом их вхождений во все возможные коалиции. Другими словами, каждый игрок при таком дележе получит
столько, сколько он стоит.
Теорема 6.2. (О справедливом дележе).
Для любой характеристической функции γ, задающей кооперативную игру n лиц с платежной функцией H(x), существует единственный вектор "справедливого" дележа T (γ) = (T1 (γ),
T2 (γ), ..., Tn (γ)), удовлетворяющий следующим естественным
условиям:
P
1) ni=1 i(γ) = 0,
2) для любой пары характеристических функций γ1 , γ2 , определенных для данного множества игроков I = {1, 2, ..., n}, для
любого i имеет место равенство
Ti (γ1 + γ2 ) = Ti (γ1 ) + Ti (γ2 ).
(5.2)
Сумма γ1 + γ2 означает характеристическую функцию, значения которой на любой коалиции K вычисляются как суммы
значений на этой коалиции данных функций γ1 , γ2 . Легко проверить, что для определенной таким образом суммы верны требования, предъявляемые характеристическим функциям. Неформально условие 2) означает, что участие сразу в двух играх одного и
того же множества игроков не влияет на справедливый дележ по
45
каждой из этих игр.
Полученный вектор "справедливого" дележа T (γ) = (T1 (γ), T2 (γ),
..., Tn (γ)) называется вектором Шепли. Самое удивительное, что
он единственный.
Вектор Шепли вычисляется в соответствии со следующими
формулами:
Ti (γ) =
X
((n − |K|)!(|K| − 1)!)/n!)(γ(K) − γ(K \ i)), i = 1, 2, ..., n
i∈K
(5.3)
(как обычно, |K| означает число игроков в коалиции K, ! – знак
"факториал": m! – произведение чисел от 1 до m, 0! = 1 по определению). Суммирование в формулах осуществляется по K, то есть
по всем коалициям, включающим данного игрока i.
Поясним, что означают множители в каждом слагаемом. Коэффициент (n − |K|)!(|K| − 1)!/n! означает вероятность образования
коалиции K, точнее - вероятность образования K с вхождением в
нее i. Второй множитель (γ(K) − γ(K \ i)) означает "вклад" i-го
игрока при вхождении его в коалицию K. Мы ставим кавычки на
слове "вклад" потому, что добавка к γ(K \ i) зависит не только
от i, но и от самой коалиции K. Она не зависит от K, если только
игрок i – болван.
Пример 5.1. Допустим, что в некой банде имеются главарь и
4 рядовых участника. "Взять" банк могут либо 4 рядовых участника, объединившись вместе, либо любые 2 рядовых участника
плюс главарь. "Куш" составляет 100 млн. Найти справедливое
распределение.
Решение. Запишем характеристическую функцию игры, считая игроков 1, 2, 3, 4 рядовыми участниками, а 5 - главарем.
γ(φ) = 0, γ(1) = ... = γ(5) = 0, γ(1, 2) = ...γ(4, 5) = 0,
γ(1, 2, 3) = ... = γ(2, 3, 4) = 0, γ(1, 2, 5) =
46
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
= γ(1, 3, 5) = γ(1, 4, 5) = γ(2, 3, 5) = γ(2, 4, 5) =
= γ(3, 4, 5) = 100, γ(любая четверка или все 5 игроков) = 100.
Считаем справедливую долю главаря. При этом учитываем
только те его вхождения в коалиции, которые приносят доход 100,
если без него коалиция не зарабатывала ничего. Другие случаи
рассматривать нет смысла, поскольку их вклад в долю равен 0.
Рассмотрим все коалиции из трех игроков, включающие главаря. Таких коалиций всего 6. При этом разница значений функции
γ на коалиции и коалиции без главаря равна 100. Вероятность
образования коалиции вычисляется в соответствии с формулой
(5.3): (5 − 3)!(3 − 1)!/5! = 1/30. Вклад в долю по всем тройкам
равен 61/30100 = 20.
Рассмотрим теперь все коалиции из четырех игроков, включающие главаря. Таких коалиций всего 4. При этом разница значений функции γ на коалиции и коалиции без главаря равна 100.
Вероятность образования коалиции вычисляется в соответствии с
формулой (5.3): (5 − 4)!(4 − 1)!/5! = 1/20. Вклад в долю по всем
четверкам равен 41/20100 = 20. Доля главаря составит 40 млн.
Вычислим доли рядовых участников. Ясно, что они одинаковы
и равны (100 − 40)/4 = 15. Проведем для проверки вычисления в
соответствии с формулой (5.3).
Выберем для определенности игрока под номером 1. Его ненулевой вклад в коалицию равен 100 в следующих случаях: (1, 2, 5),
(1, 3, 5), 1, 4, 5), (1, 2, 3, 4). Вероятности образования первых трех
коалиций равны (5 − 3)!(3 − 1)!/5! = 1/30, последней - (5 − 4)!(4 −
1)!/5! = 1/20; значит, доля составит (31/30 + 1/20)100 = 15.
Задачи
Задача 5.1. Рассмотрим множество игроков I4 = {1, 2, 3}. Какие из следующих функций χ : 23 → R могут считаться характеристическими и почему?
2)χ2 (1) = χ2 (2) = χ2 (3) = 4, χ2 (1, 3) = 9, χ2 (1, 3) = 12,
χ2 (2, 3) = 11, χ2 (1, 2, 3) = 17;
3)χ3 (1) = χ3 (2) = 1, χ3 (3) = 2, χ3 (1, 2) = 3, χ3 (1, 3) = 4,
χ3 (2, 3) = 10, χ3 (1, 2, 3) = 11;
4)χ4 (1) = 1, χ4 (2) = 2, χ4 (3) = 3, χ4 (1, 2) = 2, χ4 (1, 3) = 10,
χ4 (2, 3) = 11, χ4 (1, 2, 3) = 21.
Задача 5.2. Пять нечестных политиков A, B, C, D, E могут
прикарманить сумму в 10 млн долларов. При этом, если объединятся A, B, C, D, то они получат всю сумму. Любая тройка получит 5 млн, если только в ней нет E. Если в тройке есть E, то сумма
составит 7 млн. Никто в отдельности или в паре не может получить ничего. Любая коалиция может получить не меньше, чем ее
подкоалиция. Например, A, B, C, E получает 7 млн (она включает
A, B, C, значит должна получить не меньше, чем 5 млн, однако
она также включает A, B, E, значит, должна получить не меньше, чем 7 млн – берется максимум, так считается в остальных не
указанных явно случаях).
Как следует разделить 10 млн между политиками, учитывая
их возможности?
Задача 5.3. Пусть имеется 4 игрока: A, B, C, D. Любая тройка выигрывает 10 единиц. Любая двойка, включающая D, выигрывает 7. В одиночку и в других двойках не выиграть ничего,
произвольная коалиция выигрывает не менее, чем любая ее подкоалиция.
Разделить 10 по справедливости.
χ1 (1, 2, 3) = 2;
Задача 5.4. "О голосовании". Имеется 5 политических
партий: A, B, C, D, E. Они могут объединяться в коалиции и выставлять единого кандидата победы на выборах президента. Для
47
48
1)χ1 (1) = χ1 (2) = χ1 (3) = 1/2, χ1 (1, 2) = χ1 (1, 3) = χ1 (2, 3) = 1,
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
победы кандидата требуется получить более 50 процентов голосов. Голоса между партиями распределяются следующим образом: A − 40, B, C, D, E - по 15 процентов. Условно выигрыш равен
1.
Найти справедливый дележ 1 между партиями.
Задача 5.5. "О фермере и батраках". Фермер нанимает
батраков для выращивания урожая. Если он наймет одного батрака, то вырастит и продаст урожай на сумму 3 (миллиона рублей).
Если двух, то получит 5, и т. д. Можно задать эти величины как
значения функции: f (1) = 3, f (2) = 5, f (3) = 8, f (4) = 9, f (5) =
f (6) = ... = 10.
Определить для каждого из возможных случаев от 1 до 5 батраков величину справедливой доли фермера. В каком случае его
часть от общего дохода самая большая?
Задача 5.6. Пусть имеется корпорация из четырех акционеров, имеющих акции соответственно в следующих размерах: a1 =
100, a2 = 200, a3 = 300, a4 = 400. Найти вектор Шепли.
Задача 5.7. Решить задачу 5.6 при данных: a1 = 150, a2 =
230, a3 = 310, a4 = 470.
6. Открытый аукцион
Рассмотрим простейший вид аукциона, на котором выставляются на продажу два лота A и B ценности a, b соответственно и
имеются два участника торгов 1 и 2, каждый из которых располагает суммами c, d соответственно. Участники поочередно называют суммы, которые они согласны заплатить за выставленный лот,
причем сумма в каждой следующей заявке должна быть строго
больше, чем предыдущая. Для простоты мы считаем, что участники торгов называют суммы по очереди. Участник при своем
ходе может не увеличивать предложенную сумму, но тогда это
означает, что лот отдается другому участнику, выигрыш которого от продажи данного лота составляет разницу между ценностью
лота и той суммой, за которую он отдается. Выигрыш в игре определяется суммарным выигрышем за два предмета, если участник
купит два лота, или выигрышем за купленный предмет, если он
один. В случае, если участник торгов не приобретет ни одного
предмета, его выигрыш по определению считается равным 0. Очевидно, что нет смысла назначать за лот цену большую, чем его
ценность.
Считаем, что, во-первых, не возможен сговор между участниками аукциона, во-вторых, при торгах за второй из предметов тот
из участников, у кого меньше оставшаяся сумма, и который, следовательно, уже не имеет возможности купить лот, торгуется до
последнего. Еще мы предполагаем, что как ценности a, b, так и
суммы c, d известны обоим участникам. При этом каждый делает
вид, что сумма c или d, которой располагает противник, ему не
известна.
Чтобы объяснить, как необходимо рассуждать при таком аукционе его участникам, возьмем следующие числовые данные:
a = 100, b = 130, c = 65, d = 80.
Рассмотрим сначала торг за предмет A с точки зрения первого участника. Предположим, что последняя из названных сумм
49
50
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
равна x. Если первый игрок хотя бы чуть-чуть повысит сумму
x, то существует вероятность, что другой игрок откажется повышать цену, и тогда первому достанется лот A за сумму, которую
приближенно можно считать равной x, при этом его сумма на
второй торг за предмет B будет c − x. В этом случае он, конечно,
уже не сможет купить и второй лот, поэтому его окончательный
выигрыш равен a − x.
Посмотрим, что произойдет, если он откажется повысить цену.
Тогда второй участник торгов приобретет предмет A за x, и у него
останется сумма d − x. Если по-прежнему у второго игрока сумма
больше, то есть c ≤ d−x, то выигрыш первого игрока равен 0, чего
он мог бы достичь, вообще не участвуя в аукционе. Значит, можно
не рассматривать отказ первого игрока до значения x = d − c.
В нашем примере это 15. Допустим, что x ≥ 15. Тогда можно
предположить, что второй лот при отказе первого игрока на этой
сумме достанется ему. Определим, за какую цену. Второй игрок по
условиям аукциона будет торговаться до конца, то есть до y = d−
x. Первый приобретет лот B за цену, которую приближенно можно
считать равной y = d − x. Его выигрыш составит b − (d − x) =
b + x − d. Итак, мы получили две возможные функции выигрыша
первого игрока: a − x, b + x − d. Одна из них возрастает по x, а
другая убывает. В какой-то момент выигрыши и в том, и в другом
случае одинаковы.
Определим это значение, которое можно назвать критическим:
чаемая цена не превосходит 25, а затем ему выгодно отказаться
от приобретения первого лота, чтобы приобрести второй.
Посмотрим на тот же процесс с точки зрения второго игрока.
Допустим, что торг достиг величины y. Если второй игрок приобретет лот за эту цену, то его выигрыш составит a − y, если сумма
первого игрока a больше, чем оставшаяся сумма d − y второго.
Если a ≤ d − y, то второй игрок купит также и следующий лот.
Однако этот случай можно не рассматривать ввиду условий аукциона. Значит, имеет место неравенство a ≥ d − y. Если второй
игрок откажется повысить цену, то он приобретет второй лот за
c − y, и его выигрыш составит b − (c − y) = b − c + y.
Определим критическое значение y :
a − y = b − c + y,
(6.3)
откуда
y = a + c − b.
(6.2)
В нашем случае x = 25. Можно сделать вывод, что первому
игроку выгодно продолжать торговаться до тех пор, пока назна-
(6.4)
В рассматриваемом примере y = 17, 5.
Перейдем теперь к окончательным выводам, зная критические
суммы игроков x = 25, y = 17, 5. Нужно определить, до какой же
все-таки суммы будут торговаться игроки. Первое впечатление,
что до 17, 5, так как второму игроку невыгодно торговаться дальше. На самом деле такое его поведение не является оптимальным.
Действительно, ведь он знает, что первому невыгодно прерывать
торг до 25. Значит, он этого не сделает. Второму в таком случае
выгоднее торговаться до 25, а затем отказаться. Тем самым он
заставит первого выплатить больше, зато его выигрыш при этом
станет больше как раз на величину 25 − 17, 5 = 7, 5.
Итак, первый игрок приобретет лот A за 25, его выигрыш составит 100 − 25 = 75. Второй приобретет лот B за 65 − 25 = 40,
его выигрыш составит 130 − 40 − 90.
51
52
a − x = b + x − d,
(6.1)
откуда получаем
x = (a + d − b)/2.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Учебное издание
Задачи
Задача 6.1. Решить задачу об открытом аукционе для следующих начальных данных:
a = 170, b = 230, c = 380, d = 420.
Задача 6.2. Решить задачу об открытом аукционе для следующих начальных данных:
a = 150, b = 130, c = 200, d = 160.
Задача 6.3. Решить задачу об открытом аукционе для следующих начальных данных:
a = 270, b = 190, c = 310, d = 390.
Виталий Анатольевич Романьков
ВВЕДЕНИЕ В ТЕОРИЮ ИГР
Задача 6.4. Решить задачу об открытом аукционе для следующих начальных данных:
a = 165, b = 180, c = 250, d = 340.
Задача 6.5. Решить задачу об открытом аукционе для трех
участников при следующих начальных данных:
a1 = 120, a2 = 140, a3 = 190 - располагаемые средства, c1 =
340, c2 = 370 - ценности предметов.
Редактор Л.М. Кицина
Технический редактор Н.С. Серопян
Подписано в печать 10.08.05.
Печ. л. 3,5. Уч.-изд. л. 2,7.
Формат 60 × 84 1/16.
Тираж 200 экз. Заказ 367
Издательство ОмГУ
644077, Омск-77, пр. Мира, 55а, госуниверситет
53
Документ
Категория
Без категории
Просмотров
208
Размер файла
270 Кб
Теги
игр, 961, учебно, пособие, введение, теория
1/--страниц
Пожаловаться на содержимое документа