Xreferat.com » Рефераты по математике » Матричные антагонистические игры с нулевой суммой в чистых стратегиях

Матричные антагонистические игры с нулевой суммой в чистых стратегиях

height="24" align="BOTTOM" border="0" />

а

…

а

…

а

… … … … … …

а

а

…

а

…

а

… … … … … …

а

а

…

а

…

а


то проведение каждой партии матричной игры с матрицей сводится к выбору игроком А i-й строки, а игроком В j-го столбца и получения игроком А (за счет игрока В) выигрыша а.

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

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


а (i = )


т.е. определяется минимальный выигрыш для игрока А при условии, что он примет свою i-ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = i, при которой этот минимальный выигрыш будет максимальным, т.е. находится


а = а= α


1.2 Определение игры


Дадим определение понятию «Игра». Игрой называется набор


,


где N – произвольное множество игроков; S – произвольное множество всех исходов игры; XK - произвольное множество стратегий коалиции KN; S(XK) S – множество возможных исходов, если коалиция K применяет стратегию хKХK; - транзитивное отношение предпочтения коалиции KN на S. При математической формализации игра, должна проходить по определенным правилам, которые представляют следующую систему условий:

  • возможные действия каждого из игроков;

  • объем информации, которую может получить каждая сторона о действиях другой;

  • исход игры в результате каждой совокупности ходов противников.

Игроки: Считается заданным список игроков. Если игроков различать по номерам, то их список сводится к множеству , где - число игроков. Считается, что игроки осведомлены о наличии каждого из своих партнеров.

Действия: Каждый игрок имеет в своём распоряжении некоторый набор стратегий . Множества могут быть как конечными, так и бесконечными. В основе рационального поведения участников игры лежит так называемый постулат «общего знания»: каждый полностью информирован о своих стратегических возможностях и о стратегических возможностях своих партнёров. Процесс игры состоит в выборе каждым из игроков своей стратегии: . В результате складывается игровая ситуация . Множество Ω всех возможных игровых ситуаций образует ситуационное пространство игры, обозначаемое .

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

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

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

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

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

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

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

  1. чередование ходов, которые могут быть как личными, так и случайными

  2. возможная недостаточность информации

  3. функция выигрыша

Запишем теперь основные этапы поиска решения игры:

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

  2. поиск доминирующих стратегий (в случае успеха этого поиска – отбрасывание доминирующих строк и столбцов в исходной матрице игры).

  3. замена игры на её смешанное расширение и отыскание оптимальных смешанных стратегий и цены игры.



Игрок 2 стратегия 1 Игрок 2 стратегия 2
Игрок 1 стратегия 1

4, 3

–1, –1

Игрок 1 стратегия 2

0, 0

3, 4

Нормальная форма для игры с 2 игроками, у каждого из которых по 2 стратегии.


Отметим, что нормальная форма антагонистической игры сводится к некоторой матрице А с числом строк равным числу стратегий игрока 1 и с числом столбцов, равным числу стратегий игрока 2. Выигрыш – если игрок 1 выбирает i-ю стратегию, а игрок 2 j-ю стратегию – представляет собой элемент в i-ой строке и в j-ом столбце данной матрицы.

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

Пример 1: игра «Орлянка».


X Y

Орел

Решка

Орел

-1, 1 1, -1

Решка

1, -1 -1, 1

Первый игрок прячет монету орлом или решкой вверх, а второй пытается угадать, как она спрятана. Если он не угадывает – платит первому одну денежную единицу, если угадывает – первый платит ему одну денежную единицу. В данной игре каждый игрок имеет две стратегии: «орёл» и «решка». Множество ситуаций в игре состоит из 4 элементов. В строках таблицы указаны стратегии первого игрока Х, в столбцах – стратегии второго игрока Y. Для каждой из ситуаций указаны выигрыши первого и второго игроков.

Рассмотрим основную теорему матричных игр.

Основная теорема теории матричных игр (по Дж. фон Нейману).

Для матричной игры с любой матрицей А величины и равны между собой, т.е.



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



Иными словами, любая матричная игра имеет решение в смешанных стратегиях. Поиск этого решения опирается на установленные факты.

Приведём доказательство данной теоремы (автор: Дж. Б. Данциг, 1951г.)

Теорема. Каждая матричная игра с нулевой суммой всегда имеет решение в смешанных стратегиях, т.е. существуют такое число и такие стратегии и игроков 1 и 2 соответственно, выполняются неравенства:


.(*)


