Общие понятия в теории игр




Введение

 

На практике проведения экономического анализа часто приходится принимать решения в условиях неопределенности. Результаты работы организации будут зависеть от действий, предпринимаемых противником. Такие ситуации называют конфликтными. Научные основания и методы решения задач с конфликтными ситуациями дает теория игр.

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

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


Общие понятия в теории игр

 

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

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

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

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

Важными являются понятия оптимальной стратегии, цены игры, среднего выигрыша. Эти понятия находят отражение в определении решения игры: стратегии Р* и Q* первого и второго игрока соответственно называются их оптимальными стратегиями, а число V - ценой игры, если для любых стратегий Р первого игрока и любых стратегий Q выполняются неравенства: где М (Р,Q) означает математическое ожидание выигрыши (средней выигрыш) первого игрока, если первым и вторым игроками избраны соответственно стратегии Р и Q.

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

По характеру взаимодействия игры делятся на:

бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции;

коалиционные (кооперативные) - могут вступать в коалиции.

В кооперативных играх коалиции наперёд определены.


Кооперативные игры

 

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

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

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

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

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

Кооперативные игры получаются в тех случаях, когда, в игре n игроков разрешается образовывать определённые коалиции. Обозначим через N множество всех игроков, N ={1, 2,..., n }, а через K - любое его подмножество. Пусть игроки из K договариваются между собой о совместных действиях и, таким образом, образуют одну коалицию. Очевидно, что число таких коалиций, состоящих из r игроков, равно числу сочетаний из n по r, то есть , а число всевозможных коалиций равно

 

= 2 n - 1.

 

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

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

Характеристическая функция u называется простой, если она принимает только два значения: 0 и 1. Если характеристическая функция u простая, то коалиции K, для которых u (K) =1, называются выигрывающими, а коалиции K, для которых u (K) = 0, - проигрывающими.

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

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

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

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

Обозначим через u G характеристическую функцию бескоалиционной игры. Эта функция обладает следующими свойствами:

персональность

u G (Æ) = 0,т.е. коалиция, не содержащая ни одного игрока, ничего не выигрывает;

супераддитивность

 

u G (K È L) ³ u G (K) + u G (L), если K, L Ì N, K Ç L ¹ Æ,

 

т.е. общий выигрыш коалиции не меньше суммарного выигрыша всех участников коалиции;

дополнительность

 

u G (K) + u (N \ K) = u (N)


т.е. для бескоалиционной игры с постоянной суммой сумма выигрышей коалиции и остальных игроков должна равняться общей сумме выигрышей всех игроков.

Распределение выигрышей (делёж) игроков должно удовлетворять следующим естественным условиям: если обозначить через xi выигрыш i- го игрока, то, во-первых, должно удовлетворяться условие индивидуальной рациональности

 

xi ³ u (i), для i ÎN

 

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

 

= u (N)

 

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

Таким образом, вектор x = (x1,..., xn), удовлетворяющий условиям индивидуальной и коллективной рациональности, называется дележём в условиях характеристической функции u.

Система { N, u}, состоящая из множества игроков, характеристической функции над этим множеством и множеством дележей, удовлетворяющих соотношениям (2) и (3) в условиях характеристической функции, называется классической кооперативной игрой.

Кооперативная игра с множеством игроков N и характеристической функцией u называется стратегически эквивалентной игрой с тем же множеством игроков и характеристической функцией u1, если найдутся такие к > 0 и произвольные вещественные Ci (iÎN), что для любой коалиции К Ì N имеет место равенство:

 

u 1 (K) = k u (K) +

 

Смысл определения стратегической эквивалентности кооперативных игр (с. э. к. и) состоит в том что характеристические функции с. э. к. и. отличаются только масштабом измерения выигрышей k и начальным капиталом Ci . Стратегическая эквивалентность кооперативных игр с характеристическими функциями u и u1 обозначается так u~u1. Часто вместо стратегической эквивалентности кооперативных игр говорят о стратегической эквивалентности их характеристических функций.

Справедливы следующие свойства для стратегических эквивалентных игр:

1. Рефлексивность, т.е. каждая характеристическая функция эквивалентна себе u~u.

2. Симметрия, т.е. если u~u1, то u1~u.

3. Транзитивность, т.е. если u~u1 и u1~u2, то u~u2.

Одними из наиболее интересных способов решения коалиционных игр являются решения с применением аксиом Шелли.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-06-03 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: