Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

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

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

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

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

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

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

Реферат

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

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

Выполнила:

Проверила:

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

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)

Представим рассуждения одного из заключённых. Если партнёр молчит, то лучше его предать и выйти на свободу (иначе — год тюрьмы). Если партнёр свидетельствует, то лучше тоже свидетельствовать против него, чтобы получить 5 лет (иначе — 10 лет). Стратегия «свидетельствовать» строго доминирует над стратегией «молчать». Аналогично другой заключённый приходит к тому же выводу.

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

Пример 4.

Пусть два предприятия, ограниченные одним рынком сбыта, выпускают продукцию одинакового назначения, но разного типа. Будем считать, что 1-е предприятие выпускает продукцию А₁, а₂ а₃ и A₄, а 2-е предприятие — В₁, В₂ и B₃. Себестоимость и продажная цена любого типа продукции одинаковы. Имеется прогноз рынка сбыта: гарантирован, сбыт всего 1000 единиц продукции и просчитан прогнозируемый сбыт каждого вида продукции (табл. 1).

Таблица 1

		2-е предприятие выпускает продукцию
		В₁	В₂	В₃
1-е предприятие выпускает продукцию	А₁	(500, 500)	(400, 600)	(500, 500)
	А₂	(100,900)	(600, 400)	(650, 350)
	А₃	(900, 100)	(700, 300)	(800, 200)
	А₄	(400, 600)	(200, 800)	(300,700)

Данные таблицы интерпретируются следующим образом: если 1-е предприятие выпускает продукцию А₁, а 2-е предприятие — продукцию В₁, то сбыт составляет 500 единиц продукции А₁ и 500 единиц продукции В₁, если 1-е предприятие выпускает продукцию А₂, а 2-е предприятие — продукцию В₁, то сбыт составляет 100 единиц продукции А₂ и 900 единиц продукции В₁. Пусть доход от продажи единицы продукции равен одной денежной единице, а мощности каждого из предприятий достаточны, чтобы полностью обеспечить рынок.

Поскольку суммарный сбыт предприятий в каждом случае полностью обеспечивает рынок (сумма чисел в каждой ячейке таблице равна 1000), то интересы предприятий противоположны, и данную ситуацию можно смоделировать в виде антагонистической игры. Первое предприятие является игроком 1, и у него есть четыре стратегии: выпускать продукцию А₁, А₂ А₃ и A₄. Его противник (2-е предприятие) имеет три стратегии: выпускать продукцию В₁, В₂ и B₃. Каждое из предприятий намерено выбрать стратегию, гарантирующую максимальную прибыль при любых действиях противника.

В таблице 1 представлена платёжная матрица этой игры. На пересечении i-й строки и J-го столбца матрицы находится число aij — выигрыш 1-го игрока, если он выпускает продукцию Ai, а его противник — Bi. Выигрыш 2-го игрока при этом равен 1000 — a_ij (таким образом, это — антагонистическая игра с постоянной суммой):

Если платежная матрица имеет седловую точку, то решение игры в чистых стратегиях.

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки	B₁	B₂	B₃	a = min(Ai)
A₁	500	400	500	400
A₂	100	600	650	100
A₃	900	700	800	700
A₄	400	200	300	200
b = max(Bi )	900	700	800

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 700, которая указывает на максимальную чистую стратегию A₃.

Верхняя цена игры b = min(b_j) = 700.

Седловая точка (3, 2) указывает решение на пару альтернатив (A3,B2).

Цена игры равна 700.

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

http://nto.immpu.sgu.ru/sites/default/files/3/_pdf_67262.pdf
http://lib.vvsu.ru/books/Bakalavr01/page0219.asp
http://ru.wikipedia.org/wiki/Дилемма_заключённого
http://works.tarefer.ru/55/100737/index.html