Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
1. Свойства седловых точек действительной функции двух векторных аргументов.
1) Свойство равнозначности: если ai1j1 и ai2j2 (i1,i2, j1,j2) – седловые точки, то ai1j1 = ai2j2
2) Свойство взаимозаменяемости: если ai1j1 и ai2j2 (i1,i2, j1,j2) – седловые точки, то ai1j2 и ai2j1 – также седловые точки.
2. Критерий пессимизма-оптимизма Гурвица оптимальности чистых стратегий относительно выигрышей.
Критерий пессимизма-оптимизма Гурвица относительно выигрышей с показателями оптимизма [0,1] – взвешенное среднее минимального и максимального выигрышей игрока А при выбранной им стратегии Аi с весами 1 − и .
Данный критерий является как бы промежуточным между критериями крайнего пессимизма и крайнего оптимизма и представляет собой частный случай обобщенного критерия Гурвица относительно выигрышей.
Показателем эффективности стратегии Ai по рассматриваемому критерию является величина:
Оптимальной же стратегией по этому критерию считается стратегия Ai0 с максимальным показателем эффективности
Вообще показатели пессимизма и оптимизма в этом критерии равны соответственно λp =1- λ и λ0 = λ. При λ=0 мы получаем критерий Вальда, а при λ=1 – максимаксный критерий. Чем ближе к нулю показатель оптимизма λ, тем ближе к единице показатель пессимизма 1- λ, и тем меньше оптимизма и больше пессимизма. И наоборот, чем ближе λ к единице, тем больше оптимизма и меньше пессимизма.
3. Задача теории игр в экономике.
Во многих задачах финансово-экономической сферы возникает необходимость принятия решения. Проблема принятия решения осложняется тем, что ее приходится решать в условиях неопределенности.
В условиях полной определенности теоретические и практические выводы носят однозначный характер и, таким образом, представляют четкое описание ситуации в рамках рассматриваемой задачи. В условиях же недостаточной информированности или полной неопределенности результаты анализа уже не обладают такой четкостью и однозначностью.
Попытка количественного анализа финансово-экономических ситуаций и принятия на их основе решения привела к созданию специальных экономико-математических методов обоснования выбора решений в условиях рыночной неопределенности. Эти методы позволяют находить количественные характеристики экономических процессов, что влечет за собой возможность наиболее полного сравнения исследуемых явлений.
При выборе решения в условиях неопределенности всегда присутствует фактор действия наудачу без обоснованной уверенности в успехе. Он неизбежно присутствует в различных хозяйственных операциях (коммерческий риск), в выполнении предприятием определенного заказа (производственный риск), в выполнении фирмой финансовых обязательств перед инвестором (кредитный риск), в решении купить акции или другие ценные бумаги (инвестиционный риск), в решениях положить деньги в банк (финансовый риск). Математические методы обоснования решений дают возможность анализа вариантов решения с целью уменьшения риска, которое иногда достигается за счет получения дополнительной информации. Математизация содержательных финансово-экономических задач о принятии решениях в условиях неопределенности приводит к соответствующим экономико-математическим моделям и методам, теоретический аспект которых составляет теорию игр. Таким образом, задачами теории игр в экономике являются задачи о выборе решений в условиях экономической неопределенности.
4. Смешанные стратегии: определение, геометрическая интерпретация.
Смешанная стратегия игрока - стратегия игрока, состоящая в случайном выборе им 1 из своих чистых стратегий с определенной вероятностью;
Смешанная стратегия – линейная комбинация чистых стратегий с коэффициентами, равными вероятностям чистых стратегий, поэтому смешанную стратегию, например, игрока А, имеющего m чистых стратегий, можно представить m-мерным вектором
Правая часть равенства является выпуклой комбинацией орт А1,...,Аm и потому мн-во SA всех смешанных стратегий геометрически представляет собой фундаментальный (m-1)-мерный симплекс с m вершинами в точках А1,...,Аm, представляющих чистые стратегии (выпуклая оболочка, натянутая на чистые стратегии).
Например, при m = 1 игрок А обладает одной чистой стратегией A1 и потому смешанная стратегия совпадает с чистой. Таким образом, мн-во смешанных стратегий состоит из единственного элемента А1 : SA= ={А1} - и представляет собой 0-мерный симплекс, состоящий из единственной точки - вершины А1. (Рис. 1)
При m = 2 игрок А имеет 2 чистые стратегии: ={А1, А2}, а мн-во SA смешанных стратегий есть 1-мерный симплекс с двумя вершинами А1 и А2, представляющий собой отрезок с концами А1, и А2. (Рис. 2)
При m = 3 у игрока А 3 чистые стратегии: ={А1, А2, А3}; мн-во SA смешанных стратегий является 2-мерным симплексом с вершинами А1, А2, А3, представляющим собой плоский правильный треугольник А1 А2 А3. (Рис. 3)
p2
При m = 4 множество смешанных стратегий SA есть 3-мерный симплекс с четырьмя вершинами А1 А2, А3, А4, представляющий собой правильный тетраэдр. (Рис. 4)
Аналогичная геометрическая интерпретация имеет место и для игрока В, мн-во чистых стратегий которого ={B1, …, Bn} представляет собой множество п вершин B1, …, Bn (n-1)-мерного симплекса смешанных стратегий.
5. Матрица игры: определение, связь элементов матрицы с функцией выигрыша.
Матрица игры – матрица выигрышей игрока А в антагонистической игре, имеющая размер m×n, где m – число строк (т.е. число стратегий игрока А, n – столбцов (стратегий В).
Соотношение между матрицами выигрышей игроков А и В в парной антагонистической игре с нулевой суммой выигрышей:
bij = FB (Bj,Ai) = − FA (Ai,Bj) = − aij, i = 1,…,m, j = 1,…, n
Из этого неравенства следует, что матрица выигрышей B игрока B является противоположной транспонированной матрице А: B = −AT
Также FB (Bj,Ai) + FA (Ai,Bj) = 0 и поэтому антагонистические игры называют также играми двух сторон с нулевой суммой выигрыша.
6. Критерий Гурвица оптимальности смешанных стратегий относительно выигрышей. (28 б.)
Пусть SA –множество всех смешанных (в том числе и чистых) стратегий игрока А и Р=(р1,…,рm) –некоторая смешанная стратегия игрока А из множества SA: Рϵ SA. Тогда выигрыш игрока А при применении им смешанной стратегии Р=(р1,…,рm), соответствующий состоянию природы Пj, равен , j=1,…,n. Где: aij , i=1,…,m , j=1,…,n –элементы матрицы.
Показатель эффективности чистой стратегии Аk - , i=1,…,m.
Показатель эффективности смешанной стратегии Р=(р1,…,рm), по критерию Гурвица относительно выигрышей с показателем оптимизма [0,1] назовем число G(P;)=(1-)W(P)+ M(P).
Где: и –соответственно минимальный и максимальный выигрыш игрока А при использовании им смешанной стратегии Р.
Если смешанная стратегия Р=(р1,…,рm) является чистой Ak, то pi =0 при i≠k, и pk =1; следовательно H(P,Пj)=H(Ak, Пj)=akj , и пок-ль эфф. G(P, ) привращается в пок-ль эфф. Gk( ) при i=k.
Оптимальной среди всех смешанных стратегий множества SA по критерию Гурвица относит-но выигрыша с показателем оптимизма [0,1], назовем стратегию Ро=(р1о,…,рmо) ϵ SA с максимальным показателем эффективности G(P, ): .
7. Определение и существование показателя эффективности смешанной стратегии игрока А относительно множеств смешанных и чистых стратегий игрока В. (25 баллов)
Показатель эффективности смешанной стратегии Рϵ SA игрока А относительно множеств смешанных стратегий SB игрока В = α (Р; SВ).
Условия существования показателя эффективности – теорема: Для каждой смешанной (в частности, чистой) стратегии Рϵ SA игрока А существует (достигается) показатель эффективности . (т.е. т.к. симплекс является ограниченным замкнутым множеством (компактом), для любого Рϵ SA существует (найдется хотя бы 1 точка) Qo ϵ SB.)
8. Теорема Дж. фон Неймана. (25 баллов)
Или основная теорема матричных игр Дж. фон Неймана: любая матричная игра имеет решение в смешанных стратегиях, т.е. существует цена игры в смешанных стратегиях V и оптимальные смешанные стратегии Ро и Qo соответственно игроков А и В.
9. Устойчивые и неустойчивые игровые ситуации. Игровые ситуации, удовлетворительные для игроков, и их критерии. (25 баллов)
Ситуация – набор стратегий игроков А и В.
Устойчивая ситуация или ситуация равновесия; седловая точка игры – ситуация, удовлетворительна для обоих игроков, т.е. когда игроки А и В придерживаются своих максиминной и минимаксной стратегий соответственно, то ни один из них не может увеличить свой выигрыш отступая от своей стратегии: aij0≤ai0j0≤ai0j , i=1…m, j=1,…,n, или αi0=ai0j0=βjo
Неустойчивая ситуация – ситуация, сложившаяся после первых ходов игры устраивает только одного игрока, например А, тогда игрок В следующим ходом меняет свою стратегию, приводя игру к ситуации, которая не удовлетворяет игрока А.
Ситуация (Ai0,Bj0) называется удовлетворительной (приемлемой/ допустимой) для игрока А, если aij0≤ai0j0 , i=1,…,m , и удовлетворительной для игрока В, если ai0j0≤ai0j , j=1,…,n.
Критерии удовлетворительных ситуаций:
10. Антагонистическая игра: сущность, связь функций выигрыша игроков. (25 баллов)
Антагонистическая игра – игра с двумя участниками, которые преследуют противоположные цели. В такой игре один из игроков выигрывает ровно столько, сколько проигрывает другой. Поэтому, функции выигрышей и соответственно игроков А и В связаны между собой соотношением FA(Ai,Bj) = ‒FB(Bj, Ai), i=1,…m, j=1,…n. или FA(Ai, Bj) + FB (Bj, Ai) =0, i=1,…,m, j=1,…,n. – поэтому антагонистическую игру называют также игрой с нулевой суммой выигрыша.
11. Игры с природой: сущность, экономические примеры. (24 балла)
Игры с природой – математическая модель принятия решений в ситуации, когда одним из игроков является окружающая процесс принятия решений среда, называемая «природой», при этом различают «принятие решений в условиях риска» и «принятие решений в условиях неопределенности». В игре с природой осознанно действует только один игрок, пусть это будет игрок А, он принимает решение. Природа, обозначенная через П, второй игрок, действует неосознанно, принимает решения неопределенным образом, действует без конкретной цели и безразлично к результату игры. Пусть игрок А имеет m возможных стратегий А1,..,Аm, а природа П может находится в одном из состояний n состояний П1,…,Пn,которые можно рассматривать, как ее «стратегии». Совокупность { П1,…,Пn,} формируется на основе анализа природы или интуиции экспертов. Выигрыш игрока А при выбранной стратегии Аi, i=1..m, и при состоянии природы Пj, j=1..n, обозначим aij, i=1..m, j=1..n. Так можно сформировать матрицу выйгрышей.
А-платежная матрица игры с природой. Строки соответствуют стратегиям игрока, а столбцы -состояниям природы. Любой элемент матрицы есть результат реализации i игрока в условиях j состояния природы.
Задача игрока А состоит в выборе оптимальной стратегии, обеспечивающей ему максимально возможный выигрыш. Поскольку стратегии Аi, i=1,…,m, выбираются игроком А осознанно, а не случайно, то их называют чистыми стратегиями. В играх с природой можно и полезно пользоваться принципом доминирования стратегий игрока А. При решении вопроса о выборе возможной стратегии в игре с природой игрок А должен исходить из матрицы выигрышей.
В зависимости от имеющейся информации различают две ситуации. Принятия решений в условиях риска, когда известны состояния природы при которых нужно принимать решения, либо известны вероятности, с которыми природа принимает каждое из возможных состояний, либо существует дополнительная информация об относительных показателях , опросах и усреднениях. Пример: три решения на перехода на выпуск новых товаров A1,A2,A3 . Результаты зависят от обстановки П1,П2,П3; вероятности каждой обстановки q1,q2,q3.Задается матрицей. Каждому сочетанию соответствует выигрыш. Так как состояния природы известны - условия риска.
Принятие решений в условиях неопределенности, когда известны возможные состояния природы, при которых нужно принимать решения, но неизвестны, вероятности этих состояний и нет возможности получить о них какую-то статистическую информацию. Пример: возможно строительство сооружений разного типа A1,A2,A3. Эффективность каждого типа определяется от различных явлений. Число возможных сочетаний факторов П1,П2,П3. Задается матрица. Поскольку вероятности состояния природы неизвестны – это условие неопределенности.
12. Критерий Лапласа оптимальности чистых стратегий относительно выигрышей.
Критерий Лапласа оптимальности относительно выигрышей – Критерий Байеса относительно выигрышей с равновероятными состояниями природы, по которому оптимальной считается стратегия Aio с максимальным показателем эффективности по этому критерию, то есть , где – взвешенно среднее выигрышей aij игрока А при выборе им стратегии Ai и при состоянии природы Пj с весовыми коэффициентами qj, представляющими собой вероятности состояний природы Пj. При Лапласе ситуация, когда игрок А лишен возможности определить состояния природы, то он вынужден оценивать их субъективно. Один из способов предположить q=1/n, j=1…n, тогда показатель эффективности чистых стратегий по критерию Лапласа относительно выигрышей называется среднее арифметическое io строки матрицы . Аio оптимальная, если . Оптимальная среди чистых стратегий по критерию Лапласа является оптимальной по тому же критерию среди смешанных стратегий.
13. Теорема о соотношении между нижней и верхней ценами игры в смешанных и чистых стратегиях.
Теорема. Нижняя цена игры α и верхняя цена игры β в чистых стратегиях, нижняя цена игры и верхняя цена игры в смешанных стратегиях удовлетворяют следующим неравенствам:
Начнем доказательство с неравенства . По определению нижней цены игры в смешанных стратегиях . Здесь правая часть не зависит от Р и потому это неравенство остается верным и для Р=Аi, i=1…m. Так как полученное равенство будет справедливым в частности для того номера i, который максмизирует показатель эффективности , Доказано.
Докажем второе неравенство . Для любых Р принадлежащих Sa и Q принадлежащих Sb имеем:
Так как утверждение справедливо для любых Р принадлежащих принадлежащих Sa и Q принадлежащих Sb, то
Докажем третью часть . . Это также верн и для чистых стратегий Q=Bj, j=1,…,n игрока В . Следовательно, ч.т.д.
14. Функция выигрыша в смешанных стратегиях: запись в координатной и матричной формах.
Определим функцию выигрыша игрока А в смешанных стратегиях как функцию Н, заданную на декартовом произведении SA x SB множеств смешанных стратегий, ставящую в соответствие каждой ситуации (P,Q) SA x SB в смешанных стратегиях средний выигрыш игрока А в этой ситуации, определяемый выражением . Таким образом,H(P,Q) = , (P,Q) SA x SB, где P=(p1,…..,pm), Q=(q1,….,qn) -координатная форма задания функции выигрыша в смешанных стратегиях.H(P,Q) = PAQT – матричная форма функции выигрыша, где P=(p1,…,pm) – вектор-строка размера 1хm,А= – матрица игры(выигрышей игрока А в чистых стратегиях) размера m x n, QT =
15. Основные понятия и определения теории игр. Классификация игр.
Теория игр – теоретическая основа математических моделей, принятие оптимальных решений в конфликтной ситуации рыночных отношений.
Неопределенность – действия сторон, направленных на уменьшение эффективности другой стороной. Риск – вероятность неблагоприятного исхода.
Конфиктная ситуация – столкновение интересов , не менее 2х сторон каждая из которых для достижения своей цели имеет возможность действовать различными способами в зависимости от действий противоборствующих сторон.
Характеризуется: а)наличие заинтересованных сторон – игроков, б)существование возможных действий у каждой стороны – стратегий, в) интересами сторон, удовлетворяющих различные эконом, соц, полит потребности. Стратегия: А-игрок А, m>=1-стратегий, => , А-игрок А, т>=1-стратегий
Игра – математическая модель конкретной ситуация. Конфликт первичен.
Коалиции - объединение игроков.(по причинам- действия, интересов, и действ и инт; временный: пост и временные; числу участ: парные и множеств)
Правила игры – система условий с целью формализации (записи на мат. язык некоторых утверждений).а) Стратегии чистые – детерминированные, смешанные – смесь разных стратегий. Б)объем инфы, к-й каждый из игроков может получить о действиях игрока. с) исход игры в результате совокупности стратегий игроков.
В условиях конфликтных ситуаций каждый игрок определяет стратегию, в результате образуется набор ситуаций – исход игры. Исход – набор всех ситуаций. Запрещенные – недопустимые по правилам игры, если так, то игра не состоится.
Функция выигрыша игрока А в чистых стратегиях Fa-степень удовлетворенности интересов игрока А. , x э Х, аналогично
Функция выигрыша игрока В в чистых стратегиях Fв - степень удовлетворенности интересов игрока В
Классификация игр: 1)от воз-сти образования коалиций а)коалиционные – для макс. Коалиционного выигрыша, в) бескоалиционные – индивидуальный выигрыш; 2) по числу множественные – более 2х игроков, парные – 2 игрока. В парных играх игроки преследует противоположные цели – антагонистические (нулевая сумма выигрыша), игры с природой – один из игроков неосознанно –природа. В) мощность множества стратеги – а)конечные игры – если множество стратегий конечные, б) бесконечные – множество большее, чем четное.
21. Принцип доминирования стратегий.
Говорят, что стратегия x игрока 1 доминирует стратегию x’ в (m*n)-игре G A , если для всех чистых стратегий j = 1,….n игрока 2 выполняются неравенства x’a j > x’a j .
Доминирование - ситуация, при которой одна из стратегий некоторого игрока дает больший выигрыш, нежели другая, при любых действиях его оппонентов.
Цель принципа доминирования – уменьшить размер матрицы, путем выбрасывания из рассмотрения тех стратегий, которые являются очевидно невыгодными.
22. Критерий Вальда оптимальности чистых и смешанных стратегий.
Данный критерий основывается на выборе игроком А лучшей среди наихудших стратегий (без информации о вероятностях состояний природы).
Для определения оптимальной стратегии Р по матрице выигрышей используют максиминный принцип – необходимо в каждой строке матрицы найти наименьший элемент и среди них выбрать наибольший: V = maxi minj {aij}.
Применение критерия к матрице затрат проводится через использование минимаксного принципа: V = mini maxj {aij}.
23. Седловая точка игры в чистых стратегиях, её свойства.
Ситуация (Ai0; Bj0) называется равновесной, или устойчивой, или седловой точкой игры, если она удовлетворительна для каждого из игроков А и В, т.е. если выполняются следующие неравенства: aij0 <= ai0j0 <= ai0j, i=1,..,m; j=1,..,n или αi0=ai0j0=βj0.
Выигрыш ai0j0 называют седловой точкой матрицы игры. Таким образом, элемент ai0j0, являющийся седловой точкой матрицы игры, является минимальным в своей i0-й строке и максимальным в своей j0-м столбце. Игра, матрица которой содержит хотя бы один такой элемент называется игрой с седловой точкой.
Свойства:
24. Игра с нулевой суммой выигрыша.
По характеру выигрышей различают игры с нулевой суммой и игры с ненулевой суммой. Игры с нулевой суммой выигрыша - это антагонистические игры, в которых проигрыш одного игрока является выигрышем другого. То есть сумма выигрышей двух игроков равна нулю.
25. Критерий цены игры и оптимальных смешанных стратегий.
Если верхняя и нижняя цены игры в смешанных стратегиях совпадают, то их общее значение называется ценой игры в смешанных стратегиях, а стратегии Р и Q будут оптимальными стратегиями. Оптимальные стратегии обладают тем свойством, что если один игрок придерживается своей оптимальной стратегии, то второму невыгодно отклонятся от своей оптимальной стратегии. Т.е. цена игры в смешанных стратегиях V не меньше нижней цены игры в чистых стратегиях и не больше верхней цены игры в чистых стратегиях.
Полным решением игр в смешанных стратегиях называется совокупность [SОА: SОВ; V]. Любая пара оптимальных стратегий P, Q и цены игры V образуют частное решение в смешанных стратегиях.
Теорема Неймана. Любая матричная игра имеет решение в смешанных стратегия, т.е. существует цена игры в смешанных стратегиях V и оптимальные смешанные стратегии P и Q соответственно игроков А и В.
26. Седловые точки матрицы игры: свойства, способы нахождения.(25 баллов)
С. т.— это наибольший элемент столбца матрицы игры, который одновременно является наименьшим элементом соответствующей строки (в игре двух лиц с нулевой суммой). В этой точке, следовательно, максимин одного игрока равен минимаксу другого; С. т. есть точка равновесия.
Свойства седловых точек:
1. Равноценность. Если в игре несколько седловых точек, то значения функции выигрыша в них одинаковы.
2. Взаимозаменяемость оптимальных стратегий. Игроки могут заменить свои оптимальные стратегии другими оптимальными стратегиями, при этом равновесие не нарушится, а выигрыш (проигрыш) останется неизменным.
С. т. матрицы — элемент aki матрицы (aij), удовлетворяющий условию:
27. Смешанные стратегии. Геометрическая интерпретация множества смешанных стратегий. (20 баллов).
Смешанная стратегия, это чередуемые случайным образом чистые стратегии, с определенными вероятностями (частотами).
Множество SA смешанных стратегий геометрически представляет собой (m-1)-мерный симплекс c m вершинами А1…Аm представляющих собой чистые стратегии
m=1
m=2
m=3
m=4
28. Теорема о сведении решения матричной игры к решению пары двойственных друг другу стандартных задач линейного программирования.
Решение матричной игры mn с матрицей игры A эквивалентно решению пары двойственных друг другу стандартных задач линейного программирования:
1. н-ти min при огран-иях xi≥0, i=1,…,m, ≥1, j=1,…,n;
2. н-ти max при огран-иях yj≥0, j=1,…,n; ≤1, i=1,…,m,
где элементы матрицы A aij>0, i=1,…,m, j=1,…,n. (3)
Точнее говоря, если - оптимальное решения задачи 1, а - оптимальное решение задачи 2, то
(4) - цена игры с матрицей A,
(5) - оптимальная стратегия игрока А,
(6) - оптимальная стратегия игрока B.
Верно и обратное утверждение. Если P0 и Q0 – оптимальные стратегии соответственно игроков А и B,а V – цена игры, то
(7) - оптимальное решение задачи 1, а (8) - оптимальное решение задачи 2.
Доказательство. Во-первых, необходимо доказать, что задачи 1 и 2 имеют хотя бы по одному допустимому решению.
На основании неравенств 3 можно утверждать, что aij>0, i=1,…,m. Учитывая это, обозначим через , i=1,…,m, произвольные числа, удовлетворяющие неравенствам , i=1,…,m. (9)
Из этих неравенств в силу неравенства 3 получим , i=1,…,m, j=1,…,n, и потому
Таким образом, вектор , удовлетворяющий условию 9, положителен и удовлетворяет ограничениям задачи 1, т. е. является допустимым решение этой задачи.
Допустимым решением задачи 2 является нулевой вектор , поскольку он неотрицателен и удовлетворяет ограничениям задачи 2.
В задаче 1 целевая функция на допустимом множестве ограничена снизу а в задаче 2 на допустимом множестве ограничена сверху, поскольку , где .
Таким образом, из непустоты допустимых множеств решений и ограничения с соответствующей стороны целевых функций следует существование для каждой задачи хотя бы одного оптимального решения.
Пусть и - оптимальны решения соответственно задач 1 и 2.
Решение неотрицательно и не может быть нулевым, поскольку это противоречило бы ограничениям задачи 1. Поэтому хотя бы одна из координат вектора положительна и, следовательно, . В таком случае согласно критерию оптимальности решений взаимно двойственных задач линейного программирования .
Учитывая это неравенство, а также 4, 5 и 6, получим
, i=1,…,m, ,
, о=1,…,m, ,
т.е , i=1,…,m, и , j=1,…,n, являются вероятностями и и - смешанные стратегии соответственно игроков А и В. Теперь покажем, что эти смешанные стратегии являются оптимальными. Используя определения и и ограничения 1 и 2, получим следующие неравенства , которые, используя формулы , (10)
где координаты чистой стратегии игрока В представлены с помощью символа Кронекера в виде , l=1,…,n; , (11)
где координаты чистой стратегии игрока А представлены в виде , k=1,…,m, можно переписать в виде
, i=1,…,m, j=1,…,n. (11)
Это двойное неравенство является критерием того, что V будет ценой игры, а и - оптимальными стратегиями игроков.
Теперь докажем обратную часть теоремы. Пусть V - цена игры, а и - оптимальные стратегии игроков. Тогда верно следующее неравенство , откуда в силу 3 получаем V>0. В этом случае можно определить векторы и по формулам 7 и 8 и получить
, i=1,…,m, (12)
, j=1,…,n. (13)
По формулам 10 и 7 и неравенству 11 получим
, (14)
где j=1,…,n,
по формулам 10, 8 и 11 получим
, (15)
где i=1,…,m.
Неравенства 12 и 14 означают, что вектор , определяемый 7, является допустимым решением задачи 1, аналогично 13 и 15 для . При этом значения целевых функций из 1 и 2 на соответствующих допустимых векторах и равны 1/V. Следовательно, по достаточной части критерия оптимальности допустимых решений взаимно двойственных задач линейного программирования решения и являются оптимальными.
Теорема доказана.
Число β(Q; SA), определенное равенством
назовем показателем неэффективности смешанной стратегии Q SB игрока В относительно множества SA смешанных стратегий игрока А, а число
- показателем неэффективности смешанной стратегии Q игрока В относительно множества чистых стратегий игрока А. В частности, если смешанная стратегия Q является чистой Вj, то из (2), H(P,Q) = H(Аi, Вj) = aij = F(Аi, Вj) = F(P,Q) и
будем иметь
Для показателей неэффективности смешанных стратегий игрока В имеет место теорема: показатели неэффективности любой смешанной (в частности, чистой) стратегии QSB игрока В относительно множеств и SA чистых и смешанных стратегий игрока А равны, т.е.
Доказательство. Из включения SA следует включение
и потому (см.(1) и (2))
С другой стороны, если P = (p1, ..., pm)SA и Q = (q1, ..., qn)SB, то по формулам
(2) и будем иметь
Правая часть этого неравенства не зависит от Р и потому по (1):
Это неравенство обратно неравенству (4) и потому равенство (3) доказано.
30. Максимаксный критерий оптимальности чистых и смешанных стратегий. (25 баллов)
Максимаксный критерий (крайнего оптимизма) оптимальности чистых стратегий.
Является противоположностью критерия Вальда. Представляет собой частный случай обобщенного критерия Гурвица относительно выигрышей, когда коэф. выбираются следующим образом:
Оптимальной среди чистых стратегий по максимаксному критерию является стратегия Аio с максимальным показателем эффективности:
Т.е. стратегия, максимальный выигрыш при которой максимален среди максимальных выигрышей всех чистых стратегий. Поэтому оптимальной будет стратегий, при которой (хотя бы) один из выигрышей является максимальным среди выигрышей всех чистых стратегий .Оптимальная по максимаксному критерию стратегия гарантирует игроку А возможность наибольшего выигрыша, равного максимаксу.
Для максимаксного критерия показатели пессимизма и оптимизма равны соответственно , . Таким образом, максимаксный критерий является критерием крайнего оптимизма, так как ориентирует ЛПР на наилучшее, благоприятнейшее для него состояния природы и, следовательно, на порой неоправданно легкомысленное поведение при выборе стратегий. Вместе с тем, в некоторых ситуациях этим критерием пользуются осознанно, например, в ситуации когда перед игроком стоит дилемма: либо получить наибольший выигрыш, либо стать банкротом. Бытовое отражение подобной ситуации иллистрируется поговорками: «Пан или пропал», «Кто не рискует, тот не выигрывает». «Всё или ничего».
Смешанные стратегии.
Смешанная стратегия игрока – стратегия игрока, состоящая в случайном выборе им одной из своих чистых стратегий с определенной вероятностью, поэтому смешанную стратегию, например, игрока А, имеющего m чистых стратегий можно представить m-мерным вектором Р=(р1,…,рm), рi, i=1,2,…m.
Смешанной стратегией игрока называется совокупность его чистых стратегий с определёнными для них вероятностями выбора:
, , .
Цена игры в смешанных стратегиях – общее значение нижней и верхней цены игры в смеш.стратегиях: V= относительно которых доказано, что они всегда существуют и равны.
Нижняя цена:
Верхняя цена игры:
Смешанная стратегия, это чередуемые случайным образом чистые стратегии, с определенными вероятностями (частотами).
Смешанную стратегию игрока "А"
|
SA = |
|
где A1, A2 - стратегии игрока "A", а p1, p2 - соответственно вероятности (частоты), с которыми эти стратегии применяются, причем p1 + p2 = 1.
Аналогично смешанную стратегию игрока "В"
|
SB = |
|
где B1, B2 - стратегии игрока "B", а q1, q2 - соответственно вероятности, с которыми эти стратегии применяются, причем q1 + q2 = 1.
31. Неопределённость при принятии решений, виды неопределённостей.
(20 баллов)
Принятие решения в условиях неопределенности характеризуется тем, что при выборе альтернативы принимающему решение неизвестно наличное состояние среды и он не имеет информации о вероятностях их появления. Отметим, что эта неопределенность не является абсолютной, так как принимающему решение известны множество возможных состояний среды (множество Y) и функция реализации F. Оценочная структура ЗПР в условиях неопределенности задается в виде оценочной функции. Композиция функции реализации и оценочной функции представляет собой целевую функцию f. При этом число f(x,y) указывает полезность (ценность, эффективность) того исхода, который получается в ситуации, когда принимающий решение выбирает альтернативу хX, а среда принимает состояние уY. Напомним, что если оценка исходов выражает затраты, убытки или другие негативные факторы, то в этом случае функция f называется функцией потерь. Итак, математическая модель ЗПР в условиях неопределенности
может быть задана в виде следующей тройки объектов (X,Y,f), где X – множество допустимых альтернатив, Y – множество возможных состояний среды, f:X×Y→R – целевая функция. Основная сложность при принятии решения в условиях неопределенности состоит в том, что, выбирая одну из допустимых альтернатив, принимающий решение не знает имеющегося состояния среды; в то же время, получающийся исход зависит от того, в каком состоянии находится среда. Формально, целевая функция f(x, у) является функцией двух аргументов х и у; принимающий решение должен выбирать значение аргумента хX, не зная значения аргумента уY. В теории принятия решений различают следующие основные позиции: оптимистическую,
пессимистическую, позиции компромисса и нейтралитета.
32. Критерий Байеса оптимальности смешанных стратегий относительно выигрышей. (30 баллов)
Пусть в матрице игры строки означают возможные варианты решений, принимаемых игроком (им могут быть менеджер-руководитель и т. п.), столбцы — возможные состояния природы (Т. е. хозяйственной среды). Элемент матрицы аij, означает сумму платежа в ситуации, когда игрок принимает решение i , то есть выбирает стратегию i при состоянии природы j.
Пусть известны не только состояния П1 … Пn но и вероятности q1 … qn с которыми природа П реализует эти состояния. Тогда мы находимся в ситуации принятия решения в условиях риска. Показателем эффективности стратегии Аi по критерию Байеса относительно выигрышей называется среднее значение или математическое ожидание выигрыша i-й строки с учётом вероятности всех возможных состояний природы:
Оптимальной среди чистых стратегий по критерию Байеса относительно выигрышей считается стратегия Аio с максимальным показателем эффективности, т.е. с максимальным средним выигрышем:
Т.о. выбранное решение по этому критерию является оптимальным не в каждом отдельном случае, а в среднем.
Рассмотрим матрицу игры:
|
Bj |
П1 |
П2 |
П3 |
П4 |
|
А1 |
2 |
3 |
1 |
7 |
|
А2 |
4 |
2 |
9 |
1 |
|
А3 |
3 |
5 |
8 |
6 |
|
А4 |
6 |
4 |
2 |
2 |
|
А5 |
5 |
3 |
7 |
2 |
известны вероятности q = (0.3;0.4;0.2;0.1)
т.к. а3 – max, то А3 – оптимально по кр. Байеса относительно выигрыша.
33. Критерий Лапласа оптимальности смешанных стратегий относительно выигрышей. (22 балла)
Часто складывается такая ситуация, когда мы лишены возможности определить вероятности состояния природы. Но желая принять решение в условиях риска, мы вынуждены оценить вероятности состояний природы субъективно. Существует множество методов выбора, один из которых состоит в том, что мы не можем дать предпочтения ни одному из состояний природы и поэтому считаем их равновероятными ( ). Этот принцип называется «принципом недостаточного основания» Лапласа. На нём основан критерий Лапласа относительно выигрышей.
Показателем эффективности стратегии Аi по критерию Лапласа относительно выигрышей называется среднее арифметической выигрышей i-й строки:
Оптимальной среди чистых стратегий по критерию Лапласа относительно выигрышей считается стратегия Aio , показатель эффективности которой, вычисляемый по формуле (строка сверху) максимален, т.е.
Очевидно, что критерий Лапласа относительно выигрышей есть частный случай критерия Байеса относит выигрышей при .
Рассмотрим матрицу игры:
|
Bj |
П1 |
П2 |
П3 |
П4 |
|
А1 |
2 |
3 |
1 |
7 |
|
А2 |
4 |
2 |
9 |
1 |
|
А3 |
3 |
5 |
8 |
6 |
|
А4 |
6 |
4 |
2 |
2 |
|
А5 |
5 |
3 |
7 |
2 |
q1=q2=q3=q4=1/4
по критерию Лапласа А3 – оптимальное решение относительно выигрыша.
34. Соотношения между множествами оптимальных и максиминных (минимаксных) чистых стратегий. (28 баллов)
Стратегиииигроков А и В, создающие равновесную ситуацию, называются оптимальными. Обозначим черези- множества чистых оптимальных стратегий соответственно игроков А и В.
Справедливы следующие утверждения.
1. Каждая оптимальная стратегия игрока А является его максиминной стратегией, а каждая оптимальная стратегия игрока В является его минимаксной стратегией.
2. В игре без седловых точек ни одна из максиминных и минимаксных стратегий не является оптимальной, поскольку в этой игре вообще нет оптимальных стратегий.
3. В игре с седловыми точками каждая максиминная и каждая минимаксная стратегии соответственно игроков А и В являются оптимальными.
35. Нижняя и верхняя цены игры. Полное и частное решения игры в чистых стратегиях. Критерий существования цены игры в чистых стратегиях. (30 баллов)
Если нижняя цена игры α равна верхней цене β, то их общее значение γ = α = β называется ценой игры в чистых стратегиях.
Совокупность {, , γ} множестви чистых оптимальных стратегий игроков А и В и цены игры γ называется полным решением игры в чистых стратегиях, а совокупность какой-нибудь пары чистых оптимальных стратегийии цены игры γ называется частным решением игры в чистых стратегиях.
Теорема 1. Для того чтобы существовала цена игры в чистых стратегиях, т. е. для того чтобы нижняя цена игры α равнялась верхней цене игры β, необходимо и достаточно существование у матрицы этой игры седловой точки.
Цена игры в смешанных стратегиях – общее значение нижней и верхней цены игры в смеш.стратегиях: V= относительно которых доказано, что они всегда существуют и равны.
Нижняя цена:
Верхняя цена игры:
Критерий решения игры в чистых стратегиях упирается в критерий существования цены игры в чистых стратегиях.
Свойство: ни одному из игроков А и В, придерживающихся одной из своих оптимальных стратегий невыгодно от нее отклоняться, поскольку в этом случае он не увеличивает свой выигрыш.
Цена игры в чистых стратегиях представляет собой значение выигрыша игрока А, которое он не может увеличить, если игрок В придерживается своей оптимальной стратегии и значение проигрыша игрока В, которое последний не может уменьшить при условии, что игрок А действует по своей оптимальной стратегии.
Теорема: для того, чтобы существовала цена игры в чистых стратегиях, т.е. для того чтобы нижняя цена игры равнялась верхней цене игры , необходимо и достаточно существование у матрицы этой игры седловой точки.
В игре без седловых точек ни у одного из игроков оптимальных стратегий нет. Т.е. задача в чистых стратегияхи меет решение, если сущ. седловая точка.
37.Теорема об эквивалентности критериев Байса относительно выигрышей и относительно рисков.
Рассмотрим игру с природой, в которой статистик-игр А имеет возможных стратегий , а природа П может прибывать в одном из своих состояний . Предположим, что статистик может оценить последствия применения каждой своей стратегии в зависимости от каждого состояния природы П, т.е. статистику известен численный результат при выборе каждой стратегии , и при каждом состоянии природы . Тогда эту игру с природой можно задать следующей платежной матрицей размера :
А=
(1)
перед тем как переходить к выбору оптимальной стратегии, целесообразно по возможности упростить матрицу А, уменьшив число строк на основании принципа доминирования стратегий игрока А.
В понятии оптимальной стратегии лежат различные соображения, составляющие содержание соответствующих критериев оптимальности стратегий.
Критерий Байеса относительно выигрышей
Предположим, что статистику из прошлого опыта известны не только состояния , в которых может находиться природа П, но и соответствующие вероятности , с которыми природа П реализует эти состояния. Тогда мы находимся в ситуации принятия решения в условиях риска.
Показателем эффективности стратегии по критерию Байеса относительно выигрышей называется среднее значение, или математическое ожидание выигрыша й строки с учетом вероятностей всех возможных состояний природы. Обозначим это среднее значение через , будем иметь
|
. |
(4) |
Таким образом, представляет собой взвешенное среднее выигрышей й строки, взятых с весами .
Оптимальной среди чистых стратегий Байеса относительно выигрышей считается стратегия с максимальным показатель эффективности (4), т.е. с максимальным среднем выигрыша
.
Таким образом, выбранное решение по этому критерию является оптимальным не в каждом отдельном случае, а в среднем.
Распространим понятие показателя эффективности по критерию Байеса относительно выигрышей на смешанные стратегии игрока А.
Пусть - некоторая смешанная стратегия игрока А, при которой чистая стратегия используется им с вероятностью . Тогда выигрыш игрока А при смешанной стратегии и при состоянии природы будет равен
|
(5) |
Показателем эффективности смешанной стратегии по критерию Байеса относительно выигрышей назовем среднее значение выигрышей (5) с учетом вероятностей состояний природы. Обозначим этот показатель через .
Используя (4), будем иметь:
|
(6) |
Таким образом, как видно из равенства (6), показатель эффективности смешанной стратегии по критерию Байеса относительно выигрышей представляет собой взвешенное среднее показателей эффективности чистых стратегий по тому же критерию с весами .
Пусть - множество всех смешанных (в том числе и чистых) стратегий игрока А. Оптимальной среди всех смешанных стратегий множества по критерию Байеса относительно выигрышей назовем стратегию , показатель эффективности (6) который максимален: .
В этом определении в связи с бесконечностью множества встает вопрос о существовании оптимальной среди всех стратегий множества стратегии . Существование такой обосновывается следующим образом. Из представления (6) функции заключаем, что она линейна, и следовательно, непрерывна по векторному аргументу . А поскольку к тому же она определена на симплексе , являющимся ограниченным замкнутым множеством в мерном евклидовом пространстве , то по теореме Вейерштрасса функция достигает на симплексе своей верхней грани, т.е. найдется стратегия , такая, что .
Критерий Байеса относительно рисков
Рассмотрим игру с природой с матрицей А, к которой известны вероятности состояний природы . При принятии решений в условиях риска можно пользоваться не только средними выигрышами, но и средними рисками. Составим матрицу рисков для матрицы А, используя формулу рисков (2):
(2)
Показателем неэффективности стратегии по критерию Байеса относительно рисков называется среднее значение (математическое ожидание) рисков й строчки матрицы (2), вероятности которых, очевидно, совпадают с вероятностями состояний природы. Обозначим средний риск при стратегии через , тогда
|
, |
(1) |
является взвешенным средним рисков й строчки матрицы (2)с весами .
Оптимальной среди чистых стратегий по критерию Байеса относительно рисков является стратегия , показатель неэффективности (1) которой минимален, т.е. минимален средний риск
.
Определим понятие риска при использовании игроком А смешанной стратегии и при состоянии природы , как разность
|
, |
(2) |
между максимальным выигрышем при всех смешанных стратегиях и состоянии природы и выигрышем при смешанной стратегии и состоянии природы .
В качестве показателя неэффективности смешанной стратегии по критерию Байеса относительно рисков рассмотрим взвешенную среднюю рисков (2) с весовыми коэффициентами, равными вероятностями состояний природы:
|
. |
(3) |
Оптимальной среди смешанных (в том числе и чистых) стратегий по критерию Байеса относительно рисков будем считать стратегию , показатель неэффективности которой, вычисляемой по формуле (3), минимален: .
Теорема Критерий Байеса относительно выигрышей и относительно рисков эквивалентны, т.е. если стратегия является оптимальным по критерию Байеса относительно выигрышей, то она является оптимальной и по критерию Байеса относительно рисков, и наоборот, стратегия , оптимальная по критерию Байеса относительно рисков, оптимальна и по критерию Байеса относительно выигрышей.
Доказательство. В силу (1), риска и среднего выигрыша
|
(4) |
Величина , представляющая собой взвешенное среднее максимальных выигрышей с учетом вероятностей состояний , является постоянной относительно номера . Поэтому из равенства (4) очевидно, что достигает своего минимума на том же номере , на котором достигает своего максимума. Таким образом, если стратегия является оптимальной по критерию Байеса относительно выигрышей, то является максимальным средним выигрышем, то тогда является минимальным средним риском и потому стратегия является оптимальной по критерию Байеса относительно рисков.
То, что из оптимальности стратегии по критерию Байеса относительно рисков следует ее оптимальность по критерию Байеса относительно выигрышей, доказывается аналогичными рассуждениями, но в обратном порядке. Теорема доказана.
36.Теорема об эквивалентности критериев Лапласа относительно выигрышей и относительно рисков
Критерий Лапласа относительно выигрышей
Довольно часто складывается такая ситуация, когда мы лишены возможности определить вероятности состояний природы. Желая все же принять решение в условиях риска, мы вынуждены оценить вероятности состояний природы субъективно. Существуют различные методы численной субъективной оценки степени правдоподобности состояний природы. Один из них состоит в том, что мы не можем отдать предпочтение ни одному из состояний природы и потому мы считаем их равновероятными, т.е. . Этот принцип называется «принципом недостаточного основания» Лапласа. На нем основан критерий Лапласа относительно выигрышей.
Показателем эффективности стратегии по критерию Лапласа относительно выигрышей называется среднее арифметическое выигрышей й строки:
|
(1) |
Оптимальной среди чистых стратегий по критерию Лапласа относительно выигрышей считается стратеги , показатель эффективности которой, вычисляется по формуле (1), максимален, т.е. .
Очевидно, что критерий Лапласа относительно выигрышей есть частный случай критерия Байеса относительно выигрышей при . Поэтому все утверждения, доказанные для критерия Байеса относительно выигрышей, остаются в силе и для критерия Лапласа относительно выигрышей.
Подставляя (1) в , получим показатель эффективности смешанной стратегии по критерию Лапласа относительно выигрышей:
|
. |
(2) |
Стратегия будет оптимальной среди всех смешанных стратегий множества по критерию Лапласа относительно выигрышей, если она максимизирует показатель эффективности (2).
Оптимальная среди чистых стратегия по критерию Лапласа относительно выигрышей является оптимальной по тому же критерию и среди смешанных.
Так как не зависит от номера , то в качестве показателя эффективности стратегии можно вместо величины (1) рассматривать правую часть равенства (1) без множителя и, следовательно оптимальной среди чистых стратегий по критерию Лапласа относительно выигрышей можно считать стратегию , для которой показатель эффективности максимален:
.
Аналогичное замечание относится и к равенству (2), правую часть которого можно рассматривать без множителя , поскольку он не зависит от смешанной стратегии .
Критерий Лапласа относительно рисков
Критерий Байеса относительно рисков при равновероятных состояниях природы, , превращается в критерий Лапласа относительно рисков. Тогда величина , получающаяся из (7) при , или более простая величина представляет собой показатель неэффективности стратегии по критерию Лапласа относительно рисков. Следовательно, оптимальной среди чистых стратегий по критерию Лапласа относительно рисков является стратегия , показатель неэффективности которой минимален. Подставляя в значения , получим показатель неэффективности смешанной стратегии по критерию Лапласа относительно рисков, вместо которого можно рассматривать более простую величину . Стратегия , для которой показатель принимает минимальное значение, является оптимальной среди всех стратегий среди множества . Для равновероятных состояний природы чистая стратегия, оптимальная среди чистых стратегий по критерию Лапласа относительно рисков, оптимальна по тому же критерию и среди всех смешанных стратегий множества
38. Игры с природой. Показатель благоприятности состояния природы. Матрица рисков. (30 баллов).
В экономике часто принятие решений связано не с сознательным противодействием противнику, а с недостаточной информированностью игрока об объективных условиях, в которых будет приниматься решение. Такая модель называется игра с природой.
В играх с природой второй игрок (природа) не действует осознанно против первого игрока, а принимает случайным образом одно из своих возможных состояний, не преследует никакой цели, безразличен к исходу игры.
Показателем благоприятности состояния Пj природы называется наибольший выигрыш при этом состоянии, т.е. наибольший элемент в j-том столбце. βj = max aij, j=1...n.
Для характеристики удачности применения стратегии Ai игрока А при состоянии природы Пj вводится понятие риска. Риск (rij) - разность между показателем благоприятности βj состояния природы Пj и выигрышем aij. rij= βj- aij, т.е. риск - это упущенная возможность максимального выигрыша. Матрица рисков строится по столбцам, исходя из формулы rij= βj- aij, имеет ту же размерность, что и матрица выигрышей.
|
Выигрыш |
П1 |
П2 |
|
А1 |
1 |
3 |
|
А2 |
4 |
2 |
|
Риски |
П1 |
П2 |
|
А1 |
3 |
0 |
|
А2 |
0 |
1 |
39. Показатели эффективности и неэффективности чистых стратегий игроков. Нижняя и верхняя цены игры в чистых стратегиях. Теорема о соотношениях между выигрышами игроков А и В, показателями эффективности и неэффективности стратегий, нижней и верхней ценами игры. (28 баллов)
Рассмотрим матричную игру mxn: ScA ={Ai}, i=1...m; ScB ={Bj}, j=1...n.
Ai0 принадлежит ScA (ai01, aio2,...,aion)
Bj0 принадлежит ScB : min ai0j=αi0, j принадлежит [1...n], где αi0 - показатель эффективности стратегии Ai0 игрока А.
А выберет стратегию с целью максимизации. max αi= max min aij = α - максимин.
Принцип выбора оптимальной стратегии для игрока А - максиминный принцип. Оптимальная стратегия, соответствующая максимину - максиминная стратегия. Если игрок А выбрал максиминную стратегию, то при любой Bj ему гарантирован выигрыш не меньше α. То есть α - нижняя цена игры.
Рассмотрим игрока В. Он выбирает Bj0 принадлежит ScB (bj01, bj02,..., bjom)T
Ai0 принадлежит ScA : max aij0=βj0, i принадлежит [1...m], где βj0 показатель неэффективности стратегии Bj0 игрока В.
В выберет стратегию с целью минимизации. min βj = min max aij = β - минимакс.
Принцип выбора оптимальной стратегии для игрока В - минимаксный принцип. Оптимальная стратегия, соответствующая минимаксу - минимаксная стратегия. Если игрок В выбрал минимаксную стратегию, то при любой Ai его проигрыш будет не больше β. То есть β - верхняя цена игры.
Теорема: αi≤ aij≤βj i=1...m, j=1...n. А, значит, и α≤β.
40. Принцип доминирования стратегий игроков
Доминирование в теории игр — ситуация, при которой одна из стратегий некоторого игрока дает больший выигрыш, нежели другая, при любых действиях его оппонентов.
Если i-я строка поэлементно не меньше (≥) j-й строки, то говорят, что i-я строка доминирует над j-й строкой. Поэтому игрок A не использует j-ю стратегию, так как его выигрыш при i-й стратегии не меньше, чем при j-й стратегии, вне зависимости от того, как играет игрок B. Аналогично, если i-й столбец поэлементно не меньше (≥) j-го столбца, то говорят, что j-й столбец доминирует над i-м столбцом. Поэтому игрок B не использует i-ю стратегию, так как его проигрыш (равный выигрышу игрока A) при j-й стратегии не больше (≤), чем при i-й стратегии, вне зависимости от того, как играет игрок A. Стратегии, над которыми доминируют другие стратегии, надо отбросить и приписать им нулевые вероятности. На цене игры это никак, конечно, не скажется, но зато размер матрицы игры понизится. С этого и нужно начинать решение игры.
Если у игры нет седловой точки, то её решение можно упростить с помощью редуцирования игр, т.е. сведением данной игры со сложной матрицей к игре с более простой матрицей. На принципе доминирования основан один из способ редуцирования.
41. Критерий цены игры и оптимальных смешанных стратегий в терминах множеств смешанных стратегий игроков. (28 баллов)
42. Основная теорема теории матричных игр. (22 балла)
Основная теорема теории игр — теорема Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть S*A = (p*1, p*2, ..., p*i, ..., p*m) и S*B = (q*1, q*2, ..., q*i, ..., q*n) — пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной.
43. Экономическая интерпретация максиминного и минимаксного принципов матричной игры. (28 баллов).
показателем эффективности стратегии Аi назовем минимальный выигрыш при этой стратегии: αi=min aij , i=1,2..m, 1≤j≤n.
Максимином, или нижней ценой игры в чистых стратегиях, называется наибольший из показателей эффективности стратегий Аi, i=1,2..m,
α=max αi=maxmin aij , 1≤j≤n 1≤i≤m
Стратегия Ак, показатель эффективности которой совпадает с максимином αк =α, называется максиминной стратегией игрока А. множество всех (чистых) стратегий максиминных стратегий игрока А обозначим через (Sac )max min
принцип выбора игроком А максиминной стратегии в качестве эффективной называется максиминным принципом. Если игрок А придерживается максиминного принципа выбора стратегий, то ему при любой игре противника В гарантирован выигрыш в читсых стратегиях, не меньший максимина α
показателем неэффективности стратегий Вj назовем максимальный проигрыш игрока В при этой стратегии: Вj=max aij , j=1,2..n, 1≤i≤m.
Минимаксом, или верхней ценой игры в чистых стратегиях, называется наименьший из показателей неэффективности стратегий Вj, j=1,2..n: β=min βj = minmax aij 1≤j≤n 1≤i≤m
Стратегия Вl, показатель неэффективности которой совпадает с минимаксом βl = β, называется минимаксной стратегией игрока В. Множество всех (чистых) минимаксных стратегий игрока В обозначим через (Sвc ) min max . принцип выбора игроком В минимаксной стратегии в качестве эффективной называется минимаксным принципом. Если игрок В придерживается минимаксного принципа выбора стратегий, то он при любой игре противника А не может проиграть больше минимакса β.
8. Теорема Дж. фон Неймана. (25 баллов) и, что тоже самое
44. Теорема о существовании решения игры в смешанных стратегиях. (22 балла)
Любая матричная игра имеет решение в смешанных стратегиях, т. е. существует цена игры в смешанных стратегиях V и оптимальные смешанные стратегии P0 и Q0 соответственно игроков A и B.
Иными словами:
45. Игра с седловой точкой. (28 баллов)
Ситуация (сложившаяся в результате выбора игроками А и В соответственно стратегий иназывается
равновесной, или ситуацией равновесия, или устойчивой, или седловой, точкой игры, если она удовлетворительна для каждого из игроков А и В, т.е. если выполняются неравенства:
или равенства:
Пара чистых стратегий Ai0 и Bj0 дает оптимальное решение игры тогда и только тогда, когда соответствующий ей элемент ai0j0 минимален в строке i0 и максимален в столбце j0. Выигрыш αi0j0, соответствующий ситуации равновесия , называют седловой точкой матрицы игры. Таким образом, игра, матрица которой содержит хотя бы один такой элемент, называется игрой с седловой точкой.
46. Алгоритм нахождения удовлетворительных ситуаций для игрока А в матричной игре. (22 балла)
Исходя из теоремы: Ситуация {Ai0; Bj0} будет удовлетворительной для игрока А тогда и только тогда (), когда ее выигрыш в этой ситуации αi0j0 = βjo, где βjo – показатель неэф. в j0 столбце.
Поэтому алгоритм нахождения удовлетворительной ситуации для игрока А:
Причем количество удовлетворительных ситуаций для А больше числа столбцов, но меньше общего числа элементов (n ≤ NAудовл≤ mn)
47.Определения нижней и верхней цен игры в смешанных стратегиях и их существование.
Нижней ценой (или максимином) матричной игры в смешанных стратегиях называется величина
Верхней ценой (или минимаксом) матричной игры в смешанных стратегиях называется величина
Докажем существование нижней и верхней цен в смешанных стратегиях, т.е. достижимость максимума в (1) и минимума в (2). Необходимость этого доказательства возникает по причине бесконечности множеств SA в (1) и SB в (2).
Сначала докажем вспомогательные предложения.
Лемма 1. Соответствие, сопоставляющее каждой смешанной стратегии Р SA игрока А показатель ее эффективности α(Р), является числовой функцией, определенной на симплексе SA, аналитическое выражение которой задается равенством
Аналогично, соответствие β(Q), задаваемое формулой
является числовой функцией, определенной на симплексе SB и ставящей в соответствие каждой смешанной стратегии Q SB игрока В показатель ее неэффективности β(Q).
Доказательство. Для каждой смешанной стратегии PSA в силу теоремы 1 - для каждой смешанной (в частности, чистой) стратегии Р SA игрока А существует (достигается)
для каждой смешанной (в частности, чистой) стратегии QSB игрока В существует (достигается)
существует число
которое по определению минимума является единственным. Следовательно, α(Р) - числовая функция векторного аргумента Р, определенная на симплексе SA.
Аналогичной аргументацией обосновывается, что
является числовой функцией векторного аргумента Q, определенного на симплексе SB.
Лемма 2. Функции α(Р) и β(Q) непрерывны в своих областях определения SA и SB.
Оставим без доказательства.
Теперь докажем следующую теорему.
Теорема 2. Для любой конечной матричной игры существуют нижняя и верхняя цены игры в смешанных стратегиях.
Доказательство. Так как функция α(Р) по лемме 2 непрерывна на компакте SA, то она достигает на этом множестве своего максимума, т.е. существует нижняя цена игры в смешанных стратегиях:
Аналогичным образом обосновывается существование и верхней цены игры в смешанных стратегиях:
Смешанная стратегия PОSA, максимизирующая показатель эффективности α(Р) (существование которой доказано в теореме 2), назовем максиминной смешанной стратегией игрока А. Таким образом, нижняя цена игрыесть (см. 1) показатель эффективности максиминной смешанной стратегии PО:
В частном случае PО =является максиминной чистой стратегией игрока A.
Аналогично, смешанная стратегия QО SB (существование которой доказано в теореме 2), минимизирующая показатель неэффективности β(Q), назовем минимаксной смешанной стратегией игрока В. Показатель неэффективности минимаксной смешанной стратегии QО равен верхней цене игры (см. 2)):
Если QО =тоявляется минимаксной чистой стратегией.
48.Алгоритм нахождения удовлетворительных ситуаций для игрока В в матричной игре.
Ситуация (Ai0, Bj0) будет удовлетворительной для игрока B тогда, и только тогда, когда его проигрыш ai0j0 совпадет с показателем эффективности αi0 стратегии Ai0 игрока A: ai0j0= αi0 , т.е. будет минимальным в i0-й строке матрицы игры.
Алгоритм нахождения удовлетворительной ситуации для игрока В:
Число удовлетворительных для игрока В ситуаций не меньше m и не больше mn.
Аналогично для игрока А.
49. Нахождение равновесной ситуации игры через удовлетворительные ситуации для игроков А и В.
Имеем mxn-игру, игроки A и B обладают множествами чистых стратегий ScA ={A1…Am} ScB ={B1…Bn}. Ситуация (Ai0, Bj0) называется удовлетворительной для игрока А, если aij0 ≤ ai0j0, i=1…m. И для игрока B: ai0j≥ai0j0, j=1…n
Ситуация (Ai0, Bj0) будет удовлетворительной для игрока A тогда и только тогда, когда его выигрыш ai0j0 совпадет с показателем неэффективности βj0 стратегии Bj0 игрока B (ai0j0= βj0) , т.е. будет максимальным в j0-м столбце матрицы игры
Ситуация (Ai0, Bj0) будет удовлетворительной для игрока B тогда и только тогда, когда его проигрыш ai0j0 совпадет с показателем эффективности αi0 стратегии Ai0 игрока A (ai0j0= αi0) , т.е. будет минимальным в i0-й строке матрицы игры
Нахождение удовлетворительных ситуаций для игрока А:
В каждом столбце матрицы находим наибольший элемент, а затем строку, в которой находится этот элемент. (Ai0, Bj0) – удовлетворительная ситуация
Нахождение удовлетворительных ситуаций для игрока B:
В каждой строке матрицы находим наименьший элемент, а затем столбец, в котором находится этот элемент. (Ai0, Bj0) – удовлетворительная ситуация
Ситуация (Ai0, Bj0) называется равновесной, если она удовлетворительна для каждого из игроков A и B, т.е. если выполняется неравенство aij0 ≤ ai0j0≤ ai0j или равенство αi0 = ai0j0 = βj0
50. Конфликтная ситуация: определение, её составляющие. Привести экономический пример конфликтной ситуации. (20 баллов)
Конфликтная ситуация – это столкновение интересов не менее 2-х сторон, каждой из которых имеет возможность для достижения своей цели действовать различными способами, в зависимости от действий противоборствующей стороны.
Конфликтная ситуация характеризуется следующими чертами:
Математическая модель конфликтной ситуации называется игрой.
Заинтересованные стороны в игре называются – игроками.
В некоторых играх по различным причинам создаются объединения игроков – коалиция.
1. По причинам образования:
2. По временному фактору:
Правила игры – система условий с целью формализации (запись на математическом языке):
В условиях конфликта каждый из игроков делает определённый ход, т.е. играет стратегиями.
В результате образуется набор ситуаций, называемый исходом игры.
Запрещённые ситуации – недопустимые ситуации.
Пример. «Борьба за рынки». Небольшая фирма (игрок А) намерена сбыть партию товара на одном из двух рынков, контролируемое другой, более крупной фирмой (игрок В) Для этого фирма А готова предпринять но одном из рынков соответствующие приготовления (например, развернуть рекламную компанию). Господствующая на рынках фирма В может пытаться воспрепятствовать этому, приняв на одном из рынков предупредительные меры (разумеется, в рамках закона). Не встречая противодействия на рынке, фирма А захватывает его; при наличии препятствий — терпит поражение.
Будем считать для определенности, что проникновение фирмы А на первый рынок более выгодно для нее, нежели проникновение на второй. Естественно также считать, что и борьба за первый рынок потребует вложения больших средств. Например, победа фирмы А на первом рынке принесет ей вдвое больший выигрыш, чем победа на втором, но зато и поражение при попытке освоиться на первом рынке полностью ее разорит, а фирму В избавит от конкурента.
Что же касается второго рынка, то при поражении фирмы А ее потери будут не столь разорительны, но и победа принесет немного.
Таким образом, у фирмы А два стратегии:
А1 — выбор первого рынка, А2 — выбор второго рынка.
Такие же стратегии и у фирмы В:
В1 — выбор первого рынка, В2 — выбор второго рынка.
Для того, чтобы составить платежные матрицы игроков, нужны расчетные количественные показатели, которые мы приведем здесь в условных единицах:
,
Взглянем на выписанные матрицы выплат. Из сказанного выше ясно, что если оба игрока выберут один и тот же рынок, то победа останется за более сильной фирмой В.
То, что в ситуации (А1, В1) выигрыш игрока В равен 5, а в ситуации (А2, В2) — 1, подчеркивает, что первый рынок более выгоден (удобно расположен, хорошо посещаем и т.п.), чем второй. Выигрыш (-10) игрока А в ситуации (А1, В1) (а точнее, проигрыш) в сопоставлении с его выигрышем (-1) в ситуации (А2, В2) выглядит, разумеется, вполне сокрушительно. Что же касается ситуации, когда фирмы уделяют основное внимание разным рынкам (А1, В2) и (А2, В1), то здесь фирму А ждет настоящий выигрыш, больший на более выгодном рынке. Потери, которые при этом несет фирма В, оказываются прямо противоположными.
51. Основные понятия и определения теории антагонистических игр
Антагонистическая игра - модель конфликтной ситуации в игре двух участников с прямо противоположными интересами: игра, моделирующая экономическую ситуацию противостояния, противоборства, конкуренции двух сторон с взаимно противоположными интересами.
Антагонистические игры (далее А. и.) — игры, в которых участвуют два игрока (обычно обозначаемые I и II) с противоположными интересами. Для А. и. характерно, что выигрыш одного игрока равен проигрышу другого и наоборот, поэтому совместные действия игроков, их переговоры и соглашения лишены смысла. Большинство азартных и спортивных игр с двумя участниками (командами) можно рассматривать как А. и. Принятие решений в условиях неопределённости, в том числе принятие статистических решений, также можно интерпретировать как А. и. Определяются А. и. заданием множеств стратегий игроков и выигрышей игрока I в каждой ситуации, состоящей в выборе игроками своих стратегий. Таким образом, формально А. и. есть тройка ‹А, В, Н›, в которой А иВ — множества стратегий игроков, а Н (а, b) — вещественная функция (функция выигрыша) от пар (а, b), где а Î A, b Î В. Игрок I, выбирая а, стремится максимизировать Н(а, b),а игрок II, выбирая b, — минимизировать Н (а, b). А. и. с конечными множествами стратегий игроков называются матричными играми.
Основой целесообразного поведения игроков в А. и. считается принцип минимакса. Следуя ему, I гарантирует себе выигрыш
точно так же II может не дать I больше, чем
Если эти "минимаксы" равны, то их общее значение называется значением игры, а стратегии, на которых достигаются внешние экстремумы, — оптимальными стратегиями игроков. Если "минимаксы" различны, то игрокам следует применять смешанные стратегии, т. е. выбирать свои первоначальные ("чистые") стратегии случайным образом с определёнными вероятностями. В этом случае значение функции выигрыша становится случайной величиной, а её математическое ожидание принимается за выигрыш игрока I (соответственно, за проигрыш II). В играх против природы оптимальную смешанную стратегию природы можно принимать как наименее благоприятное априорное распределение вероятностей её состояний. В А. и. игроки, используя свои оптимальные стратегии, ожидают получения (например, в среднем, если игра повторяется многократно) вполне определённых выигрышей. На этом основан рекуррентный подход к динамическим играм в тех случаях, когда они сводятся к последовательностям А. и., решения которых можно найти непосредственно (например, если эти А. и. являются матричными). А. и. составляют класс игр, в которых принципиальные основы поведения игроков достаточно ясны. Поэтому всякий анализ более общих игр при помощи А. и. полезен для теории.
52. Биматричная игра: сущность, привести экономический пример.
Биматричная игра - конечная бескоалиционная игра двух лиц. Биматричная игра задается двумя матрицами одинакового размера , являющимися матрицами выигрышей соответственно игроков I и II. Стратегией игрока I является выбор строки матриц, стратегией игрока II - выбор столбца. Если игрок I выбирает , а игрок II выбирает , то они получают соответственно выигрыши и , Если для всех то биматричная игра является матричной игрой.
Пример: «Борьба за рынки». Небольшая фирма (игрок А) намерена сбыть партию товара на одном из двух рынков, контролируемое другой, более крупной фирмой (игрок В) Для этого фирма А готова предпринять но одном из рынков соответствующие приготовления (например, развернуть рекламную компанию). Господствующая на рынках фирма В может пытаться воспрепятствовать этому, приняв на одном из рынков предупредительные меры (разумеется, в рамках закона). Не встречая противодействия на рынке, фирма А захватывает его; при наличии препятствий — терпит поражение.
Будем считать для определенности, что проникновение фирмы А на первый рынок более выгодно для нее, нежели проникновение на второй. Естественно также считать, что и борьба за первый рынок потребует вложения больших средств. Например, победа фирмы А на первом рынке принесет ей вдвое больший выигрыш, чем победа на втором, но зато и поражение при попытке освоиться на первом рынке полностью ее разорит, а фирму В избавит от конкурента.
Что же касается второго рынка, то при поражении фирмы А ее потери будут не столь разорительны, но и победа принесет немного.
Таким образом, у фирмы А два стратегии:
А1 — выбор первого рынка, А2 — выбор второго рынка.
Такие же стратегии и у фирмы В:
В1 — выбор первого рынка, В2 — выбор второго рынка.
Для того, чтобы составить платежные матрицы игроков, нужны расчетные количественные показатели, которые мы приведем здесь в условных единицах:
,
Взглянем на выписанные матрицы выплат. Из сказанного выше ясно, что если оба игрока выберут один и тот же рынок, то победа останется за более сильной фирмой В.
То, что в ситуации (А1, В1) выигрыш игрока В равен 5, а в ситуации (А2, В2) — 1, подчеркивает, что первый рынок более выгоден (удобно расположен, хорошо посещаем и т.п.), чем второй. Выигрыш (-10) игрока А в ситуации (А1, В1) (а точнее, проигрыш) в сопоставлении с его выигрышем (-1) в ситуации (А2, В2) выглядит, разумеется, вполне сокрушительно. Что же касается ситуации, когда фирмы уделяют основное внимание разным рынкам (А1, В2) и (А2, В1), то здесь фирму А ждет настоящий выигрыш, больший на более выгодном рынке. Потери, которые при этом несет фирма В, оказываются прямо противоположными.
53. Критерий существования седловых точек действительной функции двух векторных аргументов
Для того, чтобы f(x,y) имела седловую точку(оптимальное решение игры) на декартовом произведении X*Y, необходимо и достаточно, чтобы существовали и были равны , где – это точная нижняя граница множества значений функции (т.е. наибольшая из бесконечного множества нижних границ множества значений функции ), а – это точная верхняя граница множества значений функции (т.е. наименьшая из бесконечного множества верхних границ множества значений функции ).
54. Теорема о сведении решения пары взаимно двойственных задач линейного программирования к решению симметричной матричной игры.
Рассмотрим пару двойственных друг другу задач линейного программирования:
1) найти min при ограничениях , i=1,…,m, , j=1,…,n
2) найти max при ограничениях , j=1,…,n, , i=1,…,m
теорема: если и - опт. стратегии, соотв-но, игроко А и В, а V-цена игры, то
- опт. решение задачи 1,
- опт. решение задачи 2.
55. Выигрыш-функции игроков в антагонистической игре: области определения, области значений.
Степень удовлетворения интересов игрока А характеризуется функцией выигрыша игрока А, определенной на мн-ве Х= всех ситуаций и ставящей в соответствие каждой ситуации x X некоторое число FA (x) R, называемое выигрышем игрока А. (т.е. обл. определения это Х, обл. значения- R- мн-во действ. чисел).
Аналогично, для игрока В функция выигрыша FB:Y R определена на мн-ве Y=ситуаций y=(Bj,Ai) и каждой из них ставит в соответствие число FB(y) R, называемое выигрышем игрока В. (т.е. обл. определения это Y, обл. значения- R-мн-во действ. чисел).
В антагонистической игре выполняется: FA(x)=-FB(y).
56.=45
57. Определение выигрыш-функции в смешанных стратегиях: координатные и векторно-матричные формулы ее представления. (26 баллов) (=14)
58. Редуцирование игр, привести пример. (24 балла) (=81)
59. Понятие седловых точек действительной функции двух векторных аргументов. (20 баллов) (=95)
60. Показателем неэффективности стратегии Ai по критерию Байеса относительно рисков является средний риск:
этот показатель является взвешенным средним рисков i-й строки матрицы рисков с весами qj, j = 1,…, n.
Оптимальной среди чистых стратегий по критерию Байеса относительно рисков является стратегия Ai0 , показатель неэффективности которой минимален, то есть минимален средний риск.
В качестве показателя неэффективности смешанной стратегии по критерию Байеса относительно рисков.
Оптимальной среди всех смешанных (в том числе и чистых) стратегий по критерию Байеса относительно рисков будем считать стратегию Р0, показатель неэффективности которой минимален.
61. Теорема. (Критерии оптимальных стратегий).
Пусть V-цена игры, H(P,Q) – выигрыш-функция, SA и SB – множества смешанных стратегий соответственно игроков А и В.
1. Для того чтобы стратегия РО игрока А была оптимальной, необходимо и достаточно, чтобы выполнялось неравенство:
H(PО,Q)≥V
Для любого Q ϵ SB , т.е. выбор игроком А оптимальной стратегии РО гарантирует ему выигрыш H(PО,Q), не меньший цены игры V, при любой стратегии Q игрока В.
2. Для того чтобы стратегия QO игрока В была оптимальной, необходимо и достаточно, чтобы выполнялось неравенство
H(PО,Q)≤V
Для любого Р ϵ SА , т.е. выбор игроком В оптимальной стратегии QО гарантирует ему проигрыш H(P,QО), не больший цены игры V, при любой стратегии Р игрока А.
Данная теорема остаётся справедливой, если в её формулировке множество смешанных стратегий SA и SB заменить соответственно на множество чистых стратегий SСA и SСB.
Доказательство:
Утверждение 1:
Необходимость:
Пусть Р0 – оптимальная стратегия игрока А. тогда по теореме фон Неймана показатель эффективности стратегии Р0 равен цене игры V:
(1)
Рассматривая как показатель эффективности стратегии Р0 относительно множества SB смешанных стратегий игрока В, будем иметь по определению:
(2)
Из равенств (1) и (2) получаем неравенство H(PО,Q)≥V
Достаточность:
Пусть для некоторой стратегии Р0 игрока А выполняется неравенство H(PО,Q)≥V. Для доказательство оптимальности стратегии Р0 достаточность показать справедливость равенства
Так как неравенство выполняется для любой стратегии игрока В, то
(3)
Но цена игры V равна нижней цене игры V, по определению которой
(4)
Совокупность (3) и (4) эквивалентна равенству . Достаточность доказана
Утверждение 2:
АНАЛОГИЧНЫЕ РАССЖУДЕНИЯ.
62.Для того, чтобы существовала цена игры в чистых стратегиях, то есть для того, чтобы нижняя цена игры равнялась верхней цене игры необходимо и достаточно, чтобы у матрицы существовала седловая точка.
Седловая точка, это ситуация, при которой удовлетворяются интересы каждого из игроков А и В, то есть если выполняются неравенства или , где - нижняя цена игры(), а - верхняя цена игры(). Таким образом элемент является минимальным в -ой строке и максимальным в -ом столбце. При этом оптимальными чистыми стратегиями для игроков А и В будут стратегии обеспечивающие выигрыш игроку А и проигрыш игроку В.
63. Пусть имеем – игру с матрицей выигрышей А игрока А. Ситуация (Ak, Bl), сложившаяся в результате выбора игроками А и В соответственно стратегий Ak и Bl, , , называется удовлетворительной для игрока А, если
ilkl, i=1,2,…,m
Ситуация (Ak, Bl) будет удовлетворительной для игрока А тогда, и только тогда, когда его выигрыш kl совпадает с показателем неэффективности l стратегии Bl игрока В:
kl = l
т.е. будет максимальной в l-м столбце матрицы А.
64. Критерий Байеса относительно рисков при равновероятных состояниях природы, q1=…=qn=1/n, превращается в критерий Лапласа относительно рисков. Тогда величина ij, получающаяся из i = q1ri1 + q2ri2 + …+qnrin = jrij , i=1,…,m при qj=1/n, j=1,2,…n, или более простая величина ij представляет собой показатель неэффективности стратегии Аi по критерию Лапласа относительно рисков. Следовательно, оптимальной среди чистых стратегий по критерию Лапласа относительно рисков является стратегия Aij , показатель неэффективности ioj который минимален.
Подставляя в (P) = jr(P,Пj) значения qj=1/n, j=1,…, n, получим показатель неэффективности смешанной стратегии Р по критерию Лапласа относительно рисков, вместо которого можно рассматривать более простую величину (P) = (P,Пj). Стратегия Р, для которой показатель (P) принимает минимальное значение, является оптимальной среди всех стратегий множества SA.
65.=39
66. Решение игры в смешанных стратегиях.
Если нижняя V и верхняя цены игры в смешанных стратегиях совпадают, то их общее значение V — V = называется ценой игры в смешанных стратегиях. Нижняя и верхняя цены игры в чистых стратегиях и и цена игры в смешанных стратегиях V связаны между собой неравенствами < V< .
Стратегии P° и Q° соответственно игроков А и В, удовлетворяющие равенствам V — а(Р°) = (Q°) (и тогда это общее значение очевидно равно Н(Р°, Q°)), называются оптимальными смешанными стратегиями соответственно игроков A и В.
Таким образом, оптимальные смешанные (в частности, чистые) стратегии Р° и Q0 соответственно игроков А и В обладают тем свойством, что если один из игроков придерживается своей оптимальной стратегии, то противнику невыгодно отклоняться от своей оптимальной стратегии.
Множества оптимальных смешанных стратегий соответственно игроков А и В обозначим через (SA)° и (SB)°.
Полным решением игры в смешанных стратегиях называется трехэлементная совокупность {( SA)°,(SB)°, V}. Любая пара оптимальных стратегий Р° и Q0 соответственно игроков А и В и цена игры в смешанных стратегиях V образуют частное решение в смешанных стратегиях.
Теорема 1. (Основная теорема матричных игр Дж. фон Неймана.) Любая матричная игра имеет решение в смешанных стратегиях, т.е. существуют цена игры в смешанных стратегиях V и оптимальные смешанные стратегии Р° и Q0 соответственно игроков А и В, т.е.
V = V = max (Р)= = min(Q) = (Р°) = (Q°) = Н(Р°, Q°).
Теорема 2. (Свойство равнозначности седловых точек.) Если (х', у') и (х", у") — седловые точки функции f (x, у) на декартовом произведении Х x Y, то значения данной функции в этих точках совпадают: f (x', у') = f (x",y").
Теорема 3. (Свойство взаимозаменяемости седловых точек.) Если (х', у') и (х", у") — седловые точки функции f(x, у) на декартовом произведении Х x Y, то (х', у") и (х", у') — также седловые точки функции/ (х, у) на множестве X x Y.
Теорема 4. (Критерий существования седловой точки.) Для того чтобы функция f (х, у), х X, у Y, имела седловую точку на декартовом произведении X x Y, необходимо и достаточно, чтобы существовали
max inf f(x,у) и min sup f(x,у)
и выполнялось их равенство
max inf f(x,у) = min sup f(x,у)
Теорема 5. Если множества X Rm и Y Rn — выпуклые компакты, а функция f(x, у) непрерывна по совокупности переменных (х, у) X x Y u вогнуто-выпукла (выпукло-вогнута) на X x У, то у нее на декартовом произведении X x Y существуют седловые точки.
67. Определение и существование показателя эффективности смешанной стратегии игрока А относительно множеств смешанных и чистых стратегий игрока В.
Теорема 1. Для каждой смешанной (в частности, чистой) стратегии Р е SA игрока А существует (достигается)
a(P;SB) = min H(P,Q).
Для каждой смешанной (в частности, чистой) стратегии Q SB игрока В существует (достигается)
(Q;SA) = max H(P,Q).
Число а(Р; SB) называется показателем эффективности смешанной стратегии Р SA игрока А относительно множества SB смешанных стратегий игрока В.
Число а(Р; ) = min Н(Р, Q) = minH(P, Вj)
называется показателем эффективности смешанной стратегии Р SA игрока А относительно множества чистых стратегий игрока В. В частности, если Р = Аi — чистая стратегия, то а(; ) = — показатель эффективности чистой стратегии (относительно множества чистых стратегий игрока В).
Теорема 2 (НЕ НУЖНО). Показатели эффективности любой смешанной (в частности, чистой) стратегии Р SA игрока А относительно множесте и SB соответственно чистых и смешанных стратегий противника В равны:
а(Р; )= а(Р;)
68. Показатели эффективности и неэффективности чистых стратегий игроков.
Рассмотрим матричную [m х n] - игру с игроками А и В, задаваемую матрицей выигрышей A.
Показателем эффективности стратегии Ai назовем минимальный выигрыш при этой стратегии (т.е. минимальный элемент i-й строки матрицы A):
Максимином, или нижней ценой игры в чистых стратегиях, называется наибольший из показателей эффективности стратегий Аi, i = 1, 2,..., т,
Стратегия Ak , показатель эффективности которой совпадает с максимином ак = а, называется максиминной стратегией игрока А. Множество всех (чистых) максиминных стратегий игрока А обозначим через . Принцип выбора игроком А максиминной стратегии в качестве эффективной называется максиминным принципом. Если игрок А придерживается максиминного принципа выбора стратегий, то ему при любой игре противника В гарантирован выигрыш в чистых стратегиях, не меньший максимина а.
Показателем неэффективности стратегии Bj назовем максимальный проигрыш игрока В при этой стратегии (т.е. максимальный элемент j-го столбца матрицы А):
Минимаксом, или верхней ценой игры в чистых стратегиях, называется наименьший из показателей неэффективности стратегий Bj , j = 1,2,..., п:
Стратегия , показатель неэффективности которой совпадает с минимаксом , называется минимаксной стратегией игрока В. Множество всех (чистых) минимаксных стратегий игрока В обозначим через . Принцип выбора игроком В минимакснои стратегии в качестве эффективной называется минимаксным принципом. Если игрок В придерживается минимаксного принципа выбора стратегий, то он при любой игре противника А не может проиграть больше мини- макса .
69=13.