Реферат: Матричные игры

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

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

Каждая модель социально-экономического явления должна отражать черты конфликта, т.е. описывать:

1. множество заинтересованных сторон (в теории матричных игр их называют игроками, т.е. сторонами, участвующими в конфликте. Так же их называют субъектами, сторонами, участниками).
2. возможные действия каждой из сторон, именуемые стратегиями или ходами. («Ход» - выбор одного из предложенных правилами игры действий; «стратегия» - план, по которому игрок совершает выбор в любой ситуации и т.д.)
3. интересы сторон, представленные функциями выигрыша (платежа) для каждого из игроков («выигрыш» - исход конфликта).

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

Классификация игр

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

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

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

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

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

3. АНТАГОНИСТИЧЕСКИЕ ИГРЫ

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

Наиболее часто приводимым примером игр с ненулевой суммой является игра «Дилемма заключенного». Суть игры состоит в том, что два преступника ожидают приговора суда за содеянное. Адвокат конфиденциально предлагает каждому из преступников облегчить его участь, если он сознается и даст показания против сообщника, которому грозит угодить в тюрьму за совершенное преступление на 10 лет. Если никто не сознается, то обоим угрожает заключение на определенный срок (например, 1 год) по обвинению в незначительном преступлении. Если сознаются оба то преступника, то, с учетом чистосердечного признания, им обоим грозит попасть в тюрьму на 5 лет. Каждый заключенный имеет на выбор 2 стратегии: не сознаться или сознаться, выдав при этом сообщника.

Обобщим выше сказанное: 1 игрок – сознаться или не сознаться и 2 игрок – сознаться или не сознаться. В итоге можно получить следующую матрицу «выигрышей» для обоих игроков:

.

Решение антагонистических игр

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

В игре могут участвовать как два игрока (её называют парной), так и множество. Но наибольшее практическое значение имеют парные игры, в которых участников обозначают за A и B. Простейшим видом стратегической игры – игра двух лиц с нулевой суммой (т.е. сумма выигрышей сторон равна нулю).

Игра состоит из двух ходов: игрок A выбирает одну из своих возможных стратегий ( i = 1, 2, …, m ), а игрок B выбирает стратегию ( j = 1, 2, .., n ), причем каждый участник делает выбор в полной ситуации незнании выбора другого игрока. В результате выигрыши и каждого из игроков удовлетворяют соотношению

, откуда если , имеем .

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

Пусть , тогда составим матрицу:

.

Строки матрицы соответствуют стратегиям , столбцы – стратегиям . Матрица А называется матрицей игры, а элемент матрицы – выигрыш игрока А , если он выбрал стратегию , а игрок B выбрал стратегию .

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

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

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

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

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

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

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

Задача: определить верхнюю и нижнюю цены для игр, заданных платежными матрицами А и В:

и .