Реферат на тему кооперативные игры

Обновлено: 07.07.2024

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

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

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

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

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

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

1. Кооперативные игры: понятие, сущность,особенности

Кооперативные игры получаются в тех случаях, когда, в игре n игроков разрешается образовывать определённые коалиции. Обозначим через N множество всех игроков, N =, а через K ( любое его подмножество. Пусть игроки из K договариваются между собой о совместных действиях и, таким образом, образуют одну коалицию. Очевидно, что число таких коалиций, состоящих из r игроков,равно числу сочетаний из n по r , то есть [pic], а число всевозможных коалиций равно[1]
[pic]= 2n ( 1.
Из этой формулы видно, что число всевозможных коалиций значительно растёт в зависимости от числа всех игроков в данной игре. Для исследования этих игр необходимо учитывать все возможные коалиции, и поэтому трудности исследований возрастают с ростом n. Образовав коалицию, множествоигроков K действует как один игрок против остальных игроков, и выигрыш этой коалиции зависит от применяемых стратегий каждым из n игроков.
Функция (, ставящая в соответствие каждой коалиции K наибольший, уверенно получаемый его выигрыш ((K), называется характеристической функцией игры. Так, например, для бескоалиционной игры n игроков ((K) может получиться, когда игроки из множества Kоптимально действуют как один игрок против остальных N\K игроков, образующих другую коалицию (второй игрок).
Характеристическая функция ( называется простой, если она принимает только два значения: 0 и 1. Если характеристическая функция ( простая, то коалиции K, для которых ((K)=1, называются выигрывающими, а коалиции K, для которых ((K) = 0, (.

Кооперативные игры получаются в тех случаях, когда, в игре n игроков разрешается образовывать определённые коалиции. Обозначим через N множество всех игроков, 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 (KÈL) ³ u_G (K) + u_G (L), если K, L Ì N, KÇL ¹ Æ,

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

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

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

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

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

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

= u(N)

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

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

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

Из этих определений непосредственно вытекает следующая

Теорема. Чтобы вектор x = (x₁ , . x_n ) был дележём в классической кооперативной игре ,

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

Краткая история развития.

Как это работает

Типы игр

Кооперативная\некооперативная игра

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

С нулевой суммой и с ненулевой суммой

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

Параллельные и последовательные

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

С полной или неполной информацией

Эти типы являются подвидом последовательных игр, и названия их говорят сами за себя.

Метаигры

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

Проблемы практического применения

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

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

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

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

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

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

Заключение

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

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

Читайте также: