Размещено на http://www.allbest.ru/

1. Задачи принятия решения. Методы оптимальных решений

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

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

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

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

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

2. Конфликтная ситуация: определение, характерные признаки, экономический пример. Классификация игр

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

1) наличие заинтересованных сторон (в качестве которых могут выступать потребители, фирмы, отдельные страны, различные таможенные, торговые, финансовые и экономические союзы, индивидуумы и т.д.)

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

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

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

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

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

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

3. Задачи теории игр в экономике, финансах и бизнесе

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

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

Виды неопределенности:

*неопределенные осознанные действия противоборствующих сторон, направленные на уменьшение эффективности принимаемых противником решений

*неопределенность в ситуации риска, когда принимающая решение сторона может определить результаты всех решений и вероятности их появления

*полная неопределенность (известны последствия решений, но не их вероятности)

*неопределенность цели решаемой задачи (показатель эффективности решения не всегда отражает полную картину)

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

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

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



4. Основные понятия и определения теории антагонистических игр

Антагонистическая игра -- матричная игра, в которой участвуют два игрока, множество стратегий каждого из игроков конечно, а выигрыш одного игрока равен проигрышу другого.

Условия построения игровой модели:

1. Существует две противоборствующие стороны (игрок А и В)

2. У каждого своя цель борьбы

3. Их цели противоположны (цель А - max прибыль, цель В - min прибыль А)

4. Каждая сторона им конечное множество применяемых действий

5. Действия должны быть допустимы (с т. зр. морали, законов и т.д.)

6. Действия и результат одного игрока зависят от действий другого

Суть игры - каждый из участников принимает такие решения (т.е. выбирает стратегию действий), которая, по его мнению, обеспечат max выигрыш или min проигрыш (в условиях неопределенности). Эти решения отражаются в таблице «матрица игры» или «платежная матрица».

Задача игры - найти некое равновесие (компромисс), устраивающее всех игроков при прочих равных условиях.

Точка, в которой достигается подобное равновесие, называется седловой.

Выигрыш - результат игры для ее игрока в денежном или условном числовом выражении.

Пусть S_A^C = {A₁, А₂, …, А_m} и S_В^C = {В₁, В₂, …, В_n} - множества чистых стратегий игроков А и В соответственно в парной антагонистической игре. Чистая стратегия - действие игрока, в котором он определенным образом выбирает какую-либо стратегию.

Стратегия в общем - последовательность ходов, обусловленная действиями игроков.

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

Цена игры - общее значение выигрыша одного игрока и проигрыша другого в «седловой точке».

5. Выигрыш-функция и матрица выигрышей. Чистые стратегии игроков. Соотношение между матрицами выигрышей игроков А и В в парной антагонистической игре с нулевой суммой выигрышей

Выигрыш функция игрока в чистых стратегиях.

Пусть S_A^C = {A₁, А₂, …, А_m} и S_В^C = {В₁, В₂, …, В_n} - множества чистых стратегий игроков А и В соответственно в парной антагонистической игре. При m=1 проблема выбора стратегии игроком A отсутствует. При n = 1 проблема выбора стратегии игроком A тривиальна, поэтому предполагают m?2 и n?2.

Из выигрышей a_ij= F_A(i,j)=F_A(A_i,B_j) игрока А в игровых ситуациях (A_i,B_j), i= 1,2,…,m; j=1,2,…,n, представляющих собой числовые значения его выигрыш-функции F_A, определенной на декартовом произведении S^C_A ЧS^C_B.

Так как игра - антагонистическая, то выигрыш-функции игроков А и B и их матрицы выигрышей связаны между собой следующим образом:

B_ij= F_B(B_jA_i)= - F_A(A_i,B_j)= - a_ij, i= 1,2,…,m; j=1,2,…,n, т.е. B = -A^T.

Выигрыш функция игрока в смешанных стратегиях.

Функция

Определенная на декартовом произведении S_A x S_B множеств смешанных стратегий S_A и S_B соответственно игроков А и В и ставящая в соответствие каждой ситуации в смешанных стратегиях P=(p₁, p₂, …, p_m) игрока А и Q=(q₁, q₂,…, q_n) игрока В средневзвешанный выигрыш игрока А в этой ситуации, определяемый выражением в правой части равенства, называется выигрыш-функцией игрока А в смешанных стратегиях. Сужение выигрыш-функции H на декартово произведение множеств чистых стратегий и совпадает с выигрыш-функцией F в чистых стратегиях, т.е. H(A_i, B_j)=F(A_i, B_j)=a_ij, i=1,2,…,m; j=1,2,…,n. Поэтому совокупность {S_A,S_B,H} множеств смешанных стратегий S_A и S_B игроков А и В и выигрыш-функции игрока А в смешанных стратегиях Н называется смешанным расширением игры { } в чистых стратегиях.

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

