Быстрый поиск

Реферат: Теория принятий решений

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

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

Первые работы по ТИ ( Цермело, Борель, фон Нейман ) относятся к началу ХХ века. Но только появление и широкое распространение ЭВМ привлекло к ТИ внимание широкого круга специаоистов.

Теория стратегических игр в своей математической форме возникла в 30-х годах нашего века. Ее создателем считается Джон фон Нейман. Первой фундаментальной книгой по теории игр была изданная в 1944 году работа "Теория игр и экономическое поведение"(Нейман Д., Моргенштерн О. М.:Наука,1970)

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

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

В зависимости от того, какими данными располагает исследователь и какую задачу перед собой ставит, могут быть сформулированы различные теоретикоигровые модели. Различают три основных типа задач:

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

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

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

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

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

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

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

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

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

Игра Г = < X,Y,H>, где X,Y - непустые множества стратегий соответственно первого и второго игроков, H - функция выигрыша Н1 = -Н2 называется антагонистической.

В процессе игры каждый игрок выбирает свою стратегию, в результате чего образуется ситуация (x,y), которой соответствует выигрыш Н(x,y) для первого игрока и - Н(x,y) для второго.

В множестве всех возможных антагонистических игр выделяются классы аффинно-эквивалентных игр.

Две антагонистические игры Г = < X,Y,H> и Г’ = < X’,Y’,H’>, называются аффинно-эквивалентными, если X = X’, Y = Y’ и H’ = k H + a, где а - вещественное, а k > 0. В этом случае используется обозначение Г ~ Г’.

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

Ситуации равновесия (седловые точки).

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

В матричных играх ситуация i*, j* называется приемлемой для первого игрока, если a ij* £ ai*j* и приемлемой для второго игрока , если ai*j* £ a i*j.

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

