«Игр теория»

раздел математики, изучающий формальные модели принятия оптимальных решений в условиях конфликта. При этом под конфликтом понимается явление, в котором участвуют различные стороны, наделённые различными интересами и возможностями выбирать доступные для них действия в соответствии с этими интересами. Отдельные математические вопросы, касающиеся конфликтов, рассматривались (начиная с 17 в.) многими учёными. Систематическая же математическая теория игр была детально разработана американскими учёными Дж. Нейманом и О. Моргенштерном (1944) как средство математического подхода к явлениям конкурентной экономики. В ходе своего развития И. т. переросла эти рамки и превратилась в общую математическую теорию конфликтов. В рамках И. т. в принципе поддаются математическому описанию военные и правовые конфликты, спортивные состязания, «салонные» игры, а также явления, связанные с биологической борьбой за существование.

В условиях конфликта стремление противника скрыть свои предстоящие действия порождает неопределённость. Наоборот, неопределённость при принятии решений (например, на основе недостаточных данных) можно интерпретировать как конфликт принимающего решения субъекта с природой. Поэтому И. т. рассматривается также как теория принятия оптимальных решений в условиях неопределённости. Она позволяет математизировать некоторые важные аспекты принятия решений в технике, сельском хозяйстве, медицине и социологии. Перспективен подход с позиций И. т. к проблемам управления, планирования и прогнозирования.

Основным в И. т. является понятие игры, являющееся формализованным представлением о конфликте. Точное описание конфликта в виде игры состоит поэтому в указании того, кто и как участвует в конфликте, каковы возможные исходы конфликта, а также кто и в какой форме заинтересован в этих исходах. Участвующие в конфликте стороны называются коалициями действия; доступные для них действия — их стратегиями; возможные исходы конфликта — ситуациями (обычно каждая ситуация понимается как результат выбора каждой из коалиций действия некоторой своей стратегии); стороны, заинтересованные в исходах конфликта, — коалициями интересов; их интересы описываются предпочтениями тех или иных ситуаций (эти предпочтения часто выражаются численными выигрышами). Конкретизация перечисленных объектов и связей между ними порождает разнообразные частные классы игр.

Если в игре имеется единственная коалиция действия, то стратегии этой коалиции можно отождествить с ситуациями и далее больше уже о стратегиях не упоминать. Такие игры называются нестратегическими. Класс нестратегических игр весьма обширен. К их числу относятся, в частности, кооперативные игры (см. Кооперативная теория игр).

Примером нестратегической (кооперативной) игры может служить простая игра, состоящая в следующем. Множеством ситуаций являются в ней всевозможные распределения (дележи) между игроками некоторого количества однородной полезности (например, денег). Каждый делёж описывается теми суммами, которые при этом получают отдельные игроки. Коалиция интересов называется выигрывающей, если она может даже в условиях противодействия со стороны всех остальных игроков присвоить и разделить между своими членами всю имеющуюся полезность. Все коалиции, не являющиеся выигрывающими, совсем не могут присвоить какой-либо доли полезности. Такие коалиции называются проигрывающими. Естественно считать, что выигрывающая коалиция предпочитает один делёж другому, если доля каждого из её членов в условиях первого дележа больше, чем в условиях второго. Проигрывающие же коалиции не могут сравнивать дележи по предпочтительности (это условие также вполне естественно: коалиция интересов, которая сама не в состоянии добиться ничего, вынуждена соглашаться на любой делёж и лишена возможности выбора между дележами).

Если в игре имеется более одной коалиции действия, то игра называется стратегической. Важный класс стратегических игр составляют бескоалиционные игры, в которых коалиции действия совпадают с коалициями интересов (они называются игроками), а предпочтения для игроков описываются их функциями выигрыша: игрок предпочитает одну ситуацию другой, если в первой ситуации он получает больший выигрыш, чем во второй.

Одним из простейших примеров бескоалиционной игры может служить «морра» в следующем своём варианте. Три игрока показывают одновременно 1 или 2 пальца каждый. Если все три игрока показывают одно и то же число, то выигрыш каждого равен нулю. В противном случае один из игроков показывает a ( = 1 или 2) и получает b из некоторого источника (например, из банка, образованного предварительными взносами), а два других игрока, показывающие одно и то жеb ( ≠ a), не получают ничего.

Если в бескоалиционной игре участвуют два игрока, а значения их функций выигрыша в любой ситуации отличаются только знаками, то игра называется антагонистической игрой (См. Антагонистические игры); в ней выигрыш одного из игроков в точности равен проигрышу другого. Если в антагонистической игре множества стратегий обоих игроков конечны, то игра называется матричной игрой (См. Матричные игры) ввиду некоторой специфической возможности её описания.