H(P,Q)=PAQ^T,

где Р-вектор-строка смешанной стратегии игрока А размера [1*m]; А-матрица выигрышей игрока А в чистых стратегиях размера[m*n]; Q^T- вектор-столбец размера [n*1] смешанной стратегии игрока В.

Чистая стратегия - любое возможное в игре действие игрока.

Полагая, что игрок А обладает m ? 1 стратегиями, обозначим их через А1, А2,…, Аm, а множество этих стратегий через S^C_A, то есть S^C_A= { А1, А2,…, Аm}. Полагая, что игрок В обладает n ? 1 чистыми стратегиями, обозначим их через B1, B2,…Bn, а множество этих стратегий через S^C_B. Таким образом, S^C_B={ B1, B2,…Bn}. Множество всех ситуаций в чистых стратегиях представляет собой декартово произведение S^C_A ЧS^C_B.

В условиях конфликта каждый игрок делает свой ход, т.е. выбирает свою стратегию в результате чего образуется набор х стратегий всех игроков, который называется исходом или ситуацией конфликта. Например, если в парной игре участвуют игроки А и В с множествами стратегий S^C_A и S^C_B

И в результате очередного хода игроки выбрали стратегии Аi & Bj, то упорядоченная пара x=(Ai,Bj) является ситуацией после этого хода.

6. Максиминный и минимаксный принципы игроков. Показатели эффективности и неэффективности чистых стратегий игроков. Максимин и минимакс игры. Максиминные и минимаксные стратегии. Нижняя и верхняя цены игры в чистых стратегиях. Теорема о соотношении между выигрышами игрока А, показателями эффективности и неэффективности стратегий, нижней и верхней ценами игры

Показатель эффективности стратегии Ai - минимальный выигрыш при этой стратегии. Максимином, или нижней ценой игры в чистых стратегиях, называется наибольший из показателей эффективности стратегии Ai, т.е.

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

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

Показателем неэффективности стратегии B_j назовем максимальный проигрыш игрока В при этой стратегии (т.е. максимальный элемент j- го столбца матрицы A):



Минимаксом, или верхней ценой игры в чистых стратегиях, называется наименьший из показателей неэффективности стратегий B_j, j=1,2…, n:

Стратегия B_l, показатель неэффективности которой совпадает с минимаксом , называется минимаксной стратегией игрока B. Множество всех (чистых) минимаксных стратегий игрока В обозначим через . Принцип выбора игроком В минимаксной стратегии в качестве эффективной называется минимаксным принципом. Если игрок В придерживается минимаксного принципа выбора стратегии, то он при любой игре противника А не может проиграть больше минимакса .

Соотношение для б и в

Для элементов матрицы A имеют место неравенства

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

Доказательство. По определению показателей эффективности б_i стратегий A_i игрока А и показателей неэффективности в_j стратегий B_j игрока В имеем: б_i = mina_ij ?a_ij ?maxa_ij =в_j, i=1, 2,..., m j=1, 2,..., n следовательно неравенство 1 доказано.

Так как доказанное неравенство б_i ? в_j справедливо для любых i=1, 2, …, m j=1, 2,..., n, то оно будет справедливо и для номеров i=i₀ и j=j₀ соответственно максиминной и минимаксной стратегий А_i0 и B_jo: б_i0 ? в_j0. Тогда в силу б=б_i0 и в=в_j0 получаем

7. Устойчивые и неустойчивые игровые ситуации. Игровые ситуации, удовлетворительные для игроков. Доказательство критериев об удовлетворительных ситуациях для игроков

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

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

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

Понятие игровой ситуации, удовлетворительной для игрока А: Ситуация (,) (сложившаяся в результате выбора игроками А и B соответственно стратегий и , ? {1,…,m}, ? {1,….,n}) называется удовлетворительной (приемлемой, допустимой) для игрока А, если , i=1,…, m

Понятие: Ситуация (A_k, B_l), сложившаяся в результате выбора игроками А и В соответственно стратегий A_k и B_l, k=1, 2, …,m, l=1,2,…,n, называется удовлетворительной (приемлемой, допустимой) для игрока В, если a_kl ? a_kj, j=1,2,…,n.



8. Равновесная ситуация. Седловая точка выигрыш-функции и седловая точка матрицы игры. Доказательство свойств равнозначности и взаимозаменяемости седловых точек матрицы игры

