Антагонистические игры

Министерство  образования и науки Российской Федерации

Федеральное государственное  образовательное учреждение высшего  профессионального образования

 «Санкт-Петербургский государственный инженерно-

экономический университет»

 

Факультет логистики и  транспорта

Кафедра высшей математики

 

 

Реферат

По дисциплине математика

Тема: антагонистические игры.

 

 

 

 

 

Выполнила:

 

Проверила:

 

 

 

 

 

 

 

 

 

 

 

Санкт-Петербург

2012

 

Содержание.

Введение…………………………………………………………………...………3

Теория антагонистических игр……………………………………….………….4

Примеры………………………………………………………………...…………8

Список используемой литературы………………………...……………………14

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

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

 

 

 

 

 

 

 

 

 

 

Теория антагонистических игр.

В теоретико-игровой  терминологии 1-я управляющая подсистема называется игроком 1, 2-я управляющая подсистема - игроком 2, множества их альтернативных действий называются множествами стратегий этих игроков. Пусть Х - множество стратегий игрока 1, Y - множество стратегий игрока 2. Состояние системы однозначно определяется выбором управляющих воздействий подсистемами 1 и 2, то есть выбором стратегий x∈X и y∈Y. Пусть F(x,y)- оценка полезности для игрока 1 того состояния системы, в которое она переходит при выборе игроком 1 стратегии х и игроком 2 стратегии у. Число F(x,y) называется выигрышем игрока 1 в ситуации (x,y), а функция F - функцией выигрыша игрока 1. Выигрыш игрока 1 одновременно является проигрышем игрока 2 , то есть величиной, которую первый игрок стремится увеличить, а второй – уменьшить. Это и есть проявление антагонистического характера конфликта: интересы игроков полностью противоположны (то, что выигрывает один, проигрывает другой).

Антагонистическую игру естественно задать системой Г=(Х, Y, F). Заметим, что формально антагонистическая игра задается фактически так же, как и задача принятия решения в условиях неопределенности - если отождествить управляющую подсистему 2 со средой. Содержательное различие между управляющей подсистемой и средой состоит в том, что поведение первой носит целенаправленный характер. Если при составлении математической модели реального конфликта у нас есть основание (или намерение) рассматривать среду как противника, цель которого - принести нам максимальный вред, то такую ситуацию можно представить в виде антагонистической игры. Другими словами, антагонистическую игру можно трактовать как крайний случай ЗПР в условиях неопределенности, характеризуемый тем, что среда рассматривается как противник, имеющий цель. При этом мы должны ограничить виды гипотез о поведении среды.

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

Определение. Если Х и Y конечны, то антагонистическая игра называется матричной. В матричной игре можно считать, что X={1,…,n}, Y={1,…,m} и положить aij=F(i,j). Таким образом, матричная игра полностью определяется матрицей A=(aij), i=1,…,n, j=1,…,m.

Пример 1. Игра с двумя  пальцами.

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

Это антагонистическая  матричная игра. Каждый игрок имеет  четыре стратегии: 1- показать 1 палец  и назвать 1, 2- показать 1 палец и  назвать 2, 3- показать 2 пальца и назвать 1, 4 - показать 2 пальца и назвать 2. Тогда  матрица выигрышей A=(aij), i=1,…,4, j=1,…,4 определяется следующим образом:

a12=2, a21 = –2, a13=a42= –3, a24=a31=3, a34 = –4, a43=4, aij=0 в остальных случаях.

 

 

Определение. Результатом, гарантированным игроку 1 при использовании им стратегии х, называется число min F(x, y).

                                                           _y∈Y.

 Результатом, гарантированным  игроку 2 при использовании им  стратегии у, называется число maxF(x, y).

                                 _x∈X.

Определение. Нижней ценой игры Г=(Х, Y, F) называется величина

υ=max min F(x, y),

      _{x∈X.  y∈Y}

Верхней ценой игры Г называется величина υ=min max F(x, y) .

                                                                                 _{y∈Y.   x∈X}

 

ТЕОРЕМА 1. Для любой непрерывной функции F(x,y), определенной на декартовом произведении компактов Х и Y, справедливо неравенство υ  ≤ υ, т.е.

Max min F(x, y) ≤ min max F(x, y) (1)

    _{x∈X   y∈Y                             y∈Y   x∈X}  

 

Доказательство. Предварительно сформулируем следующую  очевидную лемму:

ЛЕММА 1. Если Z - компактное множество, H(z) - непрерывная функция, то справедливы соотношения

∀z∈Z  H(z)≤a↔max H(z)≤a (2)

                                                              _z∈Z

 

∀z∈Z  H(z)≥a↔min H(z)≥a (3)

                                                              _z∈Z

 

Очевидно, что при всех х и у min  F(x, y′) ≤ F(x, y) ≤max F(x’, y).

                                                                                           _{y’∈Y                                                     x’∈X}  