В качестве другого примера бескоалиционной игры можно привести шахматы. В этой игре участвуют два игрока (белые и чёрные). Стратегия каждого из игроков есть мыслимое (хотя практически и не поддающееся детальному описанию) правило выбора в каждой возможной позиции некоторого хода, допускаемого движениями фигур. Пара таких правил (за белых и за чёрных) составляет ситуацию, которая полностью определяет протекание шахматной партии и в том числе её исход. Функция выигрыша белых имеет значение 1 на выигрываемых партиях, 0 на ничейных и — 1 на проигрываемых (такой способ начисления очков практически ничем не отличается от принятого в турнирной и матчевой практике). Функция выигрыша чёрных отличается от функции выигрыша белых лишь знаком. Из сказанного видно, что шахматы относятся к числу антагонистических и притом матричных игр. В шахматах стратегии не выбираются игроками до начала игры, а реализуются постепенно, ход за ходом. Это значит, что шахматы принадлежат к позиционным играм (См. Позиционные игры).

И. т. является нормативной теорией, тоесть предметом её изучения являются не столько сами модели конфликтов (игры), как таковые, сколько содержание принимаемых в играх принципов оптимальности, существования ситуаций, на которых эти принципы оптимальности реализуются (такие ситуации или множества ситуаций называются решениями в смысле соответствующего принципа оптимальности), и, наконец, способы нахождения таких ситуаций. Рассматриваемые в И. т. объекты — игры — весьма разнообразны, и пока не удалось установить принципов оптимальности, общих для всех классов игр. Практически это означает, что единого для всех игр истолкования понятия оптимальности ещё не выработано. Поэтому прежде чем говорить, например, о наивыгоднейшем поведении игрока в игре, необходимо установить, в каком смысле эта выгодность понимается. Все применяемые в И. т. принципы оптимальности при всём их внешнем разнообразии отражают прямо или косвенно идею устойчивости ситуаций или множеств ситуаций, составляющих решения. В бескоалиционных играх основным принципом оптимальности считается принцип осуществимости цели, приводящий к ситуациям равновесия. Эти ситуации характеризуются тем свойством, что любой игрок, который отклонится от ситуации равновесия (при условии, что остальные игроки не изменят своих стратегий), не увеличит этим своего выигрыша.

В частном случае антагонистических игр принцип осуществимости цели превращается в так называемый принцип максимина (отражающий стремление максимизировать минимальный выигрыш).

Принципы оптимальности (первоначально выбиравшиеся интуитивно) выводятся на основании некоторых заранее задаваемых их свойств, имеющих характер аксиом. Существенно, что различные применяемые в И. т. принципы оптимальности могут противоречить друг другу.

Теоремы существования в И. т. доказываются преимущественно теми же неконструктивными средствами, что и в других разделах математики: при помощи теорем о неподвижной точке, о выделении из бесконечной последовательности сходящейся подпоследовательности и т. п., или же, в весьма узких случаях, путём интуитивного указания вида решения и последующего нахождения решения в этом виде.

Фактическое решение некоторых классов антагонистических игр сводится к решению дифференциальных и интегральных уравнений, а матричных игр — к решению стандартной задачи линейного программирования (См. Линейное программирование). Разрабатываются приближённые и численные методы решения игр. Для многих игр оптимальными оказываются так называемые смешанные стратегии, тоесть стратегии, выбираемые случайно (например, по жребию).

И. т., созданная для математического решения задач экономического и социального происхождения, не может в целом сводиться к классическим математическим теориям, созданным для решения физических и технических задач. Однако в различных конкретных вопросах И. т. широко используются весьма разнообразные классические математические методы. Кроме этого, И. т. связана с рядом математических дисциплин внутренним образом. В И. т. систематически и по существу употребляются понятия теории вероятностей. На языке И. т. можно сформулировать большинство задач математической статистики. Необходимость при анализе игры количественного учёта неопределённости предопределяет важность и тем самым связь И. т. с теорией информации и через её посредство — с кибернетикой. Кроме того, И. т., будучи теорией принятия решений, может рассматриваться как существенная составная часть математического аппарата операций исследования (См. Операций исследование).

И. т. применяется в экономике, технике, военном деле и даже в антропологии. Основные трудности практического применения И. т. связаны с экономической и социальной природой моделируемых ею явлений и недостаточным умением составлять такие модели на количественном уровне.

К 70-м гг. 20 в. число публикаций по научным вопросам И. т. достигло многих сотен (в том числе несколько десятков монографий). Курсы по И. т. читаются во многих высших учебных заведениях для студентов математических и экономических специальностей (в СССР — с 1956).

Международные конференции по И. т. проходили в Принстоне (1961), Иерусалиме (1965), Вене (1967) и Беркли (1970). Всесоюзные конференции по И. т. состоялись в Ереване (1968) и Вильнюсе (1971).