Ситуация () называется равновесной, или седловой точкой выигрыш-функции игрока A, если она удовлетворительна для каждого из игроков А и В, т.е.

Или эквивалентным образом

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

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

1) Свойство равнозначности - если - седловые точки, то

2) Свойство взаимозаменяемости - если - седловые точки, то и - также седловые точки.

9. Нижняя и верхняя цены игры. Соотношение между ними. Цена игры в чистых стратегиях. Чистые оптимальные стратегии. Полное и частное решения игры в чистых стратегиях. Допустимые (приемлимые) ситуации для игроков. Критерий существования цены игры в чистых стратегиях. Соотношения между множествами оптимальных и максиминных (минимаксных) стратегий. Алгоритм поиска седловых точек

Показатель эффективности стратегии Аi - минимальный выигрыш при этой стратегии: б_i=min a_ij (минимум по j Є[1;n]),

А максимином, или нижней ценой игры в чистых стратегиях называют наибольший из показателей эффективности стратегий Ai: б=max б_i=maxmin a_ij (i от 1 до m, j от 1 до n).

Показатель неэффективности стратегии Bj - максимальный проигрыш при этой стратегии: в_i=max a_ij (минимум по i Є[1;m]),

А минимаксом, или верхней ценой игры в чистых стратегиях, называется наименьший из показателей неэффективности: в=min в_i=minmax a_ij (i от 1 до m, j от 1 до n).

Если нижняя цена игры бравна верхней в, то их общее значение г=б=в называется ценой игры в чистых стратегиях

Оптимальной называется та стратегия, показатель не/эффективности которой равен цене игры. Множество чистых оптимальных стратегий обозначается S_A^C и S_В^C

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

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



10. Смешанные стратегии. Геометрическая интерпретация множества смешанных стратегий

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

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

Множество смешанный стратегий SA геометрически представляет собой фундаментальный (m-1)- мерный симплекс с m вершинами в точках A1,A2…Am, представляющих чистые стратегии.

Р = (р1,р2,…,pm) - выпуклая линейная комбинация. Выпуклая оболочка - наименьшее выпуклое мн-во, которое содержит в себе мн-во S. Фундаментальный симплекс - выпуклая оболочка, натянутая на фундаментальный базис.

m=1 - симплекс размерности 0 с 1 вершиной - точка - A1.

m=2 - одномерный симплекс с 2 вершинами - каждая точка отрезка - смешанная стратегия

При m=3 - треугольник в пространстве - симплекс размерности 2 с 3 верш.

При m=4 - тетраэдр - симплекс размерности 3 с 4 вершинами.

11. Определение выигрыш-функции в смешанных стратегиях; координатные и векторно-матричные формулы ее представления.

Определенная на декартовом произведении S_A x S_B множеств смешанных стратегий S_A и S_B соответственно игроков А и В и ставящая в соответствие каждой ситуации в смешанных стратегиях P=(p₁, p₂, …, p_m) игрока А и Q=(q₁, q₂,…, q_n) игрока В средневзвешанный выигрыш игрока А в этой ситуации, определяемый выражением в правой части равенства, называется выигрыш-функцией игрока А в смешанных стратегиях. Сужение выигрыш-функции H на декартово произведение множеств чистых стратегий и совпадает с выигрыш-функцией F в чистых стратегиях, т.е. H(A_i, B_j)=F(A_i, B_j)=a_ij, i=1,2,…,m; j=1,2,…,n. Поэтому совокупность {S_A,S_B,H} множеств смешанных стратегий S_A и S_B игроков А и В и выигрыш-функции игрока А в смешанных стратегиях Н называется смешанным расширением игры { } в чистых стратегиях.

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

H(P,Q)=PAQ^T,

где Р-вектор-строка смешанной стратегии игрока А размера [1*m]; А-матрица выигрышей игрока А в чистых стратегиях размера[m*n]; Q^T- вектор-столбец размера [n*1] смешанной стратегии игрока В.

12. Определение и существование показателя эффективности смешанной стратегии игрока А относительно множеств смешанных и чистых стратегий игрока В

Определение показателя эффективности смешанной стратегии игрока ?? относительно множества чистых стратегий игрока ??. Теорема о равенстве показателей эффективности смешанной стратегии игрока ?? относительно множеств чистых стратегий игрока ??.

Показатель эффективности смешанной стратегии ??????? игрока ?? относительно множества чистых стратегий игрока ?? - это наименьший выигрыш игрока ?? при данной стратегии ?? и всех чистых стратегиях ????,??=1,...,??, игрока ??: ??(??,??????)=??????1????????(??,????).

