Геометрическая интерпретация мн-ва опт.смеш.стр-ий

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

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

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

[Пусть V – цена игры, H (P, Q) – ф-ия выигрыша, { A ₁,..., A_m } и { B ₁,..., B_n } – мн-ва чистых стр-ий соответственно иг-ов А и В. 1. Для того чтобы стр. P ⁰иг-ка А была опт.⇔чтобы H (P ⁰, B_j) ≥ V, j = 1,..., n. 2. Для того чтобы стр. Q ⁰иг-ка B была опт.⇔чтобы H (A_i, Q ⁰) ≤ V, i = 1,..., m ]

справедливо нерав-во H (P ⁰, B_j) ≥ V, j = 1,..., n, которое в соответствие с формулой можно переписать следующим образом: . Мн-во точек m-мерного пр-ва R^m, координаты , которых удовлетворяют этому нерав-тву для фиксированного j = 1,..., n, является замкнутым полупр-вом, а мн-во точек , координаты , которых удовлетворяют этому нерав-тву для всех j = 1,..., n, является пересечением конечного числа n замкнутых полупространств и называется выпуклым замкнутым полиэдром. Т.к. к тому же мн-во опт. стр-ий иг-ка А ограничено, Т.к. оно является подмн-вом симплекса всех его смеш.стр-ий S_A, то является выпуклым многогранником (политопом). Это утв. для мн-ва опт. стр-ий иг-ка В доказывается аналогично.

R^m, x₁,x₂,…,x_k называется линейно независимыми, если λ₁x₁+λ₂x₂+…+λ_kx_k= (0;0;…0), следовательно λ₁= λ₂=…=λ_k

Точки x_1,x_2,… x_kназываются афино-независимыми, если х2-х1,х3-х1,…хk-х1 – линейно независимые.

S∈R^mназывается выпуклым если оно с любыми 2 точками содержит отрезок с концами этих точек

(1- λ)x1+ λy, x,y∈S, 0<λ<1

λ1x1+λ2x2+…+λkxk, λi>=0,

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

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

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

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

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

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

m=4 тетраэдр

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

 

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

Т. Для того, чтобы V было ценой игры, а P ⁰, Q ⁰- оптимальными стр.ми соответственно иг-ов А и В, другими словами для того, чтобы { P ⁰, Q ⁰, V} было решением игры, ⇔ выполнение двойного нерав-ва

∀ (1)

Док-во. Необх-ть. Пусть V – цена игры и P ⁰, Q ⁰- опт.стр-ии. Тогда по необх. части Т о критериях опт. смеш.стр-ий в терминах цены игры, ф-ии выигрышей и мн-твсмеш.стр-ийиг-ов[Пусть V – цена игры, H (P, Q) – ф-ия выигрыша, S_A и S_B – мн-ва смеш.стр-ий соответственно иг-ов А и В. 1. Для того чтобы стр. P ⁰иг-ка А была опт.⇔чтобы выполнялось нерав-во H (P ⁰, Q) ≥ V ∀ Q Î S_B, т.е. выбор игроком А опт.стр-ии P ⁰ гарантирует ему выигрыш H (P ⁰, Q), не меньший цены игры V, при любой стр-ии Q иг-ка В. 2. Для того чтобы стр. Q ⁰иг-ка В была опт.⇔чтобы выполнялось нерав-во H (P, Q ⁰) ≤ V ∀ P Î S_A, т.е. выбор игроком В одной из своихопт. стр-ий Q ⁰ гарантирует ему проигрыш, не больший цены игры V, при любой стр-ии P иг-ка А. ] справедливы нерав-ва и , которые можно записать в виде двойного нерав-ва (1).

Дост-ть. Пусть для некоторого числа V и некоторых стр-ий P ⁰иг-ка А и Q ⁰иг-ка В выполняется двойное нерав-во (1). Т.к. это нерав-во верно ∀ , то в частности оно будет справедливо и для : (2) Подставим это значение V в (1): (3) Т.к. нерав-во (3) имеет место при любых , то или в силу и получим Отсюда по опр. верхней и нижней цен игры получим: (4) Но по Т фон Неймана и поэтому из (4) получаем рав-ва: (5) Из (2) и (5) следует, что V – цена игры, а также справедливость рав-ва , которое по опр. опт.стр-ий, означает, что P ⁰, Q ⁰ — опт. стр-ии соответственно иг-ов А и В.

Критерий цены игры и опт.смеш.стр-ий в терминах мн-тв чистых стр-ий иг-ов.

Т. Для того, чтобы V была ценой игры, а P ⁰, Q ⁰- оптимальными стр.ми иг-ов А и В, ⇔ выполнение двойного нерав-ва

, (1)

Док-во. Достаточно установить эквивалентность нерав-тв (2) и (1), где (2)

Пусть справедливо нерав-во (2). Т.к. оно имеет место ∀стр-ий , то оно справедливо и ∀чистыхстр-ий , т.е. справедливо двойное нерав-во (1). Итак, показано, что из нерав-ва (2) следует нерав-во (1). Докажем обратное следствие: из (1) => (2)

Пусть имеет место (1). Тогда, по формулам и , из него получим: Значит, справедливо нерав-во (2).Доказана эквивалентность (2) ó (1) и соответственно Т.