Ситуация ( i*, j* ) называется равновесной, если она приемлема для обоих игроков. a ij* £ ai*j* £ a i*j . Применительно к антагонистическим играм говорят о седловых точках на поверхности выигрыша ( на них достигается max по первой координате и min по второй.

Свойства седловых точек:

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

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

Теорема. Аффинно-эквивалентные игры имеют одни и те же седловые точки ( то есть их решения совпадают).

Седловыке точки и минимаксы

Устойчивое решение игры может быть получено путем следующих рассуждений:

В самом неблагоприятном случае выигрыш первого игрока не может быть уменьшен по вине противника, если он удовлетворяет условию:

a ij* = min аij

С другой стороны, руководствуясь принципом выгоднгодности первый игрок будет стремиться увеличить свой выигрыш, сохраняя свойство устойчивости, поэтому vн = max min аij

Это нижняя цена игры. Рассуждая подобным образом за второго игрока получим верхнюю цену игры:

vв = min max аij

Интуитивно ясно, что значение ( цена ) игры лежит между vн и vв.

Теорема. Для того, чтобы в матричной игре существовали минимаксы, необходимо и достаточно, чтобы равны были минимаксы:

max min аij = min max аij

Оптимальные смешанные стратегии и их свойства.

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

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

Смешанной стратегией игрока в матричной игре называется полный набор вероятностей x = ( x1, x2 ... xm) и y = ( y1, y2 ... yn) применения его чистых стратегий. (чистые стратегии - исходные).

Свойства смешанных стратегий.

1 свойство. Если x" = ( x1, x2, ... xm ) и y" = ( y1, y2,...yn ) - оптимальные смешанные стратегии игроков в матричной игре, то для произвольных стратегий x и y справедливо

Н ( А, x", y) = å aij xi" ³ v для всех j=1:n, так как это равносильно использованию вторым игроком чистой j-той стратегии: y = ( 0, 0,...yj=1,... 0, 0 )

Н ( А, x, y") = å aij yj" £ v для всех i=1:m, так как это равносильно использованию первым игроком чистой i-той стратегии: x = ( 0, 0,...xi=1,... 0, 0 )

2 свойство. Если в матричной игре с матрицей А и ценой игры v стратегии x" и y" - оптимальные, то

если å aij xi" > v, то yj" = 0

если å aij yj" < v, то xi" = 0

если неравенства обращаются в равенства, то соответственно:

xi" ¹ 0, yj" ¹ 0.

На приведенных свойствах основано решение матричных игр в смешанных стратегиях.

2.6. Доминирование в матричных играх.

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

Пусть задана матричная игра с платежной матрицей А, а смешанные стратегии игроков представлены в виде x = ( x1, x2,... xm ) и y = ( y1, y2,... yn). Вектор х' строго доминирует вектор х"( вектор x" строго доминируется вектором x' ), если справедливо: xi' > xi" , i=1:m. Если неравенство нестрогое, то и доминирование является нестрогим.

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

Если x~, y~- пара оптимальных смешанных стратегий игры с матрицей A, то удалив из вектора x~ нулевую координату с номером r получим пару оптимальных смешанных стратегий x`~,y~ игры с матрицей A`, полученной из матрицы A вычеркиванием строки с номером r.

Обратное утверждение тоже верно. Если x`~,y~- пара оптимальных смешанных стратегий игры с матрицей A`, то добавив в качестве r-той коодинаты вектора x`~ ноль и сдвинув на одно место вправо все координаты вектора x~ с номерами r, r+1... m-1, получим пару оптимальных смешанных стратегий x~,y~ игры с матрицей A.

Теорема. Если строка с номером r в матрице А нестрого доминируется выпуклой линейной комбинацией всех остальных строк, то существует оптимальная смешанная стратегия первого игрока x~, у которой r-тая координата равна нулю.

Любая пара x`~,y~ оптимальных смешанных стратегий игры с матрицей А` преобразуется в пару оптимальных смешанных стратегий x~,y~ игры с матрицей А добавлением нулевой координаты с номером r в вектор x`~ и сдвигом координат этого вектора с номерами r, r+1,...m-1 на одно место вправо.

Во всех этих случаях значение игры с матрицей А совпадает со значением игры с матрицей А~.

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

Если x~,y~ - пара оптимальных смешанных стратегий в игре с матрицей А, то удалив из вектора y~ нулевую координату с номером s, получим пару оптимальных смешанных стратегий x~,y`~ игры с матрицей A`, полученной из матрицы А вычеркиванием столбца с номером s.

Обратное: если x~,y`~ - пара оптимальных смешанных стратегий игры с матрицей A`, то добавив в качестве координаты с номером s вектора y`~ ноль и сдвинув все координаты с номерами s, s+1,... n-1 на одно место вправо получим пару x~,y~ оптимальных смешанных стратегий в игре с матрицей А.

Теорема. Если столбец с номером s в матрице А нестрого доминирует выпуклую линейную комбинацию всех остальных столбцов, то существует такая оптимальная смешанная стратегия y~ второго игрока, в которой координата с номером s равна нулю и любая пара x~,y`~ оптимальных смешанных стратегий игры с матрицей А` преобразуется в пару оптимальных смешанных стратегий x~,y~ игры с матрицей А добавлением нулевой s-той координаты и сдвигом координат с номерами s, s+1,... n-1 вектора y`~ вправо на одно место.

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

Если столбец матрицы А доминирует какой-либо другой (то есть он больше) или выпуклую линейную комбинацию всех остальных столбцов, то ее можно вычеркнуть, решить игру с меньшим количеством столбцов и получить оптимальные смешанные стратегии добавлением нулей вместо невостающих координат в векторе второго игрока.

Метод приближенного определения цены игры.

Способ отыскания приближенного решения прямоугольных игр был сформулирован в работе Г.В.Брауна, а сходимость процесса была доказана Джулией Робинсон в 1951 году.

Этот метод, называемый еще итеративным, опирается на традиционный статистический принцип: основывать будущие решения на соответствующей предыстории.

Заключается он в последовательной процедуре "сближения" вержней и ниждей цены игры с заданной точностью.

Глава . Биматричные игры

[VU1]

Функция выигрыша биматричной игры представляет собой две платежные матрицы : А - определяет выигрыш первого игрока, а В - выигрыш второго игрока. Первый игрок имеет m чистых стратегий ( m строк в матрицах А и В ) Второй игрок имеет n чистых стратегий ( n столбцов в матрицах А и В ).

В результате выбора первым игроком i-той стратегии, а вторым игроком j-той стратегии, первый игрок получает выигрыш aij, а второй - bij .

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

В биматричной игре ситуация i*j называется приемлемой для первого игрока, если его выигрыш в этой ситуации не меньше, чем в любой другой:

аi*j ³ аij j=1:n

Для второго игрока ситуация ij* приемлема, если его выигрыш в этой ситуации не меньше, чем в любой другой:

bi*j ³ bij i=1:m

Tаким образом, приемлемые ситуации для первого игрока - это максимальные элементы встолбцах матрицы А, а для второго игрока - максимальные (тоже!) элементы в строках матрицы В.

Ситуация i*j* в биматричной игре называется равновесной, если она приемлема для обоих игроков, то есть если любое отклонение от нее как для первого игрока, так и для второго только лишь уменьшает их выигрыш:

аi*j* ³ аij*

bi*j* ³ bi*j

Множество ситуаций равновесия G образуется как пересечение множеств приемлемых ситуаций первого и второго игроков.

Пример.