Теорема. Показатели эффективности любой смешанной (в частности, чистой) стратегии ??????? игрока ?? относительно множеств чистых и смешанных стратегий противника ?? равны, то есть ??(??,??????)=??(??,????)

Доказательство: Так как S_B , то и, следовательно (2)

Докажем противоположное неравенство. Пусть Р=(р₁,…, р_m) Q. Тогда получим неравенство:

для любых Так кА правая часть неравенства зависит от , то имеем

(3).

Неравенства 2 и 3 доказывают равенство 1.

Определение и существование показателя эффективности смешанной стратегии игрока ?? относительно множества смешанных стратегий игрока ??.

Показатель эффективности смешанной стратегии ??????? игрока ?? относительно множества ???? смешанных стратегий игрока ?? - наименьший выигрыш игрока ?? при данной стратегии ?? и всех смешанных стратегиях ??????? игрока ??: ??(??,????)=???????????????(??,??).

Теорема. Для каждой смешанной (в частности, чистой) стратегии ??????? игрока ?? существует (достигается) ??(??,????)=???????????????(??,??).



13. Определение и существование показателя неэффективности смешанной стратегии игрока В относительно множеств смешанных и чистых стратегий игрока А

Определение и существование показателя неэффективности смешанной стратегии игрока ?? относительно множества смешанных стратегий игрока ??.

Определение. Показателем неэффективности смешанной стратегии ?? игрока ?? относительно множества ???? смешанных стратегий игрока ?? называется число: ??(??,????)=???????????????(??,??), ???????

Теорема. Для любой смешанной (в частности, чистой) стратегии ??????? игрока ?? существует (достигается) показатель ??(??,????).

Определение показателя неэффективности смешанной стратегии игрока ?? относительно множества чистых стратегий игрока ??. Теорема о равенстве показателей неэффективности смешанной стратегии игрока ?? относительно множеств смешанных и чистых стратегий игрока ??.

Определение. Показателем неэффективности смешанной стратегии ?? игрока ?? относительно множества ?????? чистых стратегий игрока ?? называется число: ??(??,??????)=?????????????????(??,??)=??????1????????(????,??), ???????

Теорема. Показатели неэффективности любой смешанной (в частности, чистой) стратегии ??????? игрока ?? относительно множеств ?????? и ???? чистых и смешанных стратегий игрока ??равны, т.е.: ??(??,??????)=??(??,????)

Доказательство. Из включения S_А следует включение то и поэтому .

С другой стороны, если Р=(р₁,…, р_m) Qто будем иметь

Правая часть этого неравенства не зависит от Р и потому: Это неравенство обратно неравенству (1) и потому равенство доказано.

14. Определения нижней и верхней цен игры в смешанных стратегиях и их существование; минимаксные и максиминные смешанные стратегии игроков

Нижней ценой (или максимином) матричной игры в смешанных стратегиях называется величина

Верхней ценой (или минимаксом) матричной игры в смешанных стратегиях называется величина

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

Сначала докажем вспомогательные предложения.

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



Аналогично, соответствие в(Q), задаваемое формулой

является числовой функцией, определенной на симплексе S_B и ставящей в соответствие каждой смешанной стратегии Q S_B игрока В показатель ее неэффективности в(Q).

Доказательство. Для каждой смешанной стратегии PS_A в силу теоремы 1 - для каждой смешанной (в частности, чистой) стратегии Р S_A игрока А существует (достигается)

для каждой смешанной (в частности, чистой) стратегии QS_B игрока В существует (достигается) существует число которое по определению минимума является единственным. Следовательно, б(Р) - числовая функция векторного аргумента Р, определенная на симплексе S_A.

Аналогичной аргументацией обосновывается, что является числовой функцией векторного аргумента Q, определенного на симплексе S_B.

Лемма 2. Функции б(Р) и в(Q) непрерывны в своих областях определения S_A и S_B.

Теорема 2. Для любой конечной матричной игры существуют нижняя и верхняя цены игры в смешанных стратегиях.

Доказательство. Так как функция б(Р) по лемме 2 непрерывна на компакте S_A, то она достигает на этом множестве своего максимума, т.е. существует нижняя цена игры в смешанных стратегиях:

Аналогичным образом обосновывается существование и верхней цены игры в смешанных стратегиях:

Смешанная стратегия P^ОS_A, максимизирующая показатель эффективности б(Р) (существование которой доказано в теореме 2), назовем максиминной смешанной стратегией игрока А. Таким образом, нижняя цена игрыесть (см. 1) показатель эффективности максиминной смешанной стратегии P^О:

В частном случае P^О =А_i0 является максиминной чистой стратегией игрока A.

