Математическая теория игр. Примеры записи и решения игр из жизни
Математическая теория игр: чем занимается
Теория игр - совокупность математических методов решения конфликтных ситуаций (столкновений интересов). В теории игр игрой называется математическая модель конфликтной ситуации. Предмет особого интереса теории игр - исследование стратегий принятия решений участников игры в условиях неопределённости. Неопределённость связана с тем, что две или более стороны преследуют противоположные цели, а результаты любого действия каждой из сторон зависят от ходов партнёра. При этом каждая из сторон стремится принимать оптимальные решения, которые реализуют поставленные цели в наибольшей степени.
Наиболее последовательно теория игр применяется в экономике, где конфликтные ситуации возникают, например, в отношениях между поставщиком и потребителем, покупателем и продавцом, банком и клиентом. Применение теории игр можно найти и в политике, социологии, биологии, военном искусстве.
Из истории теории игр
История теории игр как самостоятельной дисциплины начинается в 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 может не видеть различия между альтернативами.
- Классификация по принципам деления выигрыша: кооперативные, коалиционные с одной стороны и некооперативные, бескоалиционные с другой стороны. В некооперативной игре, или иначе - бескоалиционной игре, игроки выбирают стратегии одновременно, не зная, какую стратегию выберет второй игрок. Коммуникация между игроками невозможна. В кооперативной игре, или иначе - коалиционной игре, игроки могут объединяться в коалиции и предпринимать коллективные действия, чтобы увеличить свои выигрыши.
- Конечная игра двух лиц с нулевой суммой или антогонистическая игра – это стратегическая игра с полной информацией, в которой участвуют стороны с противоположными интересами. Анатагонистическими играми являются матричные игры.
Классический пример из теории игр - дилемма заключённого
Двух подозреваемых берут под стражу и изолируют друг от друга. Окружной прокурор убеждён, что они совершили тяжкое преступление, но не имеет достаточных доказательств, чтобы предъявить им обвинение на суде. Он говорит каждому из заключённых, что у него имеется две альтернативы: признаться в преступлении, которое по убеждению полиции он совершил, или не признаваться. Если оба не признаются, то окружной прокурор предъявит им обвинение в каком-либо незначительном преступлении, например, мелкая кража или незаконное владение оружием, и они оба получат небольшое наказание. Если они оба признаются, то будут подлежать судебной ответственности, но он не потребует самого строгого приговора. Если же один признается, а другой нет, то признавшемуся приговор будет смягчён за выдачу сообщника, в то время как упорствующий получит "на полную катушку".
Если эту стратегическую задачу сформулировать в сроках заключения, то она сводится к следующему:
| 2-й заключённый Непризнание | 2-й заключённый Признание |
|
| 1-й заключённый Непризнание | По 1 году каждому | 10 лет первому и 3 месяца второму |
| 1-й заключённый Признание | 3 месяца первому и 10 лет второму | 8 лет каждому |
Таким образом, если оба заключённых не признаются, они получат по 1 году каждый. Если оба признаются, то каждый получит по 8 лет. А если один признается, другой не признается, то тот, который признался отделается тремя месяцами заключения, а тот, который не признается, получит 10 лет. Приведённая выше матрица правильно отражает дилемму заключённого: перед каждым стоит вопрос - признаться или не признаться. Игра, которую окружной прокурор предлагает заключённым, представляет собой некооперативную игру или иначе - бескоалиционную игру. Если бы оба заключённых имели возможность сотрудничать (то есть игра была бы кооперативной или иначе коалиционной игрой), то оба не признались бы и получили по году тюрьмы каждый.
Примеры использования математических средств теории игр
Переходим теперь к рассмотрению решений примеров распространённых классов игр, для которых в теории игр существуют методы исследования и решения.
Пример формализации некооперативной (бескоалиционной) игры двух лиц
В предыдущем параграфе мы уже рассмотрели пример некооперативной (бескоалиционной) игры (дилемма заключённого). Давайте закрепим наши навыки. Для этого подойдёт также классический сюжет, навеянный "Приключениями Шерлока Холмса" Артура Конан Дойля. Можно, конечно, возразить: пример не из жизни, а из литературы, но ведь Конан Дойль не зарекомендовал себя как писатель-фантаст! Классический ещё и потому, что задание выполнено Оскаром Моргенштерном, как мы уже установили - одним из основателей теории игр.
Пример 1. Будет приведено сокращённое изложение фрагмента одного из "Приключений Шерлока Холмса". Согласно известным понятиям теории игр составить модель конфликтной ситуации и формально записать игру.
Шерлок Холмс намерен отправиться из Лондона в Дувр с дальнейшей целю попасть на континент (европейский), чтобы спастись от профессора Мориарти, который преследует его. Сев в поезд, он увидел на вокзальной платформе профессора Мориарти. Шерлок Холмс допускает, что Мориарти может выбрать особый поезд и обогнать его. У Шерлока Холмса две альтернативы: продолжать поездку до Дувра или сойти на станции Кентерберри, являющейся единственной промежуточной станцией на его маршруте. Мы принимаем, что его противник достаточно разумен, чтобы определить возможности Холмса, поэтому перед ним те же две альтернативы. Оба противника должны выбрать станцию, чтобы сойти на ней с поезда, не зная, какое решение примет каждый из них. Если в результате принятия решения оба окажутся на одной и той же станции, то можно однозначно считать, что Шерлок Холмс будет убит профессором Мориарти. Если же Шерлок Холмс благополучно доберётся до Дувра, то он будет спасён.
Решение. Героев Конан Дойля можем рассматривать как участников игры, то есть игроков. В распоряжении каждого игрока i (i=1,2) две чистые стратегии:
- сойти в Дувре (стратегия si1 (i=1,2));
- сойти на промежуточной станции (стратегия si2 (i=1,2))
В зависимости от того, какую из двух стратегий выберет каждый из двух игроков, будет создана особая комбинация стратегий как пара s = (s1, s2).
Каждой комбинации можно поставить в соответствие событие - исход попытки убийства Шерлока Холмса профессором Мориарти. Составляем матрицу данной игры с возможными событиями.
| Холмс Сойти в Дувре s21 | Холмс Сойти в Кентерберри s22 |
|
| Мориарти Сойти в Дувре s11 | Холмс будет убит (100) | Холмс спасётся, но не достигнет континента (0) |
| Мориарти Сойти в Кентерберри s12 | Холмс спасётся и достигнет континента (-50) | Холмс будет убит (100) |
Под каждым из событий указан индекс, означающий приобретение профессора Мориарти, и рассчитываемый в зависимости от спасения Холмса. Оба героя выбирают стратегию одновременно, не зная, что выберет противник. Таким образом, игра является некооперативной, поскольку, во-первых, игроки находятся в разных поездах, а во-вторых, имеют противоположные интересы.
Пример формализации и решения кооперативной (коалиционной) игры n лиц
В этом пункте практическая часть, то есть ход решения примера задачи, будет предварена теоретической частью, в которой будем знакомиться с понятиями теории игр для решения кооперативных (бескоалиционных) игр. Для этой задачи теория игр предлагает:
- характеристическую функцию (если говорить упрощённо, она отражает величину выгоды объединения игроков в коалицию);
- понятие аддитивности (свойства величин, состоящее в том, что значение величины, соответствующее целому объекту, равно сумме значений величин, соответствующих его частям, в некотором классе разбиений объекта на части) и супераддитивности (значение величины, соответствующее целому объекту, больше суммы значений величин, соответствующих его частям) характеристической функции.
Супераддитивность характеристической функции говорит о том, что объединение в коалиции выгодна игрокам, так как в этом случае величина выигрыша коалиции увеличивается с увеличением числа игроков.
Для формализации игры нам нужно ввести формальные обозначения вышеназванных понятий.
Для игры n обозначим множество всех её игроков как N = {1,2,...,n} Любое непустое подмножество множества N обозначим как Т (включая само N и все подмножества, состоящие из одного элемента). На сайте есть занятие "Множества и операции над множествами", которое при переходе по ссылке открывается в новом окне.
Характеристическая функция обозначается как v и область её определения
состоит из 
возможных
подмножеств множества N. v(T) - значение характеристической
функции для того или иного подмножества, например, доход, полученный коалицией, в том числе, возможно,
состоящей из одного игрока. Это важно по той причине, что теория игр требует проверить наличие супераддитивности
для значений характеристической функции всех непересекающихся коалиций.
Для двух непустых коалиций из подмножеств T1 и T2 аддитивность характеристической функции кооперативной (коалиционной) игры записывается так:
.
А супераддитивность так:
Пример 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; это значение характеристической функции определено по средней выручке в случае, когда игроки объединялись в тройки.
Таким образом, мы перечислили все возможные коалиции игроков, их получилось восемь, как и должно быть, так как область определения характеристической функции игры состоит именно из восьми возможных подмножеств множества всех игроков. Что и требует теория игр, так как нам нужно проверить наличие супераддитивности для значений характеристической функции всех непересекающихся коалиций.
Как выполняются условия супераддитивности в этом примере? Определим, как игроки образуют непересекающиеся коалиции T1 и T2. Если часть игроков входят в коалицию T1, то все остальные игроки входят в коалицию T2 и по определению эта коалиция образуется как разность всего множества игроков и множества T1. Тогда, если T1 - коалиция из одного игрока, то в коалиции T2 будут второй и третий игроки, если в коалиции T1 будут первый и третий игроки, то коалиция T2 будет состоять только из второго игрока, и так далее.
Теперь установим, выполняется ли условие супераддитивности характеристической функции для нашего примера:
v(T{1})+v(T{2,3})<v(T1∪T2)=v(N),
т.е. 600+1900=2500<3000;
v(T{2})+v(T{1,3})<v(T1∪T2)=v(N),
т.е. 700+1800=2500<3000;
v(T{3})+v(T{1,2})<v(T1∪T2)=v(N),
т.е. 900+1500=2400<3000.
Так как каждое из рассмотренных неравенств выполняется, характеристическая функция нашей игры супераддитивна. Таким образом, по условию теории игр для кооперативной (коалиционной) игры n лиц, игрокам из этого примера выгодно объединяться в коалиции, чтобы увеличить свои выигрыши.
Поделиться с друзьями