Лит.: Нейман Дж. Моргенштерн О., Теория игр и экономическое поведение, пер. с англ., М., 1970; Льюс Р., Райфа Х., Игры и решения, пер. с англ., М., 1961; Карлин С., Математические методы в теории игр, программировании и экономике, пер. с англ., М., 1964; Воробьев Н. Н., Современное состояние теории игр, «Успехи математических наук», 1970, т. 25, № 2(152), с. 80—140; Оуэн Г., Теория игр, пер. с англ., М., 1971; Contributions to the theory of games, v.1—4, Princeton, 1950—59; Advances in game theory, Princeton, 1964.

Н. Н. Воробьев.

ИГР ТЕОРИЯ - раздел математики, в котором изучаются математические модели принятия оптимальных решений в условиях конфликта, т. е. при явлении, в котором участвуют различные стороны, наделенные различными возможностями выбирать доступные для них действия в соответствии с их интересами. Схемы теории игр охватывают как собственно игры (шахматы, домино), так и различные ситуации, возникающие в экономических, военных и других вопросах.

раздел математики, предметом которого является анализ принятия оптимальных решений в условиях конфликта. Возникнув из задач классической теории вероятностей, теория игр превратилась в самостоятельный раздел в 1945-1955. Таким образом, теория игр - один из новейших разделов математики. Наиболее полное изложение идей и методов теории игр впервые появилось в 1944 в труде Теория игр и экономическое поведение (Theory of Games and Economic Behavior) математика Дж. фон Неймана (1903-1957) и экономиста О.Моргенштерна (1902-1977). Фон Нейман опубликовал несколько работ по теории игр в 1928 и 1935; другим предшественником теории игр по праву считается французский математик Э. Борель (1871-1956). Некоторые фундаментальные идеи были независимо предложены А. Вальдом (1902-1950), заложившим основы нового подхода к статистической теории принятия решений.

См. также ВЕРОЯТНОСТЕЙ ТЕОРИЯ. Первые приложения теория игр нашла в математической статистике и в решении некоторых возникших во время второй мировой войны военных проблем специального характера. Ее использовали как плодотворный источник теоретических моделей в экономике и социологии. Методы теории игр используются также в теории операций и в линейном программировании.

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

Математическое понятие игры необычайно широко. Оно включает в себя и т.н. салонные игры (в том числе шахматы, шашки, го, карточные игры, домино), а может использоваться и для описания моделей экономической системы с многочисленными конкурирующими друг с другом покупателями и продавцами, для обсуждения статистических проблем, возникающих при непрерывном контроле производственного процесса, а также для решения военных задач, например, при определении оптимальных маневров подводной лодки, преследуемой обнаружившим ее надводным кораблем противника. Не вдаваясь в детали, игру в общих чертах можно определить как ситуацию, в которой одно или несколько лиц ("игроков") совместно управляют некоторым множеством переменных и каждый игрок, принимая решения, должен учитывать действия всей группы, "платеж", приходящийся на долю каждого игрока, определяется не только его собственными действиями, но и действиями других членов группы. Некоторые из "ходов", или индивидуальных действий, в ходе игры могут носить случайный характер. Наглядной иллюстрацией может служить известная игра в покер: начальная сдача карт представляет собой случайный ход, последовательность ставок и контрставок, предшествующая финальному сравнению взяток, образована остальными ходами в игре. Платежом называется сумма очков, получаемая игроком по окончании партии. Величина платежа зависит от исхода случайных ходов в игре и от индивидуальных выборов каждого игрока при последующих ходах. Платеж обычно принято выражать числом очков или денежной суммой; положительный платеж означает выигрыш игрока, отрицательный - проигрыш. Предполагается, что каждый игрок стремится максимально увеличить свой выигрыш. "Наиболее разумные" стратегии в игре называются решениями этой игры. Основой проблематики теории игр как математической дисциплины, является изучение связей между условиями игры и ее решениями. Основными вопросами в каждой игре являются следующие: "Что такое решение данной игры?", "Существуют ли решения данной игры?", "Каково решение данной игры и как его найти?". Удовлетворительное понятие решения было выработано для важного класса игр с числом игроков не более двух. Для игр более общего типа используется ряд критериев, позволяющих получать "оптимальные решения", удовлетворяющие некоторым интуитивно правдоподобным требованиям; однако в настоящее время ни одно из таких решений нельзя считать вполне удовлетворительными.

ИГРЫ С ПОЛНОЙ ИНФОРМАЦИЕЙ

