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

Седл. точка выигрыш-ф-ии (седл. точка игры, ситуация равновесия, равновесная ситуация) – ситуация удовлетворительная для обоих иг-ов.

Седл. точка мат-цы игры – выигрыш иг-ка А в ситуации равновесия; элемент, являющийся седл. точкой мат-цы игры, — минимальный в своей строке и максимальный в своём столбце.

Т 1 Если и — седл. точки, то

Док-во. Т.к. - седл. точка, то по правому нерав-тву (1) при i₀ = i₁, j₀ = j₁, j = j₂ имеем Т.к. - седл. точка, то по левому нерав-тву (1) при i₀ = i₂, j₀ = j₂, i = i₁ получим Из нерав-тв (4) и (5) следует нерав-во Применив аналогичные рассуждения сначала к седл. точке а затем к седл. точке получим нерав-во Нерав-ва (6) и (7) доказывают рав-во (3).

Т 2 Если и - седл. точки, то и и - также седл. точки.

Док-во. Т.к. и - седл. точки, то по Т 1 справедливо рав-во (3), из которого, используя (2), получим С другой стороны, по определениям пок-ля ффективности и пок-ля неэфф-ти будем иметь: Из рав-ва (8) и нерав-ва (11) следует, что А это означает, что - седл. точка. Тот факт, что - седл. точка, доказывается аналогично. А именно, из (3) с использованием (2) получаем рав-во а из (9) и (10) — нерав-во и потому имеют место рав-ва которые означают, что - седл. точка.

 

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

Стратегии и , создающие равновесн ситуацию – оптимальные. и - множ-ва чист.опт страт. и.А и и.В.

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

Теорема(критерий существования цены игры в чистых стр): для существования цены игры в чистых страт. необх и достат существование у матр этой игры седловой тчк.

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

Пусть - максимин.стр и.А, а -минимаксн.стр.и.В. тогда , . Рассмотрим ,стоящий на пересеч -той строки и -столбца. Из предыдущ рав-в, опред показ эфф и неэф: , отсюда в силу рав-ва и , получим: , кот означ, что явл седл тчк. Необходимость доказана.

Достаточноть. Пусть сущ седл тчк. , тогда: . Отсюда по опред нижн и верхн цен игры: , т.е. . Но по теореме (, , ) и поэтому , существует цена игры в чистых страт.

Т1: Для элементов мат-цы (1) имеют место нерав-ва (8) И следовательно, нижняя цена игры не больше её верхней цены игры в чистых стр-ях. (9).

Док-во: По опр. (2) и (3) получаем: следовательно (8) доказано. Т.к. доказанное нерав-во , справедливо ∀i=1,…,m, j=1,…,n, то оно будет справедливо в частности для номеров i=i₀ и j=j₀ соответственно максиминной и минимаксной стр-ий и : Тогда в силу (6) и (7)получаем (9).

ОПР. Обозначим и — мн-тва чистых оптимальных стр-ийиг-ов A и B соответственно, — цена игры. Тогда совокупность — полное решение игры в чистыхстр-ях, а совокупность какой-нибудь пары чистых оптимальных стр-ий и и цены игры называется частным решением игры в чистых стр-ях.

Т2. Для того чтобы ∃а цена игры в чистыхстр-ях, т. е. для того чтобы нижняя цена игры α равнялась верхней цене игры β, ⇔сущ-ие у мат-цы этой игры седл. точки.

Док-во. Необх-ть. Пусть ∃ цена игры в чистых стр-ях, т.е. нижняя цена игры α совпадает с ее верхней ценой β: α = β. (1)Пусть - максиминная стр.иг-ка A, a - минимаксная стр.иг-ка В. Тогда Рассмотрим элемент стоящий на пересечении i ₀-й строки и j ₀- го столбца мат-цы игры. Из (2), определений пок-ляэфф-ти стр-ии и пок-ля неэфф-ти стр-ии будем иметь: откуда, в силу (1) получим рав-во которое означает, что элемент является седл. точкой. Необх-ть доказана. Дост-ть. Пусть ∃седл. точка Тогда Отсюда по опр. нижней и верхней цен игры т. е. α ≥ β. Но поТ: нижняя цена игры не больше ее верхней цены в чистых стр-ях: α ≤ β и потому α = β, т. е. ∃ цена игры в чистых стр-ях.

Т 3. Справедливы следующие утв.

1. Каждая опт.стр.иг-каА является его максиминной стратегией, а каждая опт.стр.иг-каВ является его минимаксной стратегией.

2. В игре без седл. точек ни одна из максиминных и минимаксных стр-ий не является опт., Т.к. в этой игре вообще нет опт.стр-ий.

3. В игре с седловыми точками каждая максиминная и каждая минимаксная стр-ии соответственно иг-овА и В являются оптимальными.

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

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

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

Выпуклая комбинация точек х1,х2,…,хк – линейная комбинация с неотрицательными коэффициентами , сумма которых равна 1.

Выпуклая оболочка мн-ваS (convS) – пересечение всех выпуклых мн-тв, содержащих мн-воS.

Мн-во состоящее из к точек х1,х2,…,хк векторного пр-ва R^m, называется аффинно независимым, если мн-во точек х2-х1, х3-х1,хк-х1, линейно независимо.

Если точки х1,х2,…,хк аффинно независимы, то их выпуклая оболочка называется (к-1) – мерным симплексом с к вершинами х1,х2,…,хк.

Орты – взаимно-перпендикулярные векторы.

Правая часть рав-ва (2) является выпуклой комбинацией орт А₁,..., А_т и потому мн-во S_A всех смеш.стр-ий геометрически представляет собой фундаментальный (m — 1)-мерный симплекс с т вершинами в точках А₁,..., А_т, представляющих чистые стр-ии (выпуклая оболочка, натянутая на чистые стр-ии).

При т = 1 игрок А обладает одной чистой стратегией A₁ и потому смеш.стр. совпадает с чистой. Т.о., мн-восмеш.стр-ий состоит из единственного элемента A₁: S_A = = {A₁} — и представляет собой 0-мерный симплекс, состоящий из единственной точки — вершины А₁.

При т = 2 игрок А имеет две чистые стр-ии: = {A₁, A₂},а мн-во S_A смеш.стр-ий есть 1-мерный симплекс с двумя вершинами А₁ и А₂, представляющий собой отрезок с концами А₁ и А_2.

При т = 3 у иг-ка А три чистые стр-ии: = {A₁, A₂, A₃}; мн-во S_A смеш.стр-ий является 2-мерным симплексом с вершинами A₁, A₂, A₃, представляющим собой плоский правильный треугольник А₁А₂А₃.

При т = 4 мн-восмеш.стр-ий S_A есть 3-мерный симплекс с четырьмя вершинами A₁, A₂, A₃, А₄, представляющий собой правильный тетраэдр. Аналогичная геометрическая интерпретация имеет место и для иг-ка В