close

Вход

Забыли?

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

?

1572.Теория игр в менеджменте

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство сельского хозяйства Российской федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Саратовский государственный аграрный университет
имени Н.И. Вавилова»
ТЕОРИЯ ИГР В МЕНЕДЖМЕНТЕ
УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ
для студентов-бакалавров аграрного университета
направления подготовки
080200.62 Менеджмент
Саратов 2014
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 51-7(519.2/.6)
ББК 22.18
У 32
У32 Теория игр в менеджменте: учебно-методическое пособие для
студентов-бакалавров
аграрного
университета
направления
подготовки 080200.62 «Менеджмент» / Сост. Н.Б. Уейская //ФГОУ
ВПО «Саратовский ГАУ». - Саратов, 2014 – с.
Данное пособие по дисциплине «Теория игр м менеджменте» направления
подготовки 080200.62 «Менеджмент» составлено с учётом требований ФГОС в
соответствии программой дисциплины, которая предполагает лишь практические
занятия.
В пособии приведены основные теоретические сведения из теории игр, методы
решения теоретико-игровых задач и применение их к задачам управления и бизнеса.
В курсе рассмотрены основные классы игр и применение теоретико-игровых
методов к решению задач принятия решений в управлении экономическими
процессами, а также использование этих методов в профессиональной деятельности.
УДК 51-7(519.2/.6)
ББК 22.18
© Уейская Н.Б., 2014
© ФГБОУ ВПО «Саратовский ГАУ», 2014
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ВВЕДЕНИЕ
Поскольку в условиях рыночной экономики полагаться только на качественный
анализ явлений и интуицию становится менее надёжным, возрастает роль
математических методов, используемых в задачах принятия управленческих решений.
Механизмы функционирования рынка, конкуренции, возникновения или распада
монополий, а также способы принятия решений в условиях конкурентной борьбы,
механизмы игры монополий, действующие в экономической реальности, не могут быть
исследованы и поняты без теории игр.
В настоящем пособии на примерах решения экономических задач
продемонстрированы возможности применения теории игр в задачах управления и
бизнеса. Рассмотрены следующие классы игр: бескоалиционные: антагонистические
(конечные, или матричные), биматричные; а также классические кооперативные игры.
Кроме того, рассмотрены задачи принятия решений для игр с природой в условиях
неопределённости и в условиях риска.
Для каждого класса игр приведены необходимые определения, даны примеры
решения и список задач и упражнений для самостоятельного решения.
Пособие ориентировано на формирование у студентов ключевых компетенций,
связанных с пониманием основных понятий по указанным разделам, на применение
теоретико-игровых методов в профессиональной деятельности.
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. ПОНЯТИЕ О МАТЕМАТИЧЕСКОМ МОДЕЛИРОВАНИИ
Теория игр является одним из разделов математического моделирования.
Математическая модель – это наборы функций, уравнений, матриц и т.д, с помощью
которых даётся приближённое описание явлений природы и общества.
Анализируя модель, можно сделать определенные выводы об изучаемом явлении.
Математическое моделирование - это метод изучения действительности с помощью
математических моделей.
Математическое моделирование предполагает четыре этапа:
1. Формулирование математических законов, связывающих основные объекты
модели (постановка задачи).
Завершается он записью в математических терминах сформулированных
качественных представлений о связях между объектами модели.
2. Решение и исследование математических задач, к которым приводят
математические модели.
Основной вопрос на этом этапе - получение посредством анализа модели выходных
данных для дальнейшего их сопоставления с результатами наблюдений изучаемых
явлений. На этом этапе важную роль приобретают математический аппарат, необходимый
для анализа математических моделей, и вычислительная техника - мощное средство для
получения количественной выходной информации как результата решения сложных
математических задач.
3. Анализ полученных результатов.
Предполагает выяснение, удовлетворяет ли принятая (гипотетическая) модель
критерию практики, то есть согласуются ли результаты наблюдений с теоретическими
следствиями модели в пределах заданной точности.
4. Последующий анализ и усовершенствование модели в связи с её уточнением.
Математическое моделирование является универсальным, так как часто одна и та же
математическая модель описывает различные по содержанию явления; оно гарантирует
объективность, уменьшив роль субъективных факторов в оценках. Кроме того,
математическое моделирование позволяет прогнозировать различные ситуации.
В природе и обществе часто встречаются явления, в которых те или иные участники
имеют несовпадающие интересы и располагают различными способами достижения
своих целей. Такие явления называются конфликтами.
Примерами конфликтов являются:
1) борьба фирм за рынки сбыта, биржевые игры;
2) военные конфликты;
З) настольные игры: шахматы, шашки, крестики-нолики и т.д.
Ход событий в конфликте зависит от решений, принимаемых каждой из сторон, и
поэтому поведение любого участника конфликта, если оно в том или ином смысле
разумно, должно учитывать возможное поведение всех его участников. Для конфликта
характерно, что ни один из его участников заранее не знает решений, принимаемых
остальными
участниками, то есть, вынужден действовать в условиях
неопределенности. Неопределенность исхода может проявляться как результат
сознательных действий других участников, а также тех или иных "стихийных сил"
(природы, среды). В конфликтных ситуациях важно то, что наличие двух или более
сторон исключает априорную оценку каких-либо вероятностных распределений того
или иного исхода.
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Конфликт может возникнуть также из различия целей, которые отражают не только
несовпадающие интересы различных сторон, но и многосторонние, интересы одного и
того же лица. Например, конструктор преследует многосторонние интересы, согласуя
противоречивые
технико-экономические
требования,
предъявляемые
к
конструируемому изделию (минимизация габаритов и стоимости, максимизация
надежности, обеспечение простоты в изготовлении и т.д.).
Обобщая то, что характеризует все конфликты независимо от их физической и
социальной природы, приходим к следующему описанию конфликта.
Конфликт, или конфликтная ситуация - это такое явление, в котором сталкиваются
интересы двух или более сторон, преследующих различные цели и имеющих для их
достижения некоторые наборы альтернатив, каждая из которых приводит к одному или
одному из нескольких возможных исходов. При этом важно, кто в этих исходах
заинтересован и в чем состоит эта заинтересованность.
В таком понимании конфликты составляют содержание многих процессов в области
экономики, военного дела, социологии, дипломатии, спорта и других видов
человеческой деятельности, а также встречаются в природе (например, в условиях
межвидовой борьбы за существование). Все это говорит о практической важности и
специфической сложности конфликта как явления, основу которого составляют
разумные действия лиц и коллективов с различными интересами.
Формализация содержательного описания конфликта представляет собой его
математическую модель, которую называют игрой.
Теория игр есть теория математических моделей принятия оптимальных решений в
условиях конфликта.
Теория игр применима к различным отраслям знаний и видам практической
деятельности, которые непосредственно имеют дело с конфликтами: военного дела,
экономики (например, в вопросах борьбы Фирм за рынки сбыта; в явлениях
олигополии, то есть монополизации производства и сбыта основной массы некоторой
продукции на основе тайного соглашения; в планировании рекламных кампаний; при
формировании цен на конкурентных рынках; в биржевой игре и т.д.).
Мы будем рассматривать в основном теорию игр в применении к экономике и
менеджменту. Хотя и не исключаем возможности рассмотрения примеров
классических игр, так как они позволяют более просто представить основные
положения этой теории.
При решении практических теоретико-игровых задач часто используются ЭВМ.
Этот аспект будет также нами рассмотрен.
Заметим, что теория игр к настоящему времени сложилась как математическая
наука, позволяющая на основе теоретического анализа в некоторых случаях получать
количественные оценки, способствующие принятию оптимальных решений в
интересующих нас ситуациях, и этим она отличается от популярных ныне деловых игр,
которые предполагают посредством эксперимента разыграть ту или иную
практическую ситуацию и, сравнив результаты с помощью экспертов и оценив их по
определенным критериям, прийти к наилучшему из решений.
Историческая справка. Можно считать, что зарождение теории игр и теории вероятностей как
математических наук произошло одновременно. Обычно оно связывается с письмом Блеза Паскаля к
Пьеру Ферма от 29 июня 1654 года, в дальнейшем отдельные идеи, которые можно отнести к теоретико игровым, высказывались Вальдегравом (1712 год, нахождение оптимальных смешанных стратегий в игре
"проходящий туз"), Даниилом Бернулли (1732 год, анализ "петербургской игры"). Ряд теоретикоигровых утверждений в эквивалентной форме рассмотрен в теории наилучших приближений русским
математиком П.Л.Чебышевым (1821-1894). Немецкий математик Эрнст Цермело (1871-1933) в 1911 году
описал теоретико-игровой подход к шахматной игре, в 1921 году французский математик Эмиль Борель
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
(1871-1956) начал систематическое изучение матричных игр. В 1928 году в работе американского
математика Джона фон Неймана (1903-1957) "К теории стратегических игр" были изложены основные
идеи современной теории игр. Эти идеи были детально разработаны им совместно с Оскаром
Моргенштерном в книге "Теория игр и экономическое поведение", опубликованной впервые в 1944 году.
Её авторы уже названием подчеркнули взаимосвязь между экономикой и теорией игр. В наши дни
глубина проникновения теории игр в экономику была оценена присуждением Нобелевской премии 1994
по экономике трём профессиональным математикам за исследования по теории игр.
В настоящее время теория игр является развитой наукой, позволяющей получать практические
результаты в различных областях человеческой деятельности.
Вопросы для самоконтроля
1. Что представляет собой математическое моделирование?
2. Что понимают под конфликтом?
3. Что является предметом теории игр?
2. БЕСКОАЛИЦИОННЫЕ ИГРЫ
Выше было дано в общих чертах понятие о конфликте. Теперь предстоит
формализовать содержательное описание конфликта, то есть создать математическую
модель игры. Понятие игры достаточно общее. Принято подразделять все игры на два
класса.
Игры, в которых целью каждого игрока является получение по возможности
наибольшего
индивидуального
выигрыша,
называются
бескоалиционными
(некооперативными).
Игры, в которых действия игроков направлены на максимизацию выигрышей
коллективов (коалиций), члены которых имеют возможность обсуждения совместных
действий, называются кооперативными.
Для формального описания такой игры существенно:
1) кто в ней участвует;
2) что может предпринять каждый участник;
3) какие могут быть исходы;
4) какой интерес имеет каждый участник по отношению к каждому исходу.
Обозначим через I - множество всех игроков (участников конфликта). Далее будем
считать множество I - конечным, хотя в современной теории игр рассматриваются игры
с бесконечными множествами игроков, также представляющие практический интерес.
Обычно принято различать игроков по номерам, то есть считать, что I = {l,2,...,n}
Заметим, что I должно содержать больше одного элемента, так как в противном случае
задача нахождения оптимального решения сведется к задаче классического анализа на
экстремум или к задаче линейного программирования. Самый простой случай, когда
I= {l,2}.
Пусть каждый игрок iI имеет в своем распоряжении некоторое количество Si,
возможных действий, которые в теории игр называются стратегиями. Естественно
считать, что каждый игрок имеет не менее двух различных стратегий, так как если бы
он располагал единственной стратегией, то его действия оказались бы заранее
предопределенными, и он фактически в игре участия не принимал бы.
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Процесс игры состоит в выборе каждым из игроков одной своей стратегии
siєSi.Таким образом, в результате проведения игры складывается система стратегий
s = (s1 ,s2 ,….,sn ), которая называется ситуацией. Множество всех ситуаций обозначим
через S, при этом S =S1 × S2 ×…×Sn - декартово произведение множеств S1 ,S2 ,…,Sn .
В каждой ситуации s игроки получают некоторые выигрыши (платежи). Заметим,
что выигрыш может быть как положительным, так и отрицательным. Выигрыши
(платежи) игроку i в ситуации s обычно обозначаются через Hi(s). Функция Hi,
определенная на множестве всех ситуаций, называется функцией выигрыша игрока i,
или функцией платежа игроку i. Величину -Hi(s), противоположную выигрышу,
называют проигрышем i-ого игрока.
Определение 2.1. Бескоалиционной игрой называется система Г = <I, {Si}iєI, {Hi}iєI >,
в которой I = {1,2, ...n} - множество игроков, Si (iєI) – множество стратегий i-го игрока,
а Hi-функция платежа i-му игроку, определенная на множестве ситуаций S =
S1 ×S2 ×…×Sn и принимающая вещественные значения.
Пример 2.1. (Спор партнеров)
Два экономических партнера договариваются о совместном проведении одного из
двух мероприятий: D1 или D2 , каждое из которых требует необходимого совместного
их участия. В случае совместного осуществления D1 первый получает доход в одну, а
второй - в две денежные единицы. Наоборот, в случае осуществления D2 первый
получает две, а второй - одну денежную единицу. Наконец, если они выполняют
различные действия, то выигрыш каждого из них равен нулю.
Здесь мы имеем дело с конфликтной ситуацией. Множество игроков I = {1,2}.
Игрок 1 - первый партнер, игрок 2 - второй партнер. Множества стратегий
S1 =S2 ={s1 ,s2 }.s1 - осуществить мероприятие D1, S2 - осуществить мероприятие D2 .
Функции выигрыша игроков задаются следующим образом: H1 (s1,s1 )=1, H1 (s1,s2 )=0,
H1 (s2,s1 )=0, H1 (s2,s2 )=2; H2 (s1,s1 )=2, H2 (s1,s2 )=0, H2 (s2,s1 )=0, H2 (s2,s2 )=1.
Пример 2.2 (Планирование посева)
Сельскохозяйственное предприятие может посеять культуры А1 ,А2 , А3 . Урожаи этих
культур во многом зависят от погоды. Требуется установить, какую из культур сеять,
чтобы обеспечить наибольший доход, если известна цена аi 1 ц культуры Аi и средняя
урожайность hij каждой культуры в зависимости от погоды (будет ли лето засушливым,
нормальным или дождливым; достоверный прогноз погоды отсутствует).
Здесь мы также имеем дело с конфликтной ситуацией.
Множество игроков I={1,2}. Игрок 1 - сельскохозяйственное предприятие, игрок 2 природа.
Множество стратегий игрока 1 S1 = s11 , s12 , s31 . Стратегии игрока 1: s11 - посеять
культуру A1 , s 12 - посеять культуру А2 , s 31 -посеять культуру А3 .
Множество стратегий игрока 2: S2 =
s
2
1

, s 22 , s32 . Cтратегии игрока 2: s12 - лето
засушливое, s 22 - лето нормальное, s 32 - лето дождливое .


H1 s1i , s 2j =aihij .Выигрыши игрока 2 здесь
несущественны. Позже мы сможем дать рекомендации игроку 1 для получения
гарантированного дохода.
Функция выигрыша игрока 1
Вопросы для самоконтроля
1. Что называется бескоалиционной игрой?
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. Что представляет собой модель бескоалиционной игры?
3. Какое наименьшее число игроков может участвовать в бескоалиционной
игре?
4. Кто может быть игроком? Приведите примеры.
Упражнения для самостоятельного решения
2.1 (Планирование выпуска продукции). Небольшое предприятие лёгкой
промышленности может выпускать продукцию одного из трёх видов: зонты, шляпы и
плащи, при этом доход его зависит от того, каким будет летний сезон - дождливым,
жарким или умеренным. В дождливое лето наибольший доход принесёт производство
зонтов, меньший производство плащей и совсем малый – производство шляп. В жаркое
лето наибольший доход даст производство шляп, средний - производство зонтов,
которые можно использовать, как от дождя, так и от солнца, и меньший – производство
плащей. В умеренное лето наибольший доход от производства плащей, несколько
меньший от производства шляп и еще меньший от производства зонтов. Доходы
предприятия определены таблицей:
Виды продукции
Зонты
Шляпы
Плащи
Дождливое
90
25
70
Лето
Жаркое
60
100
50
Умеренное
40
50
60
Готовясь к летнему сезону, экономист при отсутствии прогноза погоды должен
принять решение, какой из трёх видов продукции выпускать. Построить модель
бескоалиционной игры.
2.2. (Экономико-экологическая проблема). Каждое из трёх предприятий,
пользующихся для технических целей водой из некоторого водоёма, может или
сбрасывать её без очистки, или же использовать очистные сооружения для
отработанной воды. Особенности водоёма и технологических процессов на
предприятиях таковы, что в случае, когда неочищенную воду сбрасывает не более
одного предприятия, вода в водоёме остаётся пригодной для использования, и
предприятия убытка не несут. Если же неочищенную воду сбрасыв ают не менее двух
предприятий, то каждый пользователь воды несёт убытки в размере трёх единиц.
Стоимость использования очистных сооружений обходится предприятию в одну
единицу. Построить модель бескоалиционной игры.
2.3. (Борьба фирм за рынки посредством рекламы). Две конкурирующие фирмы
ведут борьбу за n рынков путём затрат денежных средств на рекламу. Фонды
рекламных расходов первой и второй фирм составляют суммы в а и b рублей
соответственно. Прибыль, которую можно получить от i-го рынка, равна сi>0, и
распределяется она между фирмами пропорционально суммам, затраченным ими на
рекламу на этом рынке. Составить модель бескоалиционной игры двух фирм, считая
выигрышем каждой их них суммарную прибыль, полученную от всех рынков.
2.4. (Олигополия с назначением выпусков). Цена на некоторый товар с насыщаемым
спросом убывает по формуле Се-s, где S – совокупное предложение. В предположении
нулевых затрат составить модель бескоалиционной игры, если количество товара,
предлагаемого на рынке i-ым производителем равно хi (i=1, 2, …n).
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2.5.
(Назначение
цен
в
дуополии).
Дуополисты
поставляют

