Математическая энциклопедия - игр теория

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

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

наз. игрой.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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