ТОП 10:

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



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

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

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

[Пусть V – цена игры, H(P, Q) – ф-ия выигрыша, {A1, ..., Am} и {B1, ..., Bn} – мн-ва чистых стр-ий соответственно иг-овА и В. 1. Для того чтобы стр.P0иг-каА была опт.⇔чтобы H(P0, Bj) ≥ V, j = 1, ..., n. 2. Для того чтобы стр.Q0иг-каB была опт.⇔чтобы H(Ai, Q0) ≤ V, i = 1, ..., m]

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

Rm, x1,x2,…,xk называется линейно независимыми, если λ1x12x2+…+λkxk= (0;0;…0), следовательно λ1= λ2=…=λk

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

S∈Rmназывается выпуклым если оно с любыми 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 было ценой игры, а P0, Q0- оптимальными стр.ми соответственно иг-ов А и В, другими словами для того, чтобы { P0, Q0, V} было решением игры, ⇔ выполнение двойного нерав-ва

(1)

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

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

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

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

, (1)

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

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

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







Последнее изменение этой страницы: 2016-09-05; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.232.188.251 (0.004 с.)