на
рынок

p 
p 
взаимозаменяемую продукцию, спрос на которую равен d 1   2  и d 2   1 
 p2 
 p1 
единиц товара, произведённых соответственно первым и вторым производителем, где
р1 и р2 – цены на их продукцию, α>1 и β>1. Затраты на выпуск единицы продукции, у
обоих производителей не зависят от масштабов производства и равны сi (i=1. 2).
Составить модель бескоалиционной игры.
2.6.(Аукцион неделимого товара). Трактор должен быть куплен одним из n
участников аукциона. Его ценность для i-го участника измеряется количеством денег аi
(i=1, 2,…,n), которые он готов заплатить за него. Будем для определённости считать,
что 0<a1 ≤a2 ≤…≤an . Победителем считается тот, кто предложил наиболее высокую
цену. Эта сумма выплачивается продавцу. Считая, что начальная цена, назначаемая
продавцом с≤а1 и при одинаковых ценах предпочтение отдаётся тому участнику, для
которого ценность товара больше, составить модель бескоалиционной
игры,
считая, что доход каждого участника равен количеству сэкономленных денег, в случае,
когда трактор достался ему, и нулю в противном случае.
2.7. (Конкуренция на однопродуктовом рынке). n фермеров производят зерно.
k
Рыночная цена 1т зерна находится по формуле c 
, где k - некоторая
x1  ...  x n
постоянная, а x i (i  1,...,n ) количество зерна, которое произвёл i -ый фермер.
Составить модель бескоалиционной игры n фермеров, если себестоимость 1т зерна,
произведённого i -ым фермером равна s i .
2.8. (Премия). Администрация фирмы стимулирует рабочего экономить сырьё и с
этой целью внедряет премиальную систему оплаты труда. Выработка рабочего
составляла N изделий в час, себестоимость изделия – S руб. Если рабочий будет
экономить х кг сырья на одном изделии, то его производительность снизится на х %.
Цена реализации 1 изделия составляет С рублей, стоимость 1 кг ресурса – Р руб.,
расценка по оплате труда за 1 изделие – К руб., размер премии за экономию 1 кг
ресурса – у рублей. Составить модель бескоалиционной игры администрации и
рабочего.
3. АНТАГОНИСТИЧЕСКИЕ ИГРЫ
Определение 3.1. Бескоалиционная игра называется игрой с постоянной суммой,
если существует такое постоянное с, что для всех ситуаций s:
n
 H s  =c.
i 1
i
Определение 3.2. Бескоалиционная игра двух лиц с нулевой суммой называется
антагонистической игрой.
Антагонистическую игру можно представить тройкой: Г= <S1 ,S2 , H>, где S1 и S2 множества стратегий игроков, H - функция выигрыша игрока 1, определенная на
множестве S= S1 ×S2 и принимающая вещественные значения. Действительно, по
определению H1 (S)+H2 (S) = 0 и, следовательно, H1 =H, а H2 .=-H. Множество игроков I =
{1,2}можно не указывать.
9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Так как в антагонистической игре игрок 2 проигрывает столько же, сколько
выигрывает игрок 1, то величина H(S) также проигрыш игрока 2. Понятия проигрыша и
выигрыша чисто условные, так как величина H(s) может быть как положительной, так и
отрицательной.
Пример 3.1. (Игра двухпальцевая Морра).
В игру играют 2 человека: каждый из них одновременно по команде "Мор-pa"
показывает один или два пальца на левой руке и одновременно на правой руке
показывает число пальцев, которое, по его мнению, покажет на левой руке его
противник. Если один из игроков угадывает правильно, то он выигрывает сумму,
равную количеству пальцев, показанных им и его противником на левой руке; в
противном случае - ничья.
Так как в этой игре каждый игрок выигрывает ровно столько, сколько проигрывает
другой, то это - пример антагонистической игры.
Замечание 3.1.
В играх такого типа, когда одним из игроков является природа или среда,
целесообразно принимать так называемую гипотезу антагонизма. Она состоит в
предположении, что среда ведет себя наихудшим для принимающего решение образом.
Конечно, можно принимать и другие гипотезы, но эта хороша тем, что при любом
другом поведении среды выигрыш принимающего решение может только увеличиться.
В таком случае игру примера 1.2 также можно рассматривать как
антагонистическую.
Определение 3.3. Бескоалиционная игра называется конечной, если множество
стратегий каждого игрока конечно.
Так как обозначение стратегий несущественно, то для конечных игр их можно
обозначать соответствующими номерами.
Для игр двух лиц будем считать, что S1 = {1,2,…,m}, a S2 = {1,2,…,n}. Тогда
ситуации представляют собой всевозможные пары (i,j), где i =1,2,…,m; j=1,2,….,n.
Определение 3.4. Конечная антагонистическая игра Г = <S1 , S2 ,H> называется
матричной игрой формата m×n, при этом число m - число стратегий игрока 1, n число стратегий игрока 2.
Определение 3.5. Для матричной игры формата m×n матрица
 à11à12 ...à1n 


À   a 21a 22 ...a 2 n  ,
 a a ...a 
 m1 m 2 mn 
где аij = H(i,j), называется платежной матрицей, или матрицей игры.
Замечание 3.2.
Формат матричной игры совпадает с размерностью ее платежной матрицы.
Платежная матрица - это матрица платежей игроку 1, а матрица платежей игроку 2
есть матрица -А.
Матричная игра полностью задана, если известна ее платежная матрица.
Пример 3.2. Найдем для игры примера 3.1, которая является матричной,
платежную матрицу.
Стратегии каждого из игроков: (1,1); (1,2); (2,1); (2,2), где первый элемент
соответствует количеству пальцев, показанных на левой руке, а второй - на правой.
Следующая таблица определяет платежную матрицу.
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2
1
1
2
3
4
(1,1)
(1,2)
(2,1)
(2,2)
1
(1,1)
0
-2
3
0
2
(1,2)
2
0
0
-3
3
(2,1)
-3
0
0
4
4
(2,2)
0
3
-4
0
Вопросы для самоконтроля
1. Какая игра называется антагонистической?
2. Что представляет собой модель антагонистической игры?
3. Какая игра называется конечной?
4. Какая игра называется матричной?
5. Что называется матрицей игры?
6. Как можно задать матричную игру?
Упражнения для самостоятельного решения
3.1. (Захват рынков сбыта). Фирма А пытается вытеснить фирму В, имеющую два
рынка сбыта, с одного из них. Общая сумма, выделяемая фирмой А на эту цель,
принимается равной единице и распределяется ею между двумя рынками. Фирма В для
удержания рынков также располагает единичной суммой средств и распределяет её
между рынками. Выигрыш фирмы считается равным сумме разностей своих средств и
средств противника, выделенных на каждый рынок, взятых с коэффициентом к i (i=1,2),
характеризующим
важность
соответствующего
рынка.
Построить
модель
бескоалиционной игры. Доказать, что данная игра является антагонистической.
Является ли данная игра матричной?
3.2. (Борьба за рынки сбыта). Фирма А имеет n рынков сбыта, а фирма В желает их
захватить. На эту цель фирма В может выделить b рублей. Фирма А для защиты своих
рынков располагает суммой в а рублей. Если для захвата рынка i фирма В выделяет хi
рублей, а фирма А для защиты своего рынка выделяет уi рублей, то фирма В получит
доход k i(αiхi –yi ), а фирма А имеет k i(yi - -αiхi). Коэффициент k i определяет степень
важности рынка i, а коэффициент αi – степень сопротивления рынка i фирме,
производящей экспансионистскую политику. Построить модель антагонистической
игры. Является ли данная игра бесконечной антагонистической?
3.3.Продавец яблок с каждого проданного килограмма получает прибыль, равную
а рублей. Непроданные яблоки он возвращает на склад, но при этом терпит убыток b
рублей с каждого килограмма. Спрос, то есть количество кг яблок, требуемых
покупателем, точно не известен, но может быть равен 200, 250 или 300 кг. Построить
модель матричной игры и её матрицу.
3.4. Предприятие реализует свою продукцию в двух магазинах. В торговую
инспекцию поступили сведения о том, что в этих магазинах продаётся бракованный
товар в объёме 20 и 10 единиц. Инспектирующий орган намерен провести инспекцию с
целью обнаружения брака. Так как магазины находятся далеко друг от друга, то может
быть проверен только один из них. Предприятие узнаёт о готовящейся инспекции и
решает изъять бракованный товар, но по техническим причинам изъятие может быть
проведено только в одном магазине. Считая выигрышем инспектора объём
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
обнаруженного им бракованного товара, который также является проигрышем
предприятия, составить модель матричной игры.
3.5. Две конкурирующие фирмы могут выставить на продажу по одному из трёх
видов товаров Т1 , Т2 , Т3 , причём Т2 имеет некоторые преимущества по сравнению с Т1 ,
Т1 по сравнению с Т3 , а Т3 - с Т2 . Если фирмы выставляют на продажу товар разных
видов, то фирма поставившая товар, имеющий преимущества, получает прибыль в 1
денежную единицу, а другая терпит убыток в том же размере. Если они выставляют
товар одного вида, то они лишь покрывают убытки, и прибыль их равна нулю.
Составить матрицу игры.
Для матричных игр, заданных платёжной матрицей определить а)её формат, b)число
стратегий игроков; с) записать матрицу выигрышей игрока 2; d) выигрыши игроков в
ситуации (2,1):
2
5
7
 1


7
2
4
2
0 2
8
 3
 2




3.6.  3  1 0 4
3. 7.   1 4 1 4 1 .


 0 5
0 3
0 
1
7
3
 4

 0
2
6
1

4. МАТРИЧНЫЕ ИГРЫ
Пусть задана матричная игра формата m×n матрицей
 а11а12 ...а1 j ...а1n 


 а21а22 ...а2 j ...a2 n 


 ......................... 
А

a a ...a ...a
 i1 i 2 ij in

 ......................... 


 am1am 2 ....amj ...amn 
Если игрок 1 выберет стратегию 1, то при любом поведении игрока 2 он
гарантирует себе выигрыш не меньший, чем  i  min aij . Чтобы сделать величину
j
выигрыша как можно больше, ему целесообразно выбрать такую стратегию i*, для
которой этот выигрыш максимален, то есть  i*  max i  max min aij .
i
i
j
Таким образом, у игрока 1 существует такая стратегия i*, что при любом поведении
игрока 2, то есть при любом j, выигрыш игрока 1 ai*j =H(i*,j) удовлетворяет
неравенству:
ài* j  max min aij .
(1)
i
j
Определение 4.1. Величина υ= max min aij называется нижней ценой игры.
i
j
Стратегия i*, гарантирующая игроку 1 получение выигрыша не менее υ, называется
максиминной стратегией игрока 1. Принцип, придерживаясь которого игрок 1
выбирает максиминную стратегию, называется принципом максимина.
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Правило нахождения нижней цены игры и максиминной стратегии:
1) находим в каждой строке платёжной матрицы минимальный элемент и
выписываем его в отдельный столбец;
2) выбираем в построенном столбце максимальный элемент или элементы, если их
окажется несколько. Он (они) и будут равны нижней цене игры, а номера строк, в
которых расположены эти элементы будут соответствовать максиминным стратегиям
игрока 1.
Следуя этому же принципу, игрок 2, выбирая стратегию j, потеряет не более
 j  max aij . Чтобы сделать свой проигрыш βj. Как можно меньше, ему целесообразно
i
выбрать стратегию j*,
 j*  min  j  min max aij .
j
j
для
которой
эта
величина
минимальна,
то
есть
i
Таким образом, у игрока 2 существует такая стратегия j*, что при любом поведении
игрока 1, то есть при любом i, выполняется неравенство:
(2)
aij*  min max aij .
j
Определение
i
4.2. Величина   min max aij называется верхней ценой игры.
j
i
Стратегия j* игрока 2, запрещающая игроку 1 получение выигрыша больше, чем  ,
называется минимаксной стратегией игрока 2.
Правило нахождения верхней цены игры и минимаксной стратегии:
1) находим в каждом столбце платёжной матрицы максимальный элемент и
выписываем его в отдельную строку;
2) выбираем в построенной строке минимальный элемент или элементы, если их
окажется несколько. Он (они) и будут равны верхней цене игры, а номера столбцов, в
которых расположены эти элементы будут соответствовать минимаксным стратегиям
игрока 2.
Если оба игрока следуют принципу максимина, то из неравенств (1) и (2) получаем,
что для максиминной i* и минимаксной j* стратегий выполняется двойное неравенство:
(3)
max min aij  ai* j*  min max aij .
i
j
j
i
Следовательно, нижняя цена игры всегда не превосходит верхнюю цену игры, то
есть
 
Игроки могут следовать и другим принципам, но принцип максимина - это принцип
осторожного игрока, так как, отклоняясь от него, игроки могут проиграть больше.
Принцип максимина был впервые явно сформулирован Дж. Фон Нейманом в 1928
году в работе "К теории стратегических игр". Этот принцип имеет важное значение и
широко используется в теории игр. В частности, теория антагонистических игр изучает
поведение игроков, придерживающихся именно этого принципа.
Пример 4.1. Найдем верхнюю и нижнюю цены игры, а также максиминную и
минимаксную стратегии для игры примера 3.1 главы 1 с платежной матрицей:
 0

 2
А
3

 0
2
0
0
3
13
3
0
0
4
0

3 .
 4

0 
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Воспользовавшись приведенными выше правилами, составим столбец из минимальных
элементов строк, а затем наибольший из них отметим звездочкой. Аналогично, составим
строку из максимальных элементов столбцов и также отметим наименьший из них
звездочкой.
min aij
j
 0

 2
А
3

 0
max aij
i
2
0
0
3
3
2*
3
0
0
4
0  3

3  2 *
 4  4

0   3
4
3
Нижняя цена игры   2 стратегия игрока. Верхняя цена игры   2 .
Максиминная стратегия игрока 1:i*=2, минимаксная стратегия игрока 2: j*=2.
Заметим, что максиминная и минимаксная стратегии не обязательно определяются
однозначно. Это может произойти потому, что в дополнительном столбце или строке
некоторые элементы, соответствующие разным стратегиям, могут совпадать.
В рассмотренном примере видно, что принцип максимина не обладает
устойчивостью. Если игрок 1 выберет стратегию 2, то игрок 2, предполагая подобное
поведение игрока 1, может отклониться от минимаксной стратегии и принять
стратегию 1 и тем самым наказать игрока 1 минимальным платежом, а игрок 1,
предполагая такое поведение игрока 2, может отклониться от своей максиминной
стратегии и принять стратегию 3, наказав игрока 2 максимальным проигрышем, и т.д.
Существуют игры, в которых принцип максимина обладает устойчивостью.
Определение 4.3. Элемент аiojo называется седловой точкой матрицы А=(аij)
(i=1,2,…m; j=1,2,….n),если для любых i и j выполняется неравенство: аijo ≤aiojo ≤aioj.
Заметим, что седловая точка матрицы - это самый маленький элемент в своей строке
и одновременно самый большой в своем столбце.
Определение 4.4. Ситуация (i0 ,j0 ) называется ситуацией равновесия, или седловой
точкой матричной игры, если aiojo - седловая точка ее платежной матрицы.
Теорема о принципе равновесия
Для того чтобы матричная игра обладала ситуацией равновесия, необходимо и
достаточно, чтобы верхняя цена игры была равна нижней цене игры.
Доказательство. Необходимость. Пусть (i0 j0 ) - ситуация равновесия. Тогда по
определениям 2.1 и 2.2 аijo ≤aiojo для всякого i и, следовательно, max aijo  aiojo .
i
Аналогично, для всякого j:аiojo ≤aioj и aiojo ≤ min aioj .Имеем:
j
  min max aij  max aijo  aiojo  min aioj  max min aij  
j
i
i
j
i
j
Так как    , то   aiojo     и, следовательно,     aiojo .
Достаточность. Пусть    и i0 и j0 - соответственно максиминная и минимаксная
стратегии игроков. Тогда из неравенств (1), (2) и (3) § 1 следует, что   aioj и аijo≤ для
всех i и j и   aiojo   , но так как   , то,     aiojo и аijo ≤aiojo ≤aioj.для всех i и j.
Следовательно, (i0 ,j0 ) - ситуация равновесия.
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Следствие 4.1. Если верхняя цена игры равна нижней цене иг-ры, а io и JO соответственно максиминная и минимаксная стратегии игроков, то (i0 ,j0 ) - ситуация
равновесия, и обратно, если (i0 ,j0 ) -ситуация равновесия, то i0 , j0 соответственно
максиминная и минимаксная стратегии.
Принцип, которому следуют игроки, стремясь достигнуть ситуации равновесия,
называется принципом равновесия.
Замечания:
1. Если для антагонистической игры принцип равновесия реализуем, то, следуя
этому принципу, игроки следуют также принципу максимина.
2. Если (i0 ,j0 ) - ситуация равновесия, то для любых i, j имеем H(i,j0 ) ≤H(i0 ,j0 ) ≤H(i0 ,j) ,
где Н - функция платежа.
3. Из предыдущего замечания следует, что ни одному из игроков не выгодно
односторонне отклоняться от ситуации равновесия. То есть ситуация равновесия
определяет наилучшие стратегии в игре.
Определение 4.5. Стратегии i0 и JO , образующие ситуацию равновесия, называются
оптимальными. При этом ситуация равновесия называется также решением игры.
Платеж   àiojo называется ценой игры.
Заметим, что иногда решением игры называют тройку (i0 ,j0,  )
Вывод
Если матрица игры имеет седловую точку, то игра имеет решение и цену, а самые
разумные действия сторон в такой игре - придерживаться оптимальных стратегий.
Пример 4.2. Для примера 2..2 о планировании посева установить, какую культуру
сеять, если доходы сельскохозяйственного предприятия в млн. рублей задаются
таблицей:
А1
А2
Сухое
0
6
Лето
нормальное
2
4
А3
7
3
Культуры
дождливое
9
8
1
Как указывалось выше, всякая игра с природой может быть рассмотрена как
антагонистическая игра. Найдем нижнюю и верхнюю цены игры и максиминную и
минимаксную стратегии. Имеем:
min aij
j
0 2 9

6 4 8
 7 31

max aij 7 4* 9





0
4*
1
i
Следовательно,    = 4 млн. рублей, и цена игры  =4 млн. рублей, а пара
стратегий (2,2) есть ситуация равновесия. То есть, следует сеять культуру А2 . При этом
будет получен доход не менее 4 млн. рублей при любой погоде.
Вопросы для самоконтроля
1. Что называется нижней ценой игры и максиминной стратегией игрока 1?
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сформулировать правило нахождения нижней цены игры и максиминной стратегии.
Что называется верхней ценой игры минимаксной стратегией игрока 2?
Сформулировать правило нахождения верхней цены игры и минимаксной стратегии.
В чём состоит принцип максимина?
Что называется седловой точкой матричной игры?
В каком случае существует седловая точка матричной игры и какие стратегии её
образуют?
8. Что называется ценой и решением игры?
2.
3.
4.
5.
6.
7.
Задачи и упражнения для самостоятельного решения.
Для игр, заданных матрицами, найти нижнюю и верхнюю цены игры, а также
максиминные и минимаксные стратегии:
3 6 1 4


4.1.  5 2 4 2  ;
1 4 3 5


 1

4. 2.   1
 2

1
1
2
 1

3 .
 1
Проверить, имеют ли игры, заданные матрицами, седловые точки:
0
2
1
 4


4
1
2
 0
4.4. 
.
1 1
3
0


 2
1
0
3 

4.5. Для игры, описанной в 3.5 найти верхнюю и нижнюю цену. Убедитесь, что
игра не имеет седловой точки.
4.6. Два фермера могут поставить на рынок продукцию либо первого, либо второго
либо третьего сорта. Если они поставили продукцию разных сортов, то тот из них, кто
поставил продукцию более высокого сорта получает прибыль в 10 тысяч рублей, а
другой терпит убытки в том же размере. Если они поставляют товар одинакового сорта,
то прибыль их равна нулю. Составить матрицу игры. Имеет ли игра седловые точки?
4.7. Конкурирующие фирмы А и В имеют возможность производить изделия одного
из пяти видов, которые затем продаются на одном рынке. Доход фирмы А, зависящий
от сочетания типов изделий, произведённых обеими фирмами, задан в таблице:
 1  3  2


5
4;
4.3.  0
 2
3
2 

1
2
3
4
5
1
0
13
11
4
8
2
6
6
7
5
7
3
15
5
8
16
17
4
6
3
7
6
7
5
10
8
9
14
7
Целью фирмы А является максимизация своего дохода, а целью фирмы В минимизация
дохода конкурирующей фирмы А. В полученной матричной игре найти седловые
точки.
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4.8. Фирма может выставить на рынок три вида товаров. В зависимости от
состояния рынка её доходы в тыс. руб. представлены в таблице.
Виды
товаров
Состояния рынка
1
2
3
4
1
1
0
-2
2
2
2
1
3
1
3
-3
-2
4
-2
Какой вид товара наиболее целесообразно поставить фирме на рынок?
4.9.Строительство дамбы высотой 1, 2 или 3 метра составляет соответственно 1,
2 и 3 млн. рублей. Ожидаемый ущерб от наводнения, уровень которого не превосходит
1м равен 5 млн. руб., 2м – 7млн. руб. 3м – 10млн. руб. Требуется дать рекомендации
относительно необходимости строительства дамбы и её высоты, если на это
мероприятие выделено 15 млн. рублей, а выигрышем проектировщиков считать
сэкономленную сумму.
5. СМЕШАННОЕ РАСШИРЕНИЕ МАТРИЧНЫХ ИГР
Остается открытым вопрос, как же следует поступать, если ситуации равновесия
нет, то есть матрица игры не содержит седловой точки. Выбор стратегий с некоторыми
вероятностями представляет собой один из планов проведения игры.
Будем называть в дальнейшем стратегии каждого игрока чистыми стратегиями.
m
Определение 5.1. Вектор Х = ( р1 , р2 ,…, рт ), где 1) рi≥0 для всех i; 2)  pi  1 .
i 1
называется смешанной стратегией игрока 1.
n
Определение 5.2. Вектор Y = (q1 ,q2 ,…,qn ), где 1) qj≥0 для всех j; 2)  q  1 .
i
j 1
называется смешанной стратегией игрока 2.
Чистая i-я стратегия игрока 1 может быть отождествлена с его смешанной
стратегией (0,...0, 1 ,0,...,0), a j-я чистая стратегия игрока 2-c его смешанной стратегией
i
(0,…,0, 1 ,0,….,0).
j
То есть, можно считать, что множество чистых стратегий игрока входит в
множество его смешанных стратегий.
Так как число чистых стратегий каждого игрока больше единицы, то множество его
смешанных стратегий бесконечно. Например, для m = 3 смешанные стратегии X =
(р1 ,р2 , p3 ) геометрически изображаются точками части плоскости р1 + р2 + р3 = 1,
лежащей в первом октанте, так как р1 , р2 , р3 ≥ 0 (рис.5.1).
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 5.1.
Чистым стратегиям соответствуют точки пересечения с осями координат.
Замечание 5.1. Компоненты смешенных стратегий можно истолковать как
- вероятности, с которыми игрок принимает свои чистые стратегии;
- относительные частоты, с которыми игрок принимает свои чистые стратегии;
- части, в которых смешиваются чистые стратегии, если это возможно.
Пусть выбрана ситуация в смешанных стратегиях (Х,Y), где X = (р1 ,р2 ,…pm), Y=
(q1 ,q2 ,…,qn ). Для случайной величины z (платеж игроку 1) возможные значения
задаются матрицей игры A=(aij), где i=1,2,….,m; j=1,2,….,n, причем вероятность
значения aij равна piqj, так как игроки выбирают свои стратегии независимо. Тогда
m n
математическое ожидание выигрыша игрока 1: M  z     aij pi q j .Это число
i 1 j 1
принимается за выигрыш игрока 1 в ситуации в смешанных стратегиях (Х,Y).
Определение 5.3. Смешанным расширением матричной игры формата m×n с
матрицей А= (aij) называется антагонистическая игра <Sm, Sn , H>, в которой
множествами стратегий являются множества смешанных стратегий игроков в исходной
игре, а функция выигрыша определяется равенством:
m
Н (X,Y)= 
i 1
n
a
j 1
ij
pi q j
(1)
где X= (р1 , р2 ,…рm), Y = (q1 , q2, …qn) - смешанные стратегии соответственно игроков 1 и 2.
Замечание 5.2. Смешанное расширение матричной игры является бесконечной
антагонистической игрой, так как в ней множество чистых стратегий каждого игрока
бесконечно. Функция выигрыша игрока 1, определяемая равенством (1), на множестве
чистых стратегий исходной игры, очевидно, совпадает с ее платежной функцией.
Определение 5..4. Ситуация (X*, Y*) в смешанном расширении матричной игры
называется ситуацией равновесия, если для любых XєSm , YєSn , выполняется двойное
неравенство:
H(X,Y*) ≤H(X*,Y*) ≤ Н(Х*,Y)
(2)
Заметим, что в определении дано обобщение соответствующего понятия для
исходной игры.
Используя произведение матриц, получаем:
m n
m
n
i 1 j 1
i 1
j 1
H  X , Y     aij pi q j   pi (  aij q j ) XAY T
где Y транспонированная строка Y.
Таким образом, (2) в матричной форме перепишется так:
XAY*T ≤ X*AY*T≤ X*AYT .
(3)
Определение 5.5. Смешанная стратегия называется оптимальной, если существует
стратегия другого игрока, в паре с которой она образует ситуацию равновесия.
Теорема о ситуации равновесия
T
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Если ситуация (i0 ,j0 ) является ситуацией равновесия в матричной игре, то она
является ситуацией равновесия и для ее смешанного расширения.
Доказательство. Так как (i0 ,j0 ) - ситуация равновесия в исходной игре, то для
любых i и j аijo ≤aiojo ≤aioj. Так как i0 ~(0,…,0,1,0,…,0), а jo ~(0,…,0,1,0,…0), то
m
m
i 1
n
i 1
n
H  X , j0    aij 0 pi  ai0 j 0  pi  aiojo  H i0 j0 
и
H i0 ,Y    ai0 j q j  ai0 j 0  q j  ai0 j 0  H i0 , j0 
j 1
j 1
To есть для любых X и Y H  X , j0   H i0 , j0   H i0 , Y  И (i0 ,j0 ) - ситуация равновесия
для смешанного расширения.
Основная теорема теории матричных игр
Пусть дана матричная игра формата m×n, А=(aij) – ее матрица. Тогда в ее
смешанном расширении существуют и равны max min H ( X ,Y ) и min max H ( X ,Y ) , где
X
Y
Y
X
m n
H ( X ,Y )    aij pi q j , причем каждый из игроков имеет хотя бы одну стратегию X*
i 1 j 1
и Y* , такую, что
max min H ( X ,Y ) = min max H ( X ,Y ) = H(X*,Y*).
X
Y
Y
(4)
X
Теорема была доказана в 1928 году Дж. Фон Нейманом. Доказательство ее
достаточно сложно, и мы его опустим. Приведем также без доказательства ряд
следствий из нее.
Следствие 5.1. Смешанное расширение любой матричной игры имеет ситуацию
равновесия (седловую точку).
Следствие 5.2. Для смешанного расширения любой матричной игры нижняя цена
игры  = max min H ( X ,Y ) = min H ( X * ,Y ) равна верхней цене игры  = min max H ( X ,Y ) =
Y
X
Y
Y
X
= max H ( X , Y ) а максиминная стратегия Х* и минимаксная стратегия Y* есть ее
*
X
оптимальные стратегии.
Следствие 5.3. Оптимальные смешанные стратегии могут определяться
неоднозначно, но любая из них образует ситуацию равновесия с любой оптимальной
смешанной стратегией другого игрока, причем выигрыши во всех ситуациях
равновесия одинаковы и равны цене игры.
Вывод
Любая матричная игра имеет решение (X*,Y*) В смешанных стратегиях, причем
цена игры  = H(X*,Y*), a X*,Y* - оптимальные стратегии игроков. Иногда решение
игры записывают в виде тройки (X*, Y*,  ).
В дальнейшем под стратегией будем понимать смешанную стратегию.
Лемма о преобразовании функции выигрыша.
Тройка (X*, Y*,  ) является решением игры Г =<S1 , S2 ,H> тогда и только тогда,
когда тройка (Х*,Y*,   a ) является решением игры Г′=<S1 , S2 ,kH+a>, где k>0, а аєR.
Доказательство. Тройка (X*, Y*,  ).является решением игры Г тогда и только
тогда, когда для любых стратегий X и Y: Н(Х,Y*) ≤H(X*,Y*)≤ Н(Х*,Y) и Н(Х*,Y*) = .
Используя свойства неравенств, замечаем, что последнее утверждение равносильно
тому, что kH(X,Y*)+a≤kH(X*,Y*)+a≤kH(X*,Y)+a и kH(X*,Y*)+a=k +a, но по
определению решения игры это означает, что (X*,Y*, k  +a)- решение игры Г′.
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Лемма об оптимальных стратегиях.
Если в оптимальной смешанной стратегии игрока вероятность применения
некоторой его чистой стратегии положительна, то выигрыш игрока 1 в ситуации,
образованной этой чистой стратегией и любой оптимальной стратегией другого игрока,
равен цене игры.

*
Доказательство. Пусть X*= p1* , p2* ,..., pm

и Y*= (q1* , q 2* ,...., q n* ) - оптимальные
стратегии игроков, причем p*i >0.
0
Так как (Х*,Y*) - ситуация равновесия и цена игры  = Н(Х*,Y*), ТО по
определению 3.3 для всех X є Sm H(X,Y*) ≤  И, следовательно, H (i0 , Y * )   . Если бы
H (i0 , Y * ) <  ,
то
m n
m n



m
m
  H ( X * , Y * )    aij pi*q *j     aij q *j  pi*   pi* H (i, Y * ) <  pi*   . Но  <


i 1 j 1
i 1 j 1
i 1
i 1
невозможно. Следовательно, H (i0 , Y )   . Аналогично доказывается утверждение для
чистой стратегии игрока 2.
Определение 5.6. Стратегия X1 игрока 1 называется строго доминирующей его
стратегию Х2 , а Х2 - строго доминируемой Х1 , если для любой чистой стратегии j
игрока 2 H(X1 ,j) > H (X2 ,j).
Определение 5.7. Стратегия Y1 игрока 2 называется строго доминирующей его
стратегию Y2 ; а Y2 - строго доминируемой Y1 если для любой чистой стратегии i игрока
1 H(i,Y1 ) < Н(i,Y2 ).
Замечание 5.3. Так как неравенство H(i,Y1 ) < Н(i,Y2 ) равносильно неравенству H(i,Y1 ) > - Н(i,Y2 ) и -Н - функция платежа игроку 2, то определение 5.7 не
противоречит определению 5.6.
Если неравенства в определениях 5.6 и 5.7 являются нестрогими, то говорят о
доминировании стратегий.
Для того чтобы чистая стратегия i1 игрока 1 была доминируема его чистой
стратегией i2 , необходимо и достаточно, чтобы элементы i1 -й строки платежной
матрицы не превосходили ее элементов i2 -й строки.
Аналогично, для того чтобы чистая стратегия j1 игрока 2 была доминируема его
чистой стратегией j2 необходимо и достаточно, чтобы элементы j2 - гo столбца
платежной матрицы не превосходили элементов ее j1 - го столбца.
Теорема о доминируемой стратегии.
Всякая строго доминируемая чистая стратегия входит в любую оптимальную
стратегию игрока с нулевой вероятностью.
Доказательство. Пусть стратегия Y0 игрока 2 строго доминирует его чистую
стратегию jo . Тогда H(i,Y0 ) <(i, j0 ) для i = 1,2,…,m. Тогда по замечанию 4 и для любой
оптимальной стратегии X* игрока 1 H(X*,Y0 ) < H(X*,j0 ). Если бы j0 входила в
некоторую оптимальную стратегию с положительной вероятностью, то по теореме 2
цена игры  =H(X*,jo ) и тогда бы Н(Х*,Yо ) <  что противоречит оптимальности X*.
Из вышесказанного следует, что наряду с принципами максимина и равновесия,
которые для смешанного расширения эквивалентны, целесообразно также
придерживаться еще одного принципа.
*
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Принцип доминирования: игрок не должен использовать с положительной
вероятностью доминируемые стратегии, так как, применяя их, он при всех действиях
другого игрока выигрывает меньше, чем при использовании других стратегий.
Таким образом, в матрице игры можно вычеркнуть строки и столбцы,
соответствующие доминируемым стратегиям. В результате получим игру меньшего
формата.
Зная решение полученной игры, легко найти решение исходной. Можно доказать,
что цены этих игр одинаковы, а оптимальные стратегии данной игры получаются из
найденных оптимальных стратегий добавлением нулей на месте доминируемых
стратегий.
Вопросы для самоконтроля
1. Что называется смешанной стратегией игрока?
2. Что такое чистая стратегия игрока и как её можно представить в виде смешанной
стратегии?
3. Что называется ситуацией равновесия в смешанном расширении матричной
игры? Когда она существует?
Задачи и упражнения для самостоятельного решения
5.1. Определить могут ли следующие векторы быть смешанными стратегиями
игрока 1 в матричной игре формата 2  3:
a) (0,5; 0,5); b) (0,1; 0,3; 0,6); c) (0,1; 0, 7); d) (-1;2); e) (0,5; 0,8; -0,3).
5.2. Определить могут ли следующие векторы быть смешанными стратегиями
игрока 2 в матричной игре формата 2  3:
a) (0,6; 0,4); b) (0,1; 0,3; 0,6); c) (0,1; 0, 7); d) (-1; 2;0); e) (0,5; 0,8; -0,3).
В задачах 5.3 –5.6 уменьшить формат игры, вычеркнув доминируемые стратегии.
 3 2 4 0
