Лабораторная работа Тема: Состязательные задачи.

Теория игр.

1.Цель работы: Приобретение практических навыков применения метода теории игр для оптимального решения задач о конфликтных ситуациях.

2.Общие положения.

2.1 Постановка задачи и краткие теоретические положения.

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

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

Стратегии могут быть чистыми, если рекомендуется принимать определенные неслучайные решения, или - смешанными, когда рекомендуется принимать те или иные решения с учетом фактора случайности.

Если все возможные комбинации стратегий сторон имеют конечное количество, то для оценки стратегий составляется матрица выигрышей:

M= C_ij , где i=1,2....n , j=1,2....m (2.1)

Cij - выигрыш стороны А, если она выбрала стратегию i, а сторона В выбрала стратегию j.

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

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

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

а=max min (C_ij) (2.2)

i j

Определенная таким образом величина «а» называется нижней ценой игры, т.е. макси - минным выигрышем.

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

b = max min (C_ij) (2.3)

i j

Величина «b» называется верхней ценой игры, или минимаксом.

Подобные определения имеют место, если обе стороны действуют по оптимальным стратегиям.

Если величины а = b (2.4)

то решение находится в области чистых стратегий,

а если a  b (2.5)

то решение находится в области смешанных стратегий.

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

Для определения оптимальных стратегий поведение сторон в состязательных задачах применяется:

а) аппарат линейного программирования для задач с полной информацией;

б) вероятностный подход для задач с неполной информацией;

в) теория статистических решений для задач при отсутствии информации.

В данной работе рассматривается состязательная задача - игра двух сторон А и В с нулевой суммой в общем виде (замкнутая игра).

Условия игры заданы платёжной матрицей ( в виде результатов см. таблицу 2.1),отдельные элементы которой (C_ij) определяют суммы, которые проигравшая сторона В обязана уплатить стороне А в заранее определённой выигрышной ситуации (A_i,B_j).

Таблица 2.1

			Bj
Ai	B1	B2		......	Bj		......	Bm
A1	C11	C12		......	C1j		.......	C1m
.....	.....	....		.....	.....		.....	.....
Aj	Ci1	Ci2		.....	Cij		.....	Cim
.....	......	.....		.....	.....		.....	.....
An	Cn1	Cn2		.....	Cnj		......	Cnm

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

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

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

		Bj
			(2.6)
	4	5	6
A=	7	4	5
	4	2	8

Игрок А имеет три возможные стратегии: a₁, а₂, а₃, а игрок В - четыре возможные стратегии : b₁,b₂, b₃,b₄.

Нижняя цена игры :

a = max {min(4,5,2,6);min(7,4,3,5);min(4,2,1,8)} = 3 (2.7)

Верхняя цена игры:

b = min {max(4,7,4);max(5,4.2);max(2,3,1);max(6,5,8)} = 3 (2.8)

Так как

а₂=3 и b₃=3,

т.е

а=b,

то имеем игру с седловой точкой. Игрок А не знает как поступит игрок В, поэтому, действуя наиболее целесообразно, он должен выбрать стратегию А2, которая гарантирует наибольший (а₂=3) из всех возможных наименьших выигрышей (2,3,2).Игрок В, продолжая рассуждение, должен выбрать, в случае выигрыша игроком А, стратегию В3, которая гарантирует ему наименьший V из всех возможных наибольших проигрышей (7,5,3,8).

В общем случае цена игры в3=3 будет

а₂ <= V <= в₃ (2.8)

Для игры рациональные правила поведения стороны А (выигрышной) следующие.

1.Если известна стратегия стороны В (например b₃), то сторона А должна выбрать ту из своих стратегий (например a₂), которая обеспечивает ей максимальный выигрыш.

2.Если стратегия стороны В неизвестна, то сторона А должна воспользоваться своей максимильной стратегией, которая обеспечивает ей в самых неблагоприятных условиях максимально - возможный выигрыш (а₂=3).

3. Если стратегия стороны В неизвестна, но задача имеет седловую точку, то наиболее выгодно для стороны А не отклоняться от оптимальной стратегии, соответствующей седловой точке.

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

Дублирующими называются стратегии, которым соответствуют одинаковые значения элементов матрицы игры, т.е. матрица содержит практически одинаковые строки (столбцы).

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

При отсутствии седловой точки, для достижения выигрыша стороне А, необходимо выбрать стратегии А_I и B_j с определёнными вероятностями или частотами их осуществления при многократной игре. Это смешанные стратегии. Теоретически доказано, что для любой игры с нулевой суммой всегда существуют оптимальные смешанные стратегии.

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

Смешанная стратегия для стороны А (для примера(2.6)):

	а1	a2	а3	(2.9)
	р1	p2	р3

где - вероятность использования соответствующих чистых стратегий, при этом

(2.9а)

Д ля стороны В одновременно будет:

	b1	b2	b3	b4	(2.10)
	Q1	q2	q3	q4

и соответственно: q₁+q₂+q₃+q₄=1 (2.10a)