Если в игре каждый из противников применяет только одну и ту же стратегию, то про саму игру в этом случае говорят, что она происходит в чистых стратегиях , а используемые игроком А и игроком В пара стратегий называются чистыми стратегиями .
Определение. В антагонистической игре пара стратегий (А i , В j) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.
Применять чистые стратегии имеет смысл тогда, когда игроки А и В располагают сведениями о действиях друг друга и достигнутых результатах. Если допустим, что хотя бы одна из сторон не знает о поведении противника, то идея равновесия нарушается, и игра ведется бессистемно.
Рассмотрим матричную игру G (3х4)
В этом примере нижняя цена игры равна верхней: ==9, т.е. игра имеет седловую точку.
Оказывается, что в этом случае максиминные стратегии А 2 и В 2 будут устойчивыми по отношению к информации о поведении противника.
Действительно, пусть игрок А узнал, что противник применяет стратегию В 2 . Но и в этом случае игрок А будет по-прежнему придерживаться стратегии А 2 , потому что любое отступление от стратегии А 2 только уменьшит выигрыш. Равным образом, информация, полученная игроком В , не заставит его отступить от своей стратегии В 2 .
Пара стратегий А 2 и В 2 обладает свойством устойчивости, а выигрыш (в рассматриваемом примере он равен 9), достигаемый при этой паре стратегий, оказывается седловой точкой платежной матрицы.
Признак устойчивости (равновесности) пары стратегии - это равенство нижней и верхней цены игры.
Стратегии А i и В j (в рассматриваемом примере А 2 , В 2), при котором выполняется равенство нижней и верхней цены игры, называются оптимальными чистыми стратегиями, а их совокупность - решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях.
Величина называется ценой игры.
Если 0, то игра выгодна для игрока А, если 0 - для игрока В; при =0 игра справедлива, т.е. является одинаково выгодной для обоих участников.
Однако наличие седловой точки в игре - это далеко не правило, скорее - исключение. Большинство матричных игр, не имеет седловой точки, а следовательно, не имеет оптимальных чистых стратегий. Впрочем, есть разновидность игр, которые всегда имеют седловую точку и, значит, решаются в чистых стратегиях. Это - игры с полной информацией.
Теорема 2. Каждая игра с полной информацией имеет седловую точку, а следовательно, решается в чистых стратегиях, т.е. имеется пара оптимальных чистых стратегий, дающая устойчивый выигрыш, равный.
Если такая игра состоит только из личных ходов, то при применении каждым игроком своей оптимальной чистой стратегии она должна кончаться выигрышем, равным цене игры. Скажем, шахматная игра, как игра с полной информацией, либо всегда кончается выигрышем белых, либо всегда - выигрышем черных, либо всегда - ничьей (только чем именно - мы пока не знаем, так как число возможных стратегий в шахматной игре огромно).
Если матрица игры содержит седловую точку, то ее решение сразу находится по принципу максимина.
Возникает вопрос: как найти решение игры, платежная матрица которой не имеет седловой точки? Применение максиминного принципа каждым из игроков обеспечивает игроку А выигрыш не менее, игроку - проигрыш не больше. Учитывая что, естественно для игрока А желание увеличить выигрыш, а для игрока В - уменьшить проигрыш. Поиск такого решения производит к необходимости применять смешанные стратегии: чередовать чистые стратегии с какими-то частотами.
Определение. Случайная величина, значениями которой являются чистые стратегии игрока, называется его смешанной стратегией .
Таким образом, задание смешанной стратегии игрока состоит в указании тех вероятностей, с которыми выбираются его чистые стратегии.
Будем обозначать смешанные стратегии игроков А и В соответственно
S A =||p 1 , p 2 , ..., p m ||,
S B =||q 1 , q 2 , ..., q n ||,
где p i - вероятность применения игроком А чистой с тратегии А і ; ; q j - вероятность применения игроком В чистой стратегии B j ; .
В частном случае, когда все вероятности, кроме одной, равны нулю, а эта одна - единице, смешанная стратегия превращается в чистую.
Применение смешанных стратегий осуществляется, например, таким образом: игра повторяется много раз, но в каждой партии игрок применяет различные чистые стратегии с относительными частотами их применения, равными p i и q j .
Смешанные стратегии в теории игр представляют собой модель изменчивой, гибкой тактики, когда ни один из игроков не знает, какую чистую стратегию выберет противник в данной партии.
Если игрок А применяет смешанную стратегию S A =||p 1 , p 2 , ..., p m ||, а игрок В смешанную стратегию S B =||q 1 , q 2 , ..., q n ||, то средний выигрыш (математическое ожидание) игрока А определяется соотношением
Естественно, что ожидаемый проигрыш игрока В равен такой же величине.
Итак, если матричная игра не имеет седловой точки, то игрок должен использовать оптимальную смешанную стратегию, которая обеспечит максимальный выигрыш.
Естественно возникает вопрос: какими соображениями нужно руководствоваться при выборе смешанных стратегий? Оказывается принцип максимина сохраняет свое значение и в этом случае. Кроме того, важное значение для понимания решения игр, играют основные теоремы теории игр.
Математические методы и модели в экономике
Матричные игры
Введение
В экономической практике часто возникают ситуации, в которых различные стороны преследуют различные цели. Например, отношения между продавцом и покупателем, поставщиком и потребителем, банком и вкладчиком и т.д. Такие конфликтные ситуации возникают не только в экономике, но в других видах деятельности. Например, при игре в шахматы, шашки, домино, лото и т.д.
Игра – это математическая модель конфликтной ситуации с участием не менее двух лиц, использующих несколько различных способов для достижения своих целей. Игра называется парной, если в ней участвуют два игрока. Игра называется антагонистической, если выигрыш одного игрока равен проигрышу другого. Следовательно, для задания игры достаточно задать величины выигрышей одного игрока в различных ситуациях.
Любой способ действия игрока в зависимости от сложившейся ситуации называется стратегией. Каждый игрок располагает определенным набором стратегий. Если число стратегий конечно, то игра называется конечной, в противном случае – бесконечной . Стратегии называются чистыми, если каждый из игроков выбирает только одну стратегию определенным, а не случайным образом.
Решение игры заключается в выборе такой стратегии, которая удовлетворяет условию оптимальности. Это условие состоит в том, что один игрок получает максимальный выигрыш , если второй придерживается своей стратегии. И наоборот, второй игрок получает минимальный проигрыш , если первый из игроков придерживается своей стратегии. Такие стратегии называются оптимальными . Таким образом, цель игры – это определение оптимальной стратегии для каждого игрока.
Игра в чистых стратегиях
Рассмотрим игру с двумя игроками А и В. Предположим, что игрок А имеет m стратегий А 1 , А 2 , …, А m , а игрок В имеет n стратегий B 1 , B 2 , … ,B n . Будем считать, что выбор игроком А стратегии А i , а игроком В стратегии B j однозначно определяет исход игры, т.е. выигрыш a ij игрока А и выигрыш b ij игрока В. Здесь i=1,2,…,m, j=1,2,…,n.
Простейшей игрой с двумя игроками является антагонистическая игра, т.е. игра, в которой интересы игроков прямо противоположны. В этом случае выигрыши игроков связаны равенством
b ij =-a ij
Это равенство означает, что выигрыш одного из игроков равен проигрышу другого. В этом случае достаточно рассматривать лишь выигрыши одного из игроков, например, игрока А.
Каждой паре стратегий А i и B j соответствует выигрыш a ij игрока А. Все эти выигрыши удобно записывать в виде так называемой платежной матрицы
Строки этой матрицы соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В. В общем случае такая игра называется (m×n)-игрой.
Пример 1. Два игрока А и В бросают монету. Если стороны монеты совпадают, то выигрывает А , т.е. игрок В платит игроку А некоторую сумму, равную 1, а если не совпадают, то выигрывает игрок В, т.е. наоборот, игрок А платит игроку В эту же сумму, равную 1. Сформировать платежную матрицу.
Решение. По условию задачи
«Чистые» стратегии
Мы уже знакомы с косяками. Однако, что будет, если из цепочки какой-либо стратегии убрать косяки? Мы получим «чистую стратегию». Чистыми стратегиями являются те, в цепочке действий которых, начиная от самого корня и до результативной части, отсутствуют неэффективные подстратегии (косяки), а об этом может зачастую свидетельствовать только наличие всех звеньев в сознании.
Конечно с точки зрения всех возможных исходов применения стратегии нам сложно говорить о самой-самой эффективной, так как мы можем просто не обладать определенным опытом, а следовательно и определенными промежуточными стратегиями, однако именно со стороны нашего опыта, стратегия должна быть максимально эффективной.
Понятие чистых стратегий также является одним из ключевых в данных материалах, поэтому приведу пример:
Вечер. Вы в родном районе спешите домой. Молоко убегает. Пролетая мимо «подозрительного типа каких-много» вы слышите в свой адрес «Эй, ты, [вырезано цензурой]. Ты тут не ходи, снег башка попадет!».
Что вы сделаете? Вариантов может быть много. Кто-то пойдет выяснять отношения, кто-то испугается и ускорит шаг, кто-то крикнет что-то в ответ. Однако, давайте подумаем, какой в данном случае является чистая стратегия поведения?
Незнакомый вам человек, что-то кричит вам на улице. У вас есть свои дела, по которым вы собственно и идете. Судя по тексту, позитивные выгоды для вас от общения с этим человеком маловероятны. Логичный вывод: спокойно пойти дальше по своим делам. Обращаю внимание на то, что именно «спокойно», без тени негативных эмоций, а со здоровым безразличием к происходящему. Как много людей так поступят? Предполагаю, что подавляющее меньшинство. Почему?
Потому что большинство людей имеет целую прослойку подсознательных стратегий, привязанных в более нижних слоях к самосохранению, в частности таковыми могут быть: «Всегда отвечать на грубость грубостью», «Если кто-то говорит гадость, то надо бежать», «Если кто-то грубит - надо набить ему лицо», «Если кто-то грубит, значит есть опасность», и тому подобное в разных вариациях. Конечно не все предпримут какие-то активные действия, но эмоционально это заденет почти всех. И это косяк.
Чистые же стратегии всегда эмоционально нейтральны или позитивны, и это заложено в вашем мозге, остается только этим воспользоваться.
Немного про чистые стратегии вы можете прочитать в заметках «Почему именно чистые стратегии?» и «Хаус, Хопкинс, и прочее».
Из книги Стратегии гениев. Альберт Эйнштейн автора Дилтс РобертСтратегии 1. Определение термина “стратегия”:а) Происходит от греческого слова “strategos”, означающего: “военачальник”,“наука, искусство ведения войны”,“искусство руководства общественной, политической борьбой”.б) Детальный план достижения цели или выгодного
Из книги Стратегии гениев (Аристотель Шерлок Холмс Уолт Дисней Вольфганг Амадей Моцарт) автора Дилтс Роберт Из книги Ты умеешь хорошо учиться?! Полезная книга для нерадивых учеников автора Карпов АлексейСТРАТЕГИИ Твоя учеба пойдет на совершенно другом уровне качества, если ты подумаешь и выберешь стратегию действий.Стратегия - это общий план. Это общая линия с учетом реальных условий. Это цели, сроки, учет непредсказуемости и многообразия… Это само ощущение пульса
Из книги Стратегия разума и успеха автора Антипов Анатолий Из книги Эмоциональный интеллект автора Гоулман ДэниелКоэффициент умственного развития и эмоциональный интеллект: чистые типы Коэффициент умственного развития и эмоциональный интеллект - это не находящиеся в оппозиции, а скорее отдельные компетенции. Все мы сочетаем интеллект с остротой переживаний; люди с высоким
Из книги 12 христианских верований, которые могут свести с ума автора Таунсенд ДжонПравильные намерения или чистые помыслы Правильное намерение - это решение поступать правильно. Мы выбираем хороший, угодный Богу поступок, обычно не задумываясь о том, сильно ли мы хотим его совершить. Просто делаем это - и все. Многие евангелические проповедники
Из книги Вступая в жизнь: Сборник автора Автор неизвестенРудольф Иванович АБЕЛЬ: «ПОМНИТЕ, КАК ГОВОРИЛ ДЗЕРЖИНСКИЙ: «ЧИСТЫЕ РУКИ, ХОЛОДНАЯ ГОЛОВА И ГОРЯЧЕЕ СЕРДЦЕ...» Более тридцати лет Рудольф Иванович Абель отдал работе в советской разведке. Он был награжден орденом Ленина, двумя орденами Красного Знамени, орденом Трудового
Из книги Homo Sapiens 2.0 [Человек Разумный 2.0 http://hs2.me] автора Sapiens HomoСтратегии
Из книги Homo Sapiens 2.0 автора Sapiens 2.0 Homo"Чистые" стратегии Мы уже знакомы с косяками. Однако, что будет, если из цепочки какой-либо стратегии убрать косяки? Мы получим «чистую стратегию». Чистыми стратегиями являются те, в цепочке действий которых, начиная от самого корня и до результативной части, отсутствуют
Из книги Начни. Врежь страху по лицу, перестань быть «нормальным» и займись чем-то стоящим автора Эйкафф Джон Из книги Человек как животное автора Никонов Александр ПетровичСтратегии Общее понятие стратегий В принципе, все в той или иной степени понимают, что такое стратегия. Обладая каким-то набором знаний, полученных в результате обретения и обработки опыта, мы строим определенные модели поведения.Стратегия - это модель достижения цели.
Из книги Включите свою рабочую память на полную мощь автора Эллоуэй ТрейсиПочему именно чистые стратегии? Львиная доля материала данного проекта постоянно указывает на тот момент, что необходимо использовать для перезаписи именно чистые стратегии и обязательно искать косяк исходя из них. Данный момент является неочевидным на первый взгляд и
Из книги Интроверт в экстравертном мире автора Романцева Елизавета Из книги автора Из книги автораСтратегии Компьютерные стратегии требуют от игрока сосредоточенности, умения планировать свои действия и решать разнообразные задачи. Последние исследования свидетельствуют о том, что стратегии помогают улучшать когнитивные навыки игроков любого возраста. Согласно
Из книги автораЧистые типы Существует такое понятие – «чистый психологический тип». Собственно, понятие есть, а предметов, то есть людей, идеально подходящих под это понятие, практически нет. Нет чистокровных интровертов и однозначных экстравертов. Тем более, что мы с вами договорились
Среди конечных игр, имеющих практическое значение, сравнительно редко встречаются игры с седловой точкой; более типичным является случай» когда нижняя и верхняя цена - игры различны. Анализируя матрицы таких игр, мы пришли к заключению, что если каждому игроку предоставлен выбор
одной - единственной стратегии., то в расчете на разумно действующего противника этот выбор должен определяться принципом минимакса. Придерживаясь своей максиминной стратегии, мы при любом поведении противника заведомо гарантируем себе выигрыш, равный нижней цене -игры а. Возникает естественный вопрос: нельзя ли гарантировать себе средний выигрыш, больший а, если применять не одну-единственную «чистую» стратегию, а чередовать случайным образом несколько стратегий?
Такие комбинированные стратегии, состоящие в применении нескольких чистых стратегий, чередующихся по случайному закону с определенным соотношением частот, в теории игр называются смешанными стратегиями.
Очевидно, каждая чистая стратегия является частным случаем смешанной, в которой все стратегии, кроме одной, применяются с нулевыми частотами, а данная - с частотой 1.
Оказывается, что, применяя не только чистые, но и смешанные стратегии, можно для каждой конечной игры получить решение, т. е. пару таких (в общем случае смешанных) стратегий, что при применении их обоими игроками выигрыш будет равен цене игры, а при любом одностороннем отклонении от оптимальной стратегии выигрыш может измениться только в сторону, невыгодную для отклоняющегося.
Высказанное утверждение составляет содержание так называемой основной теоремы теории игр. Эта теорема была впервые доказана фон Нейманом в 1928 г. Известные доказательства теоремы сравнительно сложны; поэтому приведем только ее формулировку.
Каждая конечная игра имеет, по крайней мере, одно решение (возможно, в области смешанных стратегий).
Выигрыш, получаемый в результате решения, называется ценой игры. Из основной теоремы следует, что каждая конечная игра имеет цену. Очевидно, что цена игры v всегда лежит между нижней ценой игры а и верхней ценой игры :
Действительно, а есть максимальный гарантированный выигрыш, который мы можем себе обеспечить, применяя только свои чистые стратегии. Так как смешанные стратегии включают в себя в качестве частного случая и все чистые, то, допуская, кроме чистых, еще и смешанные
стратегии, мы, во всяком случае, не ухудшаем своих возможностей; следовательно,
Аналогично, рассматривая возможности противника, покажем, что
откуда следует доказываемое неравенство (3.1).
Введем специальное обозначение для смешанных стратегий. Если, например, наша смешанная стратегия состоит в применении стратегий АЛ, с частотами причем будем обозначать эту стратегию
Аналогично смешанную стратегию противника будем обозначать:
где - частоты, в которых смешиваются стратегии
Предположим, что нами найдено решение игры, состоящее из двух оптимальных смешанных стратегий S, S. В общем случае не все чистые стратегии, доступные данному игроку, входят в его оптимальную смешанную стратегию, а только некоторые. Будем называть стратегии, входящие в оптимальную смешанную стратегию игрока, его «полезными» стратегиями.
Оказывается, что решение игры обладает еще одним замечательным свойством: если один из игроков придерживается своей оптимальной смешанной стратегии 5 (5). то выигрыш остается неизменным и равным цене игры v, независимо от того, что делает другой игрок, если он. только не выходит за пределы своих «полезных» стратегий. Он, например, может пользоваться любой из своих «полезных» стратегий в чистом виде, а также может смешивать их в любых пропорциях.
Докажем это утверждение. Пусть имеется решение игры . Для конкретнрсти будем считать, что оптимальная смешанная стратегия состоит из смеси трех
«полезных» стратегий соответственно состоит из смеси трех «полезных» стратегий
причем Утверждается что если мы будем придерживаться стратегии S, то противник может применять стратегии в любых пропорциях, а выигрыш останется неизменным и по-прежнему будет равен цене игры
Смешанной стратегией SA игрока А называется применение чистых стратегий A1, A2, ..., Am с вероятностями p1, p2, ..., pi, ..., pm причем сумма вероятностей равна 1: Смешанные стратегии игрока А записываются в виде матрицы или в виде строки SA = (p1, p2, ..., pi, ..., pm) Аналогично смешанные стратегии игрока В обозначаются: , или, SB = (q1, q2, ..., qi, ..., qn), где сумма вероятностей появления стратегий равна 1: Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*A , S*B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству: ? ? v ? ? (3.5) где? и? - нижняя и верхняя цены игры. Справедлива следующая основная теорема теории игр - теорема Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть S*A = (p*1, p*2, ..., p*i, ..., p*m) и S*B = (q*1, q*2, ..., q*i, ..., q*n) - пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной. Справедлива теорема об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий. Эта теорема имеет большое практическое значение - она дает конкретные модели нахождения оптимальных стратегий при отсутствии седловой точки. Рассмотрим игру размера 2×2, которая является простейшим случаем конечной игры. Если такая игра имеет седловую точку, то оптимальное решение - это пара чистых стратегий, соответствующих этой точке. Игра, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий S*A = (p*1, p*2) и S*B = (q*1, q*2). Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок А придерживается своей оптимальной стратегии S"A, то его средний выигрыш будет равен цене игры v, какой бы активной стратегией ни пользовался игрок В. Для игры 2×2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А (проигрыш игрока В) - случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выигрыш игрока А (оптимальная стратегия) будет равен v и для 1-й, и для 2-й стратегии противника. Пусть игра задана платежной матрицей Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию, а игрок В - чистую стратегию B1 (это соответствует 1-му столбцу платежной матрицы Р), равен цене игры v: a11 p*1+ a21 p*2= v. Тот же средний выигрыш получает игрок А, если 2-й игрок применяет стратегию B2, т.е. a12 p*1+ a22 p*2= v. Учитывая, что p*1+ p*2= 1, получаем систему уравнений для определения оптимальной стратегии S"A и цены игры v: (3.6) Решая эту систему, получим оптимальную стратегию (3.7) и цену игры (3.8) Применяя теорему об активных стратегиях при отыскании SВ*- оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А1 или А2) средний проигрыш игрока В равен цене игры v, т.е. (3.9) Тогда оптимальная стратегия определяется формулами: (3.10)