2 4 5 1




 3 4 2 4
 3 5 8 2
5.3. 
;
5.4. 
4 2 4 0
1 4 7 1




0 4 0 8
0 3 2 6




 5 5 4 5 2


1
2
3
 2


5 4 7 1 6
1
2
 3 1,5
5.5. 
; 5.6.  2 3 4 1 7  .



2
2
1
1


3
6
7
3
2


 1
1
1 0,5 

 4 4 3 0 2


6. МЕТОДЫ РЕШЕНИЯ МАТРИЧНЫХ ИГР
А). Метод непосредственного решения матричных игр
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
a12 
a
 оптимальное решение
Для матричных игр формата 2  2 с матрицей А=  11
 a 21 a 22 
Х*=(р*, 1-р*) и У*=(q*, 1-q*) находится по формулам:
a 22  a 21
p* 
;
a11  a12  a 21  a 22
a 22  a12
.
a11  a12  a 21  a 22
При этом цена игры (выигрыш игрока 1в ситуации равновесия) равен:
a11a 22  a12 a 21
v
.
a11  a12  a 21  a 22
q* 
Пример 6.1.. (Планирование выпуска сельхозпродукции)
Фермер может произвести несколько типов продукции. Если продукция типа j будет
пользоваться спросом, то он получит прибыль Pj. Если же нет, то он потерпит убытки qj
(транспортные расходы, порча, хранение и т.д.). При неизвестном потребительском
спросе требуется выбрать тип продукции с целью максимизации доходов для случая:
Тип продукции
1
2
Доход от реализации в
условных единицах
10
20
Убыток при хранении в
условных единицах
4
5
Здесь игрок 1 - фермер, игрок 2 - потребительский спрос (среда). Принимая
гипотезу антагонизма, игру можно рассматривать как антагонистическую с матрицей
10 - 4 

 .
 - 5 20 
Легко проверить, что доминируемых стратегий и седловой точки матрица не имеет.
Тогда решение игры можно найти по формулам:
20  5
25
20  4 24
10  20  5  4 180
P* 
 ; q* 
 ; 

.
10  4  5  20 39
39
39
39
39
25 14
24 15
180
Таким образом, X *   , ; Y*   , ; v 
 4,7 усл.ед.
39
39
39
39
39




Здесь вероятности можно трактовать как доли производимого товара, а именно:
следует производить 25/39 частей продукции типа 1 и 14/39 типа 2, то есть нужно
производить продукцию типа 1 и 2 в отношении 25:14. При этом будет гарантирован
доход  = 4,7 условных единиц в наихудшем для фермера случае, когда спрос на
продукцию типов 1 и 2 будет распределен в отношении 24:15. Во всех остальных
случаях доход может быть выше.
Б). Графоаналитический метод для игр формата 2  п и т  2
 2 3 11
 .
Пример 6.2. Решить графическим методом игру, заданную матрицей 
7 5 2 
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
13
12
11
11
10
9
8
7
7
6
5
5
4
3
3
2
2
2
1
0
0
0,2
0,4
0,6
0,8
1
1,2
Рис.6.1.
Построим прямые:   2 p  7( 1  p );   3 p  5( 1  p );   11 p  2( 1  p ) , соответствующие
чистым стратегиям 1, 2, 3 игрока 2.
Затем построим нижнюю огибающую и найдем ее наивысшую точку М.
Из рисунка 5.1 видно, что стратегия 1 не входит в оптимальную стратегию игрока 2
 3 11
 .
и, следовательно, решение игры можно найти по формулам, исходя из матрицы 
5 2 
3  2  5  11
49
25 3
2  11 9
Итак, цена игры  

 4,45 . Ð* 
 . q* 
 .
3  2  5  11 11
 11 11
 11 11
9 2
3 8
Оптимальные стратегии X *   ,  , Y *  (0, , ) .
11 11
 11 11 
2 7 


Пример 6.3. Решить графическим методом игру, заданную матрицей  3 5  .
11 2 


Построим
прямые
  2q  7(1  q);
  3q  5(1  q);
  11q  2(1  q) ,
соответствующие стратегиям 1, 2, 3 игрока 1.
Затем построим верхнюю огибающую всех прямых, соответствующих чистым
стратегиям игрока 1, и найдем ее низшую точку N. Из рисунка 5.2 видно, что стратегия
2 игрока 1 не входит в его оптимальную стратегию и, следовательно, решение игры
2 7 
 .
можно найти по формулам (1), (2) и (3), исходя из матрицы 
11 2 
2  2  7 11 73
2  11 9
27 5

 5,21. P * 
 . q* 
 .
Цена игры  
2  2  11  7 14
 14 14
 14 14
Итак, цена игры   5,21 ; оптимальные смешанные стратегии:
5 9
5
9
X *   ,0,  ; Y *  ( , ) .
14 14
 14 14 
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
13
12
11
11
10
9
8
7
7
6
5
5
4
3
3
2
2
2
1
0
0
0,2
0,4
0,6
0,8
1
1,2
Рис.6.2.
В). Решение матричных игр методами линейного программирования
Рассмотрим матричную игру формата m×n с матрицей А = (aij). Будем считать, что
цена игры  >0. Для игр с положительными матрицами это выполняется всегда, а в
остальных случаях можно прибавить достаточно большую константу ко всем
элементам платежной матрицы, что, согласно теореме 1, не меняет оптимальных
стратегий игроков.
Если игроки применяют стратегии X  ( p1 , p2 ,..., pm ) и Y  (q1 , q2 ,..., qn ) , то
m n
средний выигрыш игрока 1 H ( X ,Y )    aij pi q j .
i 1 j 1
Если игрок 2 применит оптимальную стратегию Y, а игрок 1 стратегию i, то средний
n
выигрыш игрока 1 H (i, Y )   aij q j   .
j 1
Так как по предположению  > 0, то, разделив обе части неравенств на  ,получим
n
qj
  aij u j  1
, где u j 
и
 j 1

 u j  0
n
n
q
j 1

u j 
j 1
j

1

.
Так как   min H ( X * ,Y ) , где X* - максиминная стратегия, то приходим к
Y
следующей задаче линейного программирования.
n
Требуется найти максимум функции L   u j при выполнении условий
j 1

  aij u j  1 .
 j 1

 uj 0
n
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Если u *  (u1* , u 2* ,..., u n* ) - оптимальное решение данной задачи, то цена игры
1
 n

    u *j  ,
 j 1 
а
оптимальная
стратегия
Y *  ( q1* , q 2* ,..., q n* ) ,
где
q*j  u *j
и
n
q *j  u *j ( u *j ) 1 .
j 1
Аналогично, если игрок 1 применит оптимальную стратегию X, а игрок 2 стратегию
n
j, то средний выигрыш игрока l H ( X , j )   aij pi   .
i 1
Так как  > о, то, разделив обе части неравенств на  получим:
m
  aij ti  1 , где t  pi .
i
i 1

 ti  0
n
m
Так как   max H ( X , Y ) , где Y* - минимаксная стратегия, и  ti 
X
*
i 1
 pi
i 1


1

, то
приходим к задаче линейного программирования, являющейся двойственной по
отношению к полученной ранее.
m
a t 1
Требуется найти минимум функции L1   t i при выполнении условий i 1 ij i
.
i 1
 ti  0
m
Если
t *  (t1* , t 2* ,..., t m* ) - оптимальное решение данной задачи, то цена игры
1
 m 
    ti*  , а оптимальная стратегия
 i 1 
X *  ( p1* , p*2 ,..., p*m ) , где p*i  ti v и
n
pi  t i* (  t i* ) 1
i 1
По основной теореме теории матричных игр обе задачи имеют решение, а согласно
основной теореме двойственности Lm ax  L1m in .
Для нахождения оптимальных решений можно использовать симплекс-метод. При
этом, так как на каждом шаге симплексные таблицы определяют двойственные задачи,
а базисным переменным в исходной задаче соответствуют свободные в двойственной и
наоборот, то оптимальные решения этих задач могут быть получены из одних и тех же
симплексных таблиц.
Пример 6.4. Найти решение задачи примера 6.1 симплекс- методом.
10 - 4 
 .Так как нам уже известно, что
В примере 5.1.1 игра была задана матрицей 
 - 5 20 
цена игры  > о, то приходим к паре взаимно двойственных задач:
L1  t1  t 2 (min)
L  u1  u 2 (max)
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
10u1  4u 2  1
10t1  5t 2  1


и
 5u1  20u 2  1
 4t1  20t 2  1
u  0, u  0
t  0, t  0
2
2
 1
1
Сведем задачу к основной задаче линейного программирования:
L  u1  u 2  0
10u1  4u 2  u3  1

 5u1  20u 2  u 4  1
u  0, u  0, u  0, u  0
2
3
4
 1
Для опорного плана (0, 0, 1, 1) L = о. Составим симплексные таблицы.
Б
u
СВ
1
u
1
3
u
1
4
u
2
1
0
3
4
5
u
2
0
u
4
1
0
0
1
0
0
1
1
Выберем разрешающий столбец. Возьмем, например, u1, хотя можно было бы
выбрать u2, так как в них коэффициенты линейной формы отрицательны и равны -1.
Выбираем разрешающую строку по наименьшему отношению свободного члена к
положительному элементу разрешающего столбца. Это - первая строка.
Составим новую таблицу, в которой первая строка получена делением
соответствующей строки на разрешающий элемент 10; вторая есть результат сложения
первой строки новой таблицы, умноженной на 5, с соответствующей строкой
предыдущей таблицы, а последняя представляет собой сумму первой строки новой
таблицы с последней строкой старой.
L
0
Б
u1
u4
L
СВ
0,1
1,5
0,1
u1
u2
1 -0,4
0 18
0 -1,4
u3
0,1
0,5
0,1
u4
0
1
0
В этой таблице разрешающий столбец u2, разрешающая строка - вторая. Поделим ее
на разрешающий элемент 18 и запишем ее в соответствующей строке следующей
таблицы. Далее преобразуем таблицу так, чтобы все остальные элементы столбца u2
обратились в нуль. Для этого полученную строку новой таблицы умножим на 0,4 и
сложим с первой, затем умножим на 1,4 и сложим с последней строкой предыдущей
таблицы. В результате преобразований получаем таблицу:
Б
u1
u2
СВ
24
180
15
180
u1
u2
1
0
0
1
26
u3
u4
1
9
5
180
1
45
1
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
L
39
180
0
0
25
180
14
180
Теперь все коэффициенты линейной формы неотрицательны, и, следовательно,
преобразования закончены, так как в двойственных задачах свободные члены в
неравенствах и коэффициенты в линейной форме меняются местами, а базисные
переменные в двойственной задаче соответствуют свободным в исходной и наоборот,
то получаем, что
39
 24 15  *  25 14 
, u*  
Lmax 
,
,
, t 
.
180
 180 180 
 180 180 
Следовательно, цена игры   180 / 39  4,7 .
24 180 24 * 15 180 15
 25 14 
 24 15 
; q2 
; X *   , , Y*  ,  .
q1* 


180 39 39
180 39 39
 39 39 
 39 39 
Получили такое же решение, как и в примере 6.1.
Г). Метод Брауна (Метод фиктивного разыгрывания)
Этот метод представляет собой модель практического взаимного обучения игроков,
при котором каждый из них, анализируя поведение противника при предыдущих
разыгрываниях, старается ответить наилучшим образом. Например, игрок 1 выбирает
максиминную стратегию, а игрок 2 отвечает стратегией, которая максимизирует его
выигрыш (минимизирует выигрыш игрока 1), затем игрок 1 выбирает стратегию,
которая максимизирует его выигрыш (проигрыш игрока 2). Далее игрок 2 выбирает
стратегию, минимизирующую суммарный выигрыш игрока 1 за предыдущие два
разыгрывания, затем игрок 1 выбирает стратегию, максимизирующую его выигрыш за
предыдущие два разыгрывания и т. д. Далее каждый игрок отвечает на очередной ход
той своей стратегией, которая даёт ему наибольший выигрыш относительно
предыдущих ходов противника.
Вычисления по методу Брауна располагают в таблице, в верхнем левом углу
которой находится матрица игры. В строках, расположенных ниже платёжной
матрицы, содержатся возможные суммарные проигрыши игрока 2 за предыдущие
разыгрывания. В столбцах справа от матрицы находятся сложенные за предыдущие
разыгрывания возможные суммарные выигрыши игрока 1. Стратегии игроков,
выбираемые на каждом шаге, помечают звёздочкой.
После к разыгрываний (итераций) игрок 1 допускает, что его противник
s 
s s
придерживается смешанной стратегии Ук=  1 , 2 ,..., n  , где s j (j=1, 2…n) –
k 
k k
количество звёздочек в каждом столбце, расположенном ниже матрицы. Ан алогично,
после к разыгрываний (итераций) игрок 2
допускает, что его противник
t 
t t
придерживается смешанной стратегии Хк=  1 , 2 ,..., m  , где t i (i=1, 2…m) –
k 
k k
количество звёздочек в каждой строке, расположенной правее матрицы. Выи грыш
после к итераций находят по формуле vк=XкAУкт, где А – матрица игры, Укт- вектор Ук ,
записанный в виде столбца.
27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример 6.4. Найти методом Брауна приближённое решение игры, заданной
 2 7


матрицей  3 5  после 10 итераций.
11 2 


Решение. Вычисления поместим в таблицу (см. табл.6.1). По количеству звёздочек в
достроенных строках и столбцах соответственно находим:
Х10 = ( 0,5; 0; 0,5);
У10 = (0,4; 0,6).
 2 7
 2 7

  0,4 

  2
Т
v10 =X10 AУ10 =(0,5;0;0,5)  7 5    =0,5·0,2 (1;0;1)  3 5    =
11 2   0,6 
11 2   3 




 2
=0,1 (13;9)   =0,1(26+27)=5,3.
 3