Аналогично, смешанная стратегия Q^О S_B (существование которой доказано в теореме 2), минимизирующая показатель неэффективности в(Q), назовем минимаксной смешанной стратегией игрока В. Показатель неэффективности минимаксной смешанной стратегии Q^О равен верхней цене игры (см. 2)):

Если Q^О =B_j0, то B_j0является минимаксной чистой стратегией.

Максиминная смешанная стратегия игрока А и минимаксная смешанная стратегия игрока В.

Смешанная стратегия , максимизирующая показатель эффективности называется максиминной смешанной стратегией игрока А. Нижняя цена игры есть показатель эффективности максиминной смешанной стратегии

Смешанная стратегия минимизирующая показатель неэффективности , называется минимаксной смешанной стратегией игрока В. Показатель неэффективности минимаксной смешанной стратегии равен верхней цене игры : .

15.Теорема о соотношении между нижней и верхней ценами игры в смешанных и чистых стратегиях

Теорема. Нижняя цена игры б и верхняя цена игры в в чистых стратегиях, нижняя цена игры и верхняя цена игры в смешанных стратегиях удовлетворяют следующим неравенствам:

Доказательство. Начнем доказательство с левого неравенства (1).

По определению

нижней цены в смешанных стратегиях



Здесь правая часть не зависит от Р и потому это неравенство остается верным и для Р = A_i, i = 1,..., m:

Так как полученное неравенство справедливо для всех i = 1,..., m, то оно будет справедливым в частности для того номера i, который максимизирует показатель эффективности б_i:

Итак, первое из неравенств (1) доказано.

Докажем второе неравенство ?в (1). Для любых Р S_A и Q S_B по

и

Соотношение (2) означает, что в любой ситуации в смешанных стратегиях (Р, Q) выигрыш H(P, Q) игрока A не меньше показателя эффективности б(P) его стратегии Р и не больше показателя неэффективности стратегии Q противника В.

Так как (2) справедливо для любых РS_A и QS_B, то из него следует, что



Докажем последнее (правое) из неравенств (1). В силу определения

верхней цены игры в смешанных стратегиях

В частности, это неравенство справедливо и для чистых стратегий Q = B_j, j = 1,..., п, игрока В

и, следовательно, неравенство остается в силе и для того номера j, который минимизирует показатель неэффективности в(B_j) стратегии В_j, т.е.

Итак, (1) доказано.



16. Понятия выпуклого множества, выпуклой функции и седловых точек действительной функции двух векторных аргументов. Нижняя и верхняя граница числового множества

· Множество называется выпуклым, если вместе с любыми двумя точками множеству K принадлежат все точки отрезка xy, соединяющего в пространстве A точки x и y.

· Числовая функция называется выпуклой на выпуклом множестве X, если для любых точек x',x''? X и произвольного числа t ? [0,1] справедливо равенство f [(1-t)x' + tx''] ? (1-t)f(x')+tf(x'').

· Пусть f(x,y) - Действительная функция двух векторных аргументов x ? X и y ? Y, заданная на декартовом произведении X x Y. Точка (x⁰,y⁰), x⁰ ? X, y⁰ ? Y, называется седловой точкой функции f(x,y) на декартовом произведении X и Y, если f(x,y⁰) ?f(x⁰,y⁰) ?f(x⁰,y) для любых x ? X, y ? Y.

Верхней границей множества Х называется любое число М такое, что для любого х из множества х, х

Нижней границей множества (x) называется любое число M такое, что для любого x из множества (x), x

17. Свойства равнозначности и взаимозаменяемости седловых точек действительной функции двух векторных аргументов

1) Свойство равнозначности седловых точек. Если (x',y') и (x'',y'') - седловые точки функции f(x,y) на декартовом произведении X x Y, то значения данной функции в этих точках совпадают: f(x',y') = f(x'',y'')

Доказательство: Так как (x',y'), (x”,y”) Є X*Y, то и (x',y') Є X*Y. f(x',y')= min(x',y)?f (x',y”)?max f(x,y')=f(x”,y”)

2) Свойство взаимозаменяемости седловых точек. Если (x',y') и (x'',y'') - седловые точки функции f(x,y) на декартовом произведении X x Y, то (x',y'') = f(x'',y') - также седловые точки функции f(x,y) на множестве X x Y.

Доказательство: Из неравенства f(x',y')= f(x',y”)= f(x”,y')= f(x”,y”).

Так как f(x”,y”)- седловая точка, то по левому неравенству при x0=x”,y0=y”, f(x,y”)?(x”,y”) для любого x Є X