При анализе любой игры важно знать, в какой степени одному игроку известны стратегии, сделанные ходы и индивидуальные выборы другого игрока. В салонных играх эта информация заложена в явном виде в правилах игры. В военной игре эти сведения определяются широтой и глубиной разведывательной информации; однако следует также учитывать и разведывательную деятельность противника. В шашках, шахматах, китайских шашках и в игре в крестики-нолики каждый игрок располагает т.н. "полной информацией". Это означает, что каждый игрок в любой момент времени полностью информирован о всех предыдущих ходах, сделанных в процессе игры, что позволяет придать простую математическую структуру любой конечной игре этого типа. Игру с полной информацией удобно изображать в виде дерева (или графа) с вершинами (черными и белыми кружками), соединенными ребрами. Играя в простую игру, изображенную на рис. 1, первый игрок (белые) помещает фишку в самую нижнюю вершину. Второй игрок (черные) может, делая ход, поставить фишку в любую соседнюю вершину, он выбирает ребро, исходящее из нижней вершины, и ставит свою фишку в ближайшую вершину, расположенную на следующем уровне. Так продолжается до тех пор, пока фишка не достигнет одного из треугольников. Платеж, получаемый белыми от черных, определяется треугольником, на котором фишка завершит свой путь. На рис. 1 платеж колеблется от +30 единиц до -50 (белые могут либо выиграть 30 единиц у черных, либо проиграть им 50).

Рис. 1. ПРОСТАЯ ИГРА с полной информацией. Платежи указаны для белых. При правильном выборе стратегии черные выигрывают.

Чтобы представить в виде дерева игру в шашки, каждая вершина должна означать одно из возможных расположений всех шашек на доске, а число ребер, исходящих из вершины, должно соответствовать количеству возможных ходов для игрока, играющего соответственно белыми или черными. В данном конкретном примере видно (и можно доказать, что так же обстоит дело и в общем случае), что в любой игре с полной информацией каждый из игроков может определить свою "наилучшую" стратегию. В модели игры, изображенной на рис. 1, черные могут заставить белых уплатить по крайней мере 5 единиц; кроме того, если белые будут придерживаться правильной стратегии, то черные не смогут выиграть больше 5 единиц несмотря на выбранную ими стратегию. Заметим, однако, что если бы игра состояла только из правой половины дерева, то наилучшая стратегия гарантировала бы белым проигрыш в 2 единицы; при менее удачной стратегии белые могли бы проиграть 10. Теоретически шахматы и шашки имеют такую же структуру, как и приведенный выше более тривиальный пример. Однако представить эти игры в виде деревьев настолько сложно, что их полный анализ никогда не производился. Имеются некоторые основания полагать, что если оба игрока придерживаются оптимальных стратегий, то игра в шашки должна заканчиваться вничью, а в шахматы всегда должны выигрывать белые, делающие по правилам первый ход.

ИГРЫ В НОРМАЛЬНОЙ ФОРМЕ

Первый шаг при построении общей математической теории игр состоит в доказательстве того, что любую конечную игру можно свести к эквивалентной ей игре, имеющей более простую частную форму; в отличие от игры с полной информацией такие игры сопряжены с минимальным обменом информацией. Предположим, что n игроков X1, X2,..., Xn играют в игру Г по следующим правилам. Каждый игрок Xk выбрал из множества Sk элемент xk, ничего не зная о том, какой элемент выбрал любой из остальных игроков; в качестве платежа игрок Xk получает величину Mk (x1, x2,..., xn). Точный характер игры Г определяется множествами S1, S2,..., Sn и n функциями платежей M1, M2,..., Mn. Элементы множества Sk называются чистыми стратегиями игрока Xk. Любая игра, которая может быть представлена таким образом, называется игрой с "нулевой суммой", если функции платежей удовлетворяют условию

при всех возможных выборах стратегий x1, x2,..., xn. Смысл этого названия заключается в том, что игра не разрушает и не создает состояния, а лишь перераспределяет его между игроками. Любую игру в нормальной форме можно превратить в игру с нулевой суммой, если ввести фиктивного игрока ("банк"), который не делает ходов, но получает платеж в размере, необходимом для поддержания общего баланса. В игре двух игроков с нулевой суммой условие (1) принимает вид:

Следовательно, игрок X1 выигрывает, только если игрок X2 проигрывает, и интересы игроков диаметрально противоположны. Но если число игроков больше двух, то существует возможность объединения нескольких игроков в коалицию для достижения совместными усилиями того, что они не могли достичь порознь. Чтобы уяснить, как обычную игру можно теоретически свести к нормальной форме, нужно глубже вникнуть в то, что понимается под "стратегией" в теории игр. В самых общих чертах стратегия игрока представляет собой детальный план действий, который может быть составлен заранее, до того, как игра действительно будет сыграна, и содержит полные инструкции, необходимые для принятия любого возможного решения; решение должно учитывать всю информацию, которой располагает игрок относительно предыдущих ходов, сделанных во время игры. В шашках или шахматах описание индивидуальной стратегии белых составило бы объемистую книгу; в ней не только указывался бы первый ход, но и перечислялись бы контрходы в ответ на любой ответный ход черных, перечислялись бы все возможные вторые ходы, ответные ходы белых на любой второй ход черных и т.д. В "упрощенном покере" у игрока X имеется только четыре возможные стратегии. Их можно обозначить символами LL, LH, HL и HH, означающими следующее: 6LL - независимо от извлеченной карты ставка минимальна (3 доллара); 6LH - если извлеченная карта - королева, то ставка минимальна, если король, то ставка максимальна (9 долларов); HL - стратегия, обратная LH; 6HH - ставка всегда максимальна. Аналогично, игрок Y располагает только четырьмя стратегиями, которые можно было бы обозначить FF, FC, CF и СС: 6FF - пропустить независимо от ставки, которую делает игрок X; 6FC - пропустить, если X делает минимальную ставку, объявить козырную масть, если X делает максимальную ставку; CF - стратегия, обратная FC; CC - объявить козырную масть независимо оттого, какую ставку делает X. После того, как каждый из игроков выбрал свою стратегию, игру мог бы проводить любой беспристрастный посредник. В этом смысле платеж для каждого игрока полностью определен выбором чистых стратегий, и мы получаем требуемую нормальную форму. Игра с многочисленными ходами и в различной степени неполной информацией оказалась сведенной к простой игре, в которой у каждого игрока есть только один ход. Если имеются случайные ходы (в нашем примере с покером - это начальная сдача карт), то их делает посредник. Разумно также описать платеж, причитающийся игроку, в терминах величины, которую он рассчитывает получить. Например, если X выбирает стратегию HL, а Y - стратегию CC, то X выигрывает 3 доллара, если он извлекает короля, и проигрывает 9 долларов, если он извлекает королеву. Так как предполагается, что игра ведется честно, то ожидаемый в конечном счете платеж при указанном выборе стратегий составляет

Полная матрица для нормальной формы "упрощенного покера" представлена на рис. 2. Платежи указаны для игрока X; соответствующие платежи для Y равны тем же числам, но с противоположным знаком.

Рис. 2. "УПРОЩЕННЫЙ ПОКЕР". Матрица платежей.

В России при построении математической модели конфликта делают различия между коалицией действия и коалицией интересов. Коалицией действия называются те или иные коллективы, участвующие в игре и принимающие решения. Коалицией интересов называются коллективы, участвующие в игре и отстаивающие некоторые общие интересы. Кроме того, вводится понятие ситуации - результат выбора всеми коалициями действия своих стратегий.

ЛИТЕРАТУРА

Мак Кинси. Введение в теорию игр. М., 1960 Берж К. Общая теория игр нескольких лиц. М., 1961 Матричные игры. М., 1963 Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М., 1970 Воробьев Н.Н. Основы теории игр. Бескоалиционные игры. М., 1984

игр тео́рия

раздел математики, в котором изучаются математические модели принятия оптимальных решений в условиях конфликта, то есть при явлении, в котором участвуют различные стороны, наделённые различными возможностями выбирать доступные для них действия в соответствии с их интересами. Схемы игр теории охватывают как собственно игры (шахматы, домино), так и различные ситуации, возникающие в экономических, военных и других вопросах.

* * *

ИГР ТЕО́РИЯ, раздел математики, в котором изучаются математические модели принятия оптимальных решений в условиях конфликта, т. е. при явлении, в котором участвуют различные стороны, наделенные различными возможностями выбирать доступные для них действия в соответствии с их интересами. Схемы теории игр охватывают как собственно игры (шахматы, домино), так и различные ситуации, возникающие в экономических, военных и других вопросах.

- теория математических моделей принятия оптимальных решений в условиях конфликтов.

Формальное определение игры. Под конфликтом понимают явление, применительно к к-рому можно говорить, кто и как в этом явлении участвует, какие у него могут быть исходы и кто и как в этих исходах заинтересован. Поэтому для формального задания конфликта необходимо указать: 1) множество участвующих в нем действующих начал (называемых коалициями действи я), 2) семейство множеств r_K стратегий каждой из коалиций действия, 3) множество ситуаций 4). множество П _U заинтересованных начал (называемых коалициями интересов) и 5) семейства бинарных отношений на выражающих предпочтения между ситуациями для коалиций интересов. Система

наз. игрой.

Содержание И. т. состоит в установлении связей между компонентами каждой игры и "оптимальными" ее исходами, и прежде всего: в уточнении самого понятия оптимальности, в доказательстве существования оптимальных исходов и в их фактич. определении. Развитие И. т. приводит к вопросам изучения взаимосвязей между различными играми, что выражается в разработке разного рода исчислений игр, и к рассмотрению классов, пространств, категорий игр.

Классификация игр. Игры, в к-рых совсем нет коалиций интересов пли же имеется лишь одна такая коалиция, являются предметами изучения чисто дескриптивных или же традиционных оптимизационных теорий. Игры в собственном смысле слова имеют не менее двух коалиций интересов.

Обычно в И. т. как коалиции действия, так и коалиции интересов принято атомизировать и считать как те, так и другие подмножествами нек-рого множества I, элементы к-рого наз. игроками. Вначале множество игроков в игре принималось конечным, но позднее (1970-е гг.) начали изучаться игры и с бесконечными и притом неатомическнми множествами игроков.

Для игр с одной коалицией действия множество всех ситуаций можно принять за множество стратегий этой единственной коалиции действия и далее о стратегиях не упоминать. Поэтому такие игры наз. нестратегическими. В отличие от них, все остальные игры, с двумя или более коалициями действия, наз. стратегическими.

Весьма широкий класс нестратегич. игр может быть получен следующим образом. Пусть I- множество игроков, и Каждому игроку ставится в соответствие координатная прямая Е ⁱ, принимаемая за шкалу его полезностей, а каждой коалиции интересов - произведение Наконец, вводятся множества для каждого и множество (элементы к-рого наз. дележами) и по определению принимается, что для дележей х, имеет место ("дележ x доминирует дележ упо коалиции K") тогда и только тогда, когда х, у(v(K) ХЕ ^I'K)Н и x_i>y_i для всех Такие игры наз. играми без побочных платежей. Они описывают положение, при к-ром каждая коалиция интересов К может форсированно обеспечить для своих членов в качестве выигрышей компоненты любого вектора из v(K), а общие соображения целесообразности делают нерациональным выбор дележей вне Н. Обычно множества v(K)подчиняются нек-рым естественным условиям: 1) v(K)является непустым замкнутым и выпуклым множеством, 2) если и

(неравенство векторов понимается покомпонентно), то ("кто способен на большее, способен и на меньшее"), 3) если то (коалиции Ки Lвместе могут добиться не меньшего, чем порознь), 4) Н состоит из всех таких векторов что для каждого из них найдется вектор для к-рого (таким образом, v{I )состоит из всех таких векторов выигрышей х, что I может дать своим членам не менее чем х; Н состоит из таких векторов х, что I может дать своим членам ровно х). В частности, если

где v(K)- некоторое действительное число, а

то получится классическая кооперативная игра. В этом случае определение v(K)означает возможность коалиции Куверенно добиться суммарного выигрыша v(K)и произвольно перераспределить его между своими членами. Определение Нозначает, что общая распределяемая в игре сумма есть v(I)(распределять меньшую сумму невыгодно; большей же просто нет!), а каждый игрок iбудет соглашаться лишь на долю x_i, не меньшую, чем та сумма v(i), к-рую он может уверенно получить самостоятельно.

Эсновной класс стратегич. игр составляют бескоалиционные игры, в к-рых множество игроков I совпадает с множествами коалиций действия и коалиций интересов Каждый игрокимеет в своем распоряжении множество стратегий в качестве множества всех ситуаций принимается декартово произведение а отношение предпочтения описывается функцией выигрыша H_i:r->Eⁱ причем тогда и только тогда, когда Н _i( х')>Н _i(x").

Таким образом, бескоалиционная игра может быть описана в виде тройки Г= <I, >.

Если все множества стратегий конечны, то и бескоалиционная игра Г наз. конечной. Конечные бескоалиционные игры с двумя игроками (I={I, II}) наз. биматричными играми..

Если I={I, II} и Н _I (х)=-H_II(x) для всех то игра Г наз. антагонистической игрой. Всякая антагонистич. игра может быть задана в виде тройки где и - множества стратегий, соответственно, игроков I и II, а H - функция выигрыша игрока I. Конечные антагонистич. игры наз. матричными играми.

Если в антагонистич. игре то всякая ситуация в такой игре описывается точкой из квадрата [0, 1][0, 1]; такие игры наз. играми на единичном квадрате.

Пусть I - множество игроков, - множества их стратегий; X- множество, элементы к-рого наз. позициями; Т- множество, элементы к-рого имеют смысл моментов времени; т. е. f ставит в соответствие каждой ситуации определяемой игры отношение, заданное на Тсо значениями в всякий f-образ ситуации наз. партией (множество всех партий обозначается через и, наконец, Сиcтема

наз. общей позиционной игрой. В конечном счете в такой игре выигрыш каждого игрока вполне определяется складыварщейся ситуацией, т. е. выбором стратегий всеми игроками. Поэтому такие игры относятся к числу бескоалиционных игр.

Пусть в общей позиционной игре Г компонента Xявляется конечномерным евклидовым пространством, Т- множеством действительных чисел, а j:Х. Пусть рассматриваются ситуации для которых система дифференциальных уравнений

(равенство понимается как векторное) имеет при данных начальных условиях единственное решение. Тогда каждая ситуация определяет некоторую партию, к-рая в данном случае наз. траекторией. Так определенная игра наз. дифференциальной игрой.

К числу общих позиционных игр относятся также позиционные игры и динамические игры (в том числе стохастические игры, рекурсивные игры, а также игры на выживание).

Основные результаты теории игр. Основная проблематика в И. т. связана с принципами оптимальности, которые, во-первых, должны в достаточной мере отражать содержательные представления об оптимальности, а во-вторых, должны быть реализуемыми на достаточно широких и естественно очерченных классах игр. Эти два требования, предъявляемые к принципам оптимальности, в известной мере противоречат друг другу, и поэтому для многих содержательно естественных классов игр И. т. еще не выработала соответствующих принципов оптимальности. Вместе с тем известны классы игр, обслуживаемые с равным успехом несколькими различными принципами оптимальности. Поэтому конструирование и анализ принципов оптимальности являются существенной составной частью И. т. Каждый принцип оптимальности реализуется (не обязательно однозначно) в виде множества ситуаций-оптимумов. Это множество (к-рое может оказаться пустым) наз. решением.

Логической основой каждого решения являются нек-рые черты обычного экстремума, сформулированные применительно к одновременной экстремизации нескольких функций. Поэтому, помимо стремления к наибольшим (в арифметическом смысле) значениям выигрышей, решения игр могут выражать нек-рые характеристики устойчивости и симметрии, а также различные комбинации того и другого.

Так, среди черт оптимальности в нестратегич. играх можно назвать недоминируемость, т. е. соглашение считать оптимальными те и только те ситуации х, для к-рых ни при какой ситуации уи коалиции интересов Кне может быть (множество оптимальных в этом смысле ситуаций наз. с-ядром игры). Другой принцип оптимальности состоит в сочетании внутренней п внешней устойчивости; это означает, что множество ситуаций R объявляется решением, если при х,. и не может быть а по всякому xПR найдутся такие zОR и что (такое Rназ. решением игры по Нейману - Моргенштерну). Можно формализовать Угрозы, предъявляемые одними коалициями другим, а также ответные контругрозы, и объявить устойчивой всякую ситуацию, в к-рой каждая угроза может парироваться контругрозой. Множество всех устойчивых в этом смысле ситуаций наз. k-я дро м игры. Представляет также интерес понимание оптимальности как своеобразной "справедливости", задаваемой нек-рой системой аксиом. Для кооперативных игр сформулирована такая аксиоматика, приводящая к единственному дележу (ситуации), называемому Шепли вектором. В стратегич. играх основой принципа оптимальности является идея равновесия. При этом оптимальными объявляются такие ситуации, отклонения от к-рых любым игроком не приводят к увеличению его выигрыша. Один и тот же принцип оптимальности, формулируемый для различных по объему классов игр, может приобретать различное содержательное выражение. Так, описанный принцип равновесия в случае антагонистич. игр превращается в минимакса принцип.

Формулы и алгоритмы, позволяющие находить решения игр, также можно отнести к числу принципов оптимальности (с узкой областью применимости). Напр., в матричной игре с диагональной матрицей выигрышей принципом оптимальности можно считать выбор игроками стратегий с вероятностями, обратно пропорциональными соответствующим диагональным элементам матрицы. Реализуемость принципа оптимальности для нек-рого класса игр состоит в существовании для всех игр этого класса соответствующих (непустых) множеств оптимумов. Их отсутствие в первоначально заданных ситуациях может преодолеваться путем расширения множеств стратегий (и тем самым - множеств конструируемых из них ситуаций). Для бескоалиционных игр плодотворно используются смешанные (рандомизированные) стратегии.

Большинство доказательств теорем существования решений в И. т. носит неэффективный характер (многие из них опираются на теоремы о неподвижной точке) и не содержат алгоритмов нахождения решений. Поэтому в И. т. важны частные аналитические и численные методы нахождения решений. При этом вопрос о фактическом нахождении решений игр нередко оказывается очень сложным, и ответ на него удается найти лишь для весьма узких классов игр.

В разработке исчислений игр можно выделить несколько направлений. Изучаются возможности нахождения и описания (хотя бы частичного) решений одной игры на основе решений другой игры, в том или ином смысле более просто устроенной. Элементарными примерами таких редукций могут служить естественное отбрасывание доминируемых стратегий игроков в бескоалиционных играх, симметризация таких игр, а также аппроксимации бесконечных игр конечными. Редукционным процессом можно считать также предложенное Дж. Нейманом (J. Neumann) построение кооперативной модели бескоалиционной игры. Известны и обратные результаты, указывающие на принципиальную несводимость решений игр того или иного класса к решению игр более узкого класса. Напр., можно указать бескоалиционные игры трех лиц, решение к-рых связано с выполнением иррациональных операций, в то время как решение биматричных игр всегда осуществимо при помощи рациональных операций.

Фиксация одних компонент в играх нек-рого класса (напр., множества игроков и множеств их стратегий в условиях класса всех бескоалиционных игр) и различение игр по остальным компонентам (в данном примере - по функциям выигрыша игроков) приводит к рассмотрению пространств игр, к-рое осуществляется средствами функционального анализа и топологии. Введение на таких пространствах игр вероятностной меры приводит к стохастич. играм.

Связи теории игр с другими разделами математики. И. т. тесно связана с различными разделами математики. Как общая теория множеств с несколькими бинарными отношениями, она близка алгебре. В И. т. используется весьма разнообразный математич. аппарат, а большое число вполне традиционных математич. задач допускает теоретико-игровые обобщения. Оптимальные поведения в стратегич. играх обычно оказываются рандомизированными, поэтому теоретико-вероятностные понятия настолько естественно входят в И. т. и употребляются в ней, что одно время даже было принято считать И. т. частью теории вероятностей.

Математич. модели исследования операций (являющиеся моделями принятия оптимальных решений) естественно распределяются по трем уровням: детерминированному, стохастическому и неопределенному - в зависимости от степени информированности принимающих решения субъектов. Принятие решения в условиях неопределенности можно интерпретировать как конфликт принимающего решение субъекта против "природы" и тем самым - как игру. По существу к играм относятся и все многокритериальные задачи.

Поэтому И. т. в ее методологич. основах и в практич. ориентированности можно считать разделом исследования операций.

И. т. является рдной из составных частей математич. аппарата кибернетики. В динамич. играх стратегии выступают как функции "информационных состояний" игроков, причем в ходе игры игроки могут приобретать или утрачивать информацию. Это обусловливает связь И. т. с информации теорией.

Приложения теории игр. Помимо разнообразных связей внутри математики, И. т. имеет многочисленные приложения вне ее. Они касаются главным образом тех отраслей знаний и видов практич. деятельности, к-рые непосредственно имеют дело с конфликтами: военного дела, капиталистич. экономики (в частности, И. т. применяется в вопросах борьбы фирм за рынки, в явлениях олигополии, в планировании рекламных компаний, при формировании цен на конкурентных рынках, в биржевой игре и т. д.), права и т. п. С позиций И. т. можно рассматривать и различные явления в условиях плановой экономики (напр., вопросы централизации и децентрализации управления производством, преодоление ведомственных противоречий, оптимальное планирование по нескольким показателям, планирование в условиях неопределенности, порождаемой, напр., технич. прогрессом, и т. д.).

Исторический очерк. Зарождение И. т. как математич. дисциплины можно отнести к тому же письму Б. Паскаля (В. Pascal) к П. Ферма (P. Fermat) от 29 июля 1654, к-рое принято считать началом математич. теории вероятностей. В дальнейшем отдельные идеи, к-рые можно отнести к теоретико-игровым, высказывались Вальдегравом (Waldegrave, 1712; нахождение оптимальных смешанных стратегий в игре "проходящий туз"), Д. Бернулли (D. Bernoulli, 1732; анализ "петербургской игры"), П. Лапласом (P. Laplace, 1814; рассмотрение принципов оптимальности) и Ж. Бертраном (J. Bertrand, 1888; теоретико-игровой подход к игре в бакара). Ряд по существу теоретико-игровых утверждений был в эквивалентной форме рассмотрен в других разделах математики: в теории наилучших приближений (П. Л. Чебышев), в геометрии выпуклых многогранников [Г. Минковский (Н. Minkowski)], в теории линейных неравенств [Э. Штимке (Е. Stiemke)]. В 1911 Э. Цермело (Е. Zermelo) описал теоретико-игровой подход к шахматной игре; в 1921 Э. Борель (Е. Borel) начал систематич. изучение матричных игр, доказав для нек-рых случаев существование оптимальных смешанных стратегий. В 1928 вышла в свет работа Дж. Неймана "К теории стратегических игр", содержащая основные идеи современной И. т. Эти идеи были детально разработаны Дж. Нейманом и О. Моргенштерном (О. Morgenstern, [1]). С тех пор И. т. вошла в число разделов современной математики.

Лит.:[1] Нейман Дж., Моргенштерн О., Теория игр и экономическое поведение, пер. с англ., М., 1970; [2] Льюс Р., Райфа X., Игры и решения, пер. с англ., М., 1961: [3] Карлин С, Математические методы в теории игр, программировании и экономике, пер. с англ., М., 1964; [4] Воробьев Н. Н., "Успехи матем. наук", 1970, т. 15, в. 2, с. 80-140; [5] Оуэн Г., Теория игр., пер. с англ., М., 1971; [6] Партхасаратхи Т., Рагхаван Т., Некоторые вопросы теории игр двух лиц, пер. с англ., М., 1974; [7] Воробьев Н. Н., Теория игр. Лекции для экономистов-кибернетиков, Л., 1974; [8] его же, Entwicklung der Spieltheorie, В., 1975; [9] Теория игр. Аннотированный указатель публикаций по 1968 г., Л., 1976; [10] Журнал "International Journal of Game Theory", Vienna (выходит с 1971).