Примечание:
крайний левый столбик в таблице служит для определения
максиминной стратегии.
Таблица 6.1
2
3*
2
2
3
11
3*
14
25
27
29
31
33*
35*
46*
57
7
5
2
5
7*
9*
16*
23*
30*
37
44
46
48*
2
3
11*
1
2
3
4
5
6
7
8
9
10
9
8
13*
2
16*
13
15
3
23*
18
17
4
30*
23
19
5
37*
28
21
6
39*
31
32
7
41
34
43*
8
43
37
54*
8
50
42
56*
10
Вопросы для самоконтроля
1. Как найти решение игры формата 2  2?
2. Как найти решение матричной игры графоаналитическим методом?
3. К какой паре взаимно двойственных задач линейного программирования
сводится задача нахождения матричной игры?
4. Как по симплексной таблице найти решение двойственной задачи?
5. В чём состоит идея метода Брауна приближённого решения матричных игр?
Задачи и упражнения для самостоятельного решения
6.1. Предприниматель может выставить на рынок два вида товаров. Найти решение
матричной игры, если его доходы в тыс. руб. в зависимости от спроса определяются
следующей таблицей:
Предложение
Спрос
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1
2
0
1
2
2
0
4
6.2. (Планирование выпуска сельхозпродукции). Фермер может произвести 2 вида
продукции. Если произведённая им продукция будет пользоваться спросом, то он
получит прибыль от её реализации соответственно 15 и 25 тыс. руб. Если же продукция
не будет пользоваться спросом, то он потерпит убытки (порча, хранение и т.д.) в
размере соответственно 3 и 5 тыс. руб. При неизвестном потребительский спросе
требуется определить, какой тип продукции следует производить с целью
максимизации среднеожидаемой гарантированной прибыли. Истолковать решение как
физическую смесь стратегий.
6.3. (Выбор момента поставки товара на рынок). Фирма А поставляет на рынок
клубнику в течение четырёх недель. Другая фирма В, производящая аналогичный
товар, пытается её разорить. Цена товара фиксирована. Чем позже поставляется товар
на рынок, тем выше его качество, а реализуется только товар более высокого качества.
Если же на рынок одновременно поступают оба товара, то они имеют одинаковый
спрос. Построить матрицу игры. Найти и истолковать решение игры, уменьшив её
формат, используя принцип доминирования, если доход от реализации товара за одну
неделю равен 4 тыс. рублей. Решить эту же задачу, при условии, что поставки велись в
течение трёх недель.
6.4. Найдите решение матричной игры упражнения 3.4.
6.5. На урожайность сахарной свёклы влияют природно-экономические условия: У1 ,
У2 , У3 , У4 . Сельскохозяйственное предприятие может применить агротехнические
мероприятия Х1 , Х2 , Х3 , Х4 . В таблице представлена зависимость урожайности свёклы
(в тоннах) от природно-экономических условий:
У1
31
32
30
38
Х1
Х2
Х3
Х4
У2
33
31
34
31
У3
34
35
36
37
У4
35
38
41
40
Построить модель матричной игры. Следуя принципу доминирования, уменьшить
формат игры, а затем найти её решение, используя графоаналитический метод.
6.6. Фермер может засеять поле культурами К 1 и К2 . Его доход (в тыс. руб.) в
зависимости от сочетания погодных условий задан в таблице:
Культуры
Погодные условия
2
4
3
1
6
1
К1
К2
3
2
7
Найти решение игры графоаналитическим методом и истолковать полученное
решение как физическую смесь стратегий.
6.7. Фирмы А и В могут вложить свой капитал в производство товаров различных
видов. Прибыль фирмы А, зависящая от сочетания типов произведённых товаров,
представлена в таблице:
1
1
3
2
2
29
3
4
4
0
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2
3
4
3
4
0
4
2
4
2
4
0
4
2
8
Считая, что цель фирмы А состоит в максимизации своей прибыли, а – фирмы В - в
разорении конкурирующей фирмы А, найти оптимальные смешанные игроков и цену
игры, используя принцип доминирования.
6.8. Состояние рынка ценных бумаг определяется многими факторами, которые
сгруппированы в 3 состояния. Инвестор предполагает вложить свой капитал в три вида
ценных бумаг. Его доходы в зависимости от состояния рынка при вложении в один вид
акций в тыс. условных единиц определяются таблицей
Виды
Акций
1
2
3
Состояния рынка
2
-1
-1
2
1
1
-1
-2
3
-1
3
-1
Дать рекомендации инвестору, в каком соотношении ему следует распределить
капитал с целью максимизации средне ожидаемой прибыли.
6.9. Сельскохозяйственное предприятие может посеять одну их трёх культур. При
отсутствии прогноза погоды требуется установить, какую из культур сеять, чтобы
максимизировать средне ожидаемый доход, если доходы (в тыс. руб.) в зависимости от
погоды заданы в таблице:
Культуры
1
2
3
Сухое
4
3
0
Лето
Нормальное
1
5
6
Дождливое
3
2
8
Используя методы линейного программирования, найти решение игры и
истолковать его как физическую смесь стратегий.
6.10. (Выбор ассортимента). На базе торговой организации имеется 3 типа товаров.
Прибыль от реализации каждого из видов товаров равна 20 тыс. рублей. Если же товар
не будет пользоваться спросом, то убытки от его хранения и порчи принесут убытки
соответственно 10, 5 и 3 тыс. рублей. Построить матрицу игры, найти её решение и
истолковать его как физическую смесь стратегий.
6.11. (Профилактический осмотр технической системы). Техническая система
состоит из трёх блоков, отказ каждого из которых ведёт к отказу всей системы. Для
предупреждения простоя системы можно провести перед началом её работы проверку и
замену элемента одного из блоков в случае его неисправности. Отказ блоков приводит
к убытку соответственно 10, 12 и 15 тыс. рублей, что существенно превышает расходы
на их профилактику. Требуется выбрать блок для профилактического осмотра с целью
минимизации средне ожидаемого убытка.
6.12. Найти методом Брауна приближённое решение игры, заданной матрицей
 1 2 3


 4 0 1  после а) 10 итераций; b) 15 итераций.
 2 3 0


30
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
6.13. Выполнить задание задачи 6.12 для матричной игры, заданной матрицей
 2 0 9 6


1 3 6 0 .
 4 2 1 3


7. ИГРЫ С ПРИРОДОЙ
Если один из игроков, как правило, игрок 2, является стихийной силой (например,
покупательский спрос, уровни температур или влажности окружающей среды и т.д.), то
такие игры называют играми с природой или средой.
Если принять гипотезу антагонизма, которая состоит в предположении, что среда
ведёт себя наихудшим образом по отношению к принимающему решение, то в случае,
когда игроки имеют конечное число стратегий, к таким играм можно применить
методы матричных игр, так как такую игру можно задать матрицей выигрышей А=(аij)
игрока 1. Однако возможны и другие гипотезы о поведении среды.
Если игрок знает только, какие могут быть состояния среды, то принятие решения
происходит в условиях неопределённости. Если же игрок имеет дополнительную
информацию о поведении среды, например, известен прогноз погоды или вероятности
наступления тех или иных её состояний, то в этом случае говорят о принятии решения
в условиях риска.
Для игр с природой в условиях неопределённости наиболее часто используют
следующие критерии оптимальности.
Для игр с природой в условиях неопределённости используют следующие критерии.
Критерий Вальда основан на гипотезе крайнего пессимизма игрока по отношению к
поведению среды, а именно: предполагается, что среда ведёт себя наихудшим образом
по отношению к принимающему решение.
Оптимальной по данному критерию стратегией является максиминная стратегия.
Критерий Гурвица связан с введением так называемого коэффициента пессимизма
α ( 0    1). Гипотеза о поведении среды состоит в том, что наихудший вариант
реализуется с вероятностью α, а наилучший с вероятностью 1-α.
Оптимальной по этому критерию считается та стратегия, для которой величина
m i naij  (1   )m a xa ij является наибольшей.
j
j
Критерий Лапласа основан на гипотезе равной вероятности состояний среды.
1 n
Оптимальной по этому критерию является та стратегия, для которой величина  a ij
n j 1
будет наибольшей.
Критерий Сэвиджа основан на преобразовании матрицы выигрышей (a ij ) в так
называемую матрицу сожалений ( r ij ) , где rij  m a xa ij  aij .
i
Оптимальной по данному критерию считается минимаксная стратегия для матрицы
сожалений.
Пример 7.1. В таб. 7.1 указаны доходы с 1га, полученные фермером при
производстве зерновых, подсолнечника и корнеплодов в зависимости от уровней
температур в летний период. Рассматривая данную ситуацию как игру фермера с
природой,
найти его оптимальные стратегии по критериям Вальда, Гурвица
(коэффициент пессимизма = 0,2 и =0,5), Сэвиджа и Лапласа.
31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Таблица 7.1.
Доход с 1 га, руб.
Уровни температур
Прохладный
Нормальный
Зерновые
227,03
1035,41
Теплый
164,10
Подсолнечник
695,94
473,97
207,56
Корнеплоды
1531,48
1052,29
-227,19
Решение. Для нахождения оптимальной стратегии по критерию Вальда используем
правило нахождения максиминной стратегии.
Таблица 7.2.
Доход с 1
га, руб.
Уровни температур
Прохлад Нормаль
-ный
-ный
Max
Min
Кр. Гурвица
α=0,2
α=0,5
Кр.
Лаплас
а
Зерновые
227,03
1035,41
Теплы
й
164,10
Подсолнеч
ник
Корнеплод
ы
695,94
473,97
207,56
207,56
695,94
598,27
451,76
459,16
1531,48
1052,29
-227,19
-227,19
1521,83
1179,75
652,15
785,53
Кр.
Сэвиджа
Зерновые
Подсолнеч
ник
Корнеплод
ы
164,10
1035,41
861,15
599,76
492,18
Матрица сожалений
Мax
1254,4
5
835,54
16,87
43,46
578,32
0
1254,4
5
835,54
0
0
434,75
434,75
Для нахождения оптимальных стратегий по критерию Гурвица составляем столбец
из максимальных элементов строк, а затем, находим те стратегии, для которых
величина m i naij  (1   )m a xa ij является наибольшей.
j
j
По критерию Лапласа для оптимальных стратегий находим среди средних
арифметических элементов строк платёжной матрицы наибольшее.
Для нахождения оптимальных стратегий по критерию Сэвиджа строим матрицу
сожалений, а затем применяем к её строкам правило нахождения минимаксной
стратегии. Решение данной задачи удобно расположить в таблице (см. таб.7.2).
Клетки, соответствующие оптимальным стратегиям по каждому критерию,
заштрихованы. Таким образом, оптимальная по критерию Вальда стратегия 2, выигрыш
207,56; оптимальная по критерию Гурвица (= 0,2) стратегия 3, выигрыш 1179,75;
(=0,5) стратегия 3 выигрыш 652,15; оптимальная по критерию Лапласа стратегия 3,
выигрыш 785,53; оптимальная по критерию Сэвиджа стратегия 3, риск 434,75.
Критерий Байеса применяется для игр с природой в условиях риска.
32
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Гипотеза о поведении среды: так как известны вероятности или отн осительные
частоты qj (j=1,2,…,n) наступлений соответствующих состояний среды, то игрок 2
применяет смешанную стратегию Y  (q1, q2 ,..., qn ) .
Оптимальной считается та стратегия i игрока 1, для которой его средне ожидаемый
n
выигрыш Н(i,Y)=  aij q j максимален.
j 1
Пример 7.2. (О выборе количества товара). Директор магазина «Молоко» должен
решить, сколько бидонов сметаны следует закупить у производителя для торговли в
течение недели, если известно, что спрос на неё за этот период будет 7, 8, 9, или 10
бидонов, а также, что 9 и 7 бидонов реализуются в 2 раза, а 8 – в 5 раз чаще, чем 10
бидонов. Покупка 1 бидона сметаны обходится магазину в 1000 рублей, а продаётся по
цене 1600 рублей за бидон. Если сметана не продаётся в течение недели, она портится,
и магазин несёт убытки. Сколько бидонов сметаны следует приобрести для продажи,
чтобы получить максимально возможную прибыль?
Решение.
Составим модель игры: I={1, 2}, где игрок 1 – директор, игрок 2- спрос (среда)
S1 ={7,8,9,10}, стратегии- закупить 7,8,9 или 10 бидонов. S2 ={7,8, 9,10}, предъявить
спрос на 7, 8, 9, 10 бидонов сметаны. Составим матрицу выигрышей игрока 1, которую
запишем в таблицу:
1
7
8
9
10
Кр. Байеса
7
8
9
10
qj
4200
3200
2200
1200
0,2
4200
4800
3800
2800
0,5
4200
4800
5400
4400
0,2
4200
4800
5400
6000
0,1
4200*
4000
3960
3120
2
(7,7), (7,8), (7,9), (7,10) : (1600-1000)  7  4200 ;
(8,7): (1600-1000)  7  1000  3200 ;
(8,8), (8,9), (8,10): (1600-1000)  8  4800 .
(9,7): (1600-1000)  7  2 1000  2200 ;
(9,8): (1600-1000)  8  1000  3800 ;
(9,9), (9,10): (1600-1000)  9  5400 ;
(10,7): (1600-1000)  7  3000  1200 ;
(10,8): (1600-1000)  8  2000  2800 ;
(10,9): (1600-1000)  9  1000  4400 ;
(10,10): (1600-1000) 10  6000 ;
Найдём относительные частоты применения чистых стратегий:
7 2х
0,2
8 5х
0,5
9 2х
0,2
10 -х
0,1
Так как 10х=1, то х=0,1
Оценим стратегии по критерию Байеса:
1: 4200  (0,2  0,5  0,2  0,1)  4200
2: 3200  0,2  4200  (0,5  0,2  0,1)  4000
33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3: 2200  0,2  3800  0,5  5400(0,2  0,1)  3960
4: 1200  0,2  2800  0,5  4400  0,2  6000  0,1  3120
Оптимальная стратегия – закупить 7 бидонов. Средне ожидаемый выигрыш – 4200.
Вопросы для самоконтроля
1.Что понимают под игрой с природой?
2. Как может быть задана игра с природой?
3. Когда находят решение игры с природой в условиях неопределённости и в
условиях риска?
4. На какой гипотезе о поведении среды основан критерий Вальда для игр с
природой? Какие стратегии игрока являются наилучшими по этому критерию?
5. На какой гипотезе о поведении среды основан критерий оптимальности Гурвица
для игр с природой? Что такое коэффициент пессимизма? Какие стратегии игрока
являются наилучшими по этому критерию?
6. Что такое матрица рисков? Какие стратегии игрока в игре с природой являются
наилучшими по критерию Сэвиджа?
7. На какой гипотезе о поведении среды основан критерий оптимальности Лапласа
для игр с природой? Какие стратегии игрока являются наилучшими по этому
критерию?
8. На какой гипотезе о поведении среды основан критерий оптимальности Байеса
для игр с природой в условиях риска? Какие стратегии игрока являются наилучшими
по этому критерию?
Задачи и упражнения для самостоятельного решения
7.1 (О выборе стратегии вложений). Бизнесмен имеет возможность вложить свои
деньги либо в государственные ценные бумаги, либо в акции высокодоходного
предприятия. Его доходы в зависимости от состояния экономики представлены в
таблице.
Объект
Вложения
Состояния экономики
Кризис
Стабильное
состояние
Государствен
ные ценные
бумаги
0
Акции
-5
3
5
Подъём
5
13
Рассматривая данную ситуацию как игру бизнесмена со средой, оц енить его
стратегии по критериям Вальда, Гурвица (α=0,2 и α=0,5), Лапласа и Сэвиджа.
7.2. Бригада рабочих должна к следующей весне построить электростанцию. В связи
с надвигающейся зимой возникла проблема угольных запасов для отопления домов.
Если зима будет нормальной, то потребуется 15 т угля, для суровой 18 т, а для мягкой –
12 т. Весной бригада переезжает на новый объект строительства, и излишки угля будут
потеряны. В зависимости от того, какая будет зима – мягкая, нормальная или суровая,
34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
стоимость тонны угля соответственно составляет 10, 12, 14 денежных единиц за 1т. В
настоящий момент можно приобрести уголь по 10 денежных единиц за тонну, а
остальное закупить потом. Считая доходом бригады деньги, сэкономленные от покупки
угля в данный момент, составить матрицу игры с природой и оценить стратегии
бригады рабочих по критериям Вальда, Гурвица (полагая коэффициент пессимизма =
0,4 и =0,8), Сэвиджа и Лапласа.
7.3. (Выбор проекта электростанции). Энергетическая компания должна выбрать
проект электростанции. Всего имеется 4 типа электростанций: тепловые,
приплотинные, бесшлюзовые и шлюзовые. Возможности их эксплуатации зависят от
ряда неопределённых факторов, связанных с погодой, возможностями наводнения,
ценами на топливо и т.д. В целом выделено 4 состояния среды. Экономическая
эффективность электростанции, определяемая как процент прироста дохода в течение
одного года эксплуатации по сравнению с затратами в зависимости от состояний среды
представлена в таблице
Типы
Состояния среды
Электростанций
1
2
3
4
Тепловая
7
5
1
10
Приплотинная
5
2
8
4
Бесшлюзовая
1
3
4
12
Шлюзовая
8
5
1
10
Оценить стратегии энергетической компании в соответствии с критериями Вальда,
Лапласа и Сэвиджа.
7.4. На время предстоящей лыжной гонки синоптики предсказали 2 состояния
погоды С1 и С2 . Есть два вида мазей М1 и М2 , пригодных для одного и другого
состояния погоды, вероятности удачного прохождения трассы в случае использования
их при С 1 равны: 0,5 и 0,4, а при С 2 – 0,3 и 0,8. Дать рекомендации лыжнику
относительно выбора мази..
7.5. В таблице указаны доходы с 1га, полученные фермером при производстве
зерновых, подсолнечника и корнеплодов в зависимости от уровней осадков в летний
период. Рассматривая данную ситуацию как игру фермера с природой, найти его
оптимальные стратегии по критериям Вальда, Гурвица (полагая коэффициент
пессимизма = 0,5 и =0,3), Сэвиджа, Лапласа, а также Байеса, используя данные
многолетних наблюдений, по которым влажный уровень наблюдается с вероятностью
0,25, а остальные с вероятностью 0,375.
Доход с 1 га, руб.
Зерновые
Уровни влажности
Влажный
6031,83
Средний
825,33
Сухой
2,72
Подсолнечник
740,22
718,04
-81,22
Корнеплоды
1082,46
308,43
-259,77
7.6. Фирма может выставить на продажу 2 вида товаров, спрос на которые зависит
от сочетания различных факторов (температура воздуха, дождливая погода, цены на
другие товары и т.д.). Всего выделено 3 таких состояния. Известно, что первое
состояние наступает в 3 раза чаще, а второе – в 4 раза чаще, чем третье. Оценить по
критерию Байеса стратегии фирмы (выбор варианта продаваемого товара), если её
доходы в зависимости от спроса в тыс. руб. заданы в таблице
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Виды
Товара
1
2
Спрос
1
8
18
2
18
15
3
40
14
7.7. Затраты швейной фабрики в течение апреля – мая на единицу продукции
составляют 8 ден. ед. на платье и 27 ден. ед. на костюм. Цена реализации
соответственно равна 16 и 48 ден. ед. Маркетинговые исследования показали, что в
течение этих месяцев фабрика может реализовать в условиях тёплой погоды 600
костюмов и 1975 платьев, а при прохладной погоде – 625 платьев и 1000 костюмов.
Составить план производства платьев и костюмов с целью максимизации средне
ожидаемой величины прибыли.
7.8. Швейная фабрика выпускает детские брюки и костюмы, себестоимость которых
составляет соответственно 10 и 25 ден. ед. Реализация будет происходить в мае по 20
ден. ед. за брюки и по 45 ден. ед. за костюм. Специалисты по изучению спроса сделали
прогноз, что в случае прохладной погоды можно продать 500 брюк и 1200 костюмов, в
случае тёплой – 600 костюмов и 2000 брюк. Обычно товар, не реализованный в течение
месяца, долго лежит на складах и не приносит дохода. Составить план производства с
целью максимизации средне ожидаемого дохода.
7.9. Предприниматель продаёт зонтики и тёмные очки на стадионе. Его доход во
многом зависит от погоды. По опыту он знает, что может продавать около 500 зонтов
во время дождя и 100 зонтов в хорошую погоду. В последнем случае он может также
рассчитывать на продажу 1000 тёмных очков. Зонты он покупает по 50 рублей, а
продаёт по 100 рублей. Очки стоят ему 20 рублей, а продаёт их по 50 рублей. Всё, что
не продано, является чистым убытком. Сколько предпринимателю выгоднее всего
купить зонтов и очков?
7.10.
Генеральный директор компании «Российский сыр», поставляющей
сырную пасту в страны ближнего зарубежья, должен решить, сколько ящиков этого
продукта следует производить в течение месяца. Вероятности того, что спрос на
сырную пасту за этот период будет 6, 7, 8, или 9 ящиков соответственно равны 0,1; 0,3;
0,5; 0,1. Затраты на производство одного ящика равны 45 у.е. Компания продаёт
каждый ящик по 95 у.е. Сколько ящиков сырной пасты следует производить, чтобы
получить максимальную средне ожидаемую прибыль, учитывая, что продукт не
реализованный в течение месяца портится, и компания не получает при этом дохода?
7.11.
Спрос на некоторый товар, производимый монополистом, определяется
зависимостью Q=100 – 5р + 5j, где р – цена товара, а j – достоверно неизвестный
уровень дохода потребителей, который может быть равен двум денежным единицам с
вероятностью 0,6 и четырём – с вероятность 0,4. Полные затраты на производство
товара определяются зависимостью 5 + 4Q+ Q2 . Сколько товара должен выпускать
монополист и по какой цене его продавать, чтобы максимизировать свою средне
ожидаемую прибыль?
8. БИМАТРИЧНЫЕ ИГРЫ
Определение 8.1. Конечная бескоалиционная игра двух игроков называется
биматричной игрой.
Замечание 8.1. Биматричная игра может быть задана системой <S1 , S2 , H1 , H2 >,
где S1 и S2 - множества стратегий игроков, H1 и H2 – функции их выигрышей, а также
парой матриц размерности m  n А=(аij) и В=(bij), где аij=Н1 (i,j), bij= Н2 (i,j), m и n-
36
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
соответственно число стратегий игроков 1 и 2 или одной матрицей, элементы которой
представляют собой пары (аij, bij), при этом их компоненты имеют уже описанный
смысл.
Замечание 8.2. Матричная игра является частным случаем биматричной игры,
когда В= -А, то есть биматричную игру можно рассматривать как обобщение
матричной с отказом от антагонистичности. Представляет интерес рассмотрение
биматричных игр, которые не являются матричными.
Определение 8.2. Для биматричной игры ситуация (i0 , j 0 ) называется ситуацией
равновесия по Нэшу, если, для любых стратегий i и j соответственно игроков 1 и 2:
aij0  ai 0 j 0 ; bi 0  bi 0 j0 .
j
Замечание 8.2. Ситуация равновесия по Нэшу является устойчивой, так как ни
одному из игроков не выгодно одностороннее отклонение от неё.
Замечание 8.3. Если bij  aij , то игра является матричной, и из условия
 ai0  ai0 j0 или ai0  ai0 j0 следует, что aij  ai j  ai0 , то есть ситуация
0
0 0
j
j
j
равновесия по Нэшу в этом случае является седловой точкой матричной игры, и
понятие ситуации равновесия по Нэшу является обобщением понятия седловой точки
при переходе к более широкому классу биматричных игр.
Особенности ситуаций равновесия по Нэшу по сравнению с седловыми
точками:
1. В матричной игре доход игрока 1 в любой седловой точке равен цене игры, а
для биматричных это не всегда так.
2. В матричной игре всякая оптимальная стратегия одного игрока со всякой
оптимальной стратегией другого игрока образуют ситуацию равновесия, а для
биматричных это не всегда так.
3. В матричной игре оптимальная стратегия игрока гарантирует ему получение
выигрыша, равного цене игры, в биматричнвх это не всегда так.
Замечание 8.4. Ситуация равновесия по Нэшу существует не всегда, поскольку
даже седловапя точка в матричной игре, являющейся частным случаем биматричной
существует не всегда.
Определение 8.2. Решением биматричной игры называется ситуация равновесия
по Нэшу, если она существует.
Пример 8.1. (Производство конкурирующей продукции).
Два небольших предприятия общественного питания производят однотипную
продукцию и затем продают её на одном рынке. Каждое предприятие
может
использовать большую или малую поточную линию. Если оба используют большую
линию, то получается перепроизводство продукции, и в результате оба предприятия
несут убытки в 9 тыс. рублей. Если одно использует большую линию, а другое малую,
то первое получает прибыль в 5 тыс. рублей, а второе только покрывает убытки.
Наконец, если оба предприятия используют малую линию, то оба получают
одинаковую прибыль в 1тыс. рублей. Требуется составить модель биматричной игры и
найти, если они есть, ситуации равновесия по Нэшу.
Решение. Этот конфликт моделируется биматричной игрой, в которой в качестве
игроков выступают предприятия 1 и 2, множества стратегий которых S1 =S2 ={1,2}, где 1
– использовать малую поточную линию, а 2 – большую. Тогда по условию Н1 (1,1)=1;
Н1 (1,2)=0; Н1 (2,1)=5; Н1 (2,2)=-9; Н2 (1,1)=1; Н2 (1,2)=5; Н2 (2,1)=0; Н2 (2,2)=-9. Эта игра
может быть задана парой матриц
37
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1 5 
1 0 
А= 
В= 

 ;
 0  9
5  9
или одной матрицей
(0,5) 
 (1,1)


 (5,0) (9,9) 
Непосредственной проверкой убеждаемся, что ситуациями равновесия по Нэшу
являются (1,2) и (2,1) с выигрышами соответственно (0, 5) и (5,0), так как ни одному
из игроков не является выгодным одностороннее отклонение, а для остальных
ситуаций это не так.
Если в биматричной игре отсутствует ситуация равновесия по Нэшу, то строят
смешанное расширение аналогично тому как это было сделано для матричных игр, в
котором уже всегда такая ситуация существует.
Смешанной стратегией игрока 1 называют всякий вектор
Х=(p 1 , p2 ,…, pm),
m
для которого pi  0;  pi  1 и m – число теперь называемых чистыми стратегий
i 1
игрока 1.
Аналогично, смешанная стратегия игрока 2 – это вектор
Х=(q1 , q2 ,…, qп ),
n
для которого qi  0;  qi  1 и п – число чистых стратегий игрока 2.
j 1
Замечание 8.5. Компоненты смешанных стратегий с содержательной точки зрения
есть:
1) вероятности, с которыми игрок принимает соответствующую чистую
стратегию;
2) относительные частоты с которыми игрок принимает чистые стратегии;
3) когда это возможно, компоненты смешанных стратегий можно рассматривать как
доли, в которых следует смешать соответствующие чистые стратегии.
Определение 8.3. Смешанным расширением биматричной игры, заданной
матрицами А=(аij) и В=(bij ) размерности m  n называется бескоалиционная игра <Sт ,
Sп , H1 , H2 >, где Sт и Sп - множества смешенных стратегий игроков 1 и 2 и
m n
m n
i 1 j 1
i 1 j 1
H1 ( X , Y )    aij pi q j и H 2 ( X , Y )    bij pi q j .
Определение 8.4. Ситуация ( X 0 , Yo ) называется ситуацией равновесия по Нэшу в
смешанном расширении, если для любых смешанных стратегий Х и У выполняются
условия H1 ( X , Yo )  H1 ( X 0 , Yo ) и H 2 ( X 0 , Y )  H 2 ( X 0 , Yo ) .
Теорема Нэша. Всякая биматричная игра имеет ситуацию равновесия по Нэшу в её
смешанном расширении.
Замечание 8.6. Теорема Нэша не даёт метода нахождения ситуации равновесия, но
даёт принципиальный ответ о её существовании.
Замечание 8.7. Доказано, что для биматричных игр формата 2  2 она может быть
найдена по тем же формулам, что и для матричных игр, но компоненты смешанной
стратегии игрока 1 находятся по матрице выигрышей игрока 2, а для игрока 2 по
матрице выигрышей игрока 1, при этом выигрыши игроков в ситуации равновесия (Х*,
У*) соответственно равны v1 =X*AУ*Т , v2 =X*ВУ*Т
Таким образом, игрок 2 минимизирует ожидаемый выигрыш игрока 1, а игрок 1
минимизирует ожидаемый выигрыш игрока 2, то есть, в биматричных играх
38
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
наблюдается «антагонизм поведения» игроков при отсутствии прямого «антагонизма
интересов».
Пример 8.2. Борьба фирм за рынки сбыта.
Фирма А намерена сбыть партию товара на одном из двух рынков, которые
контролируются более крупной фирмой В. С этой целью она проводит
подготовительную работу, связанную с некоторыми затратами. Если фирма В
разгадает, на каком из рынков фирма А будет продавать свой товар, она примет
контрмеры и воспрепятствует захвату рынка (этот вариант означает поражение фирмы
А), если нет, то фирма А одерживает победу. Для фирмы А проникновение на первый
рынок более выгодно, чем проникновение на второй, но и борьба за первый рынок
требует от неё больших средств, а именно: победа фирмы А на первом рынке
оценивается в 2 единицы, а на втором – в 1 единицу, а её поражение на первом рынке
оценивается в -10, а на втором – в -1. Для фирмы В её победа составляет
соответственно 5 и 1 единицу, а поражение -2 и -1.
Решение. Составим математическую модель конфликта.
I={А, В} , S1 = {1,2} - проникновение на рынок 1 или 2. S2 ={1,2} - контрмеры на
рынке 1 или 2.
Выигрыши игроков задаются матрицами:
  10 2 
 (10,5) (2,2) 
 5  2
А= 
В= 
 и
 .
 или 
 1  1
 (1,1) (1,1) 
 1 1 
Непосредственной проверкой убеждаемся, что в данной игре отсутствует ситуация
7
1  (1)
2
2 7
равновесия в чистых стратегиях. р*=
и Х*=  ,  . q*=
 и 1- р*=
5 11 2 9
9 9
9
11
1 2
3
 3 11 
и У*=  ,  .
 , 1- q*=
 10  1  2  1 14
14
 14 14 
При этом средне ожидаемый выигрыш игрока 1 равен v1 =Х*АУ*Т =
  10 2   3  1 1
  8
 2 7    10 2   314  1 1
 ·
   =  (2,7)   =
=  ,  · 
=  (2,7) 
 9 9   1  1 1114  9 14
 1  1 11 9 14
  8
8
4
= 
(2  7) =  ≈-0,57.
9 14
7
Для игрока 2:
 2   314  1 1
 7
 5  2  3  1 1
Т 2 7  5
 ·
   =  (2,7)   =
v2 =X*BУ* =  ,  · 
==  (2,7) 
 9 9    1 1  1114  9 14
 8 
  1 1  11 9 14
1 1
42 1
 (14  56) =
= ≈0,33.
9  14 3
9 14
Вопросы для самоконтроля
1.
2.
3.
4.
Какая игра называется биматричной?
Как можно задать биматричную игру?
Что называется ситуацией равновесия по Нэшу?
Что общего между седловой точкой для матричных игр и ситуацией
равновесия по Нэшу для биматричных?
39
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
5. Какие особенности имеют ситуации равновесия по Нэшу по сравн ению с
седловыми точками?
6. Как строится смешанное расширение биматричной игры?
7. Всегда ли существует ситуация равновесия в смешанном расширении?
8. Запишите формулы для нахождения ситуации равновесия в смешанном
расширении.
Задачи и упражнения для самостоятельного решения
8.1. (Вывоз продукции). Предприятие для отправки своей продукции потребителю
вывозит её на перевалочный пункт, где она грузится в машины, принадлежащие
транспортному управлению. Если не вся продукция может быть погружена, то её
остаток сдаётся на склад; в этом случае расходы на хранение продукции предприятие и
транспортное управление несут поровну. Предприятие может отправить продукции в
расчёте на 5 или 10 автомашин. Транспортное управление может направить на
перевозку продукции обычную автоколонну (4 автомашины) или большую
автоколонну (7 автомашин), две обычные автоколонны (8) или обычную и большую
(11). От отправки одной машины продукции предприятие имеет доход а рублей,
стоимость хранения на складе продукции, перевозимой одной автомашиной равна b
рублей, а затраты транспортного управления на посылку к перевалочному пункту
одной автомашины с рублей. Составить модель биматричной игры. Найти матрицы
выигрышей игроков при a=10; b=4; c=2.
8.2. Для игры примера 2.1 (спор партнёров) составить матрицы выигрышей игроков и
найти ситуации равновесия по Нэшу.
8.3. (Конкурс на реализацию проекта). Две фирмы участвуют в конкурсе на
реализацию разработки некоторого проекта, причём доход от реализации проекта
составляет 10 денежных единиц. Каждая фирма может либо подать простую заявку на
участие в конкурсе (затраты равны 1 денежной единице) либо представить программу
реализации проекта (затраты равны 3 денежным единицам). Условия конкурса таковы,
что в случае, когда обе фирмы выбирают одинаковый способ действия, заказ на
реализацию проекта, а также доход делится между ними пополам. Если же фирмы
выбирают различные способы действий, то предпочтение отдаётся той, которая
представила подробную программу. Построить модель игры и найти ситуации
равновесия по Нэшу.
8.4. (Распределение прибыли). Фирма А может выпускать изделия А 1 и А2 , а фирма
В – В1 и В2 , которые затем продаются на одном рынке. Прибыль этих фирм в
зависимости от того являются ли эти изделия взаимно дополнительными или
конкурирующими определяется таблицей:
В1
(1, 6)
(3,2)
А1
А2
В2
(5,1)
(2,3)
Найти ситуации равновесия в смешанных стратегиях. Дайте истолкование
полученного решения.
8.5. Два предприятия по обслуживанию населения предлагают жителям посёлка,
имеющего 1000 потенциальных клиентов, 4 вида услуг. Если первое предприятие
предлагает i-ю услугу, а второе j- ю, то доля клиентов, пользующихся услугой i равна
40
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
рij, а остальные клиенты выбирают услугу j. Выигрышем предприятия считается число
его клиентов. Составьте модель биматричной игры, если матрица (pij) имеет вид:
 0,6 0,5 0,6 0,5 


 0,4 0,5 0,5 0,6 
 0,1 0,6 0,2 0,7  .


 0,4 0,6 0,4 0,6 


Покажите, что полученная биматричная игра эквивалентна некоторой матричной
игре и найдите её решение в смешенных стратегиях, используя принцип
доминирования.
Убедившись, что следующие биматричные игры не имеют ситуаций равновесия в
чистых стратегиях, найдите их решение в смешанных стратегиях.
 (8,4) (3,3) 
 (9,5) (4,4) 
