Предмет теории игр

КРЕМЛЁВ Александр Гурьевич доктор физико-математических наук профессор ТЕОРИЯ ИГР 1. ПРЕДМЕТ ТЕОРИИ ИГР Предметом теории игр является математический анализ конфликтных ситуаций, формализованное описание которых представлено в виде математической модели, определяющей некоторую игру. Конфликтная ситуация – это ситуация, в которой сталкиваются интересы двух (и более) противодействующих сторон, преследующих различные цели (несовпадающие полностью или частично). Эти конфликтующие стороны стремятся предпринять такие действия (выбрать такие решения), чтобы достичь наибольшего для себя в данных условиях успеха. Таким образом, если цели сторон противоположны, то максимизация успеха (например, выигрыша) одной из сторон будет означать максимизацию проигрыша другой стороны. А если сторон несколько (более двух), то это ведет к уменьшению их возможных выигрышей. Поэтому конфликтующие стороны будут осуществлять поиск наиболее приемлемых для себя решений (причем эта приемлемость должна быть для каждой из сторон, и, в какой-то мере, для всех сторон одновременно). Если каждая из сторон (в результате собственной оценки текущей ситуации) примет какое-то определенное решение, то последующая реализация принятых решений приведет к конкретному результату – распределению выигрышей сторон. Решения сторонами могут приниматься независимо друг от друга и не сообщаться заранее другим сторонам конфликта. Таким образом, каждой из сторон приходится принимать решение в условиях неопределенности поведения противника (противодействующих сторон), т. е. выигрыш каждой стороны зависит от того, как поведут себя другие стороны конфликта. Как оптимизировать принятие (или выбор) правильного решения? Какие требования предъявляются к таким оптимальным решениям? Как найти оптимальные решения? Теория игр занимается исследованием математических моделей конфликтных ситуаций (игр) и их формальным решением, что позволяет: • смоделировать процесс игры и ее возможные результаты до ее фактического начала; • по результатам анализа смоделированной игры принять решение о целесообразности участия и оптимальном поведении в реальном конфликте. Таким образом, теория игр дает математический прогноз конфликта (с учетом степени адекватности используемой модели конфликта). Пример. 1) Рассмотрим следующую игру, в которой участвуют два игрока. Игрок 1 бросает случайным образом на горизонтальную плоскость монету. Если выпадает «герб», то он платит игроку 2 в размере 1 д. е., если выпадает «решка» (цифра), то игрок 2 платит ему в размере 1 д. е. Цель каждого игрока – максимизация своего выигрыша. Решение. Сформируем таблицу выигрышей игрока 2 (очевидно, что выигрыши игрока 1 противоположны по знаку и равны по модулю соответствующим выигрышам игрока 2). Таблица выигрышей Игрок 1 Исходы бросания монеты Г Р Игрок 2 +1 –1 Если монета правильная, однородная, то вероятности выпадения «герба» и «решки» равные: в соответствии с классической формулой находим . Если обозначить , – сл. в., определяющие величины выигрышей соответственно игроков 1 и 2 в одной партии (при одном бросании монеты), то средние ожидаемые выигрыши игроков 1 и 2 (т. е. их выигрыши в среднем на одну партию игры при многократном повторении игры) равны соответственно и – математическим ожиданиям сл. в. и . Тогда средний ожидаемый выигрыш игрока 2 равен . Поскольку – дискретная сл. в., то по формуле математического ожидания имеем (где , т. е. при достаточно большом числе партий выигрыши игроков (даже суммарные) → 0. В данной игре ничего не зависит от игроков. Для каждой партии (каждого хода) правила игры определяют конкретное распределение вероятностей возможных исходов. 2) Изменим правила игры. Игрок 1 бросает случайным образом монету, но игроку 2 не сообщается исход бросания. Более того игрок 2 пытается отгадать этот исход. Если отгадывает, то получает 1 д. е. от игрока 1, если не отгадывает, то платит ему 1 д. е. Цели игроков – прежние. Сформируем таблицу выигрышей игрока 2. Таблица выигрышей Игрок 1 Исходы бросания монеты Г Р Варианты выбора игрока 2 Г +1 –1 Р –1 +1 Цель игрока 2 – получить максимально возможный выигрыш. Какой вариант выбора выбрать? Если игрок 2 всегда выбирает вариант «Г», то = 0 как в игре типа 1. Аналогичный результат получится, если игрок 2 всегда выбирает вариант «Р», так как . А если игрок 2 выбирает варианты случайно, например, P(Г) = x, P(Р) = 1 – x, где 0 ≤ x ≤ 1, то его средний ожидаемый выигрыш равен . Таблица выигрышей Игрок 1 Вероятности исходов бросания монеты 1/2 1/2 Г Р Вероятности выбора вариантов игроком 2 x Г +1 –1 1 – x Р –1 +1 3) Изменим правила игры. Игрок 1 не бросает монету, а выбирает сторону монеты, но игроку 2 не сообщает о своем выборе. Игрок 2 пытается отгадать, какую сторону выбрал игрок 1. Если отгадывает, то получает 1 д. е. от игрока 1, если не отгадывает, то платит ему 1 д. е. Сформируем таблицу выигрышей игрока 2. Обозначим вероятности выбора вариантов игроком 1 P(Г) = y, P(Р) = 1 – y, где 0 ≤ y ≤ 1, Таблица выигрышей Вероятности выбора вариантов игроком 1 y 1 – y Г Р Вероятности выбора вариантов игроком 2 x Г +1 –1 1 – x Р –1 +1 Как вести себя игрокам? Какую стратегию (образ действий) выбрать игрокам? Цели игроков – получить для себя максимально возможный выигрыш – противоположные по отношению друг к другу. Обозначим через X = (x, 1 – x) стратегию игрока 2 при фиксированной вероятности x. Тогда {X | 0 ≤ x ≤ 1} – множество возможных стратегий игрока 2. Аналогично Y = (y, 1 – y) – стратегия игрока 1 при фиксированной вероятности y; {Y | 0 ≤ y ≤ 1} – множество возможных стратегий игрока 1. Найдем средний ожидаемый выигрыш игрока 2 при стратегиях игроков X и Y: . Выигрыш игрока 2 (как и игрока 1) может составить от –1 до +1. Например, при получим , т. е. игрок 2 выиграет в среднем больше игрока 1. Рассмотрим следующий вопрос: среди всех возможных стратегий X, 0 ≤ х ≤ 1 игрока 2 найти такую стратегию X* = (x*, 1 – x*) и величину , чтобы выполнялось условие: для стратегий Y, 0 ≤ y ≤ 1, игрока 1, т. е. стратегия X* гарантирует выигрыш игроку 2 не менее . Указанное условие можно записать в следующем виде: . В нашем примере имеем т. е. . Тогда получим при x* = 1/2. Итак, стратегия X* = (½, ½) гарантирует выигрыш игроку 2, равный = 0. Аналогичный результат игры получим при стратегии Y* = (½, ½) игрока 1. Пример. Рассмотрим игру с бросанием игрального кубика. 1) Игрок 1 бросает случайным образом на горизонтальную плоскость игральный кубик. Если выпадает четное число очков, то он платит игроку 2 количество д. е., равное выпавшему числу, если выпадает нечетное число очков, то игрок 2 платит ему в размере выпавшего числа. Сформируем таблицу выигрышей игрока 2 (очевидно, что выигрыши игрока 1 противоположны по знаку и равны по модулю соответствующим выигрышам игрока 2). Таблица выигрышей Игрок 1 Исходы бросания кубика 1 2 3 4 5 6 Игрок 2 –1 2 –3 4 –5 6 Вычислим средние ожидаемые выигрыши (математические ожидания) игроков: , т. е. данная игра более выгодная для игрока 2, чем для игрока 1. 2) Игрок 1 бросает случайным образом на горизонтальную плоскость игральный кубик, но игроку 2 не сообщает исход бросания. Игрок 2 пытается отгадать, четное выпало число очков или нечетное. Если выпадает четное число очков и игрок 2 правильно называет четность, то он получает от игрока 1 количество д. е., равное выпавшему числу. Если выпадает нечетное число очков и игрок 2 правильно называет нечетность, то игроки ничего не платят друг другу. Если игрок 2 не отгадывает, то он платит игроку 1 в размере выпавшего числа. Сформируем таблицу выигрышей игрока 2 (выигрыши игрока 1 противоположны по знаку и равны по модулю соответствующим выигрышам игрока 2). Таблица выигрышей Игрок 1 Исходы бросания кубика 1 2 3 4 5 6 Вероятности выбора вариантов игроком 2 x Ч –1 2 –3 4 –5 6 1 – x Н/Ч –2 –4 –6 Вычислим средние ожидаемые выигрыши игроков: , т. е. игра безобидна () при x = 4/5. Если игрок 2 все время называет Ч, то . 3) Игрок 1 не бросает кубик, а выбирает сторону кубика (или выбирает целое число от 1 до 6), но игроку 2 не сообщает о своем выборе. Условия платежей совпадают с условиями в игре 2. Определим множества стратегий игроков: – игрока 2; – игрока 1. Средние ожидаемые выигрыши игроков равны: , где матрица выигрышей в данной игре . Оптимальные (равновесные) стратегии игроков: X0 = (6/17, 11/17), Y0 = (0, 0, 0, 0, 12/17, 5/17). Значение игры v0 = –30/17. Замечание. В условиях предположения о рациональности игроков можно исключить заведомо невыгодные для игроков стратегии. Действительно, игроку 1 невыгодно применять стратегии «1» и «3», поскольку они дают худший результат по сравнению со стратегией «5». Поэтому он никогда не будет выбирать стратегии «1» и «3», т. е. . Игрок 2 это понимает и принимает в расчет при выборе своей стратегии. Поэтому можно уменьшить размерность матрицы выигрышей, вычеркнув 1-й и 3-й столбцы, т. е. получим следующую матрицу Далее, игрок 1, выбирая определенную комбинацию стратегий «5» и «6» (т. е. 3-го и 4-го столбцов матрицы ), может получить больший выигрыш, чем при выборе стратегии «2» (1-й столбец матрицы ). Действительно, например, при  = 1/2 имеем Аналогичный результат имеем и для 2-го столбца матрицы . Таким образом, игрок 1 не будет применять свои стратегии «2» и «4», т. е. . Вычеркнув эти столбцы, получим следующую матрицу Обозначим р – вероятность выбора игроком 2 своей стратегии «Ч», тогда (1 – р) – вероятность выбора игроком 2 своей стратегии «Н/Ч», т. е. . Тогда при выборе игроком 1 своей стратегии «5» получим для игрока 2 , а при выборе игроком 1 своей стратегии «6» получим . Тогда наилучший результат игры v0 для игрока 2 (максимизация своего ожидаемого выигрыша при его минимизации игроком 1) определяется равенством . Решение из данного условия можно получить, используя следующую графическую интерпретацию. Найдем координаты точки А – точки пересечения : –5р = 12р – 6, 17р = 6, , , т. е. игроку 2 с вероятностью 6/17 нужно выбирать стратегию «Ч», а с вероятностью 11/17 – стратегию «Н/Ч». Теперь аналогично найдем наилучший результат игры для игрока 1. Обозначим q вероятность выбора игроком 1 своей стратегии «5», тогда (1 – q) – вероятность выбора игроком 1 своей стратегии «6», т. е. . Тогда при выборе игроком 2 своей стратегии «Ч» получим средний проигрыш игрока 1 (поскольку ) , а при выборе игроком 2 своей стратегии «Н/Ч» получим . Тогда наилучший результат игры v0 для игрока 1 (минимизация своего ожидаемого проигрыша при его максимизации игроком 2) определяется равенством . Решение из данного условия можно получить, используя следующую графическую интерпретацию. Найдем координаты точки В – точки пересечения : –11q +6 = 6q – 6, 17q = 12, , , т. е. игроку 1 с вероятностью 12/17 нужно выбирать стратегию «5», а с вероятностью 5/17 – стратегию «6». Таким образом, равновесные стратегии игроков: X0 = (6/17, 11/17), Y0 = (0, 0, 0, 0, 12/17, 5/17). Значение игры v0 = –30/17. ВЫВОДЫ 1. Игра – это конфликтная ситуация, регламентированная определенными правилами, указывающими: – порядок чередования действий (или «ходов») участников; – правила выполнения каждого хода; – количественный результат игры (выигрыш, проигрыш), к которому приводит данная совокупность ходов. 2. Сформулировать реальную конфликтную ситуацию в игровой форме – это значит схематизировать ее так, чтобы ясно были видны возможные способы поведения участников (называемые стратегиями) и численный результат (количественная оценка – платеж), к которому приводит каждая комбинация стратегий той и другой стороны. Формализованная схема конфликтной ситуации в математической форме представляет ее математическую модель. 3. Целью теории игр является выработка рекомендаций для разумного поведения игроков в конфликтных ситуациях, т. е. определение оптимальной стратегии каждого из игроков. Оптимальной стратегией игрока называется такая стратегия, которая при многократном повторении игры обеспечивает данному игроку максимально возможный средний выигрыш (или, что то же, минимально возможный средний проигрыш). 4. При выборе игроком этой стратегии за основу берется предположение, что его противник (или противники) является вполне разумным (мыслящим рационально), который делает все, чтобы помешать ему (игроку) добиться своей цели. Важным предположением в теории игр является следующее: все игроки действуют рационально, т. е. каждый игрок рассматривает доступные ему альтернативы, формирует представления относительно неизвестных параметров (возможных действий других игроков, их ресурсов), имеет четко определенные предпочтения и выбирает свои действия в результате некоторого процесса оптимизации (максимизации своей целевой функции). Более того, существенным является факт общеизвестности (общего знания) рациональности игроков, т. е. все игроки не только рациональны, но и знают, что другие игроки рациональны, что все игроки знают о том, что все они рациональны. 4. Основной принцип теории игр можно сформулировать так: выбирай свое поведение так, чтобы оно было рассчитано на наихудший для тебя образ действий противника. 5. «Решить игру» – это значит указать оптимальные стратегии для каждого игрока, такие, что они гарантируют каждому игроку при систематическом их применении в среднем наилучший возможный для него результат. Если игроки (участники некоторой игры) одинаково разумны (действуют рационально), то должно быть найдено некоторое равновесное положение, определяющее равновесный средний выигрыш для каждого игрока. Этот равновесный средний выигрыш, на который вправе рассчитывать каждый игрок, реализуется, если игроки будут вести себя разумно, т. е. придерживаться своих оптимальных стратегий. Следует заметить, что если какой-то игрок будет вести себя неразумно (нерационально) и примет иную, отличную от оптимальной стратегию, то его выигрыш может уменьшиться (в общем случае не увеличиться по сравнению с равновесным выигрышем).