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

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

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

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

Рассмотрим парную игру с иг-ками А и В. Пусть игрок А имеет mстр-ий , а игрок В — nстр-ий . Натуральные числа m и n в общем случае никак не связаны между собой. Если каждый из иг-ов А и В сознательно определенным образом выбирает стр-ии и соответственно, то сложившаяся ситуация (в чистых стр-ях) однозначно определяет выигрыш иг-ка А, выражающийся действительным числом , которое одновременно является и проигрышем иг-ка В. А число выражает проигрыш иг-ка А и выигрыш иг-ка В. Если число отрицательно, то оно будет представлять отрицательный выигрыш иг-ка А, то есть его проигрыш. Числа — это значения ф-ии выигрыша иг-ка A: . Ходы иг-ов с сознательным выбором одной из возможных своих чистых стр-ий называют иногда личными ходами.

Выигрыши , i = 1,..., m, j = 1,...,n, можно расположить в виде мат-цы, номера строк которой соответствуют номерам стр-ийиг-ка А, а номера столбцов — номерам стр-ийиг-ка В. Мат-ца А называется матрицей выигрышей иг-ка A.

Обозначим через значения ф-ии выигрыша иг-ка В, т. е. . Если рассматриваемая игра — антагонистическая (т.е. с нулевой суммой выигрышей), то ф-ии выигрышей и иг-ов А и В связаны между собой рав-вом и, следовательно, Эти рав-ва означают, что мат-ца выигрышей В иг-ка В является противоположной транспонированной матрице A:

 

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

Матричная игра игра с и.А и и.В,задаваемая матр выигр.А.

Показатель эффективности стр. -минимальный выигрыш при этой стратегии (мин.эл-т i-ой строки):

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

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

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

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

Минимаксная стр и.В – стр , пок-тель неэф которой совпадает с минимаксом . Мн-во всех ч.страт и.В - . Принцип выбора минмакс.стр в кач-ве эффект – минимаксный принцип (т.о. при любой игре А не может проиграть ≥ ).

Для нахожд ниж.и верх.цен игры в ч.страт. дополним матр столбцами стр , и стр :

Т 1. Для элементов расширенноймат-цы выигрышей имеют место нерав-ва

и, следовательно, нижняя цена игры не больше ее верхней цены в чистыхстр-ях: α ≤ β. (15)

Док-во. По опр. показателей эфф-ти α_iстр-ий А_iиг-ка А и опр. показателей неэфф-ти β_j стр-ий B_jиг-ка В имеем Т.к. доказанное нерав-во α_i ≤ β_j справедливо ∀ i = 1,..., m, j =1,..., n, то оно будет справедливым в частности для номеров i = i₀ и j = j₀ соответственно максиминной и минимаксной стр-ий.Тогда α ≤ β.Т доказана.

 

 

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

Число β(Q; S_A), определенное рав-вом

назовем Пок-ем неэфф-тисмеш.стр-ии Q S_Bиг-каВ относ.мн-ва S_Aсмеш.стр-ийиг-ка А, а число — Пок-ем неэфф-тисмеш.стр-ии Q иг-ка В относ.мн-ва чистых стр-ийиг-ка А. В частности, если смеш.стр. Q является чистой В_j, то из (2), H (P, Q) = H (А_i, В_j) = a_ij= F(А_i, В_j) = F(P,Q) и

будем иметь Для показателей неэфф-тисмеш.стр-ийиг-ка В имеет место Т: п оказатели неэфф-ти любой смеш. (в частности, чистой) стр-ииQ S_Bиг-ка В относ.мн-тв и S_Aчистых и смеш.стр-ийиг-ка А равны, т.е.

Чтд.

Если нижняя и верхняя цены игры в смешанных стратегиях совпадают, то их общее значение V= = называется ценой игры в смешанных стратегиях. Нижняя и верхняя цены игры в чистых стратегиях α и β и цены игры в смешанных стратегиях V связаны между собой неравенствами α≤V≤β.

Стратегии P^O и Q^O соответственно игроков А и В, удовлетворяющие равенствам V=α(P^O)=β(Q^O) (и тогда это общее значение очевидно равно H(P^O,Q^O)), называется оптимальными смешанными стратегиями игроков А и В.

Таким образом, оптимальные смешанные (в частности, чистые) стратегии P^O и Q^O соответственно игроков А и В обладают тем свойством, что если один из игроков придерживается своей оптимальной стратегии, то противнику невыгодно отклоняться от своей оптимальной стратегии.

Множество оптимальных смешанных стратегий соответственно игроков А и В обозначим через (S_A)^О и (S_B)^О.

Полным решением игры в смешанных стратегиях называется трехэлементная совокупность {(S_A)^O,(S_B)^O,V}. Любая пара оптимальных стратегий P^O и Q^O соответственно игроков А и В и цена игры в смешанных стратегиях V образуют частное решение в смешанных стратегиях.

Теорема

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

 

21. Цена игры в смешанных стратегиях. Стратегии, оптимальные во множестве смешанных стратегий. Полное (общее) и частное решения игры в смешанных стратегиях. Основная теорема теории игр Дж. фон Неймана.

Если нижняя и верхняя цены игры в смешанных стратегиях совпадают, то их общее значение V= = называется ценой игры в смешанных стратегиях. Нижняя и верхняя цены игры в чистых стратегиях α и β и цены игры в смешанных стратегиях V связаны между собой неравенствами α≤V≤β.

Стратегии P^O и Q^O соответственно игроков А и В, удовлетворяющие равенствам V=α(P^O)=β(Q^O) (и тогда это общее значение очевидно равно H(P^O,Q^O)), называется оптимальными смешанными стратегиями игроков А и В.

Таким образом, оптимальные смешанные (в частности, чистые) стратегии P^O и Q^O соответственно игроков А и В обладают тем свойством, что если один из игроков придерживается своей оптимальной стратегии, то противнику невыгодно отклоняться от своей оптимальной стратегии.

Множество оптимальных смешанных стратегий соответственно игроков А и В обозначим через (S_A)^О и (S_B)^О.

Полным решением игры в смешанных стратегиях называется трехэлементная совокупность {(S_A)^O,(S_B)^O,V}. Любая пара оптимальных стратегий P^O и Q^O соответственно игроков А и В и цена игры в смешанных стратегиях V образуют частное решение в смешанных стратегиях.

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

Т: Любая матричная игра имеет решение в смеш.стр-ях, т.е. ∃ цена игры в смеш.стр-яхV и опт.смешанные стр-ии и соответственно иг-ов А и В, т.е.

Надо доказать ее

Следствие 1

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

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

Следствие 2 (о дублирующих чистых стратегиях). Одну из двух дублирующих чистых стратегий можно удалить

 

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

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

34. Критерий седл. точки мат-цы игры 2х2, основанный на принципе доминирования.

Т: Пусть i — номера строк, а , — номера столбцов мат-цы А размера 2x2. Для того чтобы элемент a_ij был седл. точкой мат-цы А, необхи дост-но выполнение хотя бы одного из следующих условий:

1. Можно удалить k-ю строку как доминируемую 1-й строкой, а затем в оставшейся i-й строке можно удалить 1-й столбец как доминируемый j-м столбцом,

2. Можно удалить 1-й столбец как доминируемый j-м столбцом, а затем в оставшемся j-м столбце удалить k-ю строку как доминируемую i-й строкой.

Док-во. Необх-ть: Пусть a_ij — седл. точка. Тогда элемент а_ij — наименьший в i-й строке и наибольший в j-м столбце: . При сравнении элементов а_ij и a_kl возможные случаи .

Рассмотрим (3): Нерав-ва (2) и (3) означают, что i-я строка доминирует k-ю строку и потому k-ю строку можно удалить. Нерав-во (1) показывает, что в оставшейся i-й строке 1-й столбец доминируется j-м столбцом, а потому 1-й столбец можно удалить. Т.о, в случае (3) выполняется условие 1. Рассмотрим (4): Из нерав-тв (4), (1) и (2) следует нерав-во , которое вместе с нерав-вом (1) означает, что 1-й столбец доминируется j-м столбцом, и потому 1-й столбец можно удалить. Нерав-во (2) означает, что в оставшемся j-м столбце i-я строка доминирует k-ю строку и, следовательно, k-ю строку можно удалить. Итак, в случае выполнения нерав-ва (4) справедливо условие 2.Если верны нерав-ва (3) и (4), т. е. если , то, как следует из доказанного, имеют место условия 1 и 2. Однако совместное выполнение условий 1 и 2 может быть и при невыполнении рав-ва (5). Итак, необходимость доказана.

Дост-ть. Пусть выполняется условие 1. Тогда i-я строка доминирует k-ю строку, откуда, в частности, следует, что верно (2). Так как в i-й строке l-й столбец доминируется j-м, то имеет место (1). Нерав-ва (1) и (2) означают, что a_ij- седл. точка игры.

Пусть выполняется условие 2. Из того, что l-й столбец доминируется j-м столбцом, следует (1), а из того, что в j-м столбце i-я строка доминирует k-ю строку, вытекает нерав-во (2). Поэтому a_ij - седл. точка игры.

Т 1

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

 

Т 2

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

Для того чтобы смешанная страт-я Р⁰=(р⁰₁, р⁰_m) игрока А, где:

p⁰_i ,

 

p⁰_i была оптимальной, необходимо и достаточно, чтобы отрезки и имели зарные наклоны.

 

 

45.Принцип решения игры методом Шепли-Сноу. Т Шепли-Сноу о крайних опт.стр-ях

Крайняя точка — это такая точка Р выпуклого мн-ва S, которой нельзя подобрать такой интервал, который бы содержал эту точку Р и сам содержался бы в S. Мн-тво крайних точек мн-ва S обозначают . Например, мн-тво крайних точек выпуклого многогранника есть мн-тво его вершин, поэтому крайние точки выпуклого многогранника называют также угловыми.

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

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

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

Отметим, что метод Шепли-Сноу — точный метод решения.

Т Шепли-Сноу

Пусть и - крайние опт.стр-ии соответственно иг-ов А и B в игре с ценой игры , т.е. и . Тогда номеров строк мат-цы , номеров столбцов мат-цы , Крайняя опт. стр. удовлетворяет системе уравнений:

, а крайняя опт.стр. удовлетворяет системе уравнений

. При этом, если , то мат-ца системы для и транспонированная мат-ца системы для невырождены, т.е. их определители не равны нулю.

Игры.

Т. Решение следующей пары взаимно двойственных задач линейного программирования:

1. найти max при ограничениях x_j≥0, j=1,…,m, , i=1,…,n;

2. найти min при ограничениях y_i≥0, i=1,…,n, , j=1,…,m,

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

Можно уточнить вышеизложенное:

Если (1) — опт.стр. любого иг-ка в игре с матрицей D и >0, то (2) — опт. решение задачи 1, а

(3) — опт.решение задачи 2.

Обратно, если — опт.решение задачи 1, а -опт. решение задачи 2, то (4) где (5) является опт. стратегией любого иг-ка в игре с матрицей D. Для того, чтобы пара взаимно двойственных задач линейного программирования 1 и 2 имела опт.решение ⇔чтобы в игре с матрицей D∃а опт. стр. (1), в которой >0.

 

 

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

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

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

Рассмотрим парную игру с иг-ками А и В. Пусть игрок А имеет mстр-ий , а игрок В — nстр-ий . Натуральные числа m и n в общем случае никак не связаны между собой. Если каждый из иг-ов А и В сознательно определенным образом выбирает стр-ии и соответственно, то сложившаяся ситуация (в чистых стр-ях) однозначно определяет выигрыш иг-ка А, выражающийся действительным числом , которое одновременно является и проигрышем иг-ка В. А число выражает проигрыш иг-ка А и выигрыш иг-ка В. Если число отрицательно, то оно будет представлять отрицательный выигрыш иг-ка А, то есть его проигрыш. Числа — это значения ф-ии выигрыша иг-ка A: . Ходы иг-ов с сознательным выбором одной из возможных своих чистых стр-ий называют иногда личными ходами.

Выигрыши , i = 1,..., m, j = 1,...,n, можно расположить в виде мат-цы, номера строк которой соответствуют номерам стр-ийиг-ка А, а номера столбцов — номерам стр-ийиг-ка В. Мат-ца А называется матрицей выигрышей иг-ка A.

Обозначим через значения ф-ии выигрыша иг-ка В, т. е. . Если рассматриваемая игра — антагонистическая (т.е. с нулевой суммой выигрышей), то ф-ии выигрышей и иг-ов А и В связаны между собой рав-вом и, следовательно, Эти рав-ва означают, что мат-ца выигрышей В иг-ка В является противоположной транспонированной матрице A:

 

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

Матричная игра игра с и.А и и.В,задаваемая матр выигр.А.

Показатель эффективности стр. -минимальный выигрыш при этой стратегии (мин.эл-т i-ой строки):

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

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

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

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

Минимаксная стр и.В – стр , пок-тель неэф которой совпадает с минимаксом . Мн-во всех ч.страт и.В - . Принцип выбора минмакс.стр в кач-ве эффект – минимаксный принцип (т.о. при любой игре А не может проиграть ≥ ).

Для нахожд ниж.и верх.цен игры в ч.страт. дополним матр столбцами стр , и стр :

Т 1. Для элементов расширенноймат-цы выигрышей имеют место нерав-ва

и, следовательно, нижняя цена игры не больше ее верхней цены в чистыхстр-ях: α ≤ β. (15)

Док-во. По опр. показателей эфф-ти α_iстр-ий А_iиг-ка А и опр. показателей неэфф-ти β_j стр-ий B_jиг-ка В имеем Т.к. доказанное нерав-во α_i ≤ β_j справедливо ∀ i = 1,..., m, j =1,..., n, то оно будет справедливым в частности для номеров i = i₀ и j = j₀ соответственно максиминной и минимаксной стр-ий.Тогда α ≤ β.Т доказана.