Как победить в теории игр. Теория игр в экономике
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ЭКОНОМИЧЕСКИЙ ФАКУЛЬТЕТ
КАФЕДРА …
Теория игр и ее применение в экономике
Курсовой проект
студента 2 курса
отделения «Менеджмент»
Научный руководитель
Минск, 2010
1. Введение. стр.3
2. Основые понятия теории игры стр.4
3. Представление игр стр. 7
4. Типы игр стр.9
5. Применение теории игр в экономике стр.14
6. Проблемы практического применения в управлении стр.21
7. Заключение стр.23
Список использованной литературы стр.24
1. ВВЕДЕНИЕ
На практике часто появляется необходимость согласования действий фирм, объединений, министерств и других участников проектов в случаях, когда их интересы не совпадают. В таких ситуациях теория игр позволяет найти лучшее решение для поведения участников, обязанных согласовывать действия при столкновении интересов. Теория игр все шире проникает в практику экономических решений и исследований. Ее можно рассматривать как инструмент, помогающий повысить эффективность плановых и управленческих решений. Это имеет большое значение при решении задач в промышленности, сельском хозяйстве, на транспорте, в торговле, особенно при заключении договоров с иностранными партнерами на любых уровнях. Так, можно определить научно обоснованные уровни снижения розничных цен и оптимальный уровень товарных запасов, решать задачи экскурсионного обслуживания и выбора новых линий городского транспорта, задачу планирования порядка организации эксплуатации месторождений полезных ископаемых в стране и др. Классической стала задача выбора участков земли под сельскохозяйственные культуры. Метод теории игр можно применять при выборочных обследованиях конечных совокупностей, при проверке статистических гипотез.
Теория игр - математический метод изучения оптимальных стратегий в играх. Под игрой понимается процесс, в котором участвуют две и более сторон, ведущих борьбу за реализацию своих интересов. Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышу - в зависимости от поведения других игроков. Теория игр помогает выбрать лучшие стратегии с учётом представлений о других участниках, их ресурсах и их возможных поступках.
Теория игр - это раздел прикладной математики, точнее - исследования операций. Чаще всего методы теории игр находят применение в экономике, чуть реже в других общественных науках - социологии, политологии, психологии, этике и других. Начиная с 1970-х годов её взяли на вооружение биологи для исследования поведения животных и теории эволюции. Очень важное значение она имеет для искусственного интеллекта и кибернетики, особенно с проявлением интереса к интеллектуальным агентам.
Теория игр берёт своё начало из неоклассической экономики. Впервые математические аспекты и приложения теории были изложены в классической книге 1944 года Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение» (англ. Theory of Games and Economic Behavior).
Эта область математики нашла некоторое отражение в общественной культуре. В 1998 году американская писательница и журналистка Сильвия Назар издала книгу о судьбе Джона Нэша, нобелевского лауреата по экономике и учёного в области теории игр; а в 2001 по мотивам книги был снят фильм «Игры разума». Некоторые американские телевизионные шоу, например, «Friend or Foe», «Alias» или «NUMB3RS», периодически ссылаются на теорию в своих эпизодах.
Нематематический вариант теории игр представлен в работах Томаса Шеллинга, нобелевского лауреата по экономике 2005г.
Нобелевскими лауреатами по экономике за достижения в области теории игр стали: Роберт Ауманн, Райнхард Зелтен, Джон Нэш, Джон Харсаньи, Томас Шеллинг.
2. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИГР
Ознакомимся с основными понятиями теории игр. Математическая модель конфликтной ситуации называется игрой, стороны, участвующие в конфликте, - игроками, а исход конфликта – выигрышем. Для каждой формализованной игры вводятся правила, т.е. система условий, определяющая: 1) варианты действий игроков; 2) объём информации каждого игрока о поведении партнёров; 3) выигрыш, к которому приводит каждая совокупность действий. Как правило, выигрыш (или проигрыш) может быть задан количественно; например, можно оценить проигрыш нулём, выигрыш – единицей, а ничью - ½.
Игра называется парной, если в ней участвуют два игрока, и множественной, если число игроков больше двух.
Игра называется игрой с нулевой суммой, или антагонистической, если выигрыш одного из игроков равен проигрышу другого, т. е. для полного задания игры достаточно указать величину одного из них. Если обозначить а – выигрыш одного из игроков, b – выигрыш другого, то для игры с нулевой суммой b = -а, поэтому достаточно рассматривать, например а.
Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход – это сознательный выбор игроком одного из возможных действий (например, ход в шахматной игре). Случайный ход – это случайно выбранное действие (например, выбор карты из перетасованной колоды). В дальнейшем мы будем рассматривать только личные ходы игроков.
Стратегией игрока называется совокупность правил, определяющих выбор его действия при каждом личном ходе в зависимости от сложившейся ситуации. Обычно в процессе игры при каждом личном ходе игрок делает выбор в зависимости от конкретной ситуации. Однако в принципе возможно, что все решения приняты игроком заранее (в ответ на любую сложившуюся ситуацию). Это означает, что игрок выбрал определённую стратегию, которая может быть задана в виде списка правил или программы. (Так можно осуществить игру с помощью ЭВМ). Игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной – в противном случае.
Для того чтобы решить игру, или найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, т.е. один из игроков должен получать максимальный выигрыш, когда второй придерживается своей стратегии. В то же время второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии. Такие стратегии называются оптимальными. Оптимальные стратегии должны также удовлетворять условию устойчивости, т. е. любому из игроков должно быть невыгодно отказаться от своей стратегии в этой игре.
Если игра повторяется достаточно много раз, то игроков может интересовать не выигрыш и проигрыш в каждой конкретной партии, а средний выигрыш (проигрыш) во всех партиях.
Целью теории игр является определение оптимальной стратегии для каждого игрока. При выборе оптимальной стратегии естественно предполагать, что оба игрока ведут себя разумно с точки зрения своих интересов. Важнейшее ограничение теории игр – естественность выигрыша как показателя эффективности, в то время как в большинстве реальных экономических задач имеется более одного показателя эффективности. Кроме того, в экономике, как правило, возникают задачи, в которых интересы партнёров не обязательно антагонистические.
3. Представление игр
Игры представляют собой строго определённые математические объекты. Игра образуется игроками, набором стратегий для каждого игрока и указания выигрышей, или платежей, игроков для каждой комбинации стратегий. Большинство кооперативных игр описываются характеристической функцией, в то время как для остальных видов чаще используют нормальную или экстенсивную форму.
Экстенсивная форма
Игра «Ультиматум» в экстенсивной форме
Игры в экстенсивной, или расширенной, форме представляются в виде ориентированного дерева, где каждая вершина соответствует ситуации выбора игроком своей стратегии. Каждому игроку сопоставлен целый уровень вершин. Платежи записываются внизу дерева, под каждой листовой вершиной.
На рисунке слева - игра для двух игроков. Игрок 1 ходит первым и выбирает стратегию F или U. Игрок 2 анализирует свою позицию и решает - выбрать стратегию A или R. Скорее всего первый игрок выберет U, а второй - A (для каждого из них это оптимальные стратегии); тогда они получат соответственно 8 и 2 очка.
Экстенсивная форма очень наглядна, с её помощью особенно удобно представлять игры с более чем двумя игроками и игры с последовательными ходами. Если же участники делают одновременные ходы, то соответствующие вершины либо соединяются пунктиром, либо обводятся сплошной линией.
Нормальная форма
Игрок
2 |
Игрок
2 |
|
Игрок
1 |
4 , 3 |
–1 , –1 |
Игрок
1 |
0 , 0 |
3 , 4 |
Нормальная форма для игры с 2 игроками, у каждого из которых по 2 стратегии. |
Игроки выбирали стратегии с максимальным для себя результатом, но проиграли, из-за незнания хода другого игрока. Обычно в нормальной форме представляются игры, в которых ходы делаются одновременно, или хотя бы полагается, что все игроки не знают о том, что делают другие участники. Такие игры с неполной информацией будут рассмотрены ниже.
Характеристическая формула
В кооперативных играх с трансферабельной полезностью, то есть возможностью передачи средств от одного игрока к другому, невозможно применять понятие индивидуальных платежей. Вместо этого используют так называемую характеристическую функцию, определяющую выигрыш каждой коалиции игроков. При этом предполагается, что выигрыш пустой коалиции равен нулю.
Основания такого подхода можно найти ещё в книге фон Неймана и Моргенштерна. Изучая нормальную форму для коалиционных игр, они рассудили, что если в игре с двумя сторонами образуется коалиция C, то против неё выступает коалиция N \ C. Образуется как бы игра для двух игроков. Но так как вариантов возможных коалиций много (а именно 2N, где N - количество игроков), то выигрыш для C будет некоторой характеристической величиной, зависящей от состава коалиции. Формально игра в такой форме (также называемая TU-игрой) представляется парой (N, v), где N - множество всех игроков, а v: 2N → R - это характеристическая функция.
Подобная форма представления может быть применена для всех игр, в том числе без трансферабельной полезности. В настоящее время существуют способы перевести любую игру из нормальной формы в характеристическую, но преобразование в обратную сторону возможно не во всех случаях.
4. Типы игр
Кооперативные и некооперативные.
Игра называется кооперативной, или коалиционной, если игроки могут объединяться в группы, беря на себя некоторые обязательства перед другими игроками и координируя свои действия. Этим она отличается от некооперативных игр, в которых каждый обязан играть за себя. Развлекательные игры редко являются кооперативными, однако такие механизмы нередки в повседневной жизни.
Часто предполагают, что кооперативные игры отличаются именно возможностью общения игроков друг с другом. В общем случае это неверно. Существуют игры, где коммуникация разрешена, но игроки преследуют личные цели, и наоборот.
Из двух типов игр, некооперативные описывают ситуации в мельчайших деталях и выдают более точные результаты. Кооперативные рассматривают процесс игры в целом. Попытки объединить два подхода дали немалые результаты. Так называемая программа Нэша уже нашла решения некоторых кооперативных игр как ситуации равновесия некооперативных игр.
Гибридные игры включают в себя элементы кооперативных и некооперативных игр. Например, игроки могут образовывать группы, но игра будет вестись в некооперативном стиле. Это значит, что каждый игрок будет преследовать интересы своей группы, вместе с тем стараясь достичь личной выгоды.
Хотя я и закончил физико-технический факультет, в вузе мне не читали теорию игр. Но, поскольку я в студенческие годы много играл сначала в преферанс, а затем в бридж, теория игр меня интересовала, и я освоил небольшой учебник. А недавно читатель сайта Михаил решить задачу на теорию игр. Поняв, что сходу задача мне не дается, решил освежить в памяти мои знания по теории игр. Предлагаю вам небольшую книгу – популярное изложение элементов теории игр и некоторых способов решения матричных игр. Она почти не содержит доказательств и иллюстрирует основные положения теории примерами. Книгу написала математик и популяризатор науки Елена Сергеевна Вентцель. Несколько поколений советских инженеров учились по ее учебнику «Теория вероятностей». Елена Сергеевна также написала несколько литературных произведений под псевдонимом И. Грекова.
Елена Вентцель. Элементы теории игр. – М.: Физматгиз, 1961. – 68 с.
Скачать краткий конспект в формате или
§ 1. Предмет теории игр. Основные понятия
При решении ряда практических задач (в области экономики, военного дела и т.д.) приходится анализировать ситуации, где налицо две (или более) враждующие стороны, преследующие противоположные цели, причем результат каждого мероприятия одной из сторон зависит от того, какой образ действий выберет противник. Такие ситуации мы будем называть «конфликтными ситуациями».
Можно привести многочисленные примеры конфликтных ситуаций из различных областей практики. Любая ситуация, возникающая в ходе военных действий, принадлежит к конфликтным ситуациям: каждая из борющихся сторон принимает все доступные ей меры для того, чтобы воспрепятствовать противнику достигнуть успеха. К конфликтным принадлежат и ситуации, возникающие при выборе системы вооружения, способов его боевого применения и вообще при планировании военных операций: каждое из решений в этой области должно приниматься в расчете на наименее выгодные для нас действия противника. Ряд ситуаций в области экономики (особенно при наличии свободной конкуренции) принадлежит к конфликтным ситуациям; в роли борющихся сторон выступают торговые фирмы, промышленные предприятия и т.д.
Необходимость анализировать подобные ситуации вызвала к жизни специальный математический аппарат. Теория игр по существу представляет собой не что иное, как математическую теорию конфликтных ситуаций. Цель теории - выработка рекомендаций по рациональному образу действий каждого из противников в ходе конфликтной ситуации. Каждая непосредственно взятая из практики конфликтная ситуация очень сложна, и анализ ее затруднен наличием многочисленных привходящих факторов. Чтобы сделать возможным математический анализ ситуации, необходимо отвлечься от второстепенных, привходящих факторов и построить упрощенную, формализованную модель ситуации. Такую модель мы будем называть «игрой».
От реальной конфликтной ситуации игра отличается тем, что ведется по вполне определенным правилам. Человечество издавна пользуется такими формализованными моделями конфликтных ситуаций, которые являются играми в буквальном смысле слова. Примерами могут служить шахматы, шашки, карточные игры и т.д. Все эти игры носят характер соревнования, протекающего по известным правилам и заканчивающегося «победой» (выигрышем) того или иного игрока.
Такие формально регламентированные, искусственно организованные игры представляют собой наиболее подходящий материал для иллюстрации и усвоения основных понятий теории игр. Терминология, заимствованная из практики таких игр, применяется и при анализе других конфликтных ситуаций: стороны, участвующие в них, условно именуются «игроками», а результат столкновения - «выигрышем» одной из сторон.
В игре могут сталкиваться интересы двух или более противников; в первом случае игра называется «парной», во втором - «множественной». Участники множественной игры могут в ее ходе образовывать коалиции - постоянные или временные. При наличии двух постоянных коалиций множественная игра обращается в парную. Наибольшее практическое значение имеют парные игры; здесь мы ограничимся рассмотрением только таких игр.
Начнем изложение элементарной теории игр с формулировки некоторых основных понятий. Будем рассматривать парную игру, в которой участвуют два игрока А и В с противоположными интересами. Под «игрой» будем понимать мероприятие, состоящее из ряда действий сторон А и В. Чтобы игра могла быть подвергнута математическому анализу, должны быть точно сформулированы правила игры. Под «правилами игры» разумеется система условий, регламентирующая возможные варианты действий обеих сторон, объем информации каждой стороны о поведении другой, последовательность чередования «ходов» (отдельных решений, принятых в процессе игры), а также результат или исход игры, к которому приводит данная совокупность ходов. Этот результат (выигрыш или проигрыш) не всегда имеет количественное выражение, но обычно можно, установив некоторую шкалу измерения, выразить его определенным числом. Например, в шахматной игре выигрышу можно условно приписать значение +1, проигрышу –1, ничьей 0.
Игра называется игрой с нулевой суммой, если один игрок выигрывает то, что проигрывает другой, т.е. сумма выигрышей обеих сторон равна нулю. В игре с нулевой суммой интересы игроков прямо противоположны. Здесь мы будем рассматривать только такие игры.
Так как в игре с нулевой суммой выигрыш одного из игроков равен выигрышу другого с противоположным знаком, то, очевидно, при анализе такой игры можно рассматривать выигрыш только одного из игроков. Пусть это будет, например, игрок А. В дальнейшем мы для удобства сторону А будем условно именовать «мы», а сторону В - «противник».
При этом сторона А («мы») будет всегда рассматриваться как «выигрывающая», а сторона В («противник») как «проигрывающая». Это формальное условие, очевидно, не означает какого-либо реального преимущества для первого игрока; легко видеть, что оно заменяется противоположным, если знак выигрыша изменить на обратный.
Развитие игры во времени мы будем представлять состоящим из ряда последовательных этапов или «ходов». Ходом в теории игр называется выбор одного из предусмотренных правилами игры вариантов. Ходы делятся на личные и случайные. Личным ходом называется сознательный выбор одним из игроков одного из возможных в данной ситуации ходов и его осуществление. Пример личного хода - любой из ходов в шахматной игре. Выполняя очередной ход, игрок делает сознательный выбор одного из вариантов, возможных при данном расположении фигур на доске. Набор возможных вариантов при каждом личном ходе регламентирован правилами игры и зависит от всей совокупности предшествующих ходов обеих сторон.
Случайным ходом называется выбор из ряда возможностей, осуществляемый не решением игрока, а каким-либо механизмом случайного выбора (бросание монеты, игральной кости, тасовка и сдача карт и т.п.). Например, сдача первой карты одному из игроков в преферанс есть случайный ход с 32 равновозможными вариантами. Чтобы игра была математически определенной, правила игры должны для каждого случайного хода указывать распределение вероятностей возможных исходов.
Некоторые игры могут состоять только из случайных ходов (так называемые чисто азартные игры) или только из личных ходов (шахматы, шашки). Большинство карточных игр принадлежит к играм смешанного типа, т.е. содержит как случайные, так и личные ходы.
Игры классифицируются не только по характеру ходов (личные, случайные), но и по характеру и по объему информации, доступной каждому игроку относительно действий другого. Особый класс игр составляют так называемые «игры с полной информацией». Игрой с полной информацией называется игра, в которой каждый игрок при каждом личном ходе знает результаты всех предыдущих ходов, как личных, так и случайных. Примерами игр с полной информацией могут служить шахматы, шашки, а также известная игра «крестики и нолики».
Большинство игр, имеющих практическое значение, не принадлежит к классу игр с полной информацией, так как неизвестность по поводу действий противника обычно является существенным элементом конфликтных ситуаций.
Одним из основных понятий теории игр является понятие «стратегии». Стратегией игрока называется совокупность правил, определяющих однозначно выбор при каждом личном ходе данного игрока в зависимости от ситуации, сложившейся в процессе игры. Обычно решение (выбор) при каждом личном ходе принимается игроком в ходе самой игры в зависимости от сложившейся конкретной ситуации. Однако теоретически дело не изменится, если мы представим себе, что все эти решения принимаются игроком заранее. Для этого игрок должен был бы заблаговременно составить перечень всех возможных в ходе игры ситуаций и предусмотреть свое решение для каждой из них. В принципе (если не практически) это возможно для любой игры. Если такая система решений будет принята, это будет означать, что игрок выбрал определенную стратегию.
Игрок, выбравший стратегию, может теперь не участвовать в игре лично, а заменить свое участие списком правил, которые за него будет применять какое-либо незаинтересованное лицо (судья). Стратегия может быть также задана машине-автомату в виде определенной программы. Именно так в настоящее время играют в шахматы ЭВМ. Чтобы понятие «стратегии» имело смысл, необходимо наличие в игре личных ходов; в играх, состоящих из одних случайных ходов, стратегии отсутствуют.
В зависимости от числа возможных стратегий игры делятся на «конечные» и «бесконечные». Конечной называется игра, в которой у каждого игрока имеется только конечное число стратегий. Конечная игра, в которой игрок А имеет m стратегий, а игрок В - n стратегий, называется игрой mxn.
Рассмотрим игру mxn двух игроков А и В («мы» и «противник»). Будем обозначать наши стратегии A 1 , А 2 , …, А m стратегии противника B 1 , В 2 , …, В n . Пусть каждая сторона выбрала определенную стратегию; для нас это будет A i , для противника B j . Если игра состоит только из личных ходов, то выбор стратегий A i , B j однозначно определяет исход игры - наш выигрыш. Обозначим его а ij . Если игра содержит, кроме личных, случайные ходы, то выигрыш при паре стратегий A i , B j есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае естественной оценкой ожидаемого выигрыша является его среднее значение (математическое ожидание). Мы будем обозначать одним и тем же знаком как сам выигрыш (в игре без случайных ходов), так и его среднее значение (в игре со случайными ходами).
Пусть нам известны значения а ij выигрыша (или среднего выигрыша) при каждой паре стратегий. Значения можно записать в виде прямоугольной таблицы (матрицы), строки которой соответствуют нашим стратегиям (A i), а столбцы - стратегиям противника (B j). Такая таблица называется платежной матрицей или просто матрицей игры. Матрица игры mxn представлена на рис. 1.
Рис. 1. Матрица mxn
Сокращенно мы будем обозначать матрицу игры ‖а ij ‖. Рассмотрим несколько элементарных примеров игр.
Пример 1. Два игрока A и В, не глядя друг на друга, кладут на стол по монете вверх гербом или решкой, по своему усмотрению. Если игроки выбрали одинаковые стороны (у обоих герб или у обоих решка), то игрок А забирает обе монеты; иначе их забирает игрок В. Требуется проанализировать игру и составить ее матрицу. Решение. Игра состоит только из двух ходов: наш ход и ход противника, оба личные. Игра не принадлежит к играм с полной информацией, так как в момент хода выполняющий его игрок не знает, что сделал другой. Так как у каждого из игроков имеется только один личный ход, то стратегия игрока представляет собой выбор при этом единственном личном ходе.
У нас две стратегии: А 1 - выбирать герб и А 2 - выбирать решку; у противника такие же две стратегии: В 1 - герб и В 2 - решка. Таким образом, данная игра есть игра 2×2. Будем считать выигрыш монеты за +1. Матрица игры:
На примере этой игры, как она ни элементарна, можно уяснить себе некоторые существенные идеи теории игр. Предположим сначала, что данная игра выполняется только один раз. Тогда, очевидно, бессмысленно говорить о каких-либо «стратегиях» игроков, более разумных, чем другие. Каждый из игроков с одинаковым основанием может принять любое решение. Однако при повторении игры положение меняется.
Действительно, допустим, что мы (игрок А) выбрали себе какую-то стратегию (скажем, А 1) и придерживаемся ее. Тогда уже по результатам первых нескольких ходов противник догадается о нашей стратегии и будет на нее отвечать наименее выгодным для нас образом, т.е. выбирать решку. Нам явно невыгодно всегда применять какую-то одну стратегию; чтобы не оказаться в проигрыше, мы должны иногда выбирать герб, иногда - решку. Однако, если мы будем чередовать гербы и решки в какой-то определенной последовательности (например, через один), противник тоже может догадаться об этом и ответить на эту стратегию наихудшим для нас образом. Очевидно, надежным способом, гарантирующим, что противник не будет знать нашей стратегии, будет такая организация выбора при каждом ходе, когда мы его сами наперед не знаем (это можно обеспечить, например, подбрасыванием монеты). Таким образом, мы путем интуитивных рассуждений подходим к одному из существенных понятий теории игр – к понятию «смешанной стратегии», т.е. такой, когда «чистые» стратегии - в данном случае A 1 и А 2 – чередуются случайно с определенными частотами. В данном примере из соображений симметрии заранее ясно, что стратегии A 1 и А 2 должны чередоваться с одинаковой частотой; в более сложных играх решение может быть далеко не тривиальным.
Пример 2. Игроки А и В одновременно и независимо друг от друга записывают каждый одно из трех чисел: 1, 2 или 3. Если сумма написанных чисел четная, то В платит А эту сумму в рублях; если она нечетная, то, наоборот, А платит В эту сумму. Требуется проанализировать игру и составить ее матрицу.
Решение. Игра состоит из двух ходов; оба - личные. У нас (А) три стратегии: А 1 - писать 1; А 2 - писать 2; А 3 - писать 3. У противника (В) - те же три стратегии. Игра представляет собой игру 3×3:
Очевидно, как и в предыдущем случае, на любую выбранную нами стратегию противник может ответить наихудшим для нас образом. Действительно, если мы выберем, например, стратегию А 1 , противник будет всегда отвечать на нее стратегией В 2 ; на стратегию А 2 - стратегией В 3 ; на стратегию А 3 - стратегией В 2 ; таким образом, любой выбор определенной стратегии неизбежно приведет нас к проигрышу (не нужно, впрочем, забывать, что в столь же бедственной положении находится и противник). Решение этой игры (т.е. совокупность наивыгоднейших стратегий обоих игроков) будет дано в § 5.
Пример 3. В нашем распоряжении имеются три вида вооружения: А 1 , А 2 , А 3 ; у противника - три вида самолетов: B 1 , В 2 , В 3 . Наша задача - поразить самолет; задача противника- сохранить его непораженным. При применении вооружения А 1 самолеты B 1 , В 2 , В 3 поражаются соответственно с вероятностями 0,9, 0,4 и 0,2; при вооружении А 2 - с вероятностями 0,3, 0,6 и 0,8; при вооружении А 3 - с вероятностями 0,5, 0,7 и 0,2. Требуется сформулировать ситуацию в терминах теории игр.
Решение. Ситуация может рассматриваться как игра 3×3 с двумя личными ходами и одним случайным. Наш личный ход - выбор типа вооружения; личный ход противника - выбор самолета для участия в бою. Случайный ход - применение вооружения; этот ход может закончиться поражением или непоражением самолета. Наш выигрыш равен единице, если самолет поражен, и равен нулю в противном случае. Нашими стратегиями являются три варианта вооружения; стратегиями противника - три варианта самолетов. Среднее значение выигрыша при каждой заданной паре стратегий есть не что иное, как вероятность поражения данного самолета данным оружием. Матрица игры:
Целью теории игр является выработка рекомендаций для разумного поведения игроков в конфликтных ситуациях, т.е. определение «оптимальной стратегии» каждого из них. Оптимальной стратегией игрока в теории игр называется такая стратегия, которая при многократном повторении игры обеспечивает данному игроку максимально возможный средний выигрыш (или минимально возможный средний проигрыш). При выборе этой стратегии основой рассуждений является предположение, что противник является по меньшей мере таким же разумным, как и мы сами, и делает все для того, чтобы помешать нам добиться своей цели.
В теории игр все рекомендации вырабатывают, исходя именно из этих принципов; следовательно, в ней не учитываются элементы риска, неизбежно присутствующие в каждой реальной стратегии, а также возможные просчеты и ошибки каждого из игроков. Теория игр, как и всякая математическая модель сложного явления, имеет свои ограничения. Важнейшим из них является то, что выигрыш искусственно сводится к одному единственному числу. В большинстве практических конфликтных ситуаций при выработке разумной стратегии приходится принимать во внимание не один, а несколько численных параметров - критериев успешности мероприятия. Стратегия, являющаяся оптимальной по одному критерию, необязательно будет оптимальной по другим. Однако, сознавая эти ограничения и поэтому не придерживаясь слепо рекомендаций, получаемых игровыми методами, можно все же разумно использовать математический аппарат теории игр для выработки если не в точности «оптимальной», то, во всяком случае, «приемлемой» стратегии.
§ 2. Нижняя и верхняя цена игры. Принцип «минимакса»
Рассмотрим игру mxn с матрицей, как на рис. 1. Будем обозначать буквой i номер нашей стратегии; буквой j- номер стратегии противника. Поставим себе задачу: определить свою оптимальную стратегию. Проанализируем последовательно каждую из наших стратегий, начиная с A 1 .
Выбирая стратегию А i , мы всегда должны рассчитывать на то, что противник ответит на нее той из стратегий В j , для которой наш выигрыш а ij минимален. Определим это значение выигрыша, т.е. минимальное из чисел а ij в i -й строке. Обозначим его α i:
Здесь знаком min (минимум по j) обозначено минимальное из значений данного параметра при всех возможных j. Выпишем числа α i ; рядом с матрицей справа в виде добавочного столбца:
Выбирая какую-либо стратегию A i , мы должны рассчитывать на то, что в результате разумных действий противника мы не выиграем больше чем α i . Естественно, что, действуя наиболее осторожно и рассчитывая на наиболее разумного противника (т.е. избегая всякого риска), мы должны остановиться на той стратегии для которой число α i является максимальным. Обозначим это максимальное значение α:
или, принимая во внимание формулу (2.1),
Величина α называется нижней ценой игры, иначе - максиминным выигрышем или просто максимином. Число α лежит в определенной строчке матрицы; та стратегия игрока А, которая соответствует этой строчке, называется максиминной стратегией. Очевидно, если мы будем придерживаться максиминной стратегии, то нам при любом поведении противника гарантирован выигрыш, во всяком случае не меньший α. Поэтому величина α и называется «нижней ценой игры». Это - тот гарантированный минимум, который мы можем себе обеспечить, придерживаясь наиболее осторожной («перестраховочной») стратегии.
Очевидно, аналогичное рассуждение можно провести и за противника В. Так как противник заинтересован в том, чтобы обратить наш выигрыш в минимум, он должен просмотреть каждую свою стратегию с точки зрения максимального выигрыша при этой стратегии. Поэтому внизу матрицы мы выпишем максимальные значения по каждому столбцу:
и найдем минимальное из β j:
Величина β называется верхней ценой игры, иначе - «минимаксом». Соответствующая минимаксному выигрышу стратегия противника называется его «минимаксной стратегией». Придерживаясь своей наиболее осторожной минимаксной стратегии, противник гарантирует себе следующее: что бы мы ни предприняли против него, он во всяком случае проиграет сумму, не большую чем β. Принцип осторожности, диктующий игрокам выбор соответствующих стратегий (максиминной и минимаксной), в теории игр и ее приложениях часто называют «принципом минимакса». Наиболее осторожные максиминную и минимаксную стратегии игроков иногда обозначают общим термином «минимаксные стратегии».
В качестве примеров определим нижнюю и верхнюю цену игры и минимаксные стратегии для примеров 1, 2 и 3 § 1.
Пример 1. В примере 1 § 1 дана игра со следующей матрицей:
Так как величины α i и β j постоянны и равны соответственно –1 и +1, нижняя и верхняя цена игры также равны –1 и +1: α = –1, β = +1. Любая стратегия игрока А является его максиминной, а любая стратегия игрока В - его минимаксной стратегией. Вывод тривиален: придерживаясь любой из своих стратегий, игрок А может гарантировать, что он проиграет не более 1; то же может гарантировать и игрок В.
Пример 2. В примере 2 § 1 дана игра с матрицей:
Нижняя цена игры α = –3; верхняя цена игры β = 4. Наша максиминная стратегия есть А 1 ; применяя ее систематически, мы можем твердо рассчитывать выиграть не менее –3 (проиграть не более 3). Минимаксная стратегия противника есть любая из стратегий В 1 и В 2 ; применяя их систематически, он, во всяком случае, может гарантировать, что проиграет не более 4. Если мы отступим от своей максиминной стратегии (например, выберем стратегию А 2), противник может нас «наказать» за это, применив стратегию В 3 и сведя наш выигрыш к –5; равным образом и отступление противника от своей минимаксной стратегии может увеличить его проигрыш до 6.
Пример 3. В примере 3 § 1 дана игра с матрицей:
Нижняя цена игры α = 0,3; верхняя ценя игры β = 0,7. Наша наиболее осторожная (максиминная) стратегия есть А 2 ; пользуясь вооружением А 2 , мы гарантируем, что будем поражать самолет в среднем не менее чем в 0,3 всех случаев. Наиболее осторожной (минимаксной) стратегией противника является В 2 ; применяя этот самолет, противник может быть уверен, что он будет поражаться не более чем в 0,7 всех случаев.
На последнем примере удобно продемонстрировать одно важное свойство минимаксных стратегий – их неустойчивость. Пусть мы применяем свою наиболее осторожную (максиминную) стратегию А 2 , а противник - свою наиболее осторожную (минимаксную) стратегию В 2 . До тех пор, пока оба противника придерживаются этих стратегий, средний выигрыш равен 0,6; он больше нижней, но меньше верхней цены игры. Теперь допустим, что противнику стало известно, что мы применяем стратегию А 2 ; он немедленно ответит на нее стратегией В 1 и сведет выигрыш к 0,3. В свою очередь, на стратегию B 1 у нас есть хороший ответ: стратегия A 1 , дающая нам выигрыш 0,9, и т.д.
Таким образом, положение, при котором оба игрока пользуются своими минимаксными стратегиями, является неустойчивым и может быть нарушено поступившими сведениями о стратегии противной стороны. Однако существуют некоторые игры, для которых минимаксные стратегии являются устойчивыми. Это те игры, для которых нижняя цена равна верхней: α = β. Если нижняя цена игры равна верхней, то их общее значение называется чистой ценой игры (иногда просто ценой игры), мы его будем обозначать буквой ν.
Рассмотрим пример. Пусть игра 4×4 задана матрицей:
Найдем нижнюю цену игры: α = 0,6. Найдем верхнюю цену игры: β = 0,6. Они оказались одинаковыми, следовательно, у игры есть чистая цена, равная α = β = ν = 0,6. Элемент 0,6, выделенный в платежной матрице, является одновременно минимальным в своей строке и максимальным в своем столбце. В геометрии точку на поверхности, обладающую аналогичным свойством (одновременный минимум по одной координате и максимум по другой), называют седловой точкой, по аналогии этот термин применяется и в теории игр. Элемент матрицы, обладающий этим свойством, называется седловой точкой матрицы, а про игру говорят, что она имеет седловую точку.
Седловой точке соответствует пара минимаксных стратегий (в данном примере А 3 и В 2). Эти стратегии называются оптимальными, а их совокупность - решением игры. Решение игры обладает следующим замечательным свойством. Если один из игроков (например А) придерживается своей оптимальной стратегии, а другой игрок (В) будет любым способом отклоняться от своей оптимальной стратегии, то для игрока, допустившего отклонение, это никогда не может оказаться выгодным, такое отклонение игрока В может в лучшем случае оставить выигрыш неизменным, а в худшем случае - увеличить его. Наоборот, если В придерживается своей оптимальной стратегии, а А отклоняется от своей, то это ни в коем случае не может быть выгодным для А.
Это утверждение легко проверить на примере рассматриваемой игры с седловой точкой. Мы видим, что в случае игры с седловой точкой минимаксные стратегии обладают своеобразной «устойчивостью»: если одна сторона придерживается своей минимаксной стратегии, то для другой может быть только невыгодным отклоняться от своей. Заметим, что в этом случае наличие у любого игрока сведений о том, что противник избрал свою оптимальную стратегию, не может изменить собственного поведения игрока: если он не хочет действовать против своих же интересов, он должен придерживаться своей оптимальной стратегии. Пара оптимальных стратегий в игре с седловой точкой является как бы «положением равновесия»: любое отклонение от оптимальной стратегии приводит отклоняющегося игрока к невыгодным последствиям, вынуждающим его вернуться в исходное положение.
Итак, для каждой игры с седловой точкой существует решение, определяющее пару оптимальных стратегий обеих сторон, отличающуюся следующими свойствами.
1) Если обе стороны придерживаются своих оптимальных стратегий, то средний выигрыш равен чистой цене игры ν, одновременно являющейся ее нижней и верхней ценой.
2) Если одна из сторон придерживается своей оптимальной стратегии, а другая отклоняется от своей, то от этого отклоняющаяся сторона может только потерять и ни в коем случае не может увеличить свой выигрыш.
Класс игр, имеющих седловую точку, представляет большой интерес как с теоретической, так и с практической точки зрения. В теории игр доказывается, что, в частности, каждая игра с полной информацией имеет седловую точку, и, следовательно, каждая такая игра имеет решение, т.е. существует пара оптимальных стратегий той и другой стороны, дающая средний выигрыш, равный цене игры. Если игра с полной информацией состоит только из личных ходов, то при применении каждой стороной своей оптимальной стратегии она должна всегда кончаться вполне определенным исходом, а именно, выигрышем, в точности равным цене игры.
В качестве примера игры с полной информацией приведем известную игру с укладыванием монет на круглый стол. Два игрока поочередно кладут одинаковые монеты на круглый стол, выбирая каждый раз произвольное положение центра монеты; взаимное накрывание монет не допускается. Выигрывает тот из игроков, кто положит последнюю монету (когда места для других уже не останется). Очевидно, что исход этой игры всегда предрешен, и существует вполне определенная стратегия, обеспечивающая достоверный выигрыш тому из игроков, который кладет монету первым. А именно, он должен первый раз положить монету в центр стола, а далее на каждый ход противника отвечать симметричным ходом. При этом второй игрок может вести себя как угодно, не изменяя предрешенного результата игры. Поэтому данная игра имеет смысл только для игроков, не знающих оптимальной стратегии. Аналогично дело обстоит с шахматами и другими играми с полной информацией; любая из таких игр обладает седловой точкой и решением, указывающим каждому из игроков его оптимальную стратегию; решение шахматной игры не найдено только потому, что число комбинаций возможных ходов в шахматах слишком велико, чтобы можно было построить платежную матрицу и найти в ней седловую точку.
§ 3. Чистые и смешанные стратегии. Решение игры в смешанных стратегиях
Среди конечных игр, имеющих практическое значение, сравнительно редко встречаются игры с седловой точкой; более типичным является случай, когда нижняя и верхняя цена игры различны. Анализируя матрицы таких игр, мы пришли к заключению, что если каждому игроку предоставлен выбор одной-единственной стратегии, то в расчете на разумно действующего противника этот выбор должен определяться принципом минимакса. Придерживаясь своей максиминной стратегии, мы при любом поведении противника заведомо гарантируем себе выигрыш, равный нижней цене игры α. Возникает естественный вопрос: нельзя ли гарантировать себе средний выигрыш, больший α, если применять не одну единственную «чистую» стратегию, а чередовать случайным образом несколько стратегий? Такие комбинированные стратегии, состоящие в применении нескольких чистых стратегий, чередующихся по случайному закону с определенным соотношением частот, в теории игр называются смешанными стратегиями.
Очевидно, каждая чистая стратегия является частным случаем смешанной, в которой все стратегии, кроме одной, применяются с нулевыми частотами, а данная - с частотой 1. Оказывается, что, применяя не только чистые, но и смешанные стратегии, можно для каждой конечной игры получить решение, т.е. пару таких (в общем случае смешанных) стратегий, что при применении их обоими игроками выигрыш будет равен цене игры, а при любом одностороннем отклонении от оптимальной стратегии выигрыш может измениться только в сторону, невыгодную для отклоняющегося.
Высказанное утверждение составляет содержание так называемой основной теоремы теории игр. Эта теорема была впервые доказана фон Нейманом в 1928 г. Известные доказательства теоремы сравнительно сложны; поэтому приведем только ее формулировку.
Каждая конечная игра имеет, по крайней мере, одно решение (возможно, в области смешанных стратегий).
Выигрыш, получаемый в результате решения, называется ценой игры. Из основной теоремы следует, что каждая конечная игра имеет цену. Очевидно, что цена игры ν всегда лежит между нижней ценой игры α и верхней ценой игры β:
(3.1) α ≤ ν ≤ β
Действительно, α есть максимальный гарантированный выигрыш, который мы можем себе обеспечить, применяя только свои чистые стратегии. Так как смешанные стратегии включают в себя в качестве частного случая и все чистые, то, допуская, кроме чистых, еще и смешанные стратегии, мы, во всяком случае, не ухудшаем своих возможностей; следовательно, ν ≥ α. Аналогично, рассматривая возможности противника, покажем, что ν ≤ β, откуда следует доказываемое неравенство (3.1).
Введем специальное обозначение для смешанных стратегий. Если, например, наша смешанная стратегия состоит в применении стратегий А 1 , А 2 , А 3 с частотами p 1 , р 2 , р 3 , причем p 1 + р 2 + р 3 = 1, будем обозначать эту стратегию
Аналогично смешанную стратегию противника будем обозначать:
где q 1 , q 2 , q 3 - частоты, в которых смешиваются стратегии B 1 , В 2 , В 3 ; q 1 + q 2 + q 3 = 1.
Предположим, что нами найдено решение игры, состоящее из двух оптимальных смешанных стратегий S A *, S B *. В общем случае не все чистые стратегии, доступные данному игроку, входят в его оптимальную смешанную стратегию, а только некоторые. Будем называть стратегии, входящие в оптимальную смешанную стратегию игрока, его «полезными» стратегиями. Оказывается, что решение игры обладает еще одним замечательным свойством: если один из игроков придерживается своей оптимальной смешанной стратегии S A * (S B *), то выигрыш остается неизменным и равным цене игры ν, независимо от того, что делает другой игрок, если он только не выходит за пределы своих «полезных» стратегий. Он, например, может пользоваться любой из своих «полезных» стратегий в чистом виде, а также может смешивать их в любых пропорциях.
§ 4. Элементарные методы решения игр. Игры 2 x 2 и 2 x n
Если игра mxn не имеет седловой точки, то нахождение решения есть вообще довольно трудная задача, особенно при больших m и n. Иногда эту задачу удается упростить, если предварительно уменьшить число стратегий путем вычеркивания некоторых излишних. Излишние стратегии бывают а) дублирующие и б) заведомо невыгодные. Рассмотрим, например, игру с матрицей:
Нетрудно убедиться, что стратегия А 3 в точности повторяет («дублирует») стратегию А 1 , поэтому любую из этих двух стратегий можно вычеркнуть. Далее, сравнивая строки A 1 и А 2 , видим, что каждый элемент строки А 2 меньше (или равен) соответствующего элемента строки A 1 . Очевидно, что мы никогда не должны пользоваться стратегией А2, она является заведомо невыгодной. Вычеркивая А 3 и А 2 , приводим матрицу к более простому виду. Далее замечаем, что для противника стратегия В 3 заведомо невыгодна; вычеркивая ее, приводим матрицу к окончательному виду:
Таким образом, игра 4×4 вычеркиванием дублирующих и заведомо невыгодных стратегий сведена к игре 2×3.
Процедура вычеркивания дублирующих и заведомо невыгодных стратегий всегда должна предшествовать решению игры. Наиболее простыми случаями конечных игр, которые всегда можно решить элементарными способами, являются игры 2×2 и 2xn.
Рассмотрим игру 2×2 с матрицей:
Здесь могут встретиться два случая: 1) игра имеет седловую точку; 2) игра не имеет седловой точки. В первом случае решение очевидно: это пара стратегий, пересекающихся в седловой точке. Заметим кстати, что в игре 2×2 наличие седловой точки всегда соответствует существованию заведомо невыгодных стратегий, которые должны быть вычеркнуты при предварительном анализе.
Пусть седловой точки нет и, следовательно, нижняя цена игры не равна верхней: α ≠ β. Требуется найти оптимальную смешанную стратегию игрока А:
Она отличается тем свойством, что, каковы бы ни были действия противника (если только он не выходит за пределы своих «полезных» стратегий), выигрыш будет равен цене игры ν. В игре 2×2 обе стратегии противника являются «полезными», - иначе игра имела бы решение в области чистых стратегий (седловую точку). Значит, если мы придерживаемся своей оптимальной стратегии (4.1), то противник может пользоваться любой из своих чистых стратегий B 1 , В 2 , не изменяя среднего выигрыша ν. Отсюда имеем два уравнения:
из которых, принимая во внимание, что p 1 + p 2 = 1, получим:
Цену игры ν найдем, подставляя значения р 1 , р 2 в любое из уравнений (4.2).
Если цена игры известна, то для определения оптимальной стратегии противника
достаточно одного уравнения, например:
откуда, учитывая, что q 1 + q 2 = 1, имеем:
Пример 1. Найдем решение игры 2×2, рассмотренной в примере 1 § 1, с матрицей:
Игра не имеет седловой точки (α = –1; β = +1), и, следовательно, решение должно лежать в области смешанных стратегий:
Нужно найти p 1 , р 2 , q 1 и q 2 . Для p 1 имеем уравнение
1*p 1 + (–1)(1 – p 1) = (–1)p 1 + 1(1 – p 1)
откуда p 1 = 1/2, p 2 = 1/2.
Аналогично найдем: q 1 = 1/2, q 2 = 1/2, ν = 0.
Следовательно, оптимальная стратегия для каждого из игроков состоит в том, чтобы случайным образом чередовать обе свои чистые стратегии, пользуясь одинаково часто каждой из них; при этом средний выигрыш будет равен нулю.
Полученный вывод был достаточно ясен заранее. В следующем примере мы рассмотрим более сложную игру, решение которой не является столь очевидным. Пример представляет собой элементарный образец игр, известных под названием игр с «обманом» или «введением в заблуждение». На практике в конфликтных ситуациях часто применяются разные способы введения противника в заблуждение (дезинформация, расстановка ложных целей и т.д.). Пример, несмотря на свою простоту, довольно поучителен.
Пример 2. Игра состоит в следующем. Имеются две карты: туз и двойка. Игрок А наугад вынимает одну из них; В не видит, какую карту он вынул. Если А вынул туза, он заявляет: «у меня туз», и требует у противника 1 рубль. Если А вынул двойку, то он может либо А 1) сказать «у меня туз» и потребовать у противника 1 рубль, либо А 2) признаться, что у него двойка, и уплатить противнику 1 рубль.
Противник, если ему добровольно платят 1 рубль, может только принять его. Если же у него потребуют 1 рубль, то он может либо В 1) поверить игроку А, что у него туз, и отдать ему 1 рубль, либо В 2) потребовать проверки с тем, чтобы убедиться, верно ли утверждение А. Если в результате проверки окажется, что у А действительно туз, В должен уплатить А 2 рубля. Если же окажется, что А обманывает и у него двойка, игрок А уплачивает игроку В 2 рубля. Требуется проанализировать игру и найти оптимальную стратегию каждого из игроков.
Решение. Игра имеет сравнительно сложную структуру; она состоит из одного обязательного случайного хода - выбора игроком А одной из двух карт - и двух личных ходов, которые, однако, необязательно осуществляются. Действительно, если А вынул туза, то он не делает никакого личного хода: ему предоставлена только одна возможность - потребовать 1 рубль, что он и делает. В этом случае личный ход - верить или не верить (т.е. платить или не платить 1 рубль,) - передается игроку В. Если А в результате первого случайного хода получил двойку, то ему предоставляется личный ход: уплатить 1 рубль или попытаться обмануть противника и потребовать 1 рубль (короче: «не обманывать» или «обманывать»). Если А выбирает первое, то В остается только принять 1 рубль; если А выбрал второе, то игроку В предоставляется личный ход: верить или не верить А (т.е. уплатить А 1 рубль или требовать проверки).
Стратегии каждого из игроков представляют собой правила, указывающие, как поступить игроку, когда ему предоставляется личный ход. Очевидно, у А только две стратегии: А 1 - обманывать, А 2 - не обманывать. У В - тоже две стратегии: B 1 - верить, В 2 - не верить. Построим матрицу игры. Для этого вычислим средний выигрыш при каждой комбинации стратегий.
1. А 1 В 1 (А обманывает, В верит). Если А получил туза (вероятность этого ½, то ему не предоставляется личного хода; он требует 1 рубль, и игрок В верит ему; выигрыш А в рублях равен 1. Если А получил двойку (вероятность этого тоже ½), он согласно своей стратегии обманывает и требует 1 рубль; В ему верит и уплачивает; выигрыш А также равен 1. Средний выигрыш: а 11 = ½*1 + ½*1 = 1.
2. А 1 В 2 (А обманывает, В не верит). Если А получил туза, у него нет личного хода; он требует 1 рубль; В согласно своей стратегии не верит и в результате проверки уплачивает 2 рубля (выигрыш А равен +2). Если А получил двойку, он согласно своей стратегии требует 1 рубль; В, согласно своей, не верит; в результате А уплачивает 2 рубля (выигрыш А равен –2). Средний выигрыш равен: а 12 = ½*(+2) + ½*(–2) = 0.
3. A 2 В 1 (А не обманывает, В верит). Если А вынул туза, он требует 1 рубль; В согласно своей стратегии уплачивает; выигрыш А равен +1. Если А вынул двойку, он согласно своей стратегии платит 1 рубль; В остается только принять (выигрыш А равен –1). Средний выигрыш равен: а 21 = ½*(+1) + ½*(–1) = 0.
4. А 2 В 2 (А не обманывает, В не верит). Если А вынул туза, он требует 1 рубль; В проверяет и в результате проверки уплачивает 2 рубля (выигрыш равен +2). Если А вынул двойку, он уплачивает 1 рубль; В остается только принять (выигрыш равен 1). Средний выигрыш равен: а 22 = ½*(+2) + ½*(–1) = ½.
Строим матрицу игры:
Матрица не имеет седловой точки. Нижняя цена игры α = 0, верхняя цена игры β = ½. Найдем решение игры в области смешанных стратегий. Применяя формулу (4.3), получим:
т.е. игрок А должен в одной трети всех случаев пользоваться своей первой стратегией (обманывать), а в двух третях – второй (не обманывать). При этом он будет выигрывать в среднем цену игры ν = 1/3.
Значение ν = 1/3 свидетельствует о том, что в данных условиях игра выгодна для А и невыгодна для В. Пользуясь своей оптимальной стратегией, А всегда может себе обеспечить положительный средний выигрыш. Заметим, что, если бы А пользовался своей наиболее осторожной (максиминной) стратегией (в данном случае обе стратегии A 1 и А 2 являются максиминными), он имел бы средний выигрыш, равный нулю. Таким образом, применение смешанной стратегии дает А возможность реализовать свое преимущество над В, возникающее при данных правилах игры.
Определим оптимальную стратегию В. Имеем: q 1 *1 + q 2 *0 = 1/3, q 1 = 1/3, q 2 = 2/3. Откуда
т.e. игрок В должен в одной трети всех случаев верить А и уплачивать ему 1 рубль без проверки, а в двух третях случаев - проверять. Тогда он будет в среднем на каждую игру проигрывать 1/3. Если бы он пользовался своей минимаксной чистой стратегией В 2 (не верить), он на каждую игру проигрывал бы в среднем 1/2.
Решению игры 2×2 можно дать простую геометрическую интерпретацию. Пусть имеется игра 2×2 с матрицей
Возьмем участок оси абсцисс длиной 1 (рис. 4.1). Левый конец участка (точка с абсциссой х = 0) будет изображать стратегию А 1 ; правый конец участка (х = 1) - стратегию А 2 . Проведем через точки А 1 и А 2 два перпендикуляра к оси абсцисс: ось I –I и ось II–II . На оси I –I будем откладывать выигрыши при стратегии A 1 ; на оси II–II -выигрыши при стратегии А 2 . Рассмотрим стратегию противника B 1 ; она дает две точки на осях I –I и II–II с ординатами соответственно а 11 и а 21 . Проведем через эти точки прямую B 1 B 1 . Очевидно, если мы при стратегии противника B 1 будем применять смешанную стратегию
то наш средний выигрыш, равный в этом случае а 11 р 1 + а 21 р 2 , изобразится точкой М на прямой В 1 B 1 ; абсцисса этой точки равна р 2 . Прямую В 1 В 1 , изображающую выигрыш при стратегии В 1 , будем условно называть «стратегией В 1 ».
Очевидно, точно таким же способом может быть построена и стратегия В 2 (рис. 4.2).
Нам нужно найти оптимальную стратегию S A *, т. е. такую, для которой минимальный выигрыш (при любом поведении В) обращался бы в максимум. Для этого построим нижнюю границу выигрыша при стратегиях В 1 , В 2 , т.е. ломаную B 1 NB 2 , отмеченную на рис. 4.2 жирной линией. Эта нижняя граница будет выражать минимальный выигрыш игрока А при любых его смешанных стратегиях; точка N, в которой этот минимальный выигрыш достигает максимума, и определяет решение и цену игры. Нетрудно убедиться, что ордината точки N есть цена игры ν, а ее абсцисса равна р 2 - частоте применения стратегии А 2 в оптимальной смешанной стратегии S A *.
В нашем случае решение игры определялось точкой пересечения стратегий. Однако это не всегда будет так; на рис. 4.3 показан случай, когда, несмотря на наличие пересечения стратегий, решение дает для обоих игроков чистые стратегии (A 2 и В 2), а цена игры ν = а 22 . В данном случае матрица имеет седловую точку, и стратегия А 1 является заведомо невыгодной, т.к. при любой чистой стратегии противника она дает меньший выигрыш, чем А 2 .
В случае, когда заведомо невыгодная стратегия имеется у противника, геометрическая интерпретация имеет вид, представленный на рис. 4.4.
В данном случае нижняя граница выигрыша совпадает со стратегией В 1 , стратегия В 2 для противника является заведомо невыгодной.
Геометрическая интерпретация дает возможность представить наглядно также нижнюю и верхнюю цены игры (рис. 4.5).
Для иллюстрации построим геометрические интерпретации игр 2×2, рассмотренных в примерах 1 и 2 (рис. 4.6 и 4.7).
Мы убедились, что любая игра 2×2 может быть решена элементарными приемами. Совершенно аналогично может быть решена любая игра 2xn. где у нас имеются всего две стратегии, а у противника - произвольное число.
Пусть мы располагаем двумя стратегиями: А 1 , А 2 , а противник - n стратегиями: В 1 , В 2 , …, В n . Матрица ‖a ij ‖ задана; она состоит из двух строк и n столбцов. Аналогично случаю двух стратегий дадим задаче геометрическую интерпретацию; n стратегий противника изобразятся n прямыми (рис. 4.8). Строим нижнюю границу выигрыша (ломаную B 1 MNB 2) и находим на ней точку N с максимальной ординатой. Эта точка дает решение игры (стратегию ) ордината точки N равна цене игры ν, а абсцисса равна частоте р 2 стратегии A 2 .
В данном случае оптимальная стратегия противника получается применением смеси двух «полезных» стратегий: В 2 и В 4 , пересекающихся в точке N. Стратегия В 3 является заведомо невыгодной, а стратегия B 1 - невыгодной при оптимальной стратегии S A *. Если А будет придерживаться своей оптимальной стратегии, то выигрыш не изменится, какой бы из своих «полезных» стратегий ни пользовался В, однако, он изменится, если В перейдет к стратегиям B 1 или В 3 . В теории игр доказывается, что у любой конечной игры mxn имеется решение, в котором число «полезных» стратегий той и другой стороны не превосходит наименьшего из двух чисел m и n. В частности, из этого следует, что у игры 2xm всегда имеется решение, в котором с той и другой стороны участвует не более двух «полезных» стратегий.
Пользуясь геометрической интерпретацией, можно дать простой способ решения любой игры 2xm. Непосредственно по чертежу находим пару «полезных» стратегий противника B j и В k , пересекающиеся в точке N (если в точке N пересекается более двух стратегий, берем любые две из них). Мы знаем, что если игрок А придерживается своей оптимальной стратегии, то выигрыш не зависит от того, в какой пропорции применяет В свои «полезные» стратегии, следовательно,
Из этих уравнений и условия р 2 = 1 – p 1 , находим р1, р2 и цену игры ν. Зная цену игры, можно сразу определить оптимальную стратегию игрока В. Для этого решается, например, уравнение: q j a 1 j + q k a 1 k = ν, где q j + q k = 1. В случае, когда мы располагаем m стратегиями, а противник - всего двумя, очевидно, задача решается совершенно аналогичным способом; достаточно заметить, что, изменяя знак выигрыша на обратный, можно превратить игрока А из «выигрывающего» в «проигрывающего». Можно решить игру и без перемены знака выигрыша; тогда задача решается непосредственно для В, но строится не нижняя, а верхняя граница выигрыша (рис. 4.9). На границе ищется точка N с минимальной ординатой, которая и есть цена игры ν.
Рассмотрим и решим несколько примеров игр 2×2 и 2xm, являющихся упрощенными образчиками игр, имеющих практическое значение.
Пример 3. Сторона А посылает в район расположения противника В два бомбардировщика I и II ; I летит спереди, II – сзади. Один из бомбардировщиков – заранее неизвестно какой – должен нести бомбу, другой выполняет функцию сопровождения. В районе противника бомбардировщики подвергаются нападению истребителя стороны В. Бомбардировщики вооружены пушками различной скорострельности. Если истребитель атакует задний бомбардировщик II , то по нему ведут огонь пушки только этого бомбардировщика; если же он атакует передний бомбардировщик, то по нему ведут огонь пушки обоих бомбардировщиков. Вероятность поражения истребителя в первом случае 0,3, во втором 0,7.
Если истребитель не сбит оборонительным огнем бомбардировщиков, то он поражает выбранную им цель с вероятностью 0,6. Задача бомбардировщиков – донести бомбу до цели; задача истребителя – воспрепятствовать этому, т.е. сбить бомбардировщик-носитель. Требуется выбрать оптимальные стратегии сторон:
а) для стороны А: какой бомбардировщик сделать носителем?
б) для стороны В: какой бомбардировщик атаковать?
Решение. Имеем простой случай игры 2×2; выигрыш- вероятность непоражения носителя. Наши стратегии: А 1 - носитель - бомбардировщик I ; А 2 - носитель - бомбардировщик II . Стратегии противника: В 1 - атакуется бомбардировщик I ; В 2 -атакуется бомбардировщик II . Составим матрицу игры, т.е. найдем средний выигрыш при каждой комбинации стратегий.
1. А 1 В 1 (носитель I , атакуется I ). Носитель не будет поражен, если бомбардировщики собьют истребитель, или не собьют, но он не поразит свою цель: а 11 = 0,7 + 0,3 * 0,4 = 0,82.
2. А 2 В 1 (носитель II , атакуется I ). a 21 = 1
3. А 1 В 2 (носитель I , атакуется II ). A 12 = 1
4. А 2 В 2 (носитель II , атакуется II ). A 22 = 0,3 + 0,7*0,4 = 0,58
Матрица игры имеет вид:
Нижняя цена игры 0,82; верхняя цена 1. Матрица не имеет седловой точки; решение ищем в области смешанных стратегий. Имеем:
p 1 *0,82 + p 2 *1 = ν
p 1 *1 + p 2 *0,58 = ν
p 1 = 0,7; p 2 = 0,3
Наша оптимальная стратегия есть т. е. в качестве носителя нужно чаще выбирать I , чем II . Цена игры равна ν = 0,874. Зная ν, определяем q 1 и q 2 - частоты стратегий В 1 и В 2 в оптимальной стратегии противника S B *. Имеем: q 1 *0,82 + q 2 *1 = 0,874 и q 2 = 1 – q 1 , откуда q 1 = 0,7; q 2 = 0,3, т. е. оптимальная стратегия противника есть .
Пример 4. Сторона А нападает на объект, сторона В - обороняет его. У стороны А - два самолета; у стороны В - три зенитных орудия. Каждый самолет является носителем мощного поражающего средства; для того чтобы объект был поражен, достаточно, чтобы к нему прорвался хотя бы один самолет. Самолеты стороны А могут выбирать для подхода к объекту любое из трех направлений: I , II , III (рис. 4.10). Противник (сторона В) может разместить любое из своих орудий на любом направлении; при этом каждое орудие простреливает только область пространства, относящуюся к данному направлению, и не простреливает соседние направления. Каждое орудие может обстрелять только один самолет; обстрелянный самолет поражается с вероятностью 1. Сторона А не знает, где размещены орудия; сторона В не знает, откуда прилетят самолеты. Задача стороны А - поразить объект; задача стороны В - не допустить его поражения. Найти решение игры.
Решение. Игра представляет собой игру 2×3. Выигрыш - вероятность поражения объекта. Наши возможные стратегии: А 1 - послать по одному самолету на два различных направления. А 2 - послать оба самолета по одному направлению. Стратегии противника: В 1 - поставить по одному орудию на каждое направление; В 2 - поставить два орудия на одно направление и одно - на другое; В 3 - поставить все три орудия на одно направление. Составляем матрицу игры.
1. А 1 В 1 (самолеты летят по разным направлениям; орудия расставлены по одному). Очевидно, при этом ни один самолет не прорвется к объекту: а 11 = 0.
2. А 2 В 1 (самолеты летят вместе по одному направлению; орудия расставлены по одному). Очевидно, при этом один самолет пройдет к объекту необстрелянным: а 21 = 1.
3. А 1 В 2 (самолеты летят по одному; противник защищает два направления и оставляет незащищенным третье). Вероятность того, что хотя бы один самолет прорвется к объекту, равна вероятности того, что один из них выберет незащищенное направление: а 12 = 2/3.
4. А 2 В 2 (самолеты летят вместе по одному направлению; противник защищает одно направление двумя орудиями и одно - одним, т. е. фактически защищает одно направление и оставляет незащищенным два). Вероятность того, что хотя бы один самолет прорвется к объекту, равна вероятности выбора парой самолетов фактически незащищенного направления: а 22 = 2/3.
5. А 1 В 3 (самолеты летят по одному; противник защищает тремя орудиями только одно направление): а 13 = 1.
6. А 2 В 3 (самолеты летят оба вместе; противник защищает тремя орудиями только одно направление). Чтобы объект был поражен, самолеты должны выбрать незащищенное направление: а 23 = 2/3.
Матрица игры:
Из матрицы видно, что стратегия В 3 является заведомо невыгодной по сравнению с В 2 (это можно было решить и заранее). Вычеркиванием стратегии В 3 игра сводится к игре 2×2:
Матрица имеет седловую точку: нижняя цена игры 2/3 совпадает с верхней. Одновременно замечаем, что для нас (А) стратегия A 1 является заведомо невыгодной. Вывод: обе стороны А и В должны пользоваться всегда своими чистыми стратегиями А 2 и В 2 , т.е. мы должны посылать самолеты по 2, выбирая случайным образом направление, по которому посылается пара; противник должен ставить орудия так: два - на одно направление, одно- на другое, причем выбор этих направлений также должен производиться случайно (здесь, как мы видим, уже «чистые стратегии» включают элемент случайности). Применяя эти оптимальные стратегии, мы всегда будем получать постоянный средний выигрыш 2/3 (т.е. объект будет поражаться с вероятностью 2/3). Заметим, что найденное решение игры не является единственным; помимо решения в чистых стратегиях, существует целый участок смешанных стратегий игрока А, являющихся оптимальными, от р 1 = 0 до р 1 = 1/3 (рис. 4.11).
Легко, например, убедиться непосредственно, что тот же средний выигрыш 2/3 получится, если мы будем применять свои стратегии А 1 и А 2 в пропорции 1/3 и 2/3.
Пример 5. Те же условия, что в предыдущем примере, но для нас возможны четыре направления удара, а противник располагает четырьмя орудиями.
Решение. У нас по-прежнему две возможные стратегии: А 1 - посылать самолеты по одному, А 2 - посылать два самолета вместе. У противника пять возможных стратегий: В 1 - ставить по одному орудию на каждое направление; В 2 - ставить по два орудия на два различных направления; В 3 - ставить два орудия на одно направление и по одному - на два других; В 4 -ставить три орудия на одно направление и одно - на другое; В 5 - ставить все четыре орудия на одно направление. Стратегии В 4 , В 5 отбросим заранее как заведомо невыгодные. Рассуждая аналогично предыдущему примеру, строим матрицу игры:
Нижняя цена игры 1/2, верхняя 3/4. Матрица не имеет седловой точки; решение лежит в области смешанных стратегий. Пользуясь геометрической интерпретацией (рис. 4.12), выделим «полезные» стратегии противника: В 1 и В 2 .
Частоты р 1 и р 2 определим из уравнений: p 1 *0 + (1 – p 1)*1 = ν и p 1 *5/6 + (1 – p 1)*1/2 = ν; откуда p 1 = 3/8; p 2 = 5/8; ν = 5/8, т.е. наша оптимальная стратегия есть . Пользуясь ею, мы гарантируем себе средний выигрыш 5/8. Зная цену игры ν = 5/8, находим частоты q 1 и q 2 «полезных» стратегий противника: q 1 *0 + (1 – q 1)*5/6 = 5/8, q 1 = ¼, q 2 = ¾. Оптимальная стратегия противника будет: .
Пример 6. Сторона А располагает двумя стратегиями A 1 и А 2 , сторона В - четырьмя B 1 , В 2 , В 3 и В 4 . Матрица игры имеет вид:
Найти решение игры.
Решение. Нижняя цена игры 3; верхняя 4. Геометрическая интерпретация (рис. 4.13) показывает, что полезными стратегиями игрока В являются В 1 и В 2 или В 2 и В 4:
Игрок А имеет бесконечно много оптимальных смешанных стратегий: в оптимальной стратегии p 1 может изменяться от 1/5 до 4/5. Цена игры ν = 4. Игрок В имеет чистую оптимальную стратегию В 2 .
§ 5. Общие методы решения конечных игр
Мы рассматривали до сих пор только самые элементарные игры типа 2xn, которые могут быть весьма просто решены и допускают удобную и наглядную геометрическую интерпретацию. В общем случае решение игры mxn представляет довольно трудную задачу, причем сложность задачи и объем необходимых для решения вычислений резко возрастает с увеличением m и n. Однако эти трудности не носят принципиального характера и связаны только с очень большим объемом расчетов, который в ряде случаев может оказаться практически невыполнимым. Принципиальная сторона метода отыскания решения остается при любом m одной и той же.
Проиллюстрируем это на примере игры 3xn. Дадим ей геометрическую интерпретацию - уже пространственную. Три наши стратегии А 1 , A 2 и A 3 изобразим тремя точками на плоскости хОу ; первая лежит в начале координат (рис. 5.1), вторая и третья - на осях Ох и Оу на расстояниях 1 от начала.
Через точки A 1 , А 2 и А 3 проводятся оси I – I , II – II и III – III , перпендикулярные к плоскости хОу . На оси I – I откладываются выигрыши при стратегии А 1 на осях II – II и III – III - выигрыши при стратегиях А 2 , А 3 . Каждая стратегия противника B j изобразится плоскостью, отсекающей на осях I – I , II – II и III – III отрезки, равные выигрышам при соответствующих стратегиях A 1 , А 2 и А 3 и стратегии В j . Построив таким образом все стратегии противника, мы получим семейство плоскостей над треугольником A 1 , А 2 и А 3 (рис. 5.2). Для этого семейства также можно построить нижнюю границу выигрыша, как мы это делали в случае 2xn и найти на этой границе точку N с максимальной высотой над плоскостью хОу . Эта высота и будет ценой игры ν.
Частоты p 1 , р 2 , р 3 стратегий A 1 , А 2 и А 3 в оптимальной стратегии S A * будут определяться координатами (х, у) точки N, а именно: p 2 = x, p 3 = y, p 1 = 1 – p 2 – p 3 . Однако такое геометрическое построение даже для случая 3xn нелегко осуществимо и требует большой затраты времени и усилий воображения. В общем же случае игры оно переносится в m-мерное пространство и теряет всякую наглядность, хотя употребление геометрической терминологии в ряде случаев может оказаться полезным. При решении игр mxn на практике удобнее пользоваться не геометрическими аналогиями, а расчетными аналитическими методами, тем более, что для решения задачи на вычислительных машинах эти методы единственно пригодны.
Все эти методы по существу сводятся к решению задачи путем последовательных проб, но упорядочение последовательности проб позволяет построить алгоритм, приводящий к решению наиболее экономичным способом. Здесь мы вкратце остановимся на одном расчетном методе решения игр mxn - на так называемом методе «линейного программирования». Для этого дадим сначала общую постановку задачи о нахождении решения игры mxn. Пусть дана игра mxn с m стратегиями A 1 , А 2 , …, А m игрока А и n стратегиями B 1 , B 2 , …, B n игрока В и задана платежная матрица ‖a i j ‖. Требуется найти решение игры, т.е. две оптимальные смешанные стратегии игроков А и В
где p 1 + p 2 + … + p m = 1; q 1 + q 2 + … + q n = 1 (некоторые из чисел p i и q j могут быть равными нулю).
Наша оптимальная стратегия S A *должна обеспечивать нам выигрыш, не меньший ν, при любом поведении противника, и выигрыш, равный ν, при его оптимальном поведении (стратегия S B *). Аналогично стратегия S B * должна обеспечивать противнику проигрыш, не больший ν, при любом нашем поведении и равный ν при нашем оптимальном поведении (стратегия S A *).
Величина цены игры ν в данном случае нам неизвестна; будем считать, что она равна некоторому положительному числу. Полагая так, мы не нарушаем общности рассуждений; для того чтобы было ν > 0, очевидно, достаточно, чтобы все элементы матрицы ‖a i j ‖ были неотрицательными. Этого всегда можно добиться, прибавляя к элементам ‖a i j ‖ достаточно большую положительную величину L ; при этом цена игры увеличится на L , а решение не изменится.
Пусть мы выбрали свою оптимальную стратегию S A *. Тогда наш средний выигрыш при стратегии B j противника будет равен: a j = p 1 a 1j + p 2 a 2j + … + p m a mj . Наша оптимальная стратегия S A * обладает тем свойством, что при любом поведении противника обеспечивает выигрыш не меньший, чем ν; следовательно, любое из чисел a j не может быть меньше ν. Получаем ряд условий:
Разделим неравенства (5.1) на положительную величину ν и обозначим
Тогда условия (5.1) запишутся в виде
где ξ 1 , ξ 2 , …, ξ m - неотрицательные числа. Так как р 1 + p 2 + … + p m = 1, то величины ξ 1 , ξ 2 , …, ξ m удовлетворяют условию
(5.3) ξ 1 + ξ 2 + … + ξ m = 1/ν.
Мы хотим сделать свой гарантированный выигрыш максимально возможным; очевидно, при этом правая часть равенства (5.3) принимает минимальное значение. Таким образом, задача нахождения решения игры сводится к следующей математической задаче: определить неотрицательные величины ξ 1 , ξ 2 , …, ξ m , удовлетворяющие условиям (5.2), так, чтобы их сумма Φ = ξ 1 + ξ 2 + … + ξ m была минимальной.
Обычно при решении задач, связанных с нахождением экстремальных значений (максимумов и минимумов), функцию дифференцируют и приравнивают производные нулю. Но такой прием в данном случае бесполезен, так как функция Φ, которую нужно обратить в минимум, линейна, и ее производные по всем аргументам равны единице, т.е. нигде не обращаются в нуль. Следовательно, максимум функции достигается где-то на границе области изменения аргументов, которая определяется требованием неотрицательности аргументов и условиями (5.2). Прием нахождения экстремальных значений при помощи дифференцирования непригоден и в тех случаях, когда для решения игры определяется максимум нижней (или минимум верхней) границы выигрыша, как мы, например, делали при решении игр 2xn. Действительно, нижняя граница составлена из участков прямых линий, и максимум достигается не в точке, где производная равна нулю (такой точки вообще нет), а на границе интервала или в точке пересечения прямолинейных участков.
Для решения подобных задач, довольно часто встречающихся на практике, в математике разработан специальный аппарат линейного программирования. Задача линейного программирования ставится следующим образом. Дана система линейных уравнений:
Требуется найти неотрицательные значения величин ξ 1 , ξ 2 , …, ξ m , удовлетворяющие условиям (5.4) и вместе с тем обращающие в минимум заданную однородную линейную функцию величин ξ 1 , ξ 2 , …, ξ m (линейную форму): Φ = c 1 ξ 1 + c 2 ξ 2 + … + c m ξ m
Легко убедиться, что поставленная выше задача теории игр является частным случаем задачи линейного программирования при с 1 = с 2 = … = с m = 1. С первого взгляда может показаться, что условия (5.2) не эквивалентны условиям (5.4), так как вместо знаков равенства они содержат знаки неравенства. Однако от знаков неравенства легко избавиться, вводя новые фиктивные неотрицательные переменные z 1 , z 2 , …, z n и записывая условия (5.2) в виде:
Форма Φ, которую нужно обратить в минимум, равна Φ = ξ 1 + ξ 2 + … + ξ m . Аппарат линейного программирования позволяет путем сравнительно небольшого числа последовательных проб подобрать величины ξ 1 , ξ 2 , …, ξ m , удовлетворяющие поставленным требованиям. Для большей ясности мы здесь продемонстрируем применение этого аппарата прямо на материале решения конкретных игр.
Пример 1. Требуется найти решение игры 3×3, данной в примере 2 § 1, с матрицей:
Чтобы сделать все а ij неотрицательными, прибавим ко всем элементам матрицы L = 5. Получим матрицу:
При этом цена игры увеличится на 5, а решение не изменится.
Определим оптимальную стратегию S A *. Условия (5.2) имеют вид:
где ξ 1 = p 1 /ν, ξ 2 = p 2 /ν, ξ 3 = p 3 /ν. Чтобы избавиться от знаков неравенства, введем фиктивные переменные z 1 , z 2 , z 3 ; условия (5.6) запишутся в виде:
Линейная форма Φ имеет вид: Φ = ξ 1 + ξ 2 + ξ 3 и должна быть сделана как можно меньше. Если все три стратегии В являются «полезными», то все три фиктивные переменные z 1 , z 2 , z 3 обратятся в нуль (т.е. выигрыш, равный цене игры ν, будет достигаться при каждой стратегии B j). Но мы пока не имеем оснований утверждать, что все три стратегии являются «полезными». Чтобы проверить это, попытаемся выразить форму Φ через фиктивные переменные z 1 , z 2 , z 3 и посмотрим, добьемся ли мы, полагая их равными нулю, минимума формы. Для этого разрешим уравнения (5.7) относительно переменных ξ 1 , ξ 2 , ξ 3 (т.е. выразим ξ 1 , ξ 2 , ξ 3 через фиктивные переменные z 1 , z 2 , z 3):
Складывая ξ 1 , ξ 2 , ξ 3 , получим: Φ = 1/5 + z 1 /20 + z 2 /10 + z 3 /20. Здесь коэффициенты при всех z положительны; значит, любое увеличение z 1 , z 2 , z 3 сверх нуля может привести только к увеличению формы Φ, а мы хотим, чтобы она была минимальна. Следовательно, значениями z 1 , z 2 , z 3 , обращающими форму Φ в минимум, являются z 1 = z 2 = z 3 = 0. Следовательно, минимальное значение формы Φ: 1/ν = 1/5, откуда цена игры ν = 5. Подставляя нулевые значения z 1 , z 2 , z 3 в формулы (5.8), находим: ξ 1 = 1/20, ξ 2 = 1/10, ξ 3 = 1/20, или, умножая их на ν, р 1 = 1/4, р 2 = 1/2, р 3 = 1/4. Таким образом, оптимальная стратегия А найдена: , т.е. мы должны в одной четверти всех случаев писать цифру 1, в половине случаев 2 и в остальной четверти случаев 3.
Зная цену игры ν = 5, можно уже известными способами найти оптимальную стратегию противника . Для этого воспользуемся нашими любыми двумя «полезными» стратегиями (например, А 2 и А 3) и напишем уравнения:
9q 1 + 11 (1-q 2 -q 1) = 5,
откуда q 1 = q3 = 1/4; q 2 = 1/2. Оптимальная стратегия противника будет такой же, как наша: . Теперь вернемся к первоначальной (не преобразованной) игре. Для этого нужно только от цены игры ν = 5 отнять величину L = 5, прибавленную к элементам матрицы. Получим цену исходной игры v 0 = 0. Следовательно, оптимальные стратегии обеих сторон обеспечивают средний выигрыш, равный нулю; игра в одинаковой мере выгодна или невыгодна для обеих сторон.
Пример 2. Спортивный клуб А располагает тремя вариантами состава команды А 1 , А 2 и А 3 . Клуб В - также тремя вариантами B 1 , В 2 и В 3 . Подавая заявку для участия в соревновании, ни один из клубов не знает, какой состав изберет противник. Вероятности выигрыша клуба А при различных вариантах составов команд, примерно известные из опыта прошлых встреч, заданы матрицей:
Найти, с какой частотой клубы должны выставлять каждый из составов во встречах друг с другом, чтобы добиться наибольшего в среднем числа побед.
Решение. Нижняя цена игры 0,4; верхняя 0,6; решение ищем в области смешанных стратегий. Чтобы не иметь дела с дробями, умножим все элементы матрицы на 10; при этом цена игры увеличится в 10 раз, а решение не изменится. Получим матрицу:
Условия (5.5) имеют вид:
а условие минимума Φ = ξ 1 + ξ 2 + ξ 3 = min.
Проверяем, все ли три стратегии противника являются «полезными». В качестве гипотезы сначала предполагаем, что фиктивные переменные z 1 , z 2 , z 3 равны нулю, и для проверки решаем уравнения (5.10) относительно ξ 1 , ξ 2 , ξ 3:
(5.12) 136Φ = 30 +13z 1 +18z 2 – 51z 3
Формула (5.12) показывает, что увеличение переменных z 1 и z 2 по сравнению с их предполагаемым значением нуль может только увеличить Φ, тогда как увеличение z 3 может уменьшить Φ. Однако увеличение z 3 надо производить осторожно, чтобы величины ξ 1 , ξ 2 , ξ 3 , зависящие от z 3 , не стали при этом отрицательными. Поэтому положим в правых частях равенств (5.11) величины z 1 и z 2 равными нулю, а величину z 3 будем увеличивать до допустимых пределов (пока какая-нибудь из величин ξ 1 , ξ 2 , ξ 3 не обратится в нуль). Из второго равенства (5.11) видно, что увеличение z 3 «безопасно» для величины ξ 2 - она от этого только увеличивается. Что касается величин ξ 1 , и ξ 3 , то здесь увеличение z 3 возможно только до некоторого предела. Величина ξ 1 обращается в нуль при z 3 = 10/23; величина ξ 3 обращается в нуль раньше, уже при z 3 = 1/4. Следовательно, давая z 3 его максимально допустимое значение z 3 = 1/4, мы при этом обратим в нуль величину ξ 3 .
Чтобы проверить, обращается ли в минимум форма Φ при z 1 = 0, z 2 = 0, ξ 3 = 0, выразим остальные (не равные нулю) переменные через предположительно равные нулю z 1 , z 2 , ξ 3 . Разрешая уравнения (5.10) относительно ξ 1 , ξ 2 и z 3 , получим:
(5.13) 32Φ = 7 + Зz 1 + 4z 2 + ξ 3
Из формулы (5.13) видно, что любое увеличение z 1 , z 2 , ξ 3 сверх их предполагаемых нулевых значений может только увеличить форму Φ. Следовательно, решение игры найдено; оно определяется значениями z 1 = z 2 = ξ 3 = 0, откуда ξ 1 = 1/32, ξ 2 = 3/16, z 3 = 1/4. Подставляя в формулу (5.13), находим цену игры ν: 32Φ = 7 = 32/ν; ν = 32/7. Наша оптимальная стратегия: . «Полезные» стратегии (составы A 1 и A 2) должны применяться с частотами 1/7 и 6/7 ; состав A 3 - никогда не применяться.
Чтобы найти оптимальную стратегию противника, в общем случае можно поступать так: изменить знак выигрыша на обратный, прибавить к элементам матрицы постоянную величину L, чтобы сделать их неотрицательными, и решать задачу за противника так же, как мы решали ее за себя. Однако то, что нам уже известна цена игры ν, несколько упрощает задачу. К тому же в данном конкретном случае задача дополнительно упрощается тем, что в решении участвуют только две «полезные» стратегии противника В 1 и В 2 , так как величина z 3 не равна нулю, и, значит, при стратегии В 3 цена игры не достигается. Выбирая любую «полезную» стратегию игрока А, например A 1 можно найти частоты q 1 и q 2 . Для этого пишем уравнение 8q 1 + 2(1 – q 1) = 32/7, откуда q 1 = 3/7, q 2 = 4/7; оптимальная стратегия противника будет: , т.е. противник не должен пользоваться составом В 3 , а составы В 1 и В 2 должны применяться с частотами 3/7 и 4/7.
Возвращаясь к первоначальной матрице, определим истинную цену игры ν 0 = 32/7:10 = 0,457. Это значит, что при большом числе встреч число побед клуба А составит 0,457 всех встреч.
§ 6. Приближенные методы решения игр
Часто в практических задачах нет необходимости находить точное решение игры; достаточно найти приближенное решение, дающее средний выигрыш, близкий к цене игры. Ориентировочное знание цены игры ν может дать уже простой анализ матрицы и определение нижней (α) и верхней (β) цен игры. Если α и β близки, практически нет надобности заниматься поисками точного решения, а достаточно будет выбрать чистые минимаксные стратегии. В случаях, когда α и β не близки, можно получить приемлемое для практики решение с помощью численных методов решения игр, из которых мы вкратце осветим метод итераций.
Идея метода итераций сводится к следующему. Разыгрывается «мысленный эксперимент», в котором противники А и В применяют друг против друга свои стратегии. Эксперимент состоит из последовательности элементарных игр, каждая из которых имеет матрицу заданной игры. Начинается с того, что мы (игрок А) выбираем произвольно одну из своих стратегий, например А i . Противник на это отвечает той своей стратегией B j , которая наименее выгодна для нас, т.е. обращает выигрыш при стратегии А i в минимум. На этот ход мы отвечаем той своей стратегией А k , которая дает максимальный средний выигрыш при применении противником стратегии B j . Далее - снова очередь противника. Он отвечает на нашу пару ходов A i и А k той своей стратегией B j , которая дает нам наименьший средний выигрыш при этих двух стратегиях (A i , А к), и так далее. На каждом шаге итерационного процесса каждый игрок отвечает на любой ход другого игрока той своей стратегией, которая является оптимальной относительно всех его предыдущих ходов, рассматриваемых как некоторая смешанная стратегия, в которой чистые стратегии представлены в пропорциях, соответствующих частоте их применения.
Такой способ представляет собой как бы модель реального практического «обучения» игроков, когда каждый из них на опыте прощупывает способ поведения противника и старается отвечать на него выгодным для себя образом. Если такую имитацию процесса обучения продолжать достаточно долго, то средний выигрыш, приходящийся на одну пару ходов (элементарную игру), будет стремиться к цене игры, а частоты р 1 … р m ; q 1 … q n , с которыми встречаются стратегии игроков в этом розыгрыше, будут приближаться к частотам, определяющим оптимальные стратегии. Расчеты показывают, что сходимость метода очень медленная, однако для быстродействующих счетных машин это не является препятствием.
Проиллюстрируем применение итерационного метода на примере игры 3×3, решенной в примере 2 предыдущего параграфа. Игра задана матрицей:
В таблице 6.1 приведены первые 18 шагов итерационного процесса. В первом столбце дан номер элементарной игры (пары ходов) n ; во втором - номер i выбранной стратегии игрока А; в последующих трех - «накопленный выигрыш» за первые n игр при стратегиях противника B 1 , В 2 , В 3 . Минимальное из этих значений подчеркнуто. Далее идет номер j стратегии, выбранной противником, и соответственно накопленный выигрыш за n игр при стратегиях A 1 , А 2 , А 3 из этих значений подчеркнуто сверху максимальное. Подчеркнутые значения определяют выбор ответной стратегии другого игрока. В следующих графах последовательно приведены: минимальный средний выигрыш ν , равный минимальному накопленному выигрышу, деленному на число игр n ; максимальный средний выигрыш , равный максимальному накопленному выигрышу, деленному на n , и их среднее арифметическое ν* = (ν + )/2. При увеличении n все три величины ν , и ν* будут приближаться к цене игры ν, но величина ν*, естественно, будет приближаться к ней сравнительно быстрее.
Таблица 6.1.
Как видно из примера, сходимость итераций весьма медленная, но все же даже такой небольшой расчет дает возможность найти ориентировочное значение цены игры и выявить преобладание «полезных» стратегий. При пользовании счетными машинами ценность метода значительно увеличивается. Преимущество итерационного метода решения игр в том, что объем и сложность вычислений сравнительно слабо возрастают по мере увеличения числа стратегий m и n .
§ 7. Методы решения некоторых бесконечных игр
Бесконечной игрой называется игра, в которой по крайней мере одна из сторон имеет бесконечное множество стратегий. Общие методы решения таких игр еще мало разработаны. Однако для практики могут представлять интерес некоторые частные случаи, которые допускают сравнительно простое решение. Рассмотрим игру двух противников А и В, каждый из которых имеет бесконечное (несчетное) множество стратегий; эти стратегии для игрока А соответствуют различным значениям непрерывно меняющегося параметра х , а для В - параметра у . В данном случае вместо матрицы ‖a ij ‖ игру определяет некоторая функция двух непрерывно меняющихся аргументов а (х, у) , которую мы будем называть функцией выигрыша (заметим, что сама функция а (х, у) необязательно должна быть непрерывной). Функцию выигрыша а(х, у) можно представить геометрически некоторой поверхностью а (х, у) над областью изменения аргументов (х, у) (рис. 7.1)
Анализ функции выигрыша а(х, у) производится аналогично анализу платежной матрицы. Сначала находится нижняя цена игры α; для этого определяется для каждого х минимум функции а(х, у) по всем у : , затем ищется максимальное из этих значений по всем х (максимин):
Верхняя цена игры (минимакс) определяется аналогично:
Рассмотрим случай, когда α = β. Так как цена игры ν всегда заключена между α и β, то общее их значение и есть ν. Равенство α = β означает, что поверхность а(х, у) имеет седловую точку, т.е., такую точку с координатами х 0 , у 0 , в которой а(х, у) является одновременно минимальным по у и максимальным по х (рис. 7.2).
Значение а(х, у) в этой точке и есть цена игры ν: ν = а(х 0 , у 0). Наличие седловой точки означает, что данная бесконечная игра имеет решение в области чистых стратегий; х 0 , у 0 представляют собой оптимальные чистые стратегии А и В. В общем случае, когда α ≠ β, игра может иметь решение только в области смешанных стратегий (возможно, не единственное). Смешанная стратегия для бесконечных игр есть некоторое распределение вероятностей для стратегий х и у , рассматриваемых как случайные величины. Это распределение может быть непрерывным и определяться плотностями f 1 (х) и f 2 (у) ; может быть дискретным, и тогда оптимальные стратегии состоят из набора отдельных чистых стратегий, выбираемых с какими-то отличными от нуля вероятностями.
В случае, когда бесконечная игра не имеет седловой точки, можно дать наглядную геометрическую интерпретацию нижней и верхней цене игры. Рассмотрим бесконечную игру с функцией выигрыша а(х, у) и стратегиями х, у , заполняющими непрерывно отрезки осей (х 1 , х 2) и (у 1 , у 2) . Чтобы определить нижнюю цену игры α, нужно «посмотреть» на поверхность а(х, у) со стороны оси у , т.е. спроектировать ее на плоскость хОа (рис. 7.3). Получим некоторую фигуру, ограниченную с боков прямыми x = x 1 и х = х 2 , а сверху и снизу - кривыми К В и К Н. Нижняя цена игры α, очевидно, есть не что иное, как максимальная ордината кривой К Н.
Аналогично, чтобы найти верхнюю цену игры β, нужно «посмотреть» на поверхность а(х, у) со стороны оси х (спроектировать поверхность на плоскость уОа ) и найти минимальную ординату верхней границы К В проекции (рис, 7.4).
Рассмотрим два элементарных примера бесконечных игр.
Пример 1. Игроки А и В имеют каждый несчетное множество возможных стратегий х и у , причем 0 ≤ х ≤ 1; 0 ≤ у ≤ 1. Функция выигрыша за а дана выражением а (х, у) – (х – у) 2 . Найти решение игры.
Решение, Поверхность а(х, у) представляет собой параболический цилиндр (рис. 7.5) и не имеет седловой точки. Определим нижнюю цену игры; очевидно, для всех х ; отсюда = 0. Определим верхнюю цену игры. Для этого найдем при фиксированном у
В данном случае максимум достигается всегда на границе интервала (при х = 0 или х = 1), т.е. он равен той из величин у 2 ; (1 – у) 2 , которая больше. Изобразим графики этих функций (рис. 7.6), т.е. проекцию поверхности а(х, у) на плоскость уОа . Жирной линией на рис. 7.6 показана функция . Очевидно, ее минимальное значение достигается при у = 1/2 и равно 1/4. Следовательно, верхняя цена игры β = 1/4. В данном случае верхняя цена игры совпадает с ценой игры ν. Действительно, игрок А может применить смешанную стратегию S А =, в которую крайние значения х = 0 и х = 1 входят с одинаковыми частотами; тогда при любой стратегии у игрока В средний выигрыш игрока А будет равен: ½у 2 + ½(1 – у) 2 . Нетрудно убедиться, что эта величина при любых значениях у между 0 и 1 имеет значение не меньшее ¼: ½у 2 + ½(1 – у) 2 ≥ ¼.
Таким образом, игрок А применением данной смешанной стратегии может гарантировать себе выигрыш, равный верхней цене игры; так как цена игры не может быть больше верхней цены, то данная стратегия S A оптимальная: S A = S A *.
Остается найти оптимальную стратегию игрока В. Очевидно, что если цена игры ν равна верхней цене игры β, то оптимальной стратегией игрока В будет всегда его чистая минимаксная стратегия, гарантирующая ему верхнюю цену игры. В данном случае такой стратегией является у 0 = ½. Действительно, при этой стратегии, что бы ни делал игрок А, выигрыш его не будет больше ¼. Это следует из очевидного неравенства (x – ½) 2 = x(x –1) + ¼ ≤ ¼
Пример 2. Сторона А («мы») ведет стрельбу по самолету В противника. Для того чтобы уклониться от обстрела, противник может маневрировать с некоторой перегрузкой у , которой он по своему усмотрению может придавать значения от у = 0 (прямолинейное движение) до у = у max (полет по окружности максимальной кривизны). Будем считать у max единицей измерения, т.е. положим у max = 1. В борьбе с противником мы можем применять прицельные приспособления, основанные на той или иной гипотезе о движении цели за время полета снаряда. Перегрузка х при этом гипотетическом маневре может полагаться равной любому значению от 0 до 1. Наша задача - поразить противника; задача противника - остаться непораженным. Вероятность поражения для данных х и у приближенно выражается формулой: а(х, у) = , где у - перегрузка, применяемая противником; х - перегрузка, учтенная в прицеле. Требуется определить оптимальные стратегии обеих сторон.
Решение. Очевидно, решение игры не изменится, если мы положим р = 1. Функция выигрыша а(х, у) изображается поверхностью, представленной на рис. 7.7.
Это - цилиндрическая поверхность, образующие которой параллельны биссектрисе координатного угла хОу , а сечение плоскостью, перпендикулярной к образующей, есть кривая типа нормальной кривой распределения. Пользуясь предложенной выше геометрической интерпретацией нижней и верхней цены игры, находим β = 1 (рис. 7.8) и (рис. 7.9). Игра не имеет седловой точки; решение нужно искать в области смешанных стратегий. Задача до некоторой степени аналогична задаче предыдущего примера. Действительно, при малых значениях k функция ведет себя примерно как функция –(х – у) 2 , и решение игры получится, если в решении предыдущего примера поменять ролями игроков A и В; т.е. нашей оптимальной стратегией будет чистая стратегия х = 1/2, а оптимальная стратегия противника S B = будет состоять в том, чтобы с одинаковыми частотами применять крайние стратегии у = 0 и y = 1. Это значит, что мы должны во всех случаях применять прицел, рассчитанный на перегрузку x = 1/2, а противник должен в половине всех случаев вообще не применять маневра, а в половине - максимально возможный маневр.
Рис. 7.8 Рис. 7.9.
Легко доказать, что это решение будет справедливо для значений k ≤ 2. Действительно, средний выигрыш при стратегии противника S B = и при нашей стратегии х выражается функцией , которая для значений k ≤ 2 имеет один максимум при х = 1/2, равный нижней цене игры α. Следовательно, применение стратегии S B гарантирует противнику проигрыш, не больший α, из чего ясно, что α - нижняя цена игры - и есть цена игры ν.
При k > 2 функция а(х) имеет два максимума (рис. 7.10), расположенные симметрично относительно х = 1/2 в точках x 0 и 1 – х 0 , причем значение х 0 зависит от k.
Очевидно, при k = 2 х 0 = 1 – x 0 = ½; при увеличении k точки х 0 и 1 – х 0 раздвигаются, подходя ближе к крайним точкам (0 и 1). Следовательно, решение игры будет зависеть от k. Зададим конкретное значение k, например k = 3, и найдем решение игры; для этого определим абсциссу х 0 максимума кривой а(х). Приравнивая нулю производную функции а(х), напишем уравнение для определения x 0:
Это уравнение имеет три корня: х = 1/2 (где достигается минимум) и х 0 , 1 – х 0 , где достигаются максимумы. Решая уравнение численно, находим приближенно x 0 ≈ 0,07; 1 – x 0 ≈ 0,93.
Докажем, что решением игры в данном случае будет следующая пара стратегий:
При нашей стратегии и стратегии противника у средний выигрыш равен
Найдем минимум a 1 (y) при 0 < у < 1. Функция a 1 (y) симметрична относительно y = 1/2 и может иметь только один или два максимума; ее минимум, во всяком случае, достигается либо в середине отрезка (0, 1), либо на его концах. Полагая у = 0 (или у = 1), найдем
Полагая у = 1/2, получаем
что больше, чем a 1 (0); следовательно, цена игры не меньше, чем а 1 (0):
Теперь допустим, что противник применяет стратегию S B *, а мы-стратегию х. Тогда средний выигрыш будет
Но мы выбрали х 0 именно так, чтобы при х = х 0 достигался максимум выражения (7.2); следовательно,
т.е. противник применением стратегии S B * может не допустить проигрыша, большего 0,530; следовательно, ν = 0,530 и есть цена игры, а стратегии S A * и S B * дают решение. Это значит, что мы должны с одинаковой частотой пользоваться прицелами с х = 0,07 и x = 0,93, а противник с одинаковой частотой не маневрировать и маневрировать с максимальной перегрузкой.
Заметим, что выигрыш ν = 0,530 заметно больше, чем нижняя цена игры , которую мы могли бы обеспечить себе, применяя свою максиминную стратегию х 0 = 1/2.
Одним из практических способов решения бесконечных игр является их приближенное сведение к конечным. При этом целый диапазон возможных стратегий каждого игрока условно объединяется в одну стратегию. Таким способом, разумеется, можно получить только приближенное решение игры, но в большинстве случаев точного решения и не требуется.
Однако нужно иметь в виду, что при применении этого приема могут появиться решения в области смешанных стратегий даже в случаях, когда решение исходной бесконечной игры возможно в чистых стратегиях, т.е. когда бесконечная игра имеет седловую точку. Если путем сведения бесконечной игры к конечной получено смешанное решение, в которое входят только две соседние «полезные» стратегии, то имеет смысл попытаться применить промежуточную между ними чистую стратегию исходной бесконечной игры.
В заключение заметим, что бесконечные игры в отличие от конечных могут и не иметь решения. Приведем пример бесконечной игры, не имеющей решения. Два игрока называют каждый любое целое число. Назвавший большее число получает от другого 1 рубль. Если оба назвали одно и то же число, игра заканчивается вничью. Игра, очевидно, не может иметь решения. Однако существуют классы бесконечных игр, для которых решение заведомо существует.
И кибернетики , особенно с проявлением интереса к интеллектуальным агентам .
История
Оптимальные решения или стратегии в математическом моделировании предлагались ещё в XVIII в. Задачи производства и ценообразования в условиях олигополии , которые стали позже хрестоматийными примерами теории игр, рассматривались в XIX в. А. Курно и Ж. Бертраном . В начале XX в. Э. Ласкер , Э. Цермело, Э. Борель выдвигают идею математической теории конфликта интересов.
Математическая теория игр берёт своё начало из неоклассической экономики . Впервые математические аспекты и приложения теории были изложены в классической книге 1944 года Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение» (англ. Theory of Games and Economic Behavior ).
Эта область математики нашла некоторое отражение в общественной культуре. В 1998 году американская писательница и журналистка Сильвия Назар издала книгу о судьбе Джона Нэша , нобелевского лауреата по экономике и учёного в области теории игр; а в по мотивам книги был снят фильм «Игры разума ». Некоторые американские телевизионные шоу, например, «Friend or Foe », «Alias» или «NUMB3RS», периодически ссылаются на теорию в своих эпизодах.
Математическая теория игр сейчас бурно развивается, рассматриваются динамические игры. Однако математический аппарат теории игр затратен . Его применяют для оправданных задач: политика, экономика монополий и распределения рыночной власти и т. п. Ряд известных ученых стали Нобелевскими лауреатами по экономике за вклад в развитие теории игр, которая описывает социально-экономические процессы. Дж. Нэш , благодаря своим исследованиям в теории игр, стал одним из ведущих специалистов в области ведения «холодной войны» , что подтверждает масштабность задач, которыми занимается теория игр.
Представление игр
Игры представляют собой строго определённые математические объекты. Игра образуется игроками, набором стратегий для каждого игрока и указания выигрышей, или платежей , игроков для каждой комбинации стратегий. Большинство кооперативных игр описываются характеристической функцией, в то время как для остальных видов чаще используют нормальную или экстенсивную форму. Характеризующие признаки игры как математической модели ситуации:
- наличие нескольких участников;
- неопределенность поведения участников, связанная с наличием у каждого из них нескольких вариантов действий;
- различие (несовпадение) интересов участников;
- взаимосвязанность поведения участников, поскольку результат, получаемый каждым из них, зависит от поведения всех участников;
- наличие правил поведения, известных всем участникам.
Экстенсивная форма
Основная статья: Экстенсивная форма игры
Игры в экстенсивной, или расширенной, форме представляются в виде ориентированного дерева , где каждая вершина соответствует ситуации выбора игроком своей стратегии. Каждому игроку сопоставлен целый уровень вершин. Платежи записываются внизу дерева, под каждой листовой вершиной .
На рисунке слева - игра для двух игроков. Игрок 1 ходит первым и выбирает стратегию F или U. Игрок 2 анализирует свою позицию и решает - выбрать стратегию A или R. Скорее всего первый игрок выберет U, а второй - A (для каждого из них это оптимальные стратегии ); тогда они получат соответственно 8 и 2 очка.
Экстенсивная форма очень наглядна, с её помощью особенно удобно представлять игры с более чем двумя игроками и игры с последовательными ходами. Если же участники делают одновременные ходы, то соответствующие вершины либо соединяются пунктиром, либо обводятся сплошной линией.
Нормальная форма
Игрок 2 стратегия 1 |
Игрок 2 стратегия 2 |
|
Игрок 1 стратегия 1 |
4 , 3 | –1 , –1 |
Игрок 1 стратегия 2 |
0 , 0 | 3 , 4 |
Нормальная форма для игры с 2 игроками, у каждого из которых по 2 стратегии. |
В нормальной, или стратегической, форме игра описывается платёжной матрицей . Каждая сторона (точнее, измерение) матрицы - это игрок, строки определяют стратегии первого игрока, а столбцы - второго. На пересечении двух стратегий можно увидеть выигрыши, которые получат игроки. В примере справа, если игрок 1 выбирает первую стратегию, а второй игрок - вторую стратегию, то на пересечении мы видим (−1, −1), это значит, что в результате хода оба игрока потеряли по одному очку.
Игроки выбирали стратегии с максимальным для себя результатом, но проиграли из-за незнания хода другого игрока. Обычно в нормальной форме представляются игры, в которых ходы делаются одновременно , или хотя бы полагается, что все игроки не знают о том, что делают другие участники. Такие игры с неполной информацией будут рассмотрены ниже.
Характеристическая функция
В кооперативных играх с трансферабельной полезностью, то есть возможностью передачи средств от одного игрока к другому, невозможно применять понятие индивидуальных платежей . Вместо этого используют так называемую характеристическую функцию, определяющую выигрыш каждой коалиции игроков. При этом предполагается, что выигрыш пустой коалиции равен нулю.
Основания такого подхода можно найти ещё в книге фон Неймана и Моргенштерна. Изучая нормальную форму для коалиционных игр, они рассудили, что если в игре с двумя сторонами образуется коалиция C , то против неё выступает коалиция N \ C . Образуется как бы игра для двух игроков. Но так как вариантов возможных коалиций много (а именно 2 N , где N - количество игроков), то выигрыш для C будет некоторой характеристической величиной , зависящей от состава коалиции. Формально игра в такой форме (также называемая TU-игрой ) представляется парой (N, v) , где N - множество всех игроков, а v: 2 N → R - это характеристическая функция.
Подобная форма представления может быть применена для всех игр, в том числе без трансферабельной полезности. В настоящее время существуют способы перевести любую игру из нормальной формы в характеристическую, но преобразование в обратную сторону возможно не во всех случаях.
Применение теории игр
Теория игр как один из подходов в прикладной математике применяется для изучения поведения человека и животных в различных ситуациях. Первоначально теория игр начала развиваться в рамках экономической науки, позволив понять и объяснить поведение экономических агентов в различных ситуациях. Позднее область применения теории игр была расширена на другие социальные науки; в настоящее время теория игр используется для объяснения поведения людей в политологии, социологии и психологии. Теоретико-игровой анализ был впервые использован для описания поведения животных Рональдом Фишером в 30-х годах XX века (хотя даже Чарльз Дарвин использовал идеи теории игр без формального обоснования). В работе Рональда Фишера не появляется термин «теория игр». Тем не менее, работа по существу выполнена в русле теоретико-игрового анализа. Разработки, сделанные в экономике, были применены Джоном Майнардом Смитом в книге «Эволюция и теория игр». Теория игр используется не только для предсказания и объяснения поведения; были предприняты попытки использовать теорию игр для разработки теорий этичного или эталонного поведения. Экономисты и философы применяли теорию игр для лучшего понимания хорошего (достойного) поведения.
Описание и моделирование
Первоначально теория игр использовалась для описания и моделирования поведения человеческих популяций. Некоторые исследователи считают, что с помощью определения равновесия в соответствующих играх они могут предсказать поведение человеческих популяций в ситуации реальной конфронтации. Такой подход к теории игр в последнее время подвергается критике по нескольким причинам. Во-первых, предположения, используемые при моделировании, зачастую нарушаются в реальной жизни. Исследователи могут предполагать, что игроки выбирают поведения, максимизирующие их суммарную выгоду (модель экономического человека), однако на практике человеческое поведение часто не соответствует этой предпосылке. Существует множество объяснений этого феномена - нерациональность, моделирование обсуждения, и даже различные мотивы игроков (включая альтруизм). Авторы теоретико-игровых моделей возражают на это, говоря, что их предположения аналогичны подобным предположениям в физике. Поэтому даже если их предположения не всегда выполняются, теория игр может использоваться как разумная идеальная модель, по аналогии с такими же моделями в физике. Однако, на теорию игр обрушился новый вал критики, когда в результате экспериментов было выявлено, что люди не следуют равновесным стратегиям на практике. Например, в играх «Сороконожка», «Диктатор» участники часто не используют профиль стратегий, составляющий равновесие по Нэшу. Продолжаются споры о значении подобных экспериментов. Согласно другой точке зрения, равновесие по Нэшу не является предсказанием ожидаемого поведения, оно лишь объясняет, почему популяции, уже находящиеся в равновесии по Нэшу, остаются в этом состоянии. Однако вопрос о том, как эти популяции приходят к равновесию Нэша, остается открытым. Некоторые исследователи в поисках ответа на этот вопрос переключились на изучение эволюционной теории игр. Модели эволюционной теории игр предполагают ограниченную рациональность или нерациональность игроков. Несмотря на название, эволюционная теория игр занимается не столько вопросами естественного отбора биологических видов. Этот раздел теории игр изучает модели биологической и культурной эволюции, а также модели процесса обучения.
Нормативный анализ (выявление наилучшего поведения)
С другой стороны, многие исследователи рассматривают теорию игр не как инструмент предсказания поведения, но как инструмент анализа ситуаций с целью выявления наилучшего поведения для рационального игрока. Поскольку равновесие Нэша включает стратегии, являющиеся наилучшим откликом на поведение другого игрока, использование концепции равновесия Нэша для выбора поведения выглядит вполне обоснованным. Однако, и такое использование теоретико-игровых моделей подверглось критике. Во-первых, в некоторых случаях игроку выгодно выбрать стратегию, не входящую в равновесие, если он ожидает, что другие игроки также не будут следовать равновесным стратегиям. Во-вторых, знаменитая игра «Дилемма заключенного » позволяет привести ещё один контрпример. В «Дилемме заключенного » следование личным интересам приводит к тому, что оба игрока оказываются в худшей ситуации в сравнении с той, в которой они пожертвовали бы личными интересами.
Типы игр
Кооперативные и некооперативные
Игра называется кооперативной, или коалиционной , если игроки могут объединяться в группы, взяв на себя некоторые обязательства перед другими игроками и координируя свои действия. Этим она отличается от некооперативных игр, в которых каждый обязан играть за себя. Развлекательные игры редко являются кооперативными, однако такие механизмы нередки в повседневной жизни.
Часто предполагают, что кооперативные игры отличаются именно возможностью общения игроков друг с другом. В общем случае это неверно. Существуют игры, где коммуникация разрешена, но игроки преследуют личные цели, и наоборот.
Из двух типов игр, некооперативные описывают ситуации в мельчайших деталях и выдают более точные результаты. Кооперативные рассматривают процесс игры в целом. Попытки объединить два подхода дали немалые результаты. Так называемая программа Нэша уже нашла решения некоторых кооперативных игр как ситуации равновесия некооперативных игр.
Гибридные игры включают в себя элементы кооперативных и некооперативных игр. Например, игроки могут образовывать группы, но игра будет вестись в некооперативном стиле. Это значит, что каждый игрок будет преследовать интересы своей группы, вместе с тем стараясь достичь личной выгоды.
Симметричные и несимметричные
А | Б | |
А | 1, 2 | 0, 0 |
Б | 0, 0 | 1, 2 |
Несимметричная игра |
Основная статья: Симметричная игра
Игра будет симметричной тогда, когда соответствующие стратегии у игроков будут равны, то есть иметь одинаковые платежи. Иначе говоря, если игроки могут поменяться местами и при этом их выигрыши за одни и те же ходы не изменятся. Многие изучаемые игры для двух игроков - симметричные. В частности, таковыми являются: «Дилемма заключённого », «Охота на оленя », «Ястребы и голуби ». В качестве несимметричных игр можно привести «Ультиматум» или «Диктатор».
В примере справа игра на первый взгляд может показаться симметричной из-за похожих стратегий, но это не так - ведь выигрыш второго игрока при профилях стратегий (А, А) и (Б, Б) будет больше, чем у первого.
С нулевой суммой и с ненулевой суммой
Игры с нулевой суммой - особая разновидность игр с постоянной суммой , то есть таких, где игроки не могут увеличить или уменьшить имеющиеся ресурсы, или фонд игры. В этом случае сумма всех выигрышей равна сумме всех проигрышей при любом ходе. Посмотрите направо - числа означают платежи игрокам - и их сумма в каждой клетке равна нулю. Примерами таких игр может служить покер , где один выигрывает все ставки других; реверси , где захватываются фишки противника; либо банальное воровство .
Многие изучаемые математиками игры, в том числе уже упоминавшаяся «Дилемма заключённого», иного рода: в играх с ненулевой суммой выигрыш какого-то игрока не обязательно означает проигрыш другого, и наоборот. Исход такой игры может быть меньше или больше нуля. Такие игры могут быть преобразованы к нулевой сумме - это делается введением фиктивного игрока , который «присваивает себе» излишек или восполняет недостаток средств.
Ещё игрой с отличной от нуля суммой является торговля , где каждый участник извлекает выгоду. Широко известным примером, где она уменьшается, является
Теория игр - совокупность математических методов решения конфликтных ситуаций (столкновений интересов). В теории игр игрой называется математическая модель конфликтной ситуации. Предмет особого интереса теории игр - исследование стратегий принятия решений участников игры в условиях неопределённости. Неопределённость связана с тем, что две или более стороны преследуют противоположные цели, а результаты любого действия каждой из сторон зависят от ходов партнёра. При этом каждая из сторон стремится принимать оптимальные решения, которые реализуют поставленные цели в наибольшей степени.
Наиболее последовательно теория игр применяется в экономике, где конфликтные ситуации возникают, например, в отношениях между поставщиком и потребителем, покупателем и продавцом, банком и клиентом. Применение теории игр можно найти и в политике, социологии, биологии, военном искусстве.
Из истории теории игр
История теории игр как самостоятельной дисциплины начинается в 1944 году, когда Джон фон Нейман и Оскар Моргенштерн опубликовали книгу "Теория игр и экономическое поведение" ("Theory of Games and Economic Behavior"). Хотя примеры теории игр встречались и раньше: трактат Вавилонского Талмуда о разделе имущества умершего мужа между его жёнами, карточные игры в 18-м веке, развитие теории шахматной игры в начале 20-го века, доказательство теоремы о минимаксе того же Джона фон Неймана в 1928 году, без которой не было бы никакой теории игр.
В 50-х годах 20-го века Мелвин Дрешер и Мерил Флод из Rand Corporation первыми экспериментально применили дилемму заключённого, Джон Нэш в работах о состоянии равновесия в играх двух лиц развил понятие равновесия Нэша.
Рейнхард Сэлтен в 1965 году опубликовал книгу "Обработка олигополии в теории игр по требованию" ("Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit"), с которой применение теории игр в экономике получило новую движущую силу. Шагом вперёд в эволюции теории игр связан с работой Джона Мейнарда Смита "Эволюционно стабильная стратегия" ("Evolutionary Stable Strategy", 1974). Дилемма заключённого была популяризована в книге Роберта Аксельрода "Эволюция кооперации" ("The Evolution of Cooperation"), опубликованной в 1984 году. В 1994 году именно за вклад в теорию игр Нобелевской премии были удостоены Джон Нэш, Джон Харсаньи и Рейнхард Сэлтен.
Теория игр в жизни и бизнесе
Остановимся подробнее на сути кофликтной ситуации (столкновении интересов) в том смысле, как он понимается в теории игр для дальнейшего моделирования различных ситуаций в жизни и бизнесе. Пусть индивидуум находится в таком положении, которое приводит к одному из нескольких возможных исходов, причём у индивидуума имеются по отношению к этим исходам некоторые личные предпочтения. Но хотя он может до некоторой степени управлять переменными факторами, определяющими исход, он не имеет полной власти над ними. Иногда управление находится в руках нескольких индивидуумов, которые, подобно ему, имеют какие-то предпочтения по отношению к возможным исходам, но в общем случае интересы этих индивидуумов не согласуются. В других случаях конечный исход может зависеть как от случайностей (которые в юридических науках иногда именуются стихийными бедствиями), так и от других индивидуумов. Теория игр систематизирует наблюдения за такими ситуациями и формулировки общих принципов для руководства разумными действиями в таких ситуациях.
В некоторых отношениях название "теория игр" неудачно, так как наводит на мысль, что теория игр рассматривает лишь не имеющие социального значения столкновения, происходящие в салонных играх, но всё же эта теория имеет значительно более широкое значение.
О применении теории игр может дать представление следующая экономическая ситуация. Пусть имеется несколько предпринимателей, каждый из которых стремится получить максимум прибыли, имея при этом лишь ограниченную власть над переменными, определяющими эту прибыль. Предприниматель не имеет власти над переменными, которыми распоряжается другой предприниматель, но которые могут сильно влиять на доход первого. Трактовка этой ситуации как игры может вызвать следующее возражение. В игровой модели предполагается, что каждый предприниматель делает один выбор из области возможных выборов и этими единичными выборами определяются прибыли. Очевидно, что этого почти не может быть в действительности, так как при этом в промышленности не были бы нужны сложные управленческие аппараты. Просто есть ряд решений и модификаций этих решений, которые зависят от выборов, совершённых другими участниками экономической системы (игроками). Но в принципе можно вообразить, что какой-либо администратор предвидит все возможные случайности и подробно описывает действие, которое нужно предпринимать в каждом случае, вместо того чтобы решать каждую задачу по мере её возникновения.
Военный кофликт, по определению, есть столкновение интересов, в котором ни одна из сторон не распоряжается полностью переменными, определяющими исход, который решается рядом битв. Можно просто считать исход выигрышем или проигрышем и приписать им численные значения 1 и 0.
Одна из самых простых конфликтных ситуаций, которая может быть записана и решена в теории игр - дуэль, представляющая собой конфликт двух игроков 1 и 2, имеющих соответственно p и q выстрелов. Для каждого игрока существует функция, указывающая вероятность того, что выстрел игрока i в момент времени t даст попадание, которое окажется смертельным.
В итоге теория игр приходит к такой формулировке некоторого класса столкновений интересов: имеются n игроков, и каждому нужно выбрать одну возможность из стого определённого набора, причём при совершении выбора у игрока нет никаких сведений о выборах других игроков. Область возможных выборов игрока может содержать такие элементы, как "ход тузом пик", "производство танков вместо автомобилей", или в общем смысле, стратегию, определяющую все действия, которые нужно совершить во всех возможных обстоятельствах. Перед каждым игроком стоит задача: какой выбор он должен сделать, чтобы его частное влияние на исход принесло ему как можно больший выигрыш?
Математическая модель в теории игр и формализация задач
Как мы уже отмечали, игра является математической моделью конфликтной ситуации и требует наличия следующих компонент:
- заинтересованных сторон;
- возможных действий с каждой стороны;
- интересов сторон.
Заинтересованные в игре стороны называются игроками , каждый из них может предпринять не менее двух действий (если в распоряжении игрока только одно действие, то он фактически не участвует в игре, так как заранее известно, что он предпримет). Исход игры называется выигрышем .
Реальная конфликтная ситуация не всегда, а игра (в понятии теории игр) - всегда - протекает по определённым правилам , которые точно определяют:
- варианты действий игроков;
- объём информации каждого игрока о поведении партнёра;
- выигрыш, к которому приводит каждая совокупность действий.
Примерами формализованных игр могут служить футбол, карточная игра, шахматы.
Но в экономике модель поведения игроков возникает, например, когда несколько фирм стремятся занять более выгодное место на рынке, несколько лиц пытаются поделить между собой какое-либо благо (ресурсы, финансы) так, чтобы каждому досталось по возможности больше. Игроками в конфликтных ситуациях в экономике, которые можно моделировать в виде игры, являются фирмы, банки, отдельные люди и другие экономические агенты. В свою очередь в условиях войны модель игры используется, например, в выборе более лучшего оружия (из имеющегося или потенциально возможного) для разгрома противника или защиты от нападения.
Для игры характерна неопределённость результата . Причины неопределённости можно распределить по следующим группам:
- комбинаторные (как в шахматах);
- влияние случайных факторов (как в игре "орёл или решка", кости, карточные игры);
- стратегические (игрок не знает, какое действие предпримет противник).
Стратегией игрока называется совокупность правил, определяющих его действия при каждом ходе в зависимости от сложившейся ситуации.
Целью теории игр является определение оптимальной стратегии для каждого игрока. Определить такую стратегию - значит решить игру. Оптимальность стратегии достигается, когда один из игроков должен получить максимальный выигрыш, при том, что второй придерживается своей стратегии. А второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии.
Классификация игр
- Классификация по числу игроков (игра двух и более лиц). Игры двух лиц занимают центральное место во всей теории игр. Основным понятием теории игр для игры двух лиц является обобщение весьма существенной идеи равновесия, которая естественно появляется в играх двух лиц. Что же касается игр n лиц, то одна часть теории игр посвящена играм, в которых сотрудничество между игроками запрещено. В другой части теории игр n лиц предполагается, что игроки могут сотрудничать для взаимной пользы (см. далее в этом параграфе о некооперативных и кооперативных играх).
- Классификация по числу игроков и их стратегиям (число стратегий не менее двух, может быть бесконечностью).
- Классификация по количеству информации относительно прошлых ходов: игры с полной информацией и неполной информацией. Пусть есть игрок 1 - покупатель и игрок 2 - продавец. Если у игрока 1 нет полной информации о действиях игрока 2, то игрок 1 может и не различить две альтернативы, между которыми ему предстоит сделать выбор. Например, выбирая между двумя видами некоторого товара и не зная о том, что по некоторым признакам товар A хуже товара B , игрок 1 может не видеть различия между альтернативами.
- Классификация по принципам деления выигрыша : кооперативные, коалиционные с одной стороны и некооперативные, бескоалиционные с другой стороны. В некооперативной игре , или иначе - бескоалиционной игре , игроки выбирают стратегии одновременно, не зная, какую стратегию выберет второй игрок. Коммуникация между игроками невозможна. В кооперативной игре , или иначе - коалиционной игре , игроки могут объединяться в коалиции и предпринимать коллективные действия, чтобы увеличить свои выигрыши.
- Конечная игра двух лиц с нулевой суммой или антогонистическая игра – это стратегическая игра с полной информацией, в которой участвуют стороны с противоположными интересами. Анатагонистическими играми являются матричные игры .
Классический пример из теории игр - дилемма заключённого
Двух подозреваемых берут под стражу и изолируют друг от друга. Окружной прокурор убеждён, что они совершили тяжкое преступление, но не имеет достаточных доказательств, чтобы предъявить им обвинение на суде. Он говорит каждому из заключённых, что у него имеется две альтернативы: признаться в преступлении, которое по убеждению полиции он совершил, или не признаваться. Если оба не признаются, то окружной прокурор предъявит им обвинение в каком-либо незначительном преступлении, например, мелкая кража или незаконное владение оружием, и они оба получат небольшое наказание. Если они оба признаются, то будут подлежать судебной ответственности, но он не потребует самого строгого приговора. Если же один признается, а другой нет, то признавшемуся приговор будет смягчён за выдачу сообщника, в то время как упорствующий получит "на полную катушку".
Если эту стратегическую задачу сформулировать в сроках заключения, то она сводится к следующему:
Таким образом, если оба заключённых не признаются, они получат по 1 году каждый. Если оба признаются, то каждый получит по 8 лет. А если один признается, другой не признается, то тот, который признался отделается тремя месяцами заключения, а тот, который не признается, получит 10 лет. Приведённая выше матрица правильно отражает дилемму заключённого: перед каждым стоит вопрос - признаться или не признаться. Игра, которую окружной прокурор предлагает заключённым, представляет собой некооперативную игру или иначе - бескоалиционную игру . Если бы оба заключённых имели возможность сотрудничать (то есть игра была бы кооперативной или иначе коалиционной игрой ), то оба не признались бы и получили по году тюрьмы каждый.
Примеры использования математических средств теории игр
Переходим теперь к рассмотрению решений примеров распространённых классов игр, для которых в теории игр существуют методы исследования и решения.
Пример формализации некооперативной (бескоалиционной) игры двух лиц
В предыдущем параграфе мы уже рассмотрели пример некооперативной (бескоалиционной) игры (дилемма заключённого). Давайте закрепим наши навыки. Для этого подойдёт также классический сюжет, навеянный "Приключениями Шерлока Холмса" Артура Конан Дойля. Можно, конечно, возразить: пример не из жизни, а из литературы, но ведь Конан Дойль не зарекомендовал себя как писатель-фантаст! Классический ещё и потому, что задание выполнено Оскаром Моргенштерном, как мы уже установили - одним из основателей теории игр.
Пример 1. Будет приведено сокращённое изложение фрагмента одного из "Приключений Шерлока Холмса". Согласно известным понятиям теории игр составить модель конфликтной ситуации и формально записать игру.
Шерлок Холмс намерен отправиться из Лондона в Дувр с дальнейшей целю попасть на континент (европейский), чтобы спастись от профессора Мориарти, который преследует его. Сев в поезд, он увидел на вокзальной платформе профессора Мориарти. Шерлок Холмс допускает, что Мориарти может выбрать особый поезд и обогнать его. У Шерлока Холмса две альтернативы: продолжать поездку до Дувра или сойти на станции Кентерберри, являющейся единственной промежуточной станцией на его маршруте. Мы принимаем, что его противник достаточно разумен, чтобы определить возможности Холмса, поэтому перед ним те же две альтернативы. Оба противника должны выбрать станцию, чтобы сойти на ней с поезда, не зная, какое решение примет каждый из них. Если в результате принятия решения оба окажутся на одной и той же станции, то можно однозначно считать, что Шерлок Холмс будет убит профессором Мориарти. Если же Шерлок Холмс благополучно доберётся до Дувра, то он будет спасён.
Решение. Героев Конан Дойля можем рассматривать как участников игры, то есть игроков. В распоряжении каждого игрока i (i =1,2) две чистые стратегии:
- сойти в Дувре (стратегия s i1 (i =1,2) );
- сойти на промежуточной станции (стратегия s i2 (i =1,2) )
В зависимости от того, какую из двух стратегий выберет каждый из двух игроков, будет создана особая комбинация стратегий как пара s = (s 1 , s 2 ) .
Каждой комбинации можно поставить в соответствие событие - исход попытки убийства Шерлока Холмса профессором Мориарти. Составляем матрицу данной игры с возможными событиями.
Под каждым из событий указан индекс, означающий приобретение профессора Мориарти, и рассчитываемый в зависимости от спасения Холмса. Оба героя выбирают стратегию одновременно, не зная, что выберет противник. Таким образом, игра является некооперативной, поскольку, во-первых, игроки находятся в разных поездах, а во-вторых, имеют противоположные интересы.
Пример формализации и решения кооперативной (коалиционной) игры n лиц
В этом пункте практическая часть, то есть ход решения примера задачи, будет предварена теоретической частью, в которой будем знакомиться с понятиями теории игр для решения кооперативных (бескоалиционных) игр. Для этой задачи теория игр предлагает:
- характеристическую функцию (если говорить упрощённо, она отражает величину выгоды объединения игроков в коалицию);
- понятие аддитивности (свойства величин, состоящее в том, что значение величины, соответствующее целому объекту, равно сумме значений величин, соответствующих его частям, в некотором классе разбиений объекта на части) и супераддитивности (значение величины, соответствующее целому объекту, больше суммы значений величин, соответствующих его частям) характеристической функции.
Супераддитивность характеристической функции говорит о том, что объединение в коалиции выгодна игрокам, так как в этом случае величина выигрыша коалиции увеличивается с увеличением числа игроков.
Для формализации игры нам нужно ввести формальные обозначения вышеназванных понятий.
Для игры n обозначим множество всех её игроков как N = {1,2,...,n} Любое непустое подмножество множества N обозначим как Т (включая само N и все подмножества, состоящие из одного элемента). На сайте есть занятие "Множества и операции над множествами ", которое при переходе по ссылке открывается в новом окне.
Характеристическая функция обозначается как v и область её определения состоит из возможных подмножеств множества N . v (T ) - значение характеристической функции для того или иного подмножества, например, доход, полученный коалицией, в том числе, возможно, состоящей из одного игрока. Это важно по той причине, что теория игр требует проверить наличие супераддитивности для значений характеристической функции всех непересекающихся коалиций.
Для двух непустых коалиций из подмножеств T 1 и T 2 аддитивность характеристической функции кооперативной (коалиционной) игры записывается так:
А супераддитивность так:
Пример 2. Трое студентов музыкальной школы подрабатывают в разных клубах, свою выручку они получают от посетителей клубов. Установить, выгодно ли им объединять свои силы (если да, то с какими условиями), используя понятия теории игр для решения кооперативных игр n лиц, при следующих исходных данных.
В среднем их выручка за один вечер составляла:
- у скрипача 600 единиц;
- у гитариста 700 единиц;
- у певицы 900 единиц.
Пытаясь увеличить выручку, студенты в течение нескольких месяцев создавали различные группы. Результаты показали, что, объединившись, они могут увеличить свою выручку за вечер следующим образом:
- скрипач + гитарист зарабатывали 1500 единиц;
- скрипач + певица зарабатывали 1800 единиц;
- гитарист + певица зарабатывали 1900 единиц;
- скрипач + гитарист + певица зарабатывали 3000 единиц.
Решение. В этом примере число участников игры n = 3 , следовательно, область определения характеристической функции игры состоит из 2³ = 8 возможных подмножеств множества всех игроков. Перечислим все возможные коалиции T :
- коалиции из одного элемента, каждая из которых состоит из одного игрока - музыканта: T {1} , T {2} , T {3} ;
- коалиции из двух элементов: T {1,2} , T {1,3} , T {2,3} ;
- коалиция из трёх элементов: T {1,2,3} .
Каждому из игроков присвоим порядковый номер:
- скрипач - 1-й игрок;
- гитарист - 2-й игрок;
- певица - 3-й игрок.
По данным задачи определим характеристическую функцию игры v :
v(T{1}) = 600 ; v(T{2}) = 700 ; v(T{3}) = 900 ; эти значения характеристической функции определены исходя из выигрышей соответственно первого, второго и третьего игроков, когда они не объединяются в коалиции;
v(T{1,2}) = 1500 ; v(T{1,3}) = 1800 ; v(T{2,3}) = 1900 ; эти значения характеристической функции определены по выручке каждой пары игроков, объединившихся в коалиции;
v(T{1,2,3}) = 3000 ; это значение характеристической функции определено по средней выручке в случае, когда игроки объединялись в тройки.
Таким образом, мы перечислили все возможные коалиции игроков, их получилось восемь, как и должно быть, так как область определения характеристической функции игры состоит именно из восьми возможных подмножеств множества всех игроков. Что и требует теория игр, так как нам нужно проверить наличие супераддитивности для значений характеристической функции всех непересекающихся коалиций.
Как выполняются условия супераддитивности в этом примере? Определим, как игроки образуют непересекающиеся коалиции T 1 и T 2 . Если часть игроков входят в коалицию T 1 , то все остальные игроки входят в коалицию T 2 и по определению эта коалиция образуется как разность всего множества игроков и множества T 1 . Тогда, если T 1 - коалиция из одного игрока, то в коалиции T 2 будут второй и третий игроки, если в коалиции T 1 будут первый и третий игроки, то коалиция T 2 будет состоять только из второго игрока, и так далее.
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Федеральное агентство связи
Сибирский Государственный Университет Телекоммуникаций и Информатики
Межрегиональный центр переподготовки специалистов
Контрольная работа
По дисциплине: Институциональная экономика
Выполнил: Лапина Е.Н.
Группа: ЭБТ-52
Вариант:4
Новосибирск, 2016 г
ВВЕДЕНИЕ
Любой человек во всем мире ежедневно совершает какие-то действия, делает для себя выбор в чем-либо. Для того чтобы совершать какие-либо действия, человеку необходимо задумываться об их последствиях, выбирать самое правильное, рациональное из всех возможных решений. Выбор необходимо осуществлять исходя из интересов собственных или групповых, в зависимости от того, к кому относится решение (к индивиду или к группе, организации в целом).
Институты создаются людьми, чтобы поддержать порядок и сократить неопределенность обмена. Они обеспечивают предсказуемость поведения людей. Институты позволяют экономить наши мыслительные способности, так как выучив правила, мы можем приспособиться к внешней среде, не пытаясь ее осмыслить и понять. Петросян Л.А, Зенкевич Н.А., Шевкопляс Е.В.: Теория игр: учебник. Издательство: BHV, 2012.-С.18.
Институты -- это «правила игры» в обществе, или, выражаясь более формально, созданные человеком ограничительные рамки, которые организуют взаимоотношения между людьми. Лабскер Л.Г., Ященко Н.А.: Теория игр в экономике. Практикум с решением задач. Учебное пособие. Издательство: Кнорус, 2014.-С.21. Институты появляются для решения проблем, возникающих при повторяющемся взаимодействии людей. При этом они не просто должны решить проблему, но и минимизировать ресурсы, затрачиваемые на ее решение.
Теорией игр называют математический метод изучения оптимальных стратегий в играх. Под игрой понимается процесс, в котором участвуют две и более сторон, ведущих борьбу за осуществление своих интересов. Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышу - в зависимости от своего поведения и поведения других игроков. Теория игр помогает выбрать наиболее выгодные стратегии с учётом некоторых факторов:
1. соображений о других участниках;
2. ресурсов участников;
3. предполагаемых действий участников.
В теории игр предполагается, что функции выигрыша и множество стратегий, доступных каждому из игроков, общеизвестны, т.е. каждый игрок знает свою функцию выигрыша и набор имеющихся в его распоряжении стратегий, а также функции выигрыша и стратегии всех остальных игроков, и в соответствии с этой информацией формирует свое поведение.
Актуальность темы состоит в широком спектре применений теории игр на практике (биология, социология, математика, менеджмент и т.д.). Конкретно в экономике - в такие моменты, когда не срабатывают теоретические основы теории выбора в классической экономической теории, заключающиеся, например, в том, что потребитель делает свой выбор рационально, он полностью осведомлен о ситуации на данном рынке и о конкретном данном товаре.
ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ ИГР
1.1 ПОНЯТИЕ ТЕОРИИ ИГР
Как уже было сказано выше, теория игр - раздел математики, изучающий формальные модели принятия оптимальных решений в условиях конфликта. При этом под конфликтом понимается явление, в котором участвуют различные стороны, наделённые различными интересами и возможностями выбирать доступные для них действия в соответствии с этими интересами. Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышу -- в зависимости от поведения других игроков. Теория игр помогает выбрать лучшие стратегии с учётом представлений о других участниках, их ресурсах и их возможных поступках
Теория игр берёт своё начало из неоклассической экономики. Впервые математические аспекты и приложения теории были изложены в классической книге 1944 года Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение».
Игра - упрощенная формализованная модель реальной конфликтной ситуации. Математически формализация означает, что выработаны определенные правила действия сторон в процессе игры: варианты действия сторон; исход игры при данном варианте действия; объем информации каждой стороны о поведении все других сторон.
Ситуации, в которых сталкиваются интересы двух сторон и результат любой операции, осуществляемой одной из сторон, зависит от действий другой стороны, называются конфликтными.
Игрок - одна из сторон в игровой ситуации. Стратегия игрока - его правила действия в каждой из возможных ситуаций игры. Доминирование в теории игр -- ситуация, при которой одна из стратегий некоторого игрока дает больший выигрыш, нежели другая, при любых действиях его оппонентов. Протасов И.Д. Теория игр и исследование операций: учеб. пособие. - М.: Гелиос АРВ, 2013.-С.121.
Фокальная точка -- это равновесие в координационной игре, выбираемое всеми участниками взаимодействия на основе общего знания, помогающего им скоординировать свой выбор. Понятие фокальной точки было введено лауреатом Нобелевской премии 2005 года экономистом Томасом Шеллингом в статье 1957 года, которая стала третьей главой его знаменитой книги «Стратегия конфликта» (1960).
Если для одного из игроков существует строго доминирующая стратегия, он будет ее использовать в любом из равновесий Нэша в игре. Если все игроки имеют строго доминирующие стратегии, игра имеет единственное равновесие Нэша. Однако, это равновесие не обязательно будет эффективным по Парето, т.е. неравновесные исходы могут обеспечить всем игрокам больший выигрыш. Классическим примером этой ситуации является игра «Дилемма заключенного». Равновесие по Нэшу -- это набор стратегий (одна для каждого игрока) такой, что ни один из игроков не имеет стимула отклоняться от своей стратегии. Ситуация будет эффективной по Парето, если ни один из игроков не может улучшить свое положение, не ухудшив при этом положение другого игрока.
Следует так же упомянуть о равновесии по Штакельбергу. Равновесие по Штакельбергу -- ситуация, когда ни один из игроков не может увеличить свой выигрыш в одностороннем порядке, а решения принимаются сначала одним игроком и становятся известными второму игроку. В отличие от равновесия доминирующих стратегий и равновесия по Нэшу этот вид равновесия существует всегда.
Интерпретация теории игр может осуществляться двумя способами: матричным и графическим. Матричный способ будет изображен ниже, где будут рассматриваться ситуации, приводящие к возникновению институтов.
Для примера графического изображения обратимся к следующей ситуации, когда имеется одно пастбище для выпаса коров. Теперь зададим вопрос: при каком количестве коров, n, использование данного пастбища было бы оптимальным? В соответствии с маржинальным принципом оптимизации, предполагающим уравнение предельных издержек и предельного дохода, следует ответить, что оптимальным будет то количество коров, при котором ценность предельного продукта от выпаса последней коровы, VМР, будет равна стоимости одной коровы, с. В условиях частной собственности на это пастбище, данный принцип был бы соблюден, поскольку отдельный хозяин сопоставлял бы выгоды и издержки, связанные с каждой дополнительной коровой, и остановился бы на том их количестве, Ер, при котором возможности получения положительной ренты от выпаса коров на пастбище, Rp, были бы исчерпаны, и, соответственно, был бы достигнут максимум этой ренты (рис. 1). Это обобщается в нижеприведенном уравнении, согласно которому при соблюдении маржинального принципа максимизируется разница между ценностью общего продукта, VТР, и общими издержками, т. е. стоимостью коровы, умноженной на количество коров
VMP (n*) = c maxn VTP (n) - cn (1)
Рисунок 1. - График ценности предельного и среднего выпаса коров
Однако в условиях свободного доступа к пастбищу, т. е. отсутствия исключительных прав на него маржинальный принцип оптимизации не будет соблюден и количество коров на пастбище превзойдет оптимальное значение, Ер, и достигнет точки равенства ценности среднего продукта от выпаса коровы, VAP, и стоимости коровы. В результате будет иметь место новое равновесное количество коров в условиях свободного доступа, Ес. При этом положительная рента, Rp, созданная за счет выпаса коров до достижения их оптимального количества, Ер, на дополнительных коровах будет растрачиваться и при достижении точки Ес станет равна нулю в результате накопления равной ей по модулю отрицательной ренты. Это обобщается в нижеприведенных уравнениях:
VTP (n")/n"=c?VTP (n")-cn"=0;
1.2 РАЗНООБРАЗИЕ СИТУАЦИЙ И СФЕР ЖИЗНИ ЧЕЛОВЕКА, В КОТОРЫХ ПРИМЕНИМА ТЕОРИЯ ИГР
В жизни известно немало примеров столкновения противоположных сторон, принимающих форму конфликта с двумя действующими сторонами, преследующими противоположные интересы.
Такие ситуации возникают, например, тогда, когда речь идет о доверии. Соответствие действий контрагента ожиданиям становится особенно важным в тех ситуациях, когда риск принимаемых индивидом решений определен действиями контрагента. Модели теории игр служат лучшей иллюстрацией сказанному: выбор игроком той или иной стратегии зависит от действий другого игрока. Доверие заключается в «ожидании определенных действий окружающих, которые влияют на выбор индивида, когда индивид должен начать действовать до того, как станут известными действия окружающих». Подчеркнем связь сделок на рынке с доверием в деперсонифицированной форме (доверия в качестве нормы, регулирующей отношения между индивидами), так как круг участников сделок не должен быть ограничен лично знакомыми людьми. Убедиться в необходимости существования доверия в деперсонифицированной форме для осуществления простейшей рыночной сделки с использованием предоплаты помогает следующая модель (рис.2).
Рисунок 2
Предположим, что покупателю противостоит множество продавцов и он из своего предыдущего делового опыта знает вероятность обмана (1 -- р). Рассчитаем такую величину p, чтобы сделка состоялась, т. е. «делать предоплату» была эволюционно-стабильной стратегией.
EU (делать предоплату) = 10р -- 5(1 -- р) = 15p -- 5,
EU(не делать предоплату) = 0,15p - -5 > 0, р>1/3.
Иначе говоря, при уровне доверия покупателя к продавцам меньше 33,3% сделки с предоплатой при заданных условиях становятся невозможными. Иными словами, р= 1/3 является критическим, минимально необходимым уровнем доверия.
Для обобщения результатов заменим конкретные величины выигрыша (10) и проигрыша (--5) покупателя символами G и L. Тогда при прежней структуре игры сделка состоится при
чем выше величина проигрыша относительно выигрыша, тем выше должен быть уровень доверия между участниками сделки. Джеймс Коулмен следующим образом изобразил зависимость потребности в доверии от условий заключаемой сделки (рис. 3).
Рисунок 3
Расчетные данные о минимально необходимом уровне доверия подтверждаются эмпирически. Так, уровень деперсонифицированного доверия в странах с развитой рыночной экономикой, измеренный с помощью ответа на вопрос: «Исходя из Вашего личного опыта, считаете ли Вы, что окружающим людям можно доверять? », составлял 94% в Дании 24, 90 -- в ФРГ, 88 -- в Великобритании, 84 -- во Франции, 72 -- на севере Италии и 65% -- на юге. Показателен низкий уровень доверия на юге Италии, где традиционно сильна мафия. Не случайно один из исследователей мафии -- Д. Гамбетта объясняет ее возникновение критически низким уровнем доверия в южных регионах Италии и, следовательно, потребностью в заменителе доверия, принимающего форму вмешательства «третьей стороны», которой доверяют оба участника сделки.
Еще один яркий пример теории игр - контракты между инвестором и государством на разработку месторождений полезных ископаемых.
Для иллюстрации этого примера возьмем контракт о купле-продаже стульев с учетом того, что наличие в них зашитых сокровищ, находится под вопросом. Изображать пример будем с учетом того, что в рамках теории игр внешние по отношению к намерениям сторон контракта факторы учитываются с помощью введения в игру с двумя участниками третьего игрока, «природы» (рис. 4).
Рисунок 4
Как следует из представления игры в развернутой форме, вместо четырех исходов их в игре шесть. И если проблема зависимости выигрыша Остапа от действий машиниста сцены находит свое решение при наличии любого отличного от нуля уровня доверия Остапа, то проблема зависимости выигрыша Остапа от наличия в стульях сокровищ остается неразрешимой, что, впрочем, и подтверждает финал романа.
1.3 ВОЗМОЖНЫЕ СТРАТЕГИИ В ПОВТОРЯЮЩИХСЯ ИГРАХ
1. Смешанные стратегии. Когда игроки попадают в определенную ситуацию выбора неоднократно, то их взаимодействие существенным образом усложняется. Они могут позволить себе комбинировать стратегии, максимизируя общий выигрыш. Покажем это с помощью модели, описывающей отношения между Центральным банком (ЦБ) и экономическим агентом в связи с проводимой ЦБ кредитно-денежной политикой.
ЦБ ориентируется либо на жесткую кредитно-денежную политику, стремясь поддержать инфляцию на фиксированном уровне (р0), либо на эмиссию и, следовательно, повышение темпов инфляции (р1). В свою очередь, экономический агент действует на основе своих инфляционных ожиданий ре (устанавливает цены на свою продукцию, решает вопросы о приобретении товаров и услуг и т.д.), которые могут либо подтверждаться, либо не подтверждаться в результате проводимой ЦБ политики. В случае если р1 > ре, ЦБ получает прибыль от сеньоража и от инфляционного налога. Если ре = р1, то в проигрыше оказывается и ЦБ из-за сокращения поступлений от сеньоража, и экономические агенты, которые продолжают нести тяжесть инфляционного налога. Если ре = р0, то сохраняется статус-кво и в проигрыше никто не оказывается. Наконец, если ре > р0, то проигрывают только экономические агенты: производители -- из-за потери спроса на необоснованно подорожавшую продукцию, потребители -- из-за создания неоправданных запасов.
В предложенной модели при однократном взаимодействии у агентов нет доминирующих стратегий, отсутствует и равновесие по Нэшу. При повторяющемся многократно взаимодействии, а именно такое взаимодействие и характерно для реальных ситуаций, оба участника могут использовать и ту, и другую имеющуюся у них в распоряжении стратегии. Позволяет ли игрокам чередование стратегий в определенной последовательности максимизировать свою полезность, т. е. достичь равновесия по Нэшу в смешанных стратегиях: исхода, при котором ни один участник не может увеличить свой выигрыш, изменяя в одностороннем порядке свою стратегию? Предположим, что ЦБ проводит жесткую кредитно-денежную политику с вероятностью Р1 (в P1 % случаев), а с вероятностью (1 - Р1) -- инфляционную политику. Тогда при выборе экономическим агентом неинфляционных ожиданий (рe = р0) ЦБ может рассчитывать на получение выигрыша, равного
теория игра стратегия
EU(ЦБ) = Р1 0+,
1 (1 - Р1) = 1- -P1
В случае инфляционных ожиданий у экономического агента выигрыш ЦБ составит
EU(ЦБ) = Р10 + (1 - Р1)(-2) = 2Р1 - 2.
Теперь допустим, что экономический агент имеет неифляционные ожидания с вероятностью Р2 (в Р2 % случаев), а инфляционные ожидания -- с вероятностью (1 - Р2). Отсюда ожидаемая полезность ЦБ составит
EU(ЦБ) = Р2(1 - Р1) + (1 - Р2)(2Р1-2) = =ЗР2-ЗР1 Р2+2Р1 - 2 (рис. 5).
Рисунок 5
Аналогичные расчеты для экономического агента дадут
EU (э.а.) = Р1(Р2- 1) + (1 - Р1)(-Р2-2) = 2Р1Р2 + Р1- Р2-2.
Если мы перепишем данные выражения в следующей форме
EU(ЦБ) = Pl(2-3P2) + ЗР2-2
EU(э.a.)= =Р2(2Р1-1) +Р1-2,
то нетрудно заметить, что при
выигрыш ЦБ не зависит от его собственной политики, а при
выигрыш экономического агента не зависит от его ожиданий.
Иными словами, равновесием по Нэшу в смешанных стратегиях будет формирование экономическим агентом в 2/3 случаев неинфляционных ожиданий и проведение ЦБ в половине случаев жесткой кредитно-денежной политики. Найденное равновесие достижимо при условии, что экономические агенты формируют ожидания рациональным образом, а не на основе инфляционных ожиданий в предыдущий период, скорректированных на ошибку прогноза предыдущего периода8. Следовательно, изменения в политике ЦБ влияют на поведение экономических агентов только в той степени, в которой они неожиданны и непредсказуемы. Стратегия ЦБ в 50% случаев проводить жесткую кредитно-денежную политику, а в 50% -- мягкую как нельзя лучше соответствует созданию атмосферы непредсказуемости.
2. Эволюционно-стабильная стратегия. Эволюционно-стабильная стратегия -- такая стратегия, что если ее использует большинство индивидов, то никакая альтернативная стратегия не может ее вытеснить посредством механизма естественного отбора, даже если последняя более эффективна по Парето.
Разновидностью повторяющихся игр являются ситуации, когда индивид многократно попадает в определенную ситуацию выбора, но его контрагент не постоянен, а в каждом периоде индивид взаимодействует с новым визави. Поэтому вероятность выбора контрагентом той или иной стратегии будет зависеть не столько от конфигурации смешанной стратегии, сколько от предпочтений каждого из контрагентов. В частности, предполагается, что из общего числа N потенциальных контрагентов n (n/N%) всегда выбирают стратегию А, а m (m/N%) -- стратегию Б. Тем самым создаются предпосылки для достижения нового типа равновесия, эволюционно-стабильных стратегий. Эволюционно-стабильной (ESS -- Evolutionary Stable Strategy) становится та стратегия, при которой если все члены определенной популяции используют ее, то никакая альтернативная стратегия не может ее вытеснить посредством механизма естественного отбора. Рассмотрим в качестве примера простейший вариант проблемы координации: разъезд на узкой дороге двух автомобилей. Предполагается, что в данной местности лево- и правосторонний стандарты движения равноправны (или же Правила дорожного движения просто не всегда выполняются). Автомобилю А движутся навстречу несколько автомобилей, с которыми ему нужно разъехаться. Если оба автомобиля принимают влево, въезжая на левую обочину по ходу движения, то они разъезжаются без проблем. То же самое происходит, если оба автомобиля принимают вправо. Когда же один автомобиль принимает вправо, а второй -- влево и наоборот, то разъехаться они не смогут (рис.6).
Рисунок 6
Итак, автомобилисту А известен приблизительный процент автомобилистов Б, систематически принимающих влево (Р), и процент автомобилистов Б, принимающих вправо (1 -- Р). Условие для того, чтобы стратегия «принять вправо» стала для автомобилиста А эволюционно-стабильной, формулируется следующим образом: EU(вправо) > EU(влево), или
0P+ 1(1 - Р) > 1Р+ 0(1 - Р),
откуда Р< 1/2. Таким образом, при превышении доли автомобилистов во встречном потоке, принимающих вправо, уровня 50% эволюционно-стабильной стратегией становится «принять вправо» -- сворачивать на правую обочину при каждом разъезде.
В общем виде требования к эволюционно-стабильной стратегии записываются следующим образом. Стратегия I, используемая контрагентами с вероятностью p, является эволюционно-стабильной для игрока тогда и только тогда, когда выполняются следующие условия
EU(I, p) > EU{J, p),
что тождественно
pU(I, I) + (l -p)U(I,J)>pU(J,I) + (1 - p)U(J,J) (3)
Из чего следует:
U(I, I)> U(J, I)
U(I, I) = U(J, I)
U(I, J) > U(J, J),
где -- U(I, I) выигрыш игрока при выборе стратегии I, если контрагент выбирает стратегию I; U(J, I) -- выигрыш игрока при выборе стратегии J, если контрагент выбирает стратегию I, и т. д.
Рисунок 7
Можно представить эти условия и в графической форме. Отложим по вертикальной оси ожидаемую полезность выбора той или иной стратегии, а по горизонтальной -- долю индивидов в общей популяции игроков, выбирающих обе стратегии. Тогда мы получим следующий график (значения взяты из модели разъезда двух автомобилей), изображенный на рис. 7.
Из рисунка следует, что и «принять влево», и «принять вправо» имеют равные шансы на то, чтобы стать эволюционно-стабильной стратегией до тех пор, пока ни одна из них не охватила больше половины «популяции» водителей. Если же стратегия перешагивает этот рубеж, то она постепенно, но неизбежно вытеснит другую стратегию и охватит всю популяцию водителей. Дело в том, что, если стратегия перешагивает рубеж 50%, для любого водителя становится выгодным использовать ее в маневрах, что, в свою очередь, еще больше увеличивает привлекательность данной стратегии для остальных водителей. В строгой форме данное утверждение будет выглядеть следующим образом
dp/dt = G , G">0 (4)
Главным результатом анализа повторяющихся игр является увеличение числа точек равновесия и решение на этой основе проблем координации, кооперации, совместимости и справедливости. Даже в дилемме заключенных, переход к повторяющемуся взаимодействию позволяет достичь оптимального по Парето результата («отрицать вину»), не выходя за рамки нормы рациональности и запрета на обмен информацией между игроками. Именно в этом смысл «всеобщей теоремы»: любой исход, устраивающий индивида индивидуально, может стать при переходе к структуре повторяющейся игры равновесным. В ситуации дилеммы заключенных равновесным исходом при определенных условиях может стать и простая стратегия «не признавать», и множество смешанных стратегий. В числе смешанных и эволюционных стратегий, отметим следующие: Tit-For-Two-Tats -- начинать с отрицания вины и признавать вину, только если в два предшествующих периода кряду контрагент признавал вину; DOWING -- стратегия, исходящая из предположения о равновероятном использовании контрагентом стратегий «отрицать вину» и «признавать» в самом начале игры. Далее каждое отрицание вины со стороны контрагента поощряется, а каждое признание -- наказывается выбором стратегии «признавать вину» в следующий период; TESTER -- начинать с признания вины, и если контрагент тоже признает вину, то в следующем периоде отрицать вину.
ЗАКЛЮЧЕНИЕ
В заключение эссе можно сделать вывод о необходимости использования теории игр в современных экономических условиях.
В условиях альтернативы (выбора) очень часто нелегко принять решение и выбрать ту или иную стратегию. Исследование операций позволяет с помощью использования соответствующих математических методов принять обоснованное решение о целесообразности той или иной стратегии. Теория игр, имеющая в запасе арсенал методов решения матричных игр, позволяет эффективно решать указанные задачи несколькими методами и из их множества выбрать наиболее эффективные, а также упрощать исходные матрицы игр.
В эссе были проиллюстрированы практическое применение основных стратегий теории игр и сделаны соответствующие выводы, изучены самые используемые и часто применяемые стратегии и основные понятия.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Петросян Л.А, Зенкевич Н.А., Шевкопляс Е.В.: Теория игр: учебник. Издательство: BHV, 2012.-212с.
2. Лабскер Л.Г., Ященко Н.А.: Теория игр в экономике. Практикум с решением задач. Учебное пособие. Издательство: Кнорус, 2014.-125с.
3. Нейлбафф, Диксит: Теория игр. Искусство стратегического мышления в бизнесе и жизни. Издательство: Манн, Иванов и Фербер, 2015 .- 99с.
4. Олейник А.Н.. Институциональная экономика. Учебное пособие, Москва ИНФРА-М, 2013.-78с.
5. Протасов И.Д. Теория игр и исследование операций: учеб. пособие. - М.: Гелиос АРВ, 2013.-100с.
6. Самаров К.Л. Математика. Учебно-методическое пособие по разделу «Элементы теории игр», ООО «Резольвента»,2011.-211с.
7. Шикин Е.В. Математические методы и модели в управлении: учеб. пособие для студентов упр. спец. вузов. - М.: Дело, 2014.-201с.
Размещено на Allbest.ru
...Подобные документы
Разнообразие ситуаций и сфер жизни человека, в которых применима теория игр. Необходимость использования теории игр в современных экономических условиях. Доказательста необходимости институтов с помощью теории игр. Эволюционно-стабильная стратегия.
курсовая работа , добавлен 28.11.2013
Характеристика сущности игр - ситуаций, в которых есть несколько субъектов, сознающих, что их действия влияют на поведение других субъектов. Цели теории игр. Выработка рекомендаций для рационального поведения игроков, определения оптимальной стратегии.
презентация , добавлен 31.03.2011
Теория международной торговли Хекшера–Олина. Теорема выравнивания цен на факторы производства Самуэльсона. Теория «цикла жизни продукта». Теория Майкла Портера: теория конкурентных преимуществ. Эклектическая теория интернационализации производства услуг.
контрольная работа , добавлен 12.05.2009
Макроэкономика. Теория потребления. Обоснование теории. Объективные и субъективные факторы потребления. Кейнсианская теория потребления. Графическая интерпретация функции потребления. Формирование спроса на товары и услуги.
контрольная работа , добавлен 23.06.2007
Расхождение кейнсианской и монетаристской теории. Внутренняя стабильность в рыночной экономике. Влияние финансовой политики и роли денег в экономике. Изменения цены на товары и услуги. Определение скорости обращения денег. Количественная теория денег.
контрольная работа , добавлен 16.01.2011
Понятие международной торговли. Классическая теория международной торговли. Теория сравнительных преимуществ. Меркантилиститская теория международной торговли. Теория абсолютных преимуществ. Тeopuя Хекшера - Олина - Самуэльсона. Теория Леонтьева.
реферат , добавлен 16.01.2008
Возникновение экономической теории. История экономики как наука. Предмет и метод экономической теории. Экономическая теория - наука в своей основе эмпирическая, то есть основана на фактах реальной жизни. Экономическая теория: функции, методы исследования.
курсовая работа , добавлен 16.12.2003
Разнообразие экономических теорий отечественных и зарубежных учёных-экономистов, которые были рождены в различных исторических эпохах, плюсы, минусы каждой теории. Этапы развития экономического мышления человека. Особенности развития экономической теории.
контрольная работа , добавлен 22.12.2009
Понятие труда, его сущность и особенности, роль в становлении человека и место в экономике. Место человека в современной экономической теории. Хозяйственные системы, их разновидности и координация выбора. Предмет и методы изучения микроэкономики.
курс лекций , добавлен 10.02.2009
Человек как потребитель, производитель, управленец в системе экономических отношений. Сравнение экономического, психологического и социологического подхода к изучению поведения человека в экономике. Разнообразие моделей человека в экономической теории.