8.6. 
8.7. 
 ;
 .
 (2,2) (2,2) 
 (3,3) (3,3) 
8.8. Инвестор желает построить один из двух объектов на территории города.
Городская администрация может принять его предложение или отказать.
Строительство первого объекта требует больших затрат инвестора, и часть площадей
оно должно передать городу. При строительстве второго объекта возможно
использование имеющихся ресурсов города. Кроме того, производятся затраты на
составление проекта строительства инвестором и его оценку городской
администрацией. Требуется найти решение биматричной игры инвестора и городской
администрации, если их прибыли задаются матрицей выигрышей в млн. руб.
 (10,5) (2,2) 

 .
 (1,1) (1,1) 
9. КООПЕРАТИВНЫЕ ИГРЫ
В предыдущих лекциях мы в основном имели дело с антагонистическими
конфликтами, но в экономике и смежных с ней областях часто встречаются и
неантагонистические конфликты, при этом их участники могут действовать независимо
друг от друга (некооперативный вариант), либо объединять свои усилия путем
кооперирования (кооперативный вариант).
Возможность сотрудничества между игроками приводит к качественно новым
конфликтам по сравнению с рассмотренными ранее. В этой главе мы будем говорить о
наиболее простых из кооперативных игр.
Всякое подмножество К множества игроков I = 1,2,..., nбудем называть коалицией.
Мы будем рассматривать всевозможные коалиции, в том числе и пустую, то есть не
содержащую игроков, а также коалиции, состоящие из одного игрока i, которые мы
будем обозначать так же, как и игрока, то есть через i. Количество игроков в коалиции
К будем в дальнейшем обозначать K .
Известно, что число всех подмножеств множества, содержащего n элементов, равно
n
2 и, следовательно, n игроков могут образовать 2n различных коалиций.
Объединение игроков в коалицию К означает превращение их в единого игрока 1,
стратегиями которого являются всевозможные совместные действия игроков из К, а
41
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
выигрышем - сумма их выигрышей. В худшем для объединенного игрока 1 случае
игроки из I/K могут также объединиться в некоторого коллективного игрока 2 с
интересами,
диаметрально
противоположными:
В
результате
возникнет
антагонистическая игра. Теперь на множестве всех коалиций можно определить
функцию v, называемую характеристической функцией, которая приписывает каждой
коалиции К  I вещественное число - цену антагонистической игры двух лиц, которую
разыграли бы К и I\K, если бы эти две коалиции действительно возникли.
Можно доказать, что характеристическая функция обладает следующими
свойствами:
V(Ø)=0.
(1)
V(K1  K 2 )≥V(K1 )+V(K2 ), если К1  К2 = Ø.
(2)
Свойство (2) называют свойством супераддитивности. Оно содержательно
означает, что объединение игроков в коалиции является целесообразным с точки
зрения увеличения выигрыша. Из этого же свойства следует, что для любой коалиции
Ê V(K)  V (i )
iK
Определение 9.1. Классической кооперативной игрой n лиц называется система
<I,V>, где I= 1,2,...., n - множество игроков, а V - характеристическая функция,
определенная на множестве всех коалиций игроков, принимающая вещественные
значения и удовлетворяющая условиям (1) и (2).
Из сказанного ранее следует, что с содержательной точки зрения V(K) - это цена
антагонистической игры, разыгрываемой между К и I\K, то есть гарантированная при
любом поведении игроков прибыль коалиции К.
В дальнейшем классические кооперативные игры будем называть кооперативными
играми.
Определение 9.2. Вектор х = (x1 , x2 , …,xn ) где xi R, называется дележом
относительно характеристической функции v, если
1) xi  v(i) , для всех i I;
n
n
2)  xi  V ( I ) .
i 1
Условие 1) называется условием индивидуальной рациональности. Оно означает, что
каждому игроку действовать в коалиции не менее выгодно, чем одному.
Условие 2) называется условием коллективной рациональности. Оно означает, что
вся имеющаяся в распоряжении игроков сумма полностью распределяется между
игроками.
Исходом кооперативной игры является дележ, который возникает в результате
соглашений игроков, поэтому в кооперативных играх сравниваются не ситуации, а
дележи.
Цель игры может быть сформулирована по-разному. Однако всегда возникает
необходимость найти такой дележ х = (x1 , x2 , …,xn ), который должен характеризовать
наилучшие в каком-то смысле возможности игроков, описываемые характеристической
функцией.
Пример 9.1. (Рынок трех лиц)
Продавец обладает единицей неделимого товара (например, коровой), а два
покупателя хотят приобрести этот товар. Продавец оценивает этот товар в а рублей,
покупатели в b и с рублей соответственно. Это означает, что цена, по которой будет
продана корова, для продавца должна быть не меньшей а, а для покупателей не
42
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
большей b и с соответственно. Для того, чтобы все трое могли участвовать в сделке,
надо потребовать, чтобы a  b и а  с. Для определенности будем считать, что а ≤ b ≤
с. Требуется определить, какие результаты сделки, то есть прибыли участников,
достаточно хорошо соответствуют их возможностям, а также возможностям их
коалиций.
Мы имеем здесь пример кооперативной игры. Множество игроков I= 1,2,3 . Игрок 1
- продавец, игроки 2 и 3 -покупатели. Рассмотрим всевозможные коалиции игроков
Ê 0  Ø, Ê 1  1 , Ê 2  2, Ê 3  3, Ê 4  1,2, Ê 5  1,3 , Ê 6  2,3, Ê 7  1,2,3.
Прибыль коалиции считаем равной сумме прибылей ее участников. Оп ределим
функцию v, для которой V(K) - гарантированная при любом поведении участников
прибыль коалиции К. Ясно, что сама по себе сделка рассматривается как результат
соглашения продавца с одним из покупателей, то есть их коалиции. Следовательно,
V(K 0 )=V(K 1 )=V(K2 )=V(K3 ) =V(K6 )=0.
Вычислим V(K 4 ). Так как товар принадлежит коалиции, то он будет использован
наилучшим для нее образом, то есть продан игроку 2 за цену х, где а≤ х  b. При этом
покупатель получит прибыль (b-х), так как он рассчитывал на b рублей, а прибыль
продавца (х-а), так как он рассчитывал получить за нее а рублей. Тогда V(K4 )=b-х+ха=b-а. Аналогично находим, что V(K3 ) = с-а.
Коалиция К7 возможна, а смысл ее, например, в том, что игрок 3, приобретая товар,
платит часть своей выручки второму игроку за совместные действия, направленные на
понижение цены. Прибыль этой коалиции тоже равна с-а, то есть V(K7 ) = с-а.
Позже мы дадим рекомендации игрокам.
Пример 9.2 (Собрание акционеров)
На собрании акционерного общества, состоящего из n лиц (n >2) необходимо
решить голосованием некоторый вопрос. Если группа из k лиц в состоянии
воздействовать на решение вопроса, то есть отклонить или принять решение
независимо от желания остальных членов, то будем приписывать ей выигрыш, равный
1, а если нет, то 0. Требуется оценить "силу" каждого участника голосования при
решении вопроса, если он принимается простым большинством.
n
Это пример кооперативной игры. Для всякой коалиции К V(К)=1, если Ê  и
2
n
V ( K )  0 , если K  .
2
Так как здесь все участники равны, то, если общая «сила» равна 1, то каждому
участнику следует приписать «силу» 1/n.
Здесь мы имеем наиболее простую схему равноправного голосования, однако
вопрос об оценке "силы" участников неравноправных схем не так прост и сводится к
нахождению такого набора неотрицательных чисел х 1 ,х 2 ,...,х n , в сумме равных единице,
который бы в соответствии со значениями характеристической функции "достаточно
хорошо" учитывал бы возможности каждого отдельного участника в принятии
решения.
Пример 9.3 (Задача о бригаде рабочих)
Бригада из четырех рабочих должна выполнить совместно некоторую работу.
Известно, что эту же работу могли бы выполнить первый с любым из остальных
рабочих и все рабочие без первого. Считая, что общая плата за работу равна одной
денежной единице, требуется найти "справедливую долю" каждого из рабочих в общей
43
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
плате за работу, то есть требуется найти такие числа х1 , х2 , х3 , х4 ≥ 0, что х1 +х2 +х3
++х4 = 1, в которых были бы учтены все возможности членов бригады.
Здесь мы также имеем дело с кооперативной игрой. Множество игроков
I  1,2,3,4. Всевозможные коалиции: К 0 =Ø, К1 = 1 , К2 = 2 , К3 = 3, К4 = 4 , К5 = 1,2 ,
К6 = 1,3, К7 = 1,4 , К8 = 2,3, К9 = 2,4 , К10 = 3,4, К11 = 1,2,3 , К12 = 1,2,4 , К13 = 1,3,4 ,
К14 = 2,3,4, К15 = 1,2,3,4.
V(К0 )=V(К1 )=V(К2 )=V(К3 )=V(К4 )=V(К8 )=V(К9 )=V(К10 )=0,
V(К5 )=V(К6 )=V(К7 )=
=V(К11 )=V(К12 )=V(К13 )=V(К14 )=V(К15 )=1.
Теперь следует искать ответы на вопросы, поставленные в примерах.
Пусть <I,V> - кооперативная игра, х = (х 1 , х 2 ,..., х n ) и у= (y1 ,y2 ,…,yn )- два ее дележа.
Определение 9.3. Будем говорить, что дележ х доминирует дележ у по коалиции K
(обозначать х  у), если
K
1). xi  yi для всех i  K ;
2)  xi  V ( K ) .
iK
Первое условие отражает необходимость единогласия в предпочтении со стороны
коалиции. Второе условие означает осуществимость дележа х, так как выполнения
условия  xi V ( K ) остальные игроки могут не допустить.
iK
Обратим внимание, что доминирование невозможно по коалиции, состоящей из
одного игрока, так как из х  у следовало бы, что yi<x i ≤V(i), что противоречило бы
(i )
индивидуальной рациональности дележа у.
Невозможно также и доминирование по коалиции, состоящей из всех игроков.
Действительно, из х  у следовало бы, что xi > yi для всех i I и поэтому
I
n
n
i 1
i 1
 xi   yi  V ( I ) , что противоречит коллективной рациональности дележа х.
Доминирование х  у выражает некоторое предпочтение, отдаваемое дележу х по
K
сравнению с у коалицией К.
Определение 9.4. Будем говорить, что дележ х доминирует дележ у (обозначать х »
у), если существует такая коалиция K, для которой х  у.
K
Доминирование х » у означает, что в множестве игроков найдется такая коалиция,
которая будет выступать в пользу дележа х при его сравнении с у.
Для примера 9.3 дележи имеют вид: х=(х 1 , х 2 , х 3 , х 4 ), х 1 ≥0, х 2 ≥0, х 3 ≥0, х 4 ≥0,
х 1 +х 2 +х 3 +х 4 =1.
Рассмотрим три дележа х 1 =(5/8, 1/8, 1/8, 1/8), х2 =(1/2, 3/8, 0, 1/8) и х3 =(1/4, 1/4, 1/4,
1/4). Мы видим, что х1  х2 , где К6 = {1, 3}, так как 5/8 > 1/2, 1/8 > 0 и 5/8+1/8 ≤V(K6 ) =
K6
1. Аналогично, х  х , где К5 = {1, 2} и х3  х1 при К14 = {2, 3, 4}. Таким образом,
2
3
K14
K5
1
2
3
1
х »х »х »х . Это значит, что, все время, улучшая выбор, мы возвратились к прежнему
состоянию,
44
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Для примера 9.1 будем считать, что b-а = 2/3; с-а = 1. Рассмотрим дележи х 1 = (1/2,
0, 1/2), х 2 = (1/3, 1/3, 1/3), х 3 = (1/4, 0, 3/4). Здесь х 1  х 2 (К5 = {1,3}), x 2  х 3
K4
K5
1
3
(К4 ={1, 2}), х не доминирует х . Так как в этом примере любое улучшение связано с
увеличением первой компоненты дележа (доминирования по коалиции {2, 3} быть не
может ввиду невозможности выполнения условия 2) определения 9.3, то здесь
постепенное улучшение, возможно, приведет к дележу, который уже нельзя улучшить.
С каждой кооперативной игрой ассоциируется игра для которой V(i)=0 для всех i I
и V(I) = 1. Действительно, построим по функции V функцию V1 , которая для любой
коалиции определяется так:
V ( K )  V (i )
iK
V1 ( K ) 
V ( I )  V (i )
iI
Легко заметить, что кооперативная игра < I, V1 > удовлетворяет требуемым
условиям и можно доказать, что множества дележей для игр < I, V > и < I, V1 >
находятся во взаимно однозначном соответствии, сохраняющем отношение
доминирования. Следовательно, можно ограничиться рассмотрением таких игр.
Определение 9.5. Дележ, не имеющий доминирующих дележей, называется
максимальным дележом.
Если для кооперативной игры <I, V> существует максимальный дележ, то любой
коалиции будет невыгодно изменить этот дележ. Следовательно, максимальный дележ
можно считать в известном смысле вполне устойчивым.
Определение 9.6. Множество всех максимальных дележей называется ядром
кооперативной игры.
Теорема о ядре
Для кооперативной игры < I, V >, удовлетворяющей условиям
1) V(i)=0 для всех i I,
2) V(I) = 1.
ядро состоит из тех и только тех дележей х = (х 1 , х 2 ,...,х n ), для которых V(K)≤  xi ,
iK
для любой коалиции K  I.
Доказательство. Необходимость. Пусть для дележа х= (х 1 , х 2 ,...,х n ) для
некоторой коалиции К имеет место: V(K) >  xi . Тогда коалиция должна состоять
iK
больше чем из одного игрока, иначе это противоречило бы условию индивидуальной
рациональности дележа х. К ≠ I, так как в противном случае мы пришли бы к
нарушению условия коллективной рациональности.
 xi  ( V ( K )   X i ) / K

i K
Положим yi= 

( 1  V ( K )) /( I  K ),
если i  K,
y2 ,
…,yn )
–
дележ
игры
V ( K )   xi
n
iK  ( I  K ) 1  V ( K )  1
.
 yi   xi  K