Комментарий. Формула (*) означает, что: если игрок 1 отклоняется от своей оптимальной стратегии, то его выигрыш не увеличивается по сравнению с ценой игры; если от своей оптимальной стратегии отклоняется игрок 2, то по сравнению с ценой игры его проигрыш не уменьшается.

Доказательство.

Пусть матрица игры равна . Всегда можно считать, что все коэффициенты . Если это не так, то предположим, что наименьший из всех отрицательных коэффициентов есть . Тогда увеличим все элементы платёжной матрицы на произвольное положительной число . Функция выигрыша при этом окажется равной


.


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

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


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


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

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

  1. так называемая позиционная форма. При этом определяются:

    • порядок ходов

    • альтернативы (возможные ходы), доступные каждому из игроков на момент наступления его хода

    • информация, которой владеет каждый из игроков на момент очередного хода

    • выигрыши (для каждого игрока) как функции от выбранных ходов

    • вероятностные распределения на множестве возможных состояний внешней среды

    1. нормальная или стратегическая форма. Каждый участник (игрок) k, где, характеризуется наличием индивидуальной системы целевых установок и множеством стратегий , т.е. возможных вариантов действий в игре.

Ранее упоминалось о таком понятии, как «антагонистическая игра». Примером такой игры может служить игра «Орлянка». Дадим определение антагонистической игре.

Антагонистическая игра - игра, в которой участвуют два игрока (обычно обозначаемые I и II) с противоположными интересами. Для антагонистической игры характерно, что выигрыш одного игрока равен проигрышу другого и наоборот, поэтому совместные действия игроков, их переговоры и соглашения лишены смысла.. Определяются антагонистические игры заданием множеств стратегий игроков и выигрышей игрока I в каждой ситуации, состоящей в выборе игроками своих стратегий. Таким образом, формально антагонистическая игра есть тройка ‹А, В, Н›, в которой А и В - множества стратегий игроков, а Н (а, b) - вещественная функция (функция выигрыша) от пар (а, b), где а A, b В. Игрок I, выбирая а, стремится максимизировать Н(а, b), а игрок II, выбирая b, - минимизировать Н (а, b).

Пример 2:

Рассмотрим игру G (4х5) в матричной форме.



3 4 5 2 3

1 8 4 3 4

10 3 1 7 6

4 5 3 4 8

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

3 4 5 2 3 2

1 8 4 3 4 1

10 3 1 7 6 1

4 5 3 4 8

3

10 8

5

7 8

Из всех значений выделено наибольшее (3). Ему соответствует величина - гарантированный выигрыш, который называется нижней ценой игры. Исходя из принципа осторожности, надо выбрать стратегию , а противник должен выбрать стратегию . Такая стратегия называется «минимаксной». Выше было упомянуто о принципе минимакса. Рассмотрим далее соответствующую терему.

Теорема о минимаксе.

Можно доказать, что для любой функции F(x,y) определённой на произвольном декартовом произведении X Ч Y имеет место неравенство . Отсюда следует, что

Запишем 2 утверждения:

Утверждение 1. Точка 0 (в m-мерном пространстве) содержится в выпуклой оболочке m+n точек


и


Утверждение 2. Существуют числа удовлетворяющие условиям

Доказательство: Пусть А – матричная игра. Имеет место либо утверждение 1, либо утверждение 2. Если верно утверждение 1 то 0 является выпуклой линейной комбинацией m+n векторов. Поэтому существуют такие


что


Если бы все числа были бы равны нулю, то 0 оказывался бы выпуклой линейной комбинацией m единичных векторов , что невозможно, т.к. они линейно независимы. Следовательно, по крайней мере одно из чисел положительно и



тогда можно положить


и получится для всех i


Значит и

Предположим, что верно утверждение 2. Тогда , так что . Следовательно, неравенство не имеет смысла. Предположим, что игра А изменена на игру , где . Для любых х и y , поэтому . Так как неравенство не имеет смысла, то неравенство также не выполняется. Но k произвольно. Значит неравенство невозможно. Т.к. то . Что и требовалось доказать.

Принцип минимакса.

Рассмотрим игру с платежной матрицей Следует определить наилучшую стратегию игрока I среди стратегий , и игрока II среди стратегий , . Определение наилучших стратегий игроков основано на принципе, который предполагает, что противники, участвующие в игре, одинаково разумны и каждый из них делает все для того, чтобы добиться своей цели. Найдем наилучшую стратегию игрока I. Допустим, что он выбрал i-ю стратегию (i –ю строку матрицы (1)). Тогда он получит меньше, чем – наименьшее число в этой строке. Причем это будет в том случае,

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: