Основные понятия теории игр

Лекция 1 (ММвТУиИО) ВВЕДЕНИЕ Экономика – это хозяйственная деятельность общества, а также совокупность отношений, складывающихся в системе производства, распределения, обмена и потребления. Эффективное управление экономикой требует поиска и выбора оптимальных решений. От того, насколько обоснованы принимаемые решения, зависит состояние производственно-технологической и социальной сфер экономики. Одним из способов повышения степени обоснованности таких решений является постановка задач принятия решений на математическую основу и, в частности, использование математического моделирования. Математическое моделирование – методика исследования явлений и объектов окружающего мира, базирующаяся на представлении и изучении объекта (явления) с помощью математического формализма (т.е. в рамках некоторой математической теории). Математический подход к постановке и анализу задач принятия решений помогают лицу, принимающему решение, более обоснованно и последовательно осуществлять определенную стратегию поведения при решении экономических проблем различной сложности. В качестве базовых подходов при моделировании экономических задач часто используются формализмы теории управления и исследования операций, а, учитывая конкурентность экономической среды и социальную значимость принимаемых решений – элементы теории игр. Теория игр, как подраздел теории исследования операций математический метод изучения и поиска оптимальных стратегий в играх, рассматриваемых как формализация конфликтных ситуаций. Таким образом, теория игр представляет собой теоретические основы математических моделей принятия оптимальных решений в конкурентных ситуациях рыночных отношений, в которых одна противоборствующая сторона выигрывает за счет другой стороны. Наряду с этим в теории рассматривают также модели риска и неопределенности, требующие использования различных критериев выбора оптимальных решений. Теория игр получила широкое использование в различных областях экономики и производства, бизнеса и финансов, сельского хозяйства, военного дела, биологии и социологии, психологии и политологии. К настоящему времени она развилась в относительно самостоятельную область математики и может рассматриваться независимо от ее приложений к математическому моделированию реальных ситуаций. 1 Лекция 1 (ММвТУиИО) ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИГР Задачи теории игр в экономике Во многих финансово-экономических задачах, в частности, в задачах маркетинга, менеджмента, финансово-банковских, инвестиционных возникает необходимость принятия обоснованных решений. Проблема принятия решений осложняется тем, что ее приходится решать в условиях неопределенности. Неопределенность может носить различный характер:  неопределенными могут быть действия одной стороны, направленные на уменьшение эффективности решений, принимаемых другой стороной. Например, фирмы, конкурирующие на одном рынке, осуществляют действия в своих интересах, препятствующие реализации интересов конкурентов;  неопределенность может относиться и к ситуациям риска, в которых сторона, принимающая решение, может оценить результаты этих решений, вместе с вероятностями их появления / непоявления. Эти вероятности представляют собой вероятности всевозможных условий, в которых решается данная задача. Сами условия формируются многими факторами (состоянием экономической и финансовой систем, курсов валют, инфляции и т.д.);  если известны все возможные последствия принимаемых решений, но неизвестны их вероятности, т.е. неизвестны вероятности возможных состояний внешней среды, в которой решается задача, то говорят, что решение принимается в условиях полной неопределенности;  неопределенностью может обладать и цель решаемой задачи, когда для оценки эффективности принимаемого решения принимаются показатели, не всегда отражающие полную картину. В условиях полной определенности теоретические и практические выводы носят однозначный характер и представляют собой четкое описание ситуации в рамках рассматриваемой модели (задачи). В условиях же недостаточной информированности или полной неопределенности результаты анализа уже не обладают такой четкостью и однозначностью. Однако и полученные при этом рекомендации оказываются полезными, так как они дают возможность обосновать варианты принимаемых решений с разных точек зрения. Попытки количественного анализа финансово-экономических ситуаций в условиях рыночной экономики привели к созданию специальных экономикоматематических методов обоснования выбора и принятия решений. Такие методы позволяют находить количественные характеристики экономических процессов и:  в одних (более простых) ситуациях находить оптимальные решения;  в других (более сложных и неопределенных) ситуациях получать дополнительную информацию, позволяющую провести детальный анализ каждого варианта решения, выявить его положительные и отрицательные 2 Лекция 1 (ММвТУиИО) стороны и остановиться на варианте, который будет наиболее обоснованным и предпочтительным для стороны, принимающей решение. При поиске решения в условиях неопределенности всегда присутствует фактор действия «наудачу» без обоснованной уверенности в правильности принимаемого решения (выбор решения в условиях неопределенности всегда сопряжен с риском). Математические методы обоснования принимаемых в экономике решений дают возможность анализа различных вариантов с целью уменьшения уровня риска, которое иногда достигается за счет получения дополнительной информации. В этом случае возникает проблема оценки стоимости этой информации, позволяющей максимизировать экономический эффект принимаемого решения. Формализация содержательных финансово-экономических задач принятия решений в условиях неопределенности и риска приводит к экономикоматематическим моделям и методам, теоретическим базисом которых является теория игр, изучению элементов которой посвящен данный курс. Конфликты и теория игр На практике часто приходится рассматривать ситуации, в которых участвуют две (или более) стороны, имеющие различные (в частности, противоречивые) интересы и обладающие возможностями применять для достижения своих целей разнообразные действия. Подобные явления и ситуации называются конфликтными или просто конфликтами. Примеры: 1. Студент приходит на экзамен, тянет билет - и здесь возможен конфликт при оценке знаний студента. Действия сторон – студента и преподавателя различны, и их интересы не во всем совпадают. 2. Разбойники делят добычу – возможны конфликты при определении объема, достающегося каждому. 3. «Три девицы под окном пряли поздно вечерком …» - конфликт целевых установок. В экономике конфликтные ситуации возникают при взаимодействии покупателя и продавца, банка и клиента, поставщика и потребителя и т.д. Математическим описанием и анализом подобных конфликтных ситуаций и занимается теория игр. Типичная конфликтная составляющими: ситуация характеризуется тремя основными  заинтересованными сторонами (потребители, фирмы, отдельные страны, финансовые и экономические союзы и т.д.);  интересами сторон (удовлетворение различных финансовых, экономических и политических потребностей, вытеснение конкурентов с рынка сбыта, повышение доходов и т.д.); 3 Лекция 1 (ММвТУиИО)  возможными действиями сторон (выбор объема потребления, способы формирования инвестиционного портфеля, выбор объема производства, выбор дивидендной политики, демпинговая политика и т.д.). Любая конфликтная ситуация, взятая из реальной жизни, как правило, довольно сложна. Ее изучение затруднено наличием многих обстоятельств, часть из которых не оказывает сколь-нибудь существенного влияния ни на развитие конфликта, ни на его исход. Для того, чтобы анализ конфликтной ситуации оказался возможным, необходимо удалить эти второстепенные факторы, что при удачном стечении обстоятельств позволяет построить упрощенную математическую модель конфликта, которую принято называть игрой. Необходимость изучения и анализа конфликтов, представляемых в виде таких упрощенных моделей (игр) привела к появлению специального математического аппарата – теории игр. Обычно теорию игр определяют как раздел математики для изучения конфликтных ситуаций с целью выбора оптимальных правил поведения каждой стороны, участвующей в разрешении таких ситуаций. Кроме того, в экономике оказался недостаточным классический аппарат математического анализа, занимающийся определением экстремума функций. Появилась необходимость изучения так называемых оптимальных минимаксных и максиминных решений, рассматриваемых в теории игр. Математико-игровые модели находят свое применение не только в конфликтных ситуациях социально-экономической области, но и во взаимодействии человека с природой, в политике, биологии, военной области и т.д. Основные понятия и классификация видов игр Игра – упрощенная формализованная модель реальной конфликтной ситуации. Формализация означает выработку определенных правил действия сторон в процессе игры: возможные варианты действий игроков, исход игры при данном варианте, степень информированности каждой стороны о поведении других сторон. Заинтересованные играющие стороны называются игроками (одна играющая сторона может представлять как одного игрока, так и группу игроков), действующими по определенным правилам игры. Стратегией игрока называется любое его возможное действие в рамках заданных правил игры. В условиях конфликта каждый игрок выбирает свою стратегию, в результате чего складывается набор стратегий, называемых ситуацией. Заинтересованность игроков в ситуации проявляется в том, что каждому игроку в каждой стратегии (ситуации) приписывается число, выражающее степень удовлетворения его интересов в этой стратегии (ситуации), называемое его выигрышем. Хотя, на практике, не каждый выигрыш можно оценить количественно, но в теории игр качественные выигрыши не рассматриваются. 4 Лекция 1 (ММвТУиИО) Игры можно классифицировать по различным критериям: 1. Количество игроков. Если в игре участвуют две стороны, то ее называют игрой двух лиц. Если число сторон больше двух, ее называют игрой n лиц (или множественной). Наиболее полно в теории проработаны игры двух лиц. 2. Количество стратегий игры. По этому критерию игры делятся на конечные и бесконечные. В конечной игре каждый из игроков имеет конечное число возможных стратегий. Игра является бесконечной, если хотя бы один из игроков имеет бесконечное число возможных стратегий. 3. Взаимоотношения сторон. По этому критерию игры подразделяются на бескоалиционные, коалиционные, кооперативные. Бескоалиционной называется игра, в которой игроки не имеют права вступать в соглашения, образовывать коалиции. В коалиционной игре игроки могут вступать в соглашения, образовывать коалиции. Если коалиции определены заранее, то такая игра называется кооперативной. 4. Характер выигрышей. По этому критерию игры подразделяются на игры с нулевой суммой и игры с ненулевой суммой. Игра с нулевой суммой означает, что сумма выигрышей всех игроков в каждой партии равна нулю (например, покер, где один выигрывает все ставки других; реверси, где захватываются фишки противника; воровство). Игры двух игроков с нулевой суммой относятся к классу антагонистических игр. При этом выигрыш одного игрока равен проигрышу другого игрока. В играх с ненулевой суммой выигрыш какого-то игрока не обязательно означает проигрыш другого, и наоборот (торговля – каждый участник извлекает выгоду; шашки, шахматы – игрок может превратить рядовую фигуру в более сильную, при этом сумма игры увеличивается; война – приобретения не соответствуют потерям). Экономические задачи теории игр относятся к обоим типам игр. 5. Вид функции выигрыша. По этому критерию игры подразделяются на матричные, биматричные, непрерывные, выпуклые, сепарабельные и др. определяемые видом функции:  матричная игра – конечная игра двух игроков с нулевой суммой;  биматричная игра – конечная игра двух лиц с ненулевой суммой. Выигрыш каждого игрока задается своей платежной матрицей;  если функция выигрышей 𝑎𝑖𝑗 = 𝑓 (𝑖, 𝑗) является непрерывной, то игра называется непрерывной, если функция выигрышей – выпуклая, то игра называется выпуклой;  если функцию выигрышей можно представить в виде суммы произведений функции одного аргумента – сепарабельной. 6. Количество ходов. По этому критерию игры делятся на одношаговые или многошаговые. Одношаговые заканчиваются после одного хода каждого игрока, и происходит распределение выигрышей. Многошаговые игры бывают позиционными, стохастическими, дифференциальными и др. 5 Лекция 1 (ММвТУиИО) 7. Информированность сторон. По этому критерию различают игры с полной и неполной информацией. Игра определяется как игра с полной информацией, если каждый игрок на каждом ходу игры знает все стратегии, примененные ранее другими игроками на предыдущих ходах, и все возможные стратегии противников, что в некоторой степени позволяет предсказать последующее развитие игры (например, в шахматах, шашках). Если же игроку известны не все стратегии предыдущих ходов других игроков, то игра называется игрой с неполной информацией. 8. Степень неполноты информации. По этому критерию игры делятся на статистические и стратегические. Стратегические игры проходят в условиях полной неопределенности. Статистические игры проводятся в условиях частичной неопределенности. В статистической игре имеется возможность получения информации на основе статистического эксперимента, по результатам которого оценивается распределение вероятностей для стратегий игроков. Исследования в теории игр можно проводить с различными целями. Будем рассматривать в качестве целей изучения игр следующие:  выработка принципов оптимальности, т.е. того, какое поведение игроков следует считать разумным или целесообразным;  выяснение реализуемости принципов оптимальности, т.е. установление существования оптимальных ситуаций (и стратегий);  отыскание оптимальных ситуаций (реализация игры). Оценка игроком ситуации путем указания его количественного выигрыша возможна не всегда, а иногда просто не имеет смысла. В этом случае численное значение выигрыша в каждой ситуации заменяют на сравнительную предпочтительность ситуаций для отдельных игроков. Тогда речь ведут о более широком понятии теории игр с предпочтениями, которая включает в себя теорию игр с выигрышами как частный случай. Основной целью теории игр является выработка рекомендаций для наиболее предпочтительного поведения игроков в конфликте, т.е. выявления для каждого из них «оптимальной стратегии». Понятие оптимальной стратегии – одно из важнейших понятий теории игр - может пониматься в различных смыслах в зависимости от показателя оптимальности (эффективности). Оптимальная стратегия – стратегия, которая при многократном повторении игры обеспечивает игроку максимально возможный средний выигрыш. При нахождении оптимальных стратегий предполагается, что противник ведет себя разумно и стремится минимизировать свой проигрыш. Стратегия, оптимальная по одному показателю, может не быть оптимальной по другому. 6 Лекция 1 (ММвТУиИО) АНТАГОНИСТИЧЕСКАЯ ИГРА ДВУХ ЛИЦ С НУЛЕВОЙ СУММОЙ Рассмотрим игру, в которой участвуют два игрока А и В, причем каждый из них имеет конечное число стратегий. Пусть игрок А имеет возможность выбирать одну из m стратегий: А1, …, Аm (Ai, 𝑖 = 1, 𝑚), а игрок В – одну из n стратегий: В1, …, Вn. Тогда игра может быть названа игрой 𝑚 × 𝑛 или 𝑚 × 𝑛 - игрой. Если первый игрок выбирает стратегию Ai, а второй игрок - стратегию Bj, то говорят, что имеет место ситуация {Ai, Bj}. Обозначим через aij значения выигрышей игрока А. Значения выигрышей aij при реализации различных ситуаций обычно представляют в виде платежной таблицы: Игрок 2 Игрок 1 A1 A2 … Am В1 a11 a21 … am1 В2 a12 a22 … am2 … … … … … Вn a1n a2n … amn Или - в виде платежной матрицы, имеющей размеры mxn и называемой матрицей игры (отсюда и название игры – матричная): 𝑎11 𝑎21 𝐴 = {𝑎𝑖𝑗 } = ( … 𝑎𝑚1 𝑎12 𝑎22 … 𝑎𝑚2 . . . 𝑎1𝑛 … 𝑎2𝑛 … … ) … 𝑎𝑚𝑛 Будем считать, что выбор игроками стратегий Аi и Вj однозначно определяет исход игры – выигрыш aij игрока А и выигрыш bij игрока В, причем эти выигрыши связаны равенством: aij = - bij где отрицательный выигрыш эквивалентен проигрышу. Последнее условие означает, что в рассматриваемых обстоятельствах выигрыш одного из игроков равен выигрышу другого, взятому с противоположным знаком. Поэтому при анализе такой игры можно рассматривать выигрыши только одного из игроков, например, игрока А. Такую игру называют антагонистической игрой двух лиц с нулевой суммой (в такой модели выделяются два игрока, а выигрыш одного всегда равен проигрышу другого). Для того, чтобы составить экономико-математическую модель конфликтной ситуации в виде матричной игры, необходимо: 7 Лекция 1 (ММвТУиИО) 1) определить игроков (А и В); 2) перечислить все возможные (чистые) стратегии игроков (Аi и Вj); 3) построить матрицу выигрышей (это может оказаться нетривиальной задачей, особенно для игр большой размерности) путем формализации правил, по которым развивается конфликт (игра) в виде функции выигрышей игрока А: 𝑎𝑖𝑗 = 𝑓 (𝑖, 𝑗). Ниже приведены примеры антагонистических игр двух лиц с нулевой суммой. Пример 1.1. («Чет – нечет»). Каждый из двух игроков А и В одновременно и независимо друг от друга записывает на листе бумаги любое целое число. Если выписанные числа имеют одинаковую четность, то игрок А получает от игрока В 1 рубль, а если разную, то, наоборот, игрок А платит 1 рубль игроку В. Т.о. у игрока А две стратегии: А1 – «записать четное число» и А2 – «записать нечетное число». У игрока В те же две стратегии: В1 – «записать четное число» и В2 – «записать нечетное число». Выбор игроками соответственно стратегий Аi и Вk однозначно определяет исход игры: aik – выигрыш игрока А. Матрица этой 2х2-игры имеет следующий вид: 1 −1 А=( ), −1 1 где строки соответствуют указанным стратегиям игрока А, а столбцы – стратегиям игрока В. Пример 1.2. («Камень, ножницы, бумага»). Каждый из двух игроков одновременно называет один из трёх предметов: камень, ножницы, бумага. При этом «бумага» побеждает «камень», «камень» - «ножницы», «ножницы» - «бумагу». Игрок, выбирающий выигрывающий предмет получает у противника один балл; если оба игрока выберут одинаковые предметы, то игроки баллов не получают. В модели этой игры также два игрока, у которых одинаковые возможности – выбрать «камень» (К), «ножницы» (Н), «бумагу» (Б). Т.о. множества стратегий игроков {K, Н, Б}. Эта игра является матричной, т.к. она конечная и выигрыш первого игрока равен проигрышу второго игрока (выигрышу первого игрока с противоположным знаком). С учетом сформулированных правил, запишем выигрыши первого игрока в таблицу: К Н Б К 1 -1 Н -1 1 Б 1 -1 Здесь строки соответствуют выбору (стратегиям) первого игрока, а столбцы – выбору (стратегиям) второго игрока. На пересечении выбранных строки и столбца в клетке показан выигрыш (проигрыш) первого (второго) игрока. Платежная матрица игры: 1 −1 А = (−1 0 1) 1 −1 0 8 Лекция 1 (ММвТУиИО) Пример 1.3. («Игра полковника Блотто».) Игра полковника Блотто – общее название класса тактических военных игр. Рассмотрим один из наиболее простых вариантов этой игры. Две воюющие армии ведут борьбу за два пункта. Первая армия под командованием полковника Блотто состоит из четырёх (m = 4) полков; вторая под командованием капитана Киже состоит из трёх (n = 3) полков. Армия, которая посылает больше полков в тот или иной пункт, занимает его и уничтожает все направленные в этот пункт силы противоположной стороны, получая по очку, как за занятый пункт, так и за каждый уничтоженный полк противника. Полковник Блотто (и капитан Киже) должен решить, как распределить силы, чтобы получить как можно больше очков. В модели представлены два игрока – Блотто и Киже. Стратегии игроков распределение полков между двумя пунктами. Т.е. стратегии полковника Блотто распределение четырёх полков между первым и вторым пунктами. Имеется пять таких распределений (чистых стратегий): {(4,0),(3,1),(2,2),(1,3),(0,4)}. Точно так же у капитана Киже есть четыре чистые стратегии, представленные парами {(3,0),(2,1),(1,2),(0,3)}. В каждой паре первое число указывает число полков, направленных на первый пункт, а второе число – на второй пункт. По условию игра является антагонистической. В таблице представлены выигрыши полковника Блотто в зависимости от действий, выбранных игроками (эти же числа указывают проигрыши капитана Киже). (3,0) (2,1) (1,2) (0,3) (4,0) 4 2 1 (3,1) 1 3 -1 (2,2) -2 2 2 -2 (1,3) -1 3 1 (0,4) 1 2 4 Платежная матрица игры: 4 2 1 0 1 3 0 −1 А = −2 2 2 −2 −1 0 3 1 (0 1 2 4) Эта игра симметрична для полковника Блотто относительно стратегий (4, 0) и (0, 4), а также относительно стратегий (3, 1) и (1, 3); для капитана Киже стратегии (3, 0), (0, 3) и (2, 1), (1, 2) также являются симметричными это позволяет найти оптимальное решение данной игры. 9