K
I K
i 1
iK
y=(y1 ,
45
если i  K.
<I,V>,
так
как
yi≥0
и
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Так как уi> x i для всех i  К и  yi   xi  V ( K )   xi  V ( K ) , то у  х.
K
i 1
iK
iK
Следовательно, х не принадлежит ядру, и для всех дележей х из ядра выполнено
условие V ( K )   xi для любой коалиции К  I.
iK
Достаточность. Пусть выполнено условие V ( K )   xi для любой коалиции
iK
К  I, Если бы х не принадлежало ядру, то нашелся бы дележ у = (у1 , у2 ,...,уn ), для
которого у  х по некоторой коалиции К, но тогда по определению 2.1
K
 xi   yi ≤ V (K ) , то есть V ( K )  xi , что невозможно. Следовательно, х
iK
iK
iK
принадлежит ядру.
Замечания
1). Можно доказать, что любой кооперативной игре можно сопоставить такую игру,
для которой выполнены условия 1) и 2) теоремы о ядре. Следовательно, теорему модно
применить практически к любой кооперативной игре.
2). Так как компоненты дележей, образующих ядро, должны удовлетворять,
согласно теореме о ядре, конечной системе линейных неравенств, то это означает, что
ядро в любой кооперативной игре является выпуклым многогранником, возможно
пустым.
В примере 9. 3 дележи ядра по теореме о ядре должны удовлетворять условиям:
х 1 +х 2 +х 3 +х 4 =1,
(1)
х 1 +х 2
≥1,
(2)
х 1 +х 3
≥1,
(3)
х 2 +х 3 +х 4 ≥1,
(4)
х 1 ≥0, х 2 ≥0, х 3 ≥0, х 4 ≥0.
(5)
Но из условий (1), (4) и (5) следует, что х 1 = 0. Тогда из (2) и (3) следует, что х 2 ≥ 1 и
х 3 ≥ 1, чего быть не может. Следовательно, ядро этой игры пусто.
Для игры примера 9.1. дележи ядра по теоремео
ядре
должны
удовлетворять
условиям:
с-а= х 1 +х 2 +х 3 ,
(6)
в-а≤ х 1 +х 2 ,
(7)
с-а≤х 1 +х 3 ,
(8)
х 1 ≥0, х 2 ≥0, х 3 ≥0, х 4 ≥0.
(9)
Из условий (6), (8) и (9) имеем, что x 2 = 0. Тогда дележи ядра имеют вид: х = (х 1 , 0,
с-а-х 1 ), где b-a ≤ х 1 ≤с-а.
Такой дележ прибыли означает, что второй игрок не участвует в сделке, и корова
достанется третьему игроку за цену p = а+х 1 , при этом так как х 1 ≥ b - а, то р ≥ b, то есть
третий игрок платит первому не меньше, чем мог бы заплатить второй игрок.
Любой такой дележ устойчив в том смысле, что никакая группа игроков не может
ему реально противодействовать. Такое завершение торга не противоречит здравому
смыслу и указывается экономической теорией. Однако возможны и другие исходы
торга, не учтенные классической экономической теорией и связанные с возможностью
образования коалиций
Теперь мы займемся нахождением такого решения, которое, вообще говоря,
определяется некоторым третьим лицом - арбитром, формулирующим некоторые
"разумные" свойства, которыми должно обладать оптимальное решение. Реально это
46
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
могут быть, например, юридические и этические нормы, которые заставляют людей в
определенных ситуациях действовать единственным образом, несмотря на их
индивидуальные различия. Такой подход приводит к аксиоматическому заданию
принципа оптимальности. В данном параграфе мы рассмотрим один из таких
принципов, который иногда называют принципом справедливого дележа.
Мы укажем способ, который ставит в соответствие каждой кооперативной игре
<I, V> некоторый вектор, компоненты которого описывают справедливые в некотором
смысле выигрыш каждого из игроков в этой игре. Этот вектор называют в ектором
Шепли по имени американского математика Л. Шепли, предложившего его в 1953 году.
Определение 9.7. Вектор Ф(V) = (Ф1 (V), Ф2 (V),...,ФN (V)) называется вектором Шепли
для кооперативной игры < I, V >, если его компоненты удовлетворяют следующим
аксиомам:
1. Аксиома симметрии: при любой перенумерации игроков, для которой игрок i
имеет номер ki , вектор Ф'(V') для новой игры удовлетворяет условию Ф ki (V') = Фi(V).
2. Аксиома эффективности:  Ô i (V )  V ( N ) , где N - носительV, то есть такое
iN
множество N  I, что для любой коалиции К V(K  N) = V(K).
3. Аксиома агрегации: если <I, V> и <I, V′> - две игры, то для игры < I, V+V'>, для
которой (V+V')(К) = V(К)+V'(К), Ф(V+V')=Ф(V)+Ф(V').
Заметим, что носитель V - это множество "активных" игроков, так как добавление к
любой коалиции игроков, не принадлежащих множеству N, не дает прибавки к
выигрышу.
Рассмотрение в аксиоме агрегации игры <I, V+V'> можно истолковать как
одновременное участие игроков в двух играх, при этом выигрыши каждой коалиции
складываются.
Теорема о векторе Шепли
Для каждой кооперативной игры существует единственный вектор Шепли, который
является дележом и вычисляется по следующим формулам:
( K  1)!(n  K )!
(1)
V ( K )  V ( K \ i).
Ô i (V )  
n!
K  I ,iK
Доказательство теоремы из-за его сложности опустим.
Заметим, что разность [V(K)-V(К\i)] показывает, какую прибавку к выигрышу дает
коалиции К i-й игрок. Ф i(V) - "справедливая" доля i-го игрока по Шепли есть среднее
арифметическое этих прибавок.
Найдем вектор Шепли для примера 1.1. Так как V(Ki) = 0, если |K i| ≤ 1, то начинаем
подсчет с коалиций, содержащих 2 элемента:
(2  1)!(3  2)!
V ( K 4 )  V ( K 2 )  V ( K 5 )  V ( K 3 )  (3  1)!(3  3)! V ( K 7 )  V ( K 6 ) 
Ô1 (V ) 
3!
3!
 (â  a  c  a) / 6  (c  a) / 3  2a / 3  â / 6  ñ / 2 .
(2  1)!(3  2)!
V ( K 4 )  V ( K1 )  V ( K 6 )  V ( K 3 )  (3  1)!(3  3)! V ( K 7 )  V ( K 5 ) 
Ô 2 (V ) 
3!
3!
 (â  à) / 6  (ñ  à  ñ  à) / 3  à / 6  â / 6 .
Ô 3 (V ) 
(2  1)!(3  2)!
V ( K 5 )  V ( K1 )  V ( K 6 )  V ( K 2 )  (3  1)!(3  3)! V ( K 7 )  V ( K 4 ) 
3!
3!
 (c  a) / 6  (c  a  â  a) / 3  a / 6  â / 3  ñ / 2 .9.1:
47
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
(2  1)!(4  2)!
V ( K 5 )  V ( K 2 )  V ( K 6 )  V ( K 3 )  V ( K 7 )  V ( K 4 )  (3  1)!(4  3)!
4!
4!
V ( K11 )  V ( K8 )  V ( K12 )  V ( K 9 )  V ( K13 )  V ( K10 )  (4  1)!(4  4)!V ( K15 )  V ( K14 ) 
4!
1  1  1 (1  1  1) 1  1 1



 .
12
12
4
2
На основании условия эффективности и симметрии игроков 2, 3, 4 получаем, что
Ф2 (V)=Ф3 (V)=Ф4 (V)=(1-0,5)/3 = 1/6.
Пример 9.4. (Фермер и сезонные рабочие)
Фермер может привлечь для уборки урожая n-1 сезонного рабочего. При участии k
рабочих будет получен доход f(k) денежных единиц. Требуется найти "справедливую"
долю фермера и каждого рабочего в общем доходе.
Это положение дел приводит к следующей кооперативной игре <I, V>, где I
={1,2,…,n}, при этом игроки l, 2,...,n-1 -сезонные рабочие, n - фермер.
Характеристическая функция,
естественно, определяется так: V(K) =
 f ( K  1), åñëè n  K
, так как сезонные рабочие сами по себе дохода получить не

0, åñëè n  Ê

могут.
Для определения "справедливой" доли найдем вектор Шепли для этой игры.
Так как число коалиций, содержащих игрока n и состоящих из К элементов, равно
K 1
C n 1 , то по формуле (1) получаем:
0!(n  1)!
1!(n  2)! 1
2!(n  3)! 2
(n  1)!0! n1
Ô1 (V ) 
f (0) 
Cn1 f (1) 
Cn2 f (2)  ...
Cn1 f (n  1) 
n!
n!
n!
n!
Ô1 (V ) 
1
1!(n  2)!(n  1)!
2!(n  3)!(n  1)!
(n  1)!0!(n  1)!
f (0) 
f (1) 
f (2)  ... 
f (n  1) 
n
n!(n  2)!1!
n!2!(n  3)!
n!(n  1)!0!
1
1 n1
( f (0)  f (1)  ...  f (n  1))  ( f (k )) .
n
n k 1
На основании условий эффективности и симметрии всех сезонных рабочих
получаем:
1
1 n1
Ô i (V ) 
( f (n  1)   f (k )) , i=1,2,…,n-1.
n 1
n k 0
Пример 9.5 (Однопродуктовый рынок)
Рассмотрим рынок, в котором участвует множество продавцов Р, причем каждый
продавец k  P располагает количеством Xk некоторого товара, и множество
покупателей Q, причем покупатель i  Q предъявляет спрос на этот товар в объеме Yi,
при этом выполняется условие равенства суммарного предложения суммарному
спросу:
 X K  YI

kP
IQ
Такой рынок можно описать кооперативной игрой с множеством игроков I=Р  Q.
Считаем, что |I|=n. Характеристическая функция определяется следующим образом:


V ( K )  min   X k , YI  .
kPK
I a  K

48
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Ее значение есть объем сделок, которые могут быть заключены между членамипродавцами и членами-покупателями коалиции К.
В приложении 7 приведена программа, позволяющая по известным объемам
покупок и продаж найти значения характеристической функции V(K). Далее, используя
программу, приведенную в приложении 6 для вычисления вектора Шепли, убеждаемся,
что для каждого продавца k  Р Фk (V)= Xk / 2, а для покупателя i  Q ФI(V)=YI/2.
Впрочем, к этому же выводу можно было бы прийти из теоретических соображений,
которые приведены в книге Н.Н. Воробьева ( Доп. Лит. [2]).
Таким образом, для рассматриваемого однопродуктового рынка доля каждого его
участника в распределении прибыли зависит только от собственного капитала, взятого
в денежной или натуральной форме, и не зависит от распределения капиталов между
отдельными участниками рынка.
В заключение отметим, что нами были в основном рассмотрены лишь некоторые
принципы оптимальности для классических кооперативных игр, называемых также
играми без побочных платежей, но кроме них существуют игры с побочными
платежами, в которых возможна передача "полезности" от одного игрока к другому, не
включенная в первоначальные стратегические возможности. Игры с побочными
платежами достаточно сложны и в настоящий курс не входят.
Вопросы для самоконтроля
1. Что понимается под коалицией? характеристической функцией?
2. Что называется классической кооперативной игрой?
3. Каков содержательный смысл значений характеристической функции?
4. Что называется дележом?
5. Когда дележ доминирует другой дележ по некоторой коалиции?
6. Когда один дележ доминирует другой?
7. Что называется максимальным дележом?
8. Что называется ядром кооперативной игры?
9. Сформулируйте теорему о ядре.
10. Сформулировать определение вектора Шепли.
11. Как найти Вектор Шепли для кооперативной игры?
Задачи и упражнения для самостоятельного решения
9.1. Группа из трёх неквалифицированных работников выполняет некоторую
однородную работу, причём каждый из работников может выполнить одинаковый
объём работы и заработать а рублей. Построить характеристическую функцию.
9.2. Каждый из четырёх работников имеет некоторый индивидуальный навык,
которым владеет только он один и который позволяет увеличить на некоторую сумму b
заработок а каждого, кто с ним работает в коалиции. Построить характеристическую
функцию.
9.3. Определить, являются ли векторы
дележами для игры рынок трёх лиц (пример 10.1)?
а) (0,1; 0,4; 0,5); b) (0,2; 0,4; 0,6); с) (-0,1; 0,5; 0,6)
9.4. Для игры рынок трёх лиц (пример 10.1) определить, доминирует ли делёж ( 0,2;
0,3; 0,5) делёж ( 0,1; 0; 0,9).
49
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
9.5. (Распределение прибыли). Имеется три предприятия, специализирующиеся на
выпуске комплектующих деталей А и В одинаковой стоимости, причём изделие
собирается из одной детали А и одной детали В. Возможности предприятий по выпуску
деталей указаны в таблице:
Предприятие
1
2
3
А
900
600
0
В
0
0
1000
Так как ни одно из предприятий не в состоянии самостоятельно произв одить данное
изделие, то они заключают между собой договор с последующим распределением
прибыли. Составить модель кооперативной игры и найти её ядро, считая прибылью
коалиции стоимость произведённых изделий, если стоимость одного изделия равна с
(с= 0,001) денежных единиц.
.9.6. (Фермер и сезонные рабочие). Фермер может привлечь для уборки урожая трёх
сезонных рабочих. При участии k (0≤k≤3) рабочих будет получен доход в k+2
денежные единицы. Требуется найти справедливую долю фермера и сезонных рабочих
в общем доходе.
9.7. (Однопродуктовый сбалансированный рынок). На рынке присутствуют 2
продавца и 2 покупателя, причем продавцы имеют соответственно 1 и 3 единицы
одинакового товара, а каждый покупатель желает приобрести по 2 единицы этого
товара, то есть спрос равен предложению. Составить модель кооперативной игры
четырёх игроков, считая выигрышем каждой коалиции объём сделок, которые могут
быть заключены между продавцами и покупателями – членами этой коалиции. Найти
справедливую долю каждого игрока в этой игре.
9.8. Построить характеристическую функцию и найти вектор Шепли для игры
задачи 10.7 при условии, что имеется 2 продавца и 3 покупателя, причём продавцы
продают соответственно 2 и 4 единицы товара, а покупатели предъявляют спрос
соответственно в объёмах 1, 2 и 3 единиц товара.
9.9. Найдите вектор Шепли для характеристической функции упражнения 10.1 и
10.2.
9.10. (Оценка «силы» держателей акций). Акции некоторой компании распределены
между четырьмя акционерами, причём 1-ый акционер обладает 10% всех акций, 2-ой –
20%, 3-ий – 30% и 4-ый – 40%. На общем собрании акционеров решение принимается
по правилу простого большинства (одна акция равна одному голосу). Найти вектор
Шепли для этой кооперативной игры, который позволит оценить «силу» акционеров
при данной схеме голосования.
9.11. Оценить «силу» держателей
акций, если в условиях задачи 9.10 решение
принимается в случае, когда за него подано не менее, чем 2/3 голосов.
9.12. Организация состоит из председателя и трёх рядовых членов. По уставу
организации решение принимается, если «за» голосуют председатель и ещё хотя бы
один рядовой член, либо «за» голосуют все рядовые члены. Найти вектор Шепли для
данной кооперативной игры.
50
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ЛИТЕРАТУРА
а) основная литература
1.
Лабскер, Л.Г., Бабешко, Л.О. Игровые методы в управлении
экономикой и бизнесом: Учебное пособие / Л.Г.Лабскер, Л.О.Бабешко– М.:Дело, 2010.
464 с. ISBN 5-7749-02233-1
2.
Уейская, Н.Б. Задачи и упражнения по теории игр для экономистов: Учебное
пособие /Н.Б. Уейская. - ФГОУ ВПО «Саратовский ГАУ». Саратов, 2004. 72 с. ISBN 570011-0429
б) дополнительная литература
1.Бондарева, 0.Н. О теоретико-игровых моделях в экономике. Учебное.
пособие /0.Н.Бондарева - Л.: Изд-во ЛГУ, 1974. - 98 с.
2. Воробьёв, Н.Н. Теория игр. Лекции для экономистов-кибернетиков/
Н.Н.Воробьёв - Л.: Изд-во ЛГУ, 1974. - 160 с.
3. Дюбин, Г.Н., Суздаль, В.Г. Введение в прикладную теорию игр./ Г.Н. Дюбин,
В.Г. Суздаль - М.: Наука, 1981.- 266с.
4. Дубов, А.М., Лагоша, Б.А., Хрусталёв, Е.Ю. Моделирование рисковых
ситуаций в экономике и бизнесе/ А.М.Дубров, Б.А.Лагоша, Е.Ю.Хрусталёв –М:
Финансы и статистика, 2000, -88 с.
5. Карлин, С. Математические методы в теории игр, программировании и
экономике / Карлин С. - : Мир, 1964. - 476с.
6. Кудрявцев, Е.М. Исследование операций в задачах, алгоритмах и программах
/ Е.М Кудрявцев - М: Радио и связь,1984, 86с.
7. Мулен, Э. Теория игр с примерами из математической экономики / Э.Мулен М.: Мир, 1985, 324 с.
8. Нейман, Дж.фон, Моргенштерн, О. Теория игр и экономическое поведение /
Дж.фон Нейман, О Моргенштерн - М: Наука 1970. - 708 с.
9. Оуэн, Г. Теория игр/ Г.Оуэн - М.: Мир, 1971. – 230с.
10. Розен, В.В. Цель – оптимальность – решение / В.В Розен - М. Радио и связь,
1982. - 168 с.
11. Розен, В.В. Теория игр и экономическое моделирование: спецкурс для
студентов экономических специальностей/ В.В.Розен - Изд. СГУ. Саратов, 1996. 76с.
12. Уейская, Н.Б. Теоретико-игровые модели в экономике: учеб. пособие/ Н.Б.
Уейская- Саратов: Изд.-во Сарат. с.- х. акад., 1996. – 96с. ISBN 5-7011-0130-4
13. Розен, В.В. Математические модели принятия решений в экономике /В.В.Розен
- М.: Высшая школа, 2002. - 288 с.ISBN 5-06-004356-8
в) базы данных, информационно-справочные и поисковые системы,
поисковые системы Rambler, Yandex, Google:

Электронная библиотека СГАУ – [Электронный ресурс].
Режим доступа: http://library.sgau.ru

[Электронный ресурс]. Режим доступа: http://www.i-exam.ru/

Уейская, Н.Б. Методы оптимальных решений в задачах и упражнениях. Учебнометодическое пособие. /Н.Б. Уейская, 2013. 84 с.[Электронный ресурс]. Режим доступа
http://rucont.ru/efd/214893?cldren=0.
51
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
СОДЕРЖАНИЕ
Введение ……………………………………………………………………………….3
1. Понятие о математическом моделировании……………………………………….4
2.. Бескоалиционные игры……………………………………………………………..6
3. Антагонистические игры…………………………………………………………….9
4. Матричные игры...…………………………………………………………………..12
5. Смешанное расширение матричной игры...……………………………………….17
6. Методы решения матричных игр..……………………………………….................21
7. Игры с природой……………………………………………………………………..31
8. Биматричные игры...…………………………………………………………………36
9. Классические кооперативные игры…………………………………………………41
Литература…………………………………………………………………………………..51
52
Документ
Категория
Экономика
Просмотров
143
Размер файла
1 022 Кб
Теги
игр, 1572, теория, менеджмент
1/--страниц
Пожаловаться на содержимое документа