Применив к этому неравенству  лемму 1, получим требуемое соотношение (1).

Определение. Если в игре Г верхняя и нижняя цены совпадают, то говорят, что в этой игре выполнено соотношение минимакса. Число υ=υ=υ называют ценой игры

ТЕОРЕМА 2. В антагонистической игре Г=(Х, Y, F) седловая точка (х0, у0) существует тогда и только тогда, когда выполнено соотношение минимакса

Max min F(x, y)=min max F(x, y). (5)

_{x∈X       y∈Y                          y∈Y   x∈X}      

 

При этом цена игры равна значению функции выигрыша в седловой точке, то есть , υ=F (x0, y).

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

Необходимость. Пусть (х0, у0) - седловая точка, то есть справедливо (4). С учетом соотношений (2) и (3) это условие можно переписать в виде

Max F(x, y₀)≤ F(x₀, y₀)≤min F(x₀, y)

    _{x∈X                                                     y∈Y}    

 

Но верны неравенства 

Min max F(x, y)≤max F(x, y₀),

                                                                   _{y∈Y       x∈X                        x∈X}

min F(x₀, y)≤max min F(x,y).

                                                                    _{y∈Y                             x∈X      y∈Y}                                              

Получаем неравенство min max F(x,y) ≤max min F(x, y), которое вместе с (1)

                                                                 _{y∈Y       x∈X                      x∈X      y∈Y}      

дает требуемое равенство.

Достаточность. Пусть справедливо (5). Выберем точки х0 и у0 так, чтобы они удовлетворяли условиям

Min F(x₀, y) =max min F(x, y),

                                                                  _{y∈Y                               x∈X      y∈Y}                                              

 

max F (x, y₀) = min max F(x, y)

                                                               _{x∈X                                  y∈Y     x∈X}      

 

Справедливы неравенства min F(x₀, y)≤F(x₀, y₀)≤max F(x, y₀)

                                                                          _{y∈Y                                                  x∈X}      

Из способа выбора х0 и у0 вытекает, что

Max F(x, y₀)=F(x₀, y₀)= min F(x₀, y).

                   _{x∈X                                                      y∈Y}    

 

Используя (2) и (3), получаем (4), что и требовалось доказать.

Определение. Если (х0, у0) - седловая точка, то стратегия х0 называется оптимальной для игрока 1, а стратегия у0 – оптимальной для игрока 2. Непосредственный поиск седловых точек чаще всего проводится с помощью проверки истинности равенства (5).

ТЕОРЕМА 3. В антагонистической игре все седловые точки эквивалентны, а оптимальные стратегии взаимозаменяемы, то есть если (х1, у1) и (х2, у2) - седловые точки, то (х1, у2) и (х2, у1) - также седловые точки, причем

F(x1, y1) =F(x2, y2)=F(x1, y2)=F(x2, y1) .  (6)

Доказательство. Поскольку (х1, у1) и (х2, у2) - седловые точки, то справедливы соотношения

∀x, y F(x, y₁)≤F(x₁, y₁)≤F(x₁, y) (7)

∀x, y F(x, y₂)≤ F(x₂, y₂)≤F(x₂, y). (8)

Из них  легко получить цепочки неравенств

F(x₂, y₂)≤F(x₂, y₁)≤F(x₁, y₁),

            F(x₁, y₁)≤ F(x₁, y₂)≤F(x₂, y₂),

которые влекут за собой систему равенств (6).

Для доказательства того, что (х1, у2) и (х2, у1) также седловые точки, нужно доказать выполнение cледующих условий:

∀x, y   F(x, y₂) ≤ F(x1, y2)≤ F(x1, y),

∀x, y  F(x, y₁) ≤ F(x2, y1)≤ F(x2, y).

Но эти  условия с учетом (6) вытекают из (7) и (8).

 

Пример 2. Игра в орлянку.

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

В итоге матрица выигрышей 1-го игрока Я, выглядит следующим образом:

 

Для антагонистических игр, в которых  выигрыш одного игрока равен проигрышу  другого (игр с нулевой суммой), выполняется соотношение   H1=-H2. Игра в орлянку, очевидно, является примером такой игры.

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

В каждой клетке этой матрицы слева  указаны значения выигрыша 1-го игрока, справа — значения выигрыша 2-го игрока.

Пример 3. Дилемма заключенного.

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

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

	Заключённый 2 хранит молчание(не сознается)	Заключённый 2 даёт показания ( сознается)
Заключенный 1 хранит молчание (не сознается)	Оба получают 1 год. (1, 1)	1 получает 10 лет, 2 освобождается (10, 0)
Заключенный 1 дает показания (сознается)	1освобождается, 2 получает 10 лет тюрьмы  (0, 10)	Оба получают 5 год тюрьмы (5, 5)