Так как f(x',y')- седловая точка, то по правому неравенству при x0=x',y0=y', f(x',y')?f(x',y) для любого y Є Y

Получим: f(x,y”)? f(x”,y”)= f(x',y”)= f(x',y') ? f(x',y), x Є X, y Є Y

18. Критерий существования седловых точек действительной функции двух векторных аргументов

Для того, чтобы f(x,y) имела седловую точку(оптимальное решение игры) на декартовом произведении X*Y, необходимо и достаточно, чтобы существовали и были равны, где - это точная нижняя граница множества значений функции (т.е. наибольшая из бесконечного множества нижних границ множества значений функции), а - это точная верхняя граница множества значений функции (т.е. наименьшая из бесконечного множества верхних границ множества значений функции).

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

1. ;

2. .



19. Теорема о единственности точки экстремума строго вогнутой (выпуклой) на выпуклом множестве функции

Стр. 93. У строго вогнутой на выпуклом множестве функции может быть только одна точка максимума. У строго выпуклой на вогнутом множестве функции может быть только одна точка минимума.

20. Теорема о достаточных условиях существования седловых точек у непрерывной вогнуто-выпуклой на декартовом произведении выпуклых компактов функции

Стр. 98. Если множества X ? R^m и Y ? Rⁿ - выпуклые множества, а функция f(x,y) непрерывна по совокупности переменных x,y ? X x Y и вогнуто-выпукла на X x Y, то у неё на декартовом произведении X x Y существуют седловые точки.

21. Цена игры в смешанных стратегиях. Оптимальные смешанные стратегии. Полное и частное решения игры в смешанных стратегиях. Основная теорема теории игр Дж. фон Неймана и её доказательство

Если нижняя и верхняя цены игры в смешанных стратегиях совпадают, то их общее значение называется ценой игры в смешанных стратегиях, а стратегии P⁰ и Q⁰, для которых выполняются равенства V= (P⁰)= (Q⁰) (и тогда это общее значение равно H (P⁰, Q⁰)), называются оптимальными смешанными стратегиями соответственно игроков А и В. Оптимальные смешанные стратегии P⁰ и Q⁰ (которые могут быть и чистыми) обладают тем свойством, что если один из игроков придерживается своей оптимальной стратегии, то противнику невыгодно отклоняться от своей оптимальной стратегии. V т.е. цена игры в смешанных стратегиях V не меньше нижней цены игры в чистых стратегиях б и не больше верхней цены игры в чистых стратегиях в. Обозначим через и множества оптимальных стратегий игроков А и В. Очевидно, что множество оптимальных стратегий каждого из игроков является подмножеством множества его смешанных стратегий: и . Полным решением игры в смешанных стратегиях называется совокупность { }множеств оптимальных стратегий игроков и цены игры. Любая пара оптимальных стратегий P⁰ и Q⁰ и цены игры V образуют частное решение в смешанных стратегиях.

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

В, т.е.

• Доказательство: Множества S_A и S_B - выпуклые компакты, представленные симплексами .

Функция выигрыша непрерывна и выпукло-вогнута на , т.к. линейна по

Тогда у H(P,Q) существует седловая точка

или в терминах показателей эффективности и неэффективности:



.

По критерию существования седловой точки функции существуют

)

По теореме 2.1 и с учетом определений точной верхней и нижней границы множества:

Тогда (3.3) имеет вид:

По определению верхней и нижней цены игры в СС

т.е. существует при чем

но с учетом (3.4) получаем (3.1).



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

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

,

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

Доказательство. Необходимость. Пусть - оптимальная смешанная стратегия игрока А. Тогда

.

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

(3).

Из равенств 2 и 3 получаем неравенство 1 и необходимость доказана.

Достаточность. Пусть для некоторой стратегии игрока А выполняется неравенство (1). Для доказательства оптимальности стратегии достаточно показать справедливость равенства . Так как неравенство (1) выполняется для любой стратегии игрока В, то

.(4)

Но цена игры равна нижней цене игры:

(5)

Совокупность 4 и 5 эквивалентна равенству . Достаточность доказана.

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

Теорема. ПустьV - цена игры,H (P, Q) - функциявыигрыша, S^C_A= { А₁, А₂,…, А_m}и S^C_B={ B₁, B₂,…B_n}- множества чистых стратегий соответственно игроков А и В. Для того чтобы стратегия Р?игрока А была оптимальной необходимо и достаточно, чтобы

H (P?, B_j) ?V, i=1,…,m. (1)

Н(Po,Q)

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

Достаточно установить эквивалентность неравенств (1) и (2). Докажем эту эквиваленцию. (1)- (2)

Пусть справедливо неравенство (1). Так как это неравенство имеет место для любой стратегии игрока В, то оно, в частности, будет справедливым и для его чистых стратегийB_jS^C_{B, j=1,…,n,} т.е. неравенство (2) имеет место. Таким образом, импликация (1)>(2) доказана.

Теперь пусть имеет место неравенство (2). Тогда с учетом того, что 1, получим

Т.е. доказано неравенство (1). Таким образом, справедлива импликация (2) >(1), и следовательно эквиваленция доказана.

24. Геометрическая интерпретация множества оптимальных смешанных стратегий

Множество (S_A)^O оптимальных стратегий игрока А является выпуклым многогранником (политопом), содержащимся в симплексе SA всех смешанных стратегий игрока А.

Множество (S_B)^O оптимальных стратегий игрока В является выпуклым многогранником (политопом), содержащимся в симплексе SB всех смешанных стратегий игрока В.

Политоп-выпуклая оболочка конечного числа точек или многогранные вектора, по длине равные 1 и все попарно перпендикулярные-отогональные орты.

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

m=1 точка. Одномерный симплекс с 1 вершиной

m=2 оси координат

m=3 три перпендик прямые

m=4 тетраэдр

Смешанные стратегии игрока А -фундаментальный симплекс размерности m-1 cm вершинами, каждый из которой изоражает чистую стратегию.

Наименьшее выпуклое мн-во сод. Мн-во S называется выпуклой оболочкой.

25. Критерий цены игры и оптимальных смешанных стратегий в терминах множеств смешанных стратегий игроков

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

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

Теорема. Пусть V - цена игры, Н(Р;Q) - выигрыш-функция, S_a, S_b - множества смешанных стратегий игроков. Для того, чтобы стратегия Q^o игрока В была оптимальной, необходимо и достаточно, чтобы выполнялось неравенство: H(P,Q^o)?V для любого РSa. Док-во: 1) Необходимость. Пусть . Тогда,. 2) Достаточность. Пусть для некоторой стратегии Q^o игрока В справедливо неравенство H(P,Q^o)?V. Поскольку оно выполняется для любого РSa, то оно справедливо и для , т.е. , но . Получаем, что , следовательно стратегия оптимальна. Ч.т.д.

26. Критерий цены игры и оптимальных смешанных стратегий в терминах множеств чистых стратегий игроков

Для того чтобы V было ценой игры, а и оптимальными стратегиями игроков А и В в терминах множеств чистых стратегий игроков A и В, необходимо и достаточно выполнение двойного неравенства , где - чистые стратегии игроков А и В.

27. Критерий цены игры и оптимальных смешанных стратегий в терминах выигрыш-функции и ее седловых точек

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

Док-во: Необходимость. Пусть V - цена игры и и оптимальные стратегии. Следовательно, по теореме о критерии решении игры в терминах смешанных стратегий, выполняется для любых и . Тогда имеет место неравенство , , , которое означает, что - седловая точка выигрыш-функции по определению. Так как V - цена игры и и оптимальные стратегии, то равенство выполняется по основной теореме матричных игр фон Неймана. Достаточность. Пусть - седловая точка функции выигрыша и имеет место равенство . По определению седловой точки справедливо , , . Подставив в него , получим неравенство , из которого вытекает, что V - цена игры и и оптимальные стратегии.

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

Множество номеров {1,2,…, m}, для которых p_i >0, называется спектром смешанной стратегии Р=(р₁, р₂,…,р_m) и обозначается

Чистая стратегия А_i называется пассивной или активной относительно смешанной оптимальной стратегии P^O=(р₁^О,…,р_i^O,…,p_m^O) в зависимости от того, i не принадлежит supp P^O или i принадлежит supp P^O, т.е. в зависимости от того, р_i^O=0 или p_i^O>0.

Теорема об активных стратегиях. Пусть V - цена игры, P^O=(р₁^О, р₂^О,…,p_m^O) и Q^O=(q₁^O, q₂^O, …, q_n^O) - оптимальные стратегии соответственно игроков А и В. Тогда справедливы следующие утверждения:

1. Для любой активной стратегии А_k (k ? {1,2,…,m} относительно оптимальной стратегии Р^О игрока А выполняется равенство Н(А_k,Q^O)=V.

2. Для любой активной стратегии В_l (l ? {1,2,…n}) относительно оптимальной стратегии Q^O игрока В выполняется равенство Н(P^O;В_l)=V.

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

Определение смеси активных стратегий игрока А

Пусть - смешанная оптимальная стратегия игрока А, I - произвольное непустое подмножество множества supp = - активная стратегия} номеров активных стратегий игрока А относительно данной смешанной стратегии .

29. Принцип доминирования стратегий. Теорема и следствия о доминируемых стратегиях

Если выпуклые комбинации для двух столбцов матрицы А

то (5.4) доминирует (5.5), или (5.5) доминируется (5.4);

если в (5.6) все неравенства есть равенства, то (5.4) и (5.5) - дублирующие;

если в (5.3) все неравенства строгие, то (5.4) строго доминирует (5.5), или (5.5) строго доминируется (5.4).

Теорема:

1.Если k-я строка матрицы А доминируется некоторой выпуклой комбинацией остальных ее строк, то в которой k-я чс является пассивной.

2.Если k-я строка матрицы А строго доминируется некоторой выпуклой комбинацией остальных ее строк, то k-я чс является пассивной.

3. Если l-ый столбец матрицы А доминируется некоторой выпуклой комбинацией остальных ее столбцов, то в которой l-я чс является пассивной.

4.Если l-ый столбец матрицы А строго доминируется некоторой выпуклой комбинацией остальных его столбцов, то l- я чс является пассивной.

Следствие1:

1.Если k-я строка матрицы А доминируется другой строкой, то существует ОСС игрока А, в которой чс A_k является пассивной.

2.Если k-я строка матрицы А строго доминируется другой строкой, то относительно любой ОСС игрока А чс A_k является пассивной.

3.Если l-ый столбец матрицы А доминируется другим столбцом, то существует ОСС игрока В, в которой чс B_l является пассивной.

4.Если l-ый столбец матрицы А строго доминируется другим столбцом, то относительно любой ОСС игрока В чс B_l является пассивной.

Следствие2:

Одну из двух дублирующих стратегий из матрицы игры удаляют.

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

Для игры с платежной матрицей А размерности mxn рассмотрим её подматрицу, которая образована k+1 строкой с номерами и l+1 столбцом с номерами , т.е. при том такую, что:



Теорема:

Если обладает свойствами (5.7), (5.8), то справедливы утверждения:

1) если то все элементы единственной строки будут равны между собой;

2) если то все элементы единственного столбца будут равны между собой;

3) Если k=l (т.е. подматрица квадратная), то сумма элементов каждой строки равна сумме элементов каждого столбца.

31. Изоморфное преобразование игры

Изоморфным преобразованием игры называется перенумерация чистых стратегий игрока А и (или) игрока В. Предположим, что каждой чистой стратегии Ai (i = 1, 2,…, m) игрока А мы ставим в соответствие его же чистую стратегию ( € (I = 1, 2,… m), причем так, что разным номерам i соответствуют разные же номера ki (т.е. если i?r, то ki ? kr, i, r € (i = 1, 2, …, m). Не исключена возможность, что для не которых (или для всех) номеров i будет выполняться равенство ki=i. Таким образом, мы получаем взаимно однозначное отображение Ai-> , i=12,..., m, множества чистых стратегий на себя, в результате которого столбец



Это преобразование сводится к перестановке строк матрицы игры, а именно - я строка переставляется на i-е место, i=1,2,…m. Если для некоторого i имеет место равенство ki=i, то это означает, что ki-я строка не переставляется и остается на своем месте. Аналогично для игрока В.

Справедливы следующие утверждения:

1. H'(P',Q') = H(P,Q), P € Sa, Q € Sb

2. a'(P')=a(P), P Sa

3. B'(Q') = B (Q)

4. V = V'

32. Зеркальный изоморфизм игры

Зеркальное изоморфное преобразование игры означает перемену ролей игроков, т.е. если в антагонистической игре с игроками А и В матрицей игры была матрица A выигрышей игрока А, то в результате зеркального изоморфизма матрицей игры становится матрица В выигрышей игрока В. Матрица В =

При таком отображении происходит отображение матрицы A: A>A'= = B. Таким образом, элементы матрицы A отображаются в элементы матрицы В по следующему правилу:



, i = 1, 2, …, m; j = 1, 2, …, n

Справедливы следующие утверждения:

1. H'(P',Q') = - H(P,Q), P € Sa, Q € Sb

2. a'(P')= - B(Q)

3. B'(Q') = - a(P)

4. - V = V'

33. Аффинное преобразование игры

Аффинное преобразование игры представляет собой преобразование матрицы игры А в матрицу A'. При преобразовании вероятности выбора игроками чистых стратегий в смешанных, очевидно, не изменятся, т.е. смешанные стратегии будут преобразовываться тождественным образом:

P = (p1, p2, …, pm) > ( = p1, …, p'm = pm) = P', P €

Q = (q1, q2, …, qn) > ( = q1, …, q'n = qn) = Q', Q €

...