Тигры, 02 лекция (от 11 сентября)

Материал из eSyr's wiki.

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: Остлось доказть, что ... x ∈ X, y ∈ Y, t ∈ (0,1) K((1-t)x*+tx+y) > (1-t)k(x*,y) + tK(x, y) ≥ (1-t)_w_(x*) + tK(x,y) ỹ = y((1-t)x* + tx) --- э...)
Текущая версия (06:42, 13 октября 2010) (править) (отменить)
 
(3 промежуточные версии не показаны)
Строка 1: Строка 1:
-
Остлось доказть, что ...
+
* '''Аудиозапись:''' http://esyr.org/lections/audio/game_theory_2008_winter/GT_08_09_11.ogg
 +
 
 +
Осталось доказать, что ...
x ∈ X, y ∈ Y, t ∈ (0,1)
x ∈ X, y ∈ Y, t ∈ (0,1)
Строка 5: Строка 7:
K((1-t)x*+tx+y) > (1-t)k(x*,y) + tK(x, y) ≥ (1-t)_w_(x*) + tK(x,y)
K((1-t)x*+tx+y) > (1-t)k(x*,y) + tK(x, y) ≥ (1-t)_w_(x*) + tK(x,y)
-
ỹ = y((1-t)x* + tx) --- это верно при фикс. ...
+
ỹ = y((1-t)x* + tx) --- это верно при фиксированном ...
-
_w_(x*) ≥ _w_((1-t)x* + tx) > (1-t)_w_(x*) + tk(x, ỹ) --- мыр списли эт сотн. при y=ỹ
+
_w_(x*) ≥ _w_((1-t)x* + tx) > (1-t)_w_(x*) + tk(x, ỹ) --- мы расписали это соотношение при y=ỹ
t_w_(x*) &gy; tK(x,ỹ)
t_w_(x*) &gy; tK(x,ỹ)
Строка 13: Строка 15:
_w_(x*) > K(x, y((1-t)x* + tx))
_w_(x*) > K(x, y((1-t)x* + tx))
-
Это соотн. справидлив ∀t ∈ (0,1). Устремим t к 0. Что получится:
+
Это соотношение справедливо ∀t ∈ (0,1). Устремим t к 0. Что получится:
-
_w_(x*) ≥ K(x,y(x*)) (здесь мы исп. докзанную в нчле непр.)
+
_w_(x*) ≥ K(x,y(x*)) (здесь мы используем доказанную в начале непрерывность)
Левая величина _w_(x*) = K(x*, y(x*))
Левая величина _w_(x*) = K(x*, y(x*))
-
То есть покзно, что это — седловая точка.
+
То есть показано, что это — седловая точка.
-
Теперь отк. от стргости выпуклости/вогнутоти.
+
Теперь откажется от строгости выпуклости/вогнутости.
Введём функцию K_ε(x,y) = K(x,y) - ε &sum_{i=1}^n x_i^2 + ε &sum_{j=1}^m y_j^2, ε > 0
Введём функцию K_ε(x,y) = K(x,y) - ε &sum_{i=1}^n x_i^2 + ε &sum_{j=1}^m y_j^2, ε > 0
-
Так кк кажде из лагаемых строго выпукло по x/y, то и сумма тоже строго выпукла по x и y. След, для неё верно только что док. утв.: (x_ε, y_ε) — седловая точка. K_ε(x,y)
+
Так как каждое из слагаемых строго выпукло по x/y, то и сумма тоже строго выпукла по x и y. Следовательно, для неё верно только что доказанное утверждение: (x_ε, y_ε) — седловая точка. K_ε(x,y)
K_ε(x,y_ε) ≤ K_ε(x_ε,y_ε) < K_ε(x_ε,y), ∀ x ∈ X, y ∈ Y
K_ε(x,y_ε) ≤ K_ε(x_ε,y_ε) < K_ε(x_ε,y), ∀ x ∈ X, y ∈ Y
Строка 36: Строка 38:
K(x, y_ε) — ε &sum_{i=1}^n x_i^2 ≤ K_ε(x_ε,y_ε) ≤ K(x_ε,y) + ε &sum_{j=1}^m y_j^2, ∀ x ∈ X, y ∈ Y
K(x, y_ε) — ε &sum_{i=1}^n x_i^2 ≤ K_ε(x_ε,y_ε) ≤ K(x_ε,y) + ε &sum_{j=1}^m y_j^2, ∀ x ∈ X, y ∈ Y
-
Теперь ε_n → 0, n → ∞, ε_n > 0. Тгд эти слаг. устр. к нулю, из гр. посл. можно выделить сходящуюся, соотв., без. гр. бщности y_{ε_n} → y*, x_{ε_n} → x*, и получем
+
Теперь ε_n → 0, n → ∞, ε_n > 0. Тогда эти слагаемые устремляются к нулю, из ограниченной последовательности можно выделить сходящуюся, соответственно, без ограничения общности y_{ε_n} → y*, x_{ε_n} → x*, и получаем
-
K(x, y*) ≤ K(x*, y), из этого условия мы дказывали ранее, что K(x*, y*) — седловя точка.
+
K(x, y*) ≤ K(x*, y), из этого условия мы доказывали ранее, что K(x*, y*) — седловая точка.
-
Важно тметить, что эти усл. являются дсттчными, но не необхдимыми.
+
Важно отметить, что эти условия являются достаточными, но не необходимыми.
-
Пример (усл. не явл. необх.):
+
Пример (условие не является необходимым):
K(x,y) = x^e + 0×y, x, y ∈ [0,1]. (1,1) — седловая точка. (доказать дома)
K(x,y) = x^e + 0×y, x, y ∈ [0,1]. (1,1) — седловая точка. (доказать дома)
Строка 50: Строка 52:
K(x,y) = y ln(x+3) + xy^2, x, y ∈ [0,1]
K(x,y) = y ln(x+3) + xy^2, x, y ∈ [0,1]
-
Условия теоремы фон Нейман выполняются:
+
Условия теоремы фон Неймана выполняются:
K_{x}' = y/(x+3) + y^2
K_{x}' = y/(x+3) + y^2
Строка 60: Строка 62:
K_{yy}'' = 2x ≥ 0 — выпукла по y.
K_{yy}'' = 2x ≥ 0 — выпукла по y.
-
Усл. т. ф-Н вып, и есть седловая точка (показать дома, чт это (1,0))
+
Условие теоремы фон Неймана выполнено, и есть седловая точка (показать дома, что это (1,0))
-
Теорема констр. и вообще говоря, ей можн польз. для нахжд. седл. точки.
+
Теорема конструктивная и вообще говоря, ей можно пользоваться для нахождения седловой точки.
-
Сейчас рассм. частный случай платжнй функции, для которой есть простой алгоритм. Он позв. свести писк. седл. точки к реш. сист. ур. и реш. мтр. игры.
+
Сейчас рассмотрим частный случай платёжной функции, для которой есть простой алгоритм. Он позволяет свести поиск седловой точки к решению системы уравнений и решению матричной игры.
-
Раздел: необх. усл. для седловой точки
+
Раздел: необходимое условие для седловой точки
-
Рассм. след. случай: множество стртегий X имеет след. вид: X={x=(x_1, ..., x_n), 0 ≤ a_i ≤ x_i ≤ b_i, i = 1..n}, Y={y=(y_1, ..., y_m), 0 ≤ c_i ≤ y_j ≤ d_j, j = 1..m}
+
Рассмотрим следующий случай: множество стратегий X имеет следующий вид: X={x=(x_1, ..., x_n), 0 ≤ a_i ≤ x_i ≤ b_i, i = 1..n}, Y={y=(y_1, ..., y_m), 0 ≤ c_i ≤ y_j ≤ d_j, j = 1..m}
-
Предполагаем, что K(x, y) непр. на X× Y и имеет част. призсв. K_{x_i}', K_{y_j}', i=1..n, j=1..m.
+
Предполагаем, что K(x, y) непрерывно на X× Y и имеет частную производную K_{x_i}', K_{y_j}', i=1..n, j=1..m.
-
Прежде, чем вып. след. деёств, рассм. систему:
+
Прежде, чем вып. след. деёств, рассмотрим систему:
K_{x_i}'(x, y)(x_i - a_i)(x_i - b_i) = 0, i=1..n
K_{x_i}'(x, y)(x_i - a_i)(x_i - b_i) = 0, i=1..n
K_{y_j}'(x, y)(y_j - c_j)(y_j - d_j) = 0, j=1..m (*)
K_{y_j}'(x, y)(y_j - c_j)(y_j - d_j) = 0, j=1..m (*)
-
Предположим, чт эта сист. имеет реш. и мн-во решений конечно. Тогда пр. след. мнжества: те x из X, что:
+
Предположим, что эта система имеет решение и множество решений конечно. Тогда пр. следующие множества: те x из X, что:
X^c = {x ∈ X: ∃y ∈ Y, (x,y) ∈ X}
X^c = {x ∈ X: ∃y ∈ Y, (x,y) ∈ X}
Строка 81: Строка 83:
....
....
-
Т. Если (x_0, y^0) — седловая точка K(x,y) на X×Y, то (x_0, y^0) ∈ C, (x_0, y^0) — c.т. K на X^c×Y^c
+
'''Теорема'''. Если (x_0, y^0) — седловая точка K(x,y) на X×Y, то (x_0, y^0) ∈ C, (x_0, y^0) — c.т. K на X^c×Y^c
-
Эта теорем даёт нам алгритм поиска седл. Тчки. Пусть есть такая функция и вып. все усл. мы вып. сист. ур. (*), решаем её, получем, чт мн. реш. кнечно. Выпис мн-в X^c×Y^c, и получаем матричную игру, и тут уже искать просто.
+
Эта теорема даёт нам алгоритм поиска седловой точки. Пусть есть такая функция и выполнены все условия мы выписываем систему уравнений (*), решаем её, получаем, что множество решений конечно. Выписываем множество X^c×Y^c, и получаем матричную игру, и тут уже искать просто.
-
Еcли с.т. у K есть, то она бяз. вйдт в число точек матр. игры. Т есть реш. матр. игру и проверяем, будет ли каждя из. седл. точек для исх. игры.
+
Еcли с.т. у K есть, то она обязательно войдёт в число точек матричной игры. То есть решаем матричную игру и проверяем, будет ли каждая из седловых точек для исходной игры.
-
Доказательство.
+
'''Доказательство'''.
K(x,y^0) ≤ K(x^0, y^0) ≤ K(x^0, y), ∀ x ∈ X, y ∈ Y
K(x,y^0) ≤ K(x^0, y^0) ≤ K(x^0, y), ∀ x ∈ X, y ∈ Y
Строка 97: Строка 99:
Таким образом мы доказали первую часть.
Таким образом мы доказали первую часть.
-
Втрая часть: если мы берём первое соотн, и оно верно при ∀ x ∈ X, y ∈ Y, то оно верно и при ∀ x ∈ X^c, y ∈ Y^c
+
Вторая часть: если мы берём первое соотношение, и оно верно при ∀ x ∈ X, y ∈ Y, то оно верно и при ∀ x ∈ X^c, y ∈ Y^c
-
Таким обр. мы получили алгоритм.
+
Таким образом мы получили алгоритм.
Пример.
Пример.
Строка 105: Строка 107:
K(x,y)=8(4xy^2-2x^2-y), x,y∈[0,1]
K(x,y)=8(4xy^2-2x^2-y), x,y∈[0,1]
-
Сначла прверим, вып. ли усл. т. ф-Н. По x она вогн. и по y она вып. Отсюда по т. ф-н. сущ. с. т.
+
Сначала проверим, выполнены ли условия теоремы фон Неймана. По x она вогнута и по y она выпукла. Отсюда по теореме фон Неймана существует седловая точка.
-
Теперь будем строить сист. ур. (*):
+
Теперь будем строить систему уравнений (*):
K'_x=8(4y^2-4x), K'_y=8(8xy-1)
K'_x=8(4y^2-4x), K'_y=8(8xy-1)
Строка 113: Строка 115:
(y^2-x)(x-0)(x-1) = 0
(y^2-x)(x-0)(x-1) = 0
(8xy-1)(y-0)(y-1) = 0
(8xy-1)(y-0)(y-1) = 0
-
решаем эту систему: (0,0), (0,1), (1,0), (1,1), (1, 1/8), (1/4, 1/2) --- построили мнжество C
+
решаем эту систему: (0,0), (0,1), (1,0), (1,1), (1, 1/8), (1/4, 1/2) --- построили множество C
X^c = {0, 1/4, 1}, Y^c = {0, 1/8, 1/2, 1}
X^c = {0, 1/4, 1}, Y^c = {0, 1/8, 1/2, 1}
-
Теперь строим матр. игру:
+
Теперь строим матричную игру:
x^c \ y^c 0 1/8 1/2 1
x^c \ y^c 0 1/8 1/2 1
0 0 -1 -4 -8
0 0 -1 -4 -8
Строка 123: Строка 125:
1 -16 -33/2 -12 8
1 -16 -33/2 -12 8
-
седл. точка --- (1/4, 1/2). Дальше над, вобще говоря, проверить все плоуч. седл. точки.
+
седловая точка --- (1/4, 1/2). Дальше надо, вообще говоря, проверить все полученные седловые точки.
-
Но пск. мыу уст., что пот . ф-Н есть 1 седл точка, а получили мы их мксимум одну, то их ровно одна.
+
Но поскольку мы установили, что по теореме фон Неймана есть одна седловая точка, а получили мы их максимум одну, то их ровно одна.
-
Смешанные стратегии в ант. играх.
+
== Смешанные стратегии в антагонистических играх ==
-
Когда рассм. игра с плат. матр. A = ||a_ij||, i=1..n, j=1..m. Каждый выбирает i/j соответственно, и один получает a_ij, другой -a_ij
+
Когда рассматривается игра с платёжной матрицей A = ||a_ij||, i=1..n, j=1..m. Каждый выбирает i/j соответственно, и один получает a_ij, другой -a_ij
-
Игра обычно разыг. много раз. При этом возн. понятие p=(p_1, ..., p_n), p_i > 0, &suum;_{i=1}^n p_i=1 --- вектор вер. выб. стратегии i --- смешанная тртегия перв. игрока. Множество этих стратегий P_n = {p=(p_1, ..., p_n), p_i > 0, ∑_{i=1}^n p_i=1}. Аналогично для второго игрока: Q_m = {q=(q_1, ..., q_m), q_j > 0, ∑_{j=1}^m q_j=1}.
+
Игра обычно разыгрывается много раз. При этом возникает понятие p=(p_1, ..., p_n), p_i > 0, ∑_{i=1}^n p_i=1 --- вектор вероятности выбора стратегии i --- смешанная стратегия первого игрока. Множество этих стратегий P_n = {p=(p_1, ..., p_n), p_i > 0, ∑_{i=1}^n p_i=1}. Аналогично для второго игрока: Q_m = {q=(q_1, ..., q_m), q_j > 0, ∑_{j=1}^m q_j=1}.
-
Пусть p∈ P_n, q ∈ Q_n. Как считется результат? читается матожидание платежа. Платёж a_ij первый игрок плучет при выборе стртегии i и выборе стр. j вторым игроком. Но первый игр. выбирает с вер. p_i, а второй — q_j. Вероятность дн. выбора --- p_i×q_j. Тогда выигрыш равен A(p,q) = &sum_{i=1}^n ∑_{j=1}^m a_ij p_i q_j. Это показ, какой выигр. получат игроки , если выбрли стратегии p, q.
+
Пусть p∈ P_n, q ∈ Q_n. Как считается результат? считается матожидание платежа. Платёж a_ij первый игрок получает при выборе стратегии i и выборе стратегии j вторым игроком. Но первый игрок выбирает с вероятностью p_i, а второй — q_j. Вероятность данного выбора --- p_i×q_j. Тогда выигрыш равен A(p,q) = &sum_{i=1}^n ∑_{j=1}^m a_ij p_i q_j. Это показывает, какой выигрыш получат игроки, если выбрали стратегии p, q.
-
От игры с плат. матр. A мы перешли к игре с плат. функцией A(p,q).
+
От игры с платёжной матрицей A мы перешли к игре с платёжной функцией A(p,q).
A(p,j) = &sum_{i=1}^n a_ij p_i, A(i, q) = ∑_{j=1}^m a_ij q_j
A(p,j) = &sum_{i=1}^n a_ij p_i, A(i, q) = ∑_{j=1}^m a_ij q_j
Строка 141: Строка 143:
A(p,q) = ∑_{j=1}^m A(p,j) q_j = &sum_{i=1}^n A(i, q) p_i
A(p,q) = ∑_{j=1}^m A(p,j) q_j = &sum_{i=1}^n A(i, q) p_i
-
Каждый игрок по прежнему действ. по принц. мкс. выгоды, тгда плучим:
+
Каждый игрок по прежнему действует по принципу максимальной выгоды, тогда получим:
max_{p∈P_n} min_{q∈Q_m} A(p,q) = min_{q∈Q_m} A(p^0,q)
max_{p∈P_n} min_{q∈Q_m} A(p,q) = min_{q∈Q_m} A(p^0,q)
Строка 147: Строка 149:
min_{q∈Q_m} max_{p∈P_n} A(p,q) = max_{p∈P_n} A(p,q^0)
min_{q∈Q_m} max_{p∈P_n} A(p,q) = max_{p∈P_n} A(p,q^0)
-
В такй игре всегд сущ. седл. точка.
+
В такой игре всегда существует седловая точка.
Л1. P_n, Q_m — выпуклые компакты.
Л1. P_n, Q_m — выпуклые компакты.
1) p^1, p^2 ∈ P_n, α ∈ (0,1)
1) p^1, p^2 ∈ P_n, α ∈ (0,1)
-
Рссмтрим αp^1 + (1-α)p^2
+
Рассмотрим αp^1 + (1-α)p^2
Тогда
Тогда
αp^1 + (1-α)p^2 ≥ 0
αp^1 + (1-α)p^2 ≥ 0
Строка 163: Строка 165:
∑_i=1^n lim_{k &rasrr; ∞} p_i^k = ∑_i=1^n p_i^0
∑_i=1^n lim_{k &rasrr; ∞} p_i^k = ∑_i=1^n p_i^0
-
Из опр. P и Q. Мы делем вывод, что A(p,q) непр, и явл. линейной. Знчит, на и вып, и вогн. по любой перем. То есть, на вогн. по p и вып. по q. Терема ф-н. По теореме ф-н сущ. седл. тчка. Т. о.., мы доказали теор. матр. игре всегда сущ. смеш. стратегия". Нуи и поск. мы тметили, чт функция A(p,q) — непр., а мнжества смеш. стр. явл. компактными, то это позволяло писать max/min.
+
Из определений P и Q. Мы делаем вывод, что A(p,q) непрерывна, и является линейной. Значит, она и выпукла, и вогнута по любой переменной. То есть, она вогнута по p и выпукла по q. По теореме фон Неймана существует седловая точка. Т.о., мы доказали теорему матричной игре всегда существует смешанная стратегия". Ну и поскольку мы отметили, что функция A(p,q) — непрерывна, а множества смешанных стратегий являются компактными, то это позволяло писать max/min.
-
Ну и вобще, мы делем какой вывд: max min и min max равны. Это следствие из теоремы.
+
Ну и вообще, мы делаем какой вывод: max min и min max равны. Это следствие из теоремы.
-
Как решать матр. игры в меш. страт.: нужно нйти любую седловую точку.
+
Как решать матричные игры в смешанных стратегиях: нужно найти любую седловую точку.
-
тметим ещ раз., чт если p*, q* --- оптимальные стртегии, то (p*, q*) — седловая точка.
+
Отметим ещё раз, что если p*, q* --- оптимальные стратегии, то (p*, q*) — седловая точка.
-
Отметим св-ва оптимальных смешанных стратегий. Тройкой (p*, q*, V) будем называть решение игры. V = max_p nim_q A(p,q) = min_q max_p A(p,q) = A(p*, q*) Когда нам будет дана со смеш. стратегией, т целью будет явл. реш. игры. Таких троек мжет быть много. Для поиска таких троек небх. знть св-ва опт. смеш. стртегий.
+
Отметим свойства оптимальных смешанных стратегий. Тройкой (p*, q*, V) будем называть решение игры. V = max_p nim_q A(p,q) = min_q max_p A(p,q) = A(p*, q*) Когда нам будет дана со смешанной стратегией, то целью будет являться решение игры. Таких троек может быть много. Для поиска таких троек небходимо знать свойства оптимальных смешанных стратегий.
-
1. Если (p*, q*, V) — решение игры с матр. A, то (p*, q*, V+c) — решение игры с матрицей Ã = ||a_ij + c||, c=const. Мы примбвили кнстанту ко всем эл-там матрицы. Чт меняется? Мнжеств реш. не меняется, меняется тльк знач. игры. Докажем:
+
1. Если (p*, q*, V) — решение игры с матрицей A, то (p*, q*, V+c) — решение игры с матрицей Ã = ||a_ij + c||, c=const. Мы прибавили константу ко всем элементам матрицы. Что меняется? Множество решений не меняется, меняется только значение игры. Докажем:
A(p,q) + c = A(p,q) + c(∑_i=1^n p_i)(∑_i=j^m q_j) = &sum_{i=1}^n ∑_{j=1}^m (a_ij + c) p_i q_j = Ã(p,q)
A(p,q) + c = A(p,q) + c(∑_i=1^n p_i)(∑_i=j^m q_j) = &sum_{i=1}^n ∑_{j=1}^m (a_ij + c) p_i q_j = Ã(p,q)
-
Пусть выплнено условие, и A(p*, q*) — ст. Тогда
+
Пусть выполнено условие, и A(p*, q*) — седловая точка. Тогда
A(p,q*) ≤ A(p*, q*) ≤ A(p*, q)
A(p,q*) ≤ A(p*, q*) ≤ A(p*, q)
Строка 184: Строка 186:
Ã(p,q*) ≤ A(p*, q*) + с ≤ Ã(p*, q)
Ã(p,q*) ≤ A(p*, q*) + с ≤ Ã(p*, q)
-
Теперь из утв., док. на пршлой лекции, следует, что (p*, q*) обр. седл. тчку и (p*, q*, V+с) — решение игры
+
Теперь из утверждения, доказанного на прошлой лекции, следует, что (p*, q*) обращает седловую точку и (p*, q*, V+с) — решение игры
-
2. Тройка (p*, q*, V) явл. реш. игры т и тт, к A(i, q*) ≤ V ≤ A(p*,j), ∀ i=1..n, j=1..m
+
2. Тройка (p*, q*, V) является решением игры тогда и только тогда, когда A(i, q*) ≤ V ≤ A(p*,j), ∀ i=1..n, j=1..m
-
Док-во. 1)Пусть (p*, q*, V) — решение. Тогда:
+
Доказательство. 1)Пусть (p*, q*, V) — решение. Тогда:
A(p,q*) ≤ A(p*, q*) = V ≤ A(p*, q), ∀ p ∈ P_n, q ∈ Q_m
A(p,q*) ≤ A(p*, q*) = V ≤ A(p*, q), ∀ p ∈ P_n, q ∈ Q_m
-
Т. к. оно верно для всех p, q, то можно взять p=(0...0, 1 (i-е место), ..., 0) ∈ P_n, q=(0...0, 1 (j-е место), ..., 0) ∈ Q_m, и срзу получаем эт и соотношения.
+
Т.к. оно верно для всех p, q, то можно взять p=(0...0, 1 (i-е место), ..., 0) ∈ P_n, q=(0...0, 1 (j-е место), ..., 0) ∈ Q_m, и сразу получаем эти соотношения.
-
2)Пусть вып. соотн:
+
2)Пусть выполнены соотношения:
A(p,q*) ≤ A(p*, q*) = V ≤ A(p*, q), ∀ p ∈ P_n, q ∈ Q_m
A(p,q*) ≤ A(p*, q*) = V ≤ A(p*, q), ∀ p ∈ P_n, q ∈ Q_m
-
Возьмём произв p, q. Возьмём соотн. A(i, q*) ≤ V, i=1..n
+
Возьмём произвольным p, q. Возьмём соотношение A(i, q*) ≤ V, i=1..n
∑_{i=1}^n p_i A(i, q*) ≤ ∑_{i=1}^n V p_i
∑_{i=1}^n p_i A(i, q*) ≤ ∑_{i=1}^n V p_i
A(p, q*) ≤ V
A(p, q*) ≤ V
-
В итоге плучится, что A(p,q*) ≤ V ≤ A(p*, q). Это значает, что (p*, q*, V) — решение.
+
В итоге получится, что A(p,q*) ≤ V ≤ A(p*, q). Это означает, что (p*, q*, V) — решение.
Пример.
Пример.
Строка 211: Строка 213:
Решение: ((1/2, 1/2), (1/2, 1/2), 1/2)
Решение: ((1/2, 1/2), (1/2, 1/2), 1/2)
-
Мжн докзать, что _I_ ≤ V ≤ ~I~ (докзать дома)
+
Можно доказать, что _I_ ≤ V ≤ ~I~ (доказать дома)
3. Справедливы следующие равенства:
3. Справедливы следующие равенства:
Строка 232: Строка 234:
V = min_q max_p A(p,q) = min_q max_i A(i,q)
V = min_q max_p A(p,q) = min_q max_i A(i,q)
-
Cл2. (доказать самстоятельно) (p*, q*, V) — решение т и тт, к min_ A(p*, j) = max_i A(i, q*) = V
+
Cл2. (доказать самостоятельно) (p*, q*, V) — решение тогда и только тогда, когда min_ A(p*, j) = max_i A(i, q*) = V
-
В это св-в тоже заложен некий алг. поиска решения.
+
В этом свойстве тоже заложен некий алгоритм поиска решения.
Св4. (p*, q*, V) — решение
Св4. (p*, q*, V) — решение
Строка 240: Строка 242:
1) q*_{j_0} > 0 ← A(p*, j_0) = V
1) q*_{j_0} > 0 ← A(p*, j_0) = V
-
Дкажем первую часть.
+
Докажем первую часть.
пусть p*_{i_0} > 0, A(i_0, q*) ≤ V
пусть p*_{i_0} > 0, A(i_0, q*) ≤ V
Строка 248: Строка 250:
Св5. P*, Q* — компакты.
Св5. P*, Q* — компакты.
-
Док-во. Выпуклсть: p_1, p62 ∈ P*, α ∈ (0,1)
+
Доказательство. Выпуклость: p_1, p62 ∈ P*, α ∈ (0,1)
~p = αp^1 + (1-α)p^2 ∈ P_n
~p = αp^1 + (1-α)p^2 ∈ P_n
-
Осталось доказать, что это оптимальная стратегия. Все линейнсти можн записть след. брзм: A(~p, j) = αA(p^1, j) + (1-α)A(p^2,j) ≥ αV + (1-α)V=V
+
Осталось доказать, что это оптимальная стратегия. Все линейности можно записать следующим образом: A(~p, j) = αA(p^1, j) + (1-α)A(p^2,j) ≥ αV + (1-α)V=V
A(~p, j) ≥ V, ∀ j=1..m
A(~p, j) ≥ V, ∀ j=1..m
Строка 267: Строка 269:
p^0 ∈ P*
p^0 ∈ P*
-
В след раз мы покажем, что крйних тчек конеч. число, и тогда это многогрнник. Тгда же будет укзн способ нахожд. крайнихз точек.
+
В следующий раз мы покажем, что крайних точек конечное число, и тогда это многогранник. Тогда же будет указан способ нахождения крайних точек.
Раздел: доминирование матричных строк и столбцов
Раздел: доминирование матричных строк и столбцов
-
Предп, что одна из стрк каз. меньше других, то первому игроку выгднее её вычеркнуть и не рассм. Аналогично для второго игрока.
+
Предположим, что одна из строк оказалась меньше других, то первому игроку выгоднее её вычеркнуть и не рассматривать. Аналогично для второго игрока.
-
Теорема. Если нек. стрк матрицы A = ||A_ij|| доминируется (строго доминируется) выпуклой линейной комб. ост. строк, то эта строка входит с нулевой верятнстью в некрую (любую) опт. смеш. стратю. первг игрока (и её мжн вычеркнуть).
+
Теорема. Если некоторая строка матрицы A = ||A_ij|| доминируется (строго доминируется) выпуклой линейной комбинацией остальных строк, то эта строка входит с нулевой вероятностью в некоторую (любую) оптимальную смешанную стратегию первого игрока (и её можно вычеркнуть).
-
Теорема. Если нек. столбец матрицы A = ||A_ij|| доминирует (строго доминирует) выпуклую лин. комб. ост. стролбцов, то этот столбец входит с нулевой вероятнстью в некрую (любую) опт. смеш. стратю. второго игрока (и его можно вычеркнуть).
+
Теорема. Если некоторый столбец матрицы A = ||A_ij|| доминирует (строго доминирует) выпуклую линейную комбинацию остальных столбцов, то этот столбец входит с нулевой вероятностью в некоторую (любую) оптимальную смешанную стратегию второго игрока (и его можно вычеркнуть).
-
Нестргое доминирование. Пусть нек-рая строка матр. нестрог доминируется. Чт это значит:
+
Нестрогое доминирование. Пусть некоторая строка матрицы нестрого доминируется. Что это значит:
-
Взьмём α+i ≥ 0, &sum_{i≠i_0} α_i = 1, ∑ α_i a_i ---вып. лин. комб.
+
Возьмём α+i ≥ 0, &sum_{i≠i_0} α_i = 1, ∑ α_i a_i — выпуклая линейная комбинация
-
Дминируется: a_ij ≤ ∑_{i≠i_0} αa_ij, j=1..m --- нестр. доминир.
+
Доминируется: a_ij ≤ ∑_{i≠i_0} αa_ij, j=1..m --- нестрогое доминирование
-
a_ij < ∑_{i≠i_0} αa_ij, j=1..m --- стр. доминир.
+
a_ij < ∑_{i≠i_0} αa_ij, j=1..m --- строгое доминирование
p* ∈ P*
p* ∈ P*
Строка 296: Строка 298:
~p ∈ P_n
~p ∈ P_n
-
Осталось показть, что это оптим. смеш. страт.
+
Осталось показать, что это оптимальная смешанная стратегия
A(~p, ) = ∑_{i ≠ i_0} (p*_i + α_i p*_{i_0}) a_ij = ∑_{i ≠ i_0} p*_i a_ij + p*_{i_0} ∑_{i ≠ i_0} ....
A(~p, ) = ∑_{i ≠ i_0} (p*_i + α_i p*_{i_0}) a_ij = ∑_{i ≠ i_0} p*_i a_ij + p*_{i_0} ∑_{i ≠ i_0} ....
Строка 302: Строка 304:
A(~p, ) ≥ V
A(~p, ) ≥ V
-
Случй строгого дминирвания:
+
Случай строгого доминирования:
-
Надо дказать, что p*_{i_0} = 0. Пусть p*_{i_0} ≥ 0. Тогда V=A(i_0, q*) = ∑_j a_{{i_0}j} q*_j < ∑_j (∑_{i≠i_0} α_i a_ij) q*_i = ∑_j α_i ∑_j a_ij q*_i = ... V < V — противоречие.
+
Надо доказать, что p*_{i_0} = 0. Пусть p*_{i_0} ≥ 0. Тогда V=A(i_0, q*) = ∑_j a_{{i_0}j} q*_j < ∑_j (∑_{i≠i_0} α_i a_ij) q*_i = ∑_j α_i ∑_j a_ij q*_i = ... V < V — противоречие.
Пример
Пример
Строка 311: Строка 313:
4 2 4 0
4 2 4 0
0 4 0 8
0 4 0 8
-
Первя строка меньше третьей, след., она доминир., но нестрого. Но если мы ищем хотя бы дн реш., то мы её мжем вычеркнуть.
+
Первая строка меньше третьей, следовательно, она доминируется, но нестрого. Но если мы ищем хотя бы одно решение, то мы её можем вычеркнуть.
3 4 2 4
3 4 2 4
4 2 4 0
4 2 4 0
0 4 0 8
0 4 0 8
-
Сравним 1 и 3 стобцы. 1 ≥ 3. Имеет место доминир. столбцов, и его можно вычеркнуть.
+
Сравним 1 и 3 столбцы. 1 ≥ 3. Имеет место доминирование столбцов, и его можно вычеркнуть.
4 2 4
4 2 4
2 4 0
2 4 0
4 0 8
4 0 8
-
Первый столбец доминирует л. к. 2 и 3 столбцв с коэф. 0.5. Оаять первый столбец вычёркиваем.
+
Первый столбец доминирует линейную комбинацию 2 и 3 столбцов с коэффициентом 0.5. Опять первый столбец вычёркиваем.
2 4
2 4
4 0
4 0
0 8
0 8
-
Здесь доминир. строк. доминируется 1 строчка ЛК 2 и 3 с коэф 0.5
+
Здесь доминирование строк. доминируется 1 строчка линейной комбинацией 2 и 3 с коэффициентом 0.5
4 0
4 0
0 8
0 8
-
Не бхъясняя, как мы ищем реш, то для посл. игры решение такое: p*' = (2/3, 1/3), q*' = (2/, 1/3), w=8/3.
+
Не объясняя, как мы ищем решение, то для последней игры решение такое: p*' = (2/3, 1/3), q*' = (2/, 1/3), w=8/3.
{{Тигры}}
{{Тигры}}
{{Lection-stub}}
{{Lection-stub}}

Текущая версия

Осталось доказать, что ...

x ∈ X, y ∈ Y, t ∈ (0,1)

K((1-t)x*+tx+y) > (1-t)k(x*,y) + tK(x, y) ≥ (1-t)_w_(x*) + tK(x,y)

ỹ = y((1-t)x* + tx) --- это верно при фиксированном ...

_w_(x*) ≥ _w_((1-t)x* + tx) > (1-t)_w_(x*) + tk(x, ỹ) --- мы расписали это соотношение при y=ỹ

t_w_(x*) &gy; tK(x,ỹ)

_w_(x*) > K(x, y((1-t)x* + tx))

Это соотношение справедливо ∀t ∈ (0,1). Устремим t к 0. Что получится:

_w_(x*) ≥ K(x,y(x*)) (здесь мы используем доказанную в начале непрерывность)


Левая величина _w_(x*) = K(x*, y(x*))

То есть показано, что это — седловая точка.

Теперь откажется от строгости выпуклости/вогнутости.

Введём функцию K_ε(x,y) = K(x,y) - ε &sum_{i=1}^n x_i^2 + ε &sum_{j=1}^m y_j^2, ε > 0

Так как каждое из слагаемых строго выпукло по x/y, то и сумма тоже строго выпукла по x и y. Следовательно, для неё верно только что доказанное утверждение: (x_ε, y_ε) — седловая точка. K_ε(x,y)

K_ε(x,y_ε) ≤ K_ε(x_ε,y_ε) < K_ε(x_ε,y), ∀ x ∈ X, y ∈ Y

K(x, y_ε) — ε &sum_{i=1}^n x_i^2 ≤ K_ε(x,y_ε) ≤ K_ε(x_ε,y_ε) ≤ K(x_ε,y) + ε &sum_{j=1}^m y_j^2

Итог следующий:

K(x, y_ε) — ε &sum_{i=1}^n x_i^2 ≤ K_ε(x_ε,y_ε) ≤ K(x_ε,y) + ε &sum_{j=1}^m y_j^2, ∀ x ∈ X, y ∈ Y

Теперь ε_n → 0, n → ∞, ε_n > 0. Тогда эти слагаемые устремляются к нулю, из ограниченной последовательности можно выделить сходящуюся, соответственно, без ограничения общности y_{ε_n} → y*, x_{ε_n} → x*, и получаем

K(x, y*) ≤ K(x*, y), из этого условия мы доказывали ранее, что K(x*, y*) — седловая точка.

Важно отметить, что эти условия являются достаточными, но не необходимыми.

Пример (условие не является необходимым):

K(x,y) = x^e + 0×y, x, y ∈ [0,1]. (1,1) — седловая точка. (доказать дома)

Пример:

K(x,y) = y ln(x+3) + xy^2, x, y ∈ [0,1]

Условия теоремы фон Неймана выполняются:

K_{x}' = y/(x+3) + y^2

K_{xx} = –y/(x+3)^2 ≤ 0 — вогнута по x

K_{y}' = ln(x+3) + 2xy

K_{yy} = 2x ≥ 0 — выпукла по y.

Условие теоремы фон Неймана выполнено, и есть седловая точка (показать дома, что это (1,0))

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

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

Раздел: необходимое условие для седловой точки

Рассмотрим следующий случай: множество стратегий X имеет следующий вид: X={x=(x_1, ..., x_n), 0 ≤ a_i ≤ x_i ≤ b_i, i = 1..n}, Y={y=(y_1, ..., y_m), 0 ≤ c_i ≤ y_j ≤ d_j, j = 1..m}

Предполагаем, что K(x, y) непрерывно на X× Y и имеет частную производную K_{x_i}', K_{y_j}', i=1..n, j=1..m.

Прежде, чем вып. след. деёств, рассмотрим систему:

K_{x_i}'(x, y)(x_i - a_i)(x_i - b_i) = 0, i=1..n
K_{y_j}'(x, y)(y_j - c_j)(y_j - d_j) = 0, j=1..m (*)

Предположим, что эта система имеет решение и множество решений конечно. Тогда пр. следующие множества: те x из X, что:

X^c = {x ∈ X: ∃y ∈ Y, (x,y) ∈ X}

....

Теорема. Если (x_0, y^0) — седловая точка K(x,y) на X×Y, то (x_0, y^0) ∈ C, (x_0, y^0) — c.т. K на X^c×Y^c

Эта теорема даёт нам алгоритм поиска седловой точки. Пусть есть такая функция и выполнены все условия мы выписываем систему уравнений (*), решаем её, получаем, что множество решений конечно. Выписываем множество X^c×Y^c, и получаем матричную игру, и тут уже искать просто.

Еcли с.т. у K есть, то она обязательно войдёт в число точек матричной игры. То есть решаем матричную игру и проверяем, будет ли каждая из седловых точек для исходной игры.

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

K(x,y^0) ≤ K(x^0, y^0) ≤ K(x^0, y), ∀ x ∈ X, y ∈ Y

max_{x_i ∈ [a_i, b_i]} K(x^0_1_j, ..., x^0_i, ..., x&0_n, y^0_1, y^0_m) = K(x^0, y^0)

K'_{x_i}(x^0, y^0) = 0 либ x_i^n=a_i, либ x^0_i=b_i

Таким образом мы доказали первую часть.

Вторая часть: если мы берём первое соотношение, и оно верно при ∀ x ∈ X, y ∈ Y, то оно верно и при ∀ x ∈ X^c, y ∈ Y^c

Таким образом мы получили алгоритм.

Пример.

K(x,y)=8(4xy^2-2x^2-y), x,y∈[0,1]

Сначала проверим, выполнены ли условия теоремы фон Неймана. По x она вогнута и по y она выпукла. Отсюда по теореме фон Неймана существует седловая точка.

Теперь будем строить систему уравнений (*):

K'_x=8(4y^2-4x), K'_y=8(8xy-1)

(y^2-x)(x-0)(x-1) = 0
(8xy-1)(y-0)(y-1) = 0

решаем эту систему: (0,0), (0,1), (1,0), (1,1), (1, 1/8), (1/4, 1/2) --- построили множество C

X^c = {0, 1/4, 1}, Y^c = {0, 1/8, 1/2, 1}

Теперь строим матричную игру:

x^c \ y^c  0   1/8  1/2   1
 0         0    -1   -4  -8
1/4       -1 -15/8   -3   1
 1       -16 -33/2  -12   8

седловая точка --- (1/4, 1/2). Дальше надо, вообще говоря, проверить все полученные седловые точки.

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

[править] Смешанные стратегии в антагонистических играх

Когда рассматривается игра с платёжной матрицей A = ||a_ij||, i=1..n, j=1..m. Каждый выбирает i/j соответственно, и один получает a_ij, другой -a_ij

Игра обычно разыгрывается много раз. При этом возникает понятие p=(p_1, ..., p_n), p_i > 0, ∑_{i=1}^n p_i=1 --- вектор вероятности выбора стратегии i --- смешанная стратегия первого игрока. Множество этих стратегий P_n = {p=(p_1, ..., p_n), p_i > 0, ∑_{i=1}^n p_i=1}. Аналогично для второго игрока: Q_m = {q=(q_1, ..., q_m), q_j > 0, ∑_{j=1}^m q_j=1}.

Пусть p∈ P_n, q ∈ Q_n. Как считается результат? считается матожидание платежа. Платёж a_ij первый игрок получает при выборе стратегии i и выборе стратегии j вторым игроком. Но первый игрок выбирает с вероятностью p_i, а второй — q_j. Вероятность данного выбора --- p_i×q_j. Тогда выигрыш равен A(p,q) = &sum_{i=1}^n ∑_{j=1}^m a_ij p_i q_j. Это показывает, какой выигрыш получат игроки, если выбрали стратегии p, q.

От игры с платёжной матрицей A мы перешли к игре с платёжной функцией A(p,q).

A(p,j) = &sum_{i=1}^n a_ij p_i, A(i, q) = ∑_{j=1}^m a_ij q_j

A(p,q) = ∑_{j=1}^m A(p,j) q_j = &sum_{i=1}^n A(i, q) p_i

Каждый игрок по прежнему действует по принципу максимальной выгоды, тогда получим:

max_{p∈P_n} min_{q∈Q_m} A(p,q) = min_{q∈Q_m} A(p^0,q)

min_{q∈Q_m} max_{p∈P_n} A(p,q) = max_{p∈P_n} A(p,q^0)

В такой игре всегда существует седловая точка.

Л1. P_n, Q_m — выпуклые компакты.

1) p^1, p^2 ∈ P_n, α ∈ (0,1) Рассмотрим αp^1 + (1-α)p^2 Тогда

αp^1 + (1-α)p^2 ≥ 0
∑_{i=1}^n(αp_i^1 + (1-α)p_i^2) = α ∑_{i=1}^n p_i^1 + (1-α) ∑_{i=1}^n p_i^2 = 1

2) p^k ←_{k ← ∞} p^0, p^k ∈ P_n

p_i^k ≥ 0 ⇒ p_i^0 ≥ 0
∑_i=1^n p_i^k = 1
lim_{k &rasrr; ∞} ∑_i=1^n p_i^k = 1
∑_i=1^n lim_{k &rasrr; ∞} p_i^k = ∑_i=1^n p_i^0

Из определений P и Q. Мы делаем вывод, что A(p,q) непрерывна, и является линейной. Значит, она и выпукла, и вогнута по любой переменной. То есть, она вогнута по p и выпукла по q. По теореме фон Неймана существует седловая точка. Т.о., мы доказали теорему "в матричной игре всегда существует смешанная стратегия". Ну и поскольку мы отметили, что функция A(p,q) — непрерывна, а множества смешанных стратегий являются компактными, то это позволяло писать max/min.

Ну и вообще, мы делаем какой вывод: max min и min max равны. Это следствие из теоремы.

Как решать матричные игры в смешанных стратегиях: нужно найти любую седловую точку.

Отметим ещё раз, что если p*, q* --- оптимальные стратегии, то (p*, q*) — седловая точка.

Отметим свойства оптимальных смешанных стратегий. Тройкой (p*, q*, V) будем называть решение игры. V = max_p nim_q A(p,q) = min_q max_p A(p,q) = A(p*, q*) Когда нам будет дана со смешанной стратегией, то целью будет являться решение игры. Таких троек может быть много. Для поиска таких троек небходимо знать свойства оптимальных смешанных стратегий.

1. Если (p*, q*, V) — решение игры с матрицей A, то (p*, q*, V+c) — решение игры с матрицей Ã = ||a_ij + c||, c=const. Мы прибавили константу ко всем элементам матрицы. Что меняется? Множество решений не меняется, меняется только значение игры. Докажем:

A(p,q) + c = A(p,q) + c(∑_i=1^n p_i)(∑_i=j^m q_j) = &sum_{i=1}^n ∑_{j=1}^m (a_ij + c) p_i q_j = Ã(p,q)

Пусть выполнено условие, и A(p*, q*) — седловая точка. Тогда

A(p,q*) ≤ A(p*, q*) ≤ A(p*, q)
Прибавим константу c:
A(p,q*) + c ≤ A(p*, q*) + c ≤ A(p*, q) + c
Ã(p,q*) ≤ A(p*, q*) + с ≤ Ã(p*, q)

Теперь из утверждения, доказанного на прошлой лекции, следует, что (p*, q*) обращает седловую точку и (p*, q*, V+с) — решение игры

2. Тройка (p*, q*, V) является решением игры тогда и только тогда, когда A(i, q*) ≤ V ≤ A(p*,j), ∀ i=1..n, j=1..m

Доказательство. 1)Пусть (p*, q*, V) — решение. Тогда:

A(p,q*) ≤ A(p*, q*) = V ≤ A(p*, q), ∀ p ∈ P_n, q ∈ Q_m

Т.к. оно верно для всех p, q, то можно взять p=(0...0, 1 (i-е место), ..., 0) ∈ P_n, q=(0...0, 1 (j-е место), ..., 0) ∈ Q_m, и сразу получаем эти соотношения.

2)Пусть выполнены соотношения: A(p,q*) ≤ A(p*, q*) = V ≤ A(p*, q), ∀ p ∈ P_n, q ∈ Q_m

Возьмём произвольным p, q. Возьмём соотношение A(i, q*) ≤ V, i=1..n

∑_{i=1}^n p_i A(i, q*) ≤ ∑_{i=1}^n V p_i
A(p, q*) ≤ V

В итоге получится, что A(p,q*) ≤ V ≤ A(p*, q). Это означает, что (p*, q*, V) — решение.

Пример.

1 0
0 1

Решение: ((1/2, 1/2), (1/2, 1/2), 1/2)

Можно доказать, что _I_ ≤ V ≤ ~I~ (доказать дома)

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

1) ∀ p ∈ P_n min_q A(p,q)=min_j A(p,j)
2) ∀ q ∈ Q_m max_p A(p,q)=max_i A(i,q)

Докажем первую часть, вторая доказывается аналогично. Покажем сначала, что лч≤ пч, потом что лч≥пч.

a) min_{j=1..m} A(p, j) = min_j A(p, q^j), q^j = (0..., 1(j-е место), ..., 0)

min_j A(p, q^j) ≥ min_q A(p, q)

b) min_q A(p,q) = min_q ∑_{j=1}^n ≤ min_q &sum_j q_j (min_j ∑ a_ij p_j) = min_j ∑ a_ij p_j (min_q &sum_j q_j (=1)) = min_j ∑ a_ij p_j = A(p, j)

min_j A(p, q^j) ≤ min_q A(p, q)

Отсюда равенство.

Следствия.

Сл1. V = max_p min_q A(p,q) = max_p min_j A(p,j)

    V = min_q max_p A(p,q) = min_q max_i A(i,q)

Cл2. (доказать самостоятельно) (p*, q*, V) — решение тогда и только тогда, когда min_ A(p*, j) = max_i A(i, q*) = V

В этом свойстве тоже заложен некий алгоритм поиска решения.

Св4. (p*, q*, V) — решение

1) p*_{i_0} > 0 ← A(i_0, q*) = V
1) q*_{j_0} > 0 ← A(p*, j_0) = V

Докажем первую часть.

пусть p*_{i_0} > 0, A(i_0, q*) ≤ V

V=A(p*, q*) = ∑_i A(i,q*) (≤ V) p_i* + A(i_0, q*) {<V} p*_i (>0) < V(1-p*_{i_0}) + Vp*_i_0 = V — противречие

Св5. P*, Q* — компакты.

Доказательство. Выпуклость: p_1, p62 ∈ P*, α ∈ (0,1) ~p = αp^1 + (1-α)p^2 ∈ P_n Осталось доказать, что это оптимальная стратегия. Все линейности можно записать следующим образом: A(~p, j) = αA(p^1, j) + (1-α)A(p^2,j) ≥ αV + (1-α)V=V

A(~p, j) ≥ V, ∀ j=1..m

P* — огр, p* ←_{k ← ∞} p^0

p_k ∈ P*, p^0 ∈ P_n

A(p^k, ) ≥ V, &orall; j=1..m

lim_{k ← ∞} A(p^k+) ≥ V

A(lim_{k ← ∞} p*, ) ≥ V

A(p^0, j) ≥ V, J=1..m

p^0 ∈ P*

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

Раздел: доминирование матричных строк и столбцов

Предположим, что одна из строк оказалась меньше других, то первому игроку выгоднее её вычеркнуть и не рассматривать. Аналогично для второго игрока.

Теорема. Если некоторая строка матрицы A = ||A_ij|| доминируется (строго доминируется) выпуклой линейной комбинацией остальных строк, то эта строка входит с нулевой вероятностью в некоторую (любую) оптимальную смешанную стратегию первого игрока (и её можно вычеркнуть).

Теорема. Если некоторый столбец матрицы A = ||A_ij|| доминирует (строго доминирует) выпуклую линейную комбинацию остальных столбцов, то этот столбец входит с нулевой вероятностью в некоторую (любую) оптимальную смешанную стратегию второго игрока (и его можно вычеркнуть).

Нестрогое доминирование. Пусть некоторая строка матрицы нестрого доминируется. Что это значит:

Возьмём α+i ≥ 0, &sum_{i≠i_0} α_i = 1, ∑ α_i a_i — выпуклая линейная комбинация

Доминируется: a_ij ≤ ∑_{i≠i_0} αa_ij, j=1..m --- нестрогое доминирование

a_ij < ∑_{i≠i_0} αa_ij, j=1..m --- строгое доминирование

p* ∈ P*


~p_i = 0, i=i_0
       p*_i + α_i p*_{i_0}, i ≠ i_0i ≠ i_0

~p_i ≥ 0

∑_i ~p_i = ∑_{} (p*_i+α_i p*_{i_0}) = ∑_{i ≠ i_0}p*_i + p*_{i_0} &sum_{i ≠ i_0} &slphs;_i = ∑_i p*_i = 1

~p ∈ P_n

Осталось показать, что это оптимальная смешанная стратегия

A(~p, ) = ∑_{i ≠ i_0} (p*_i + α_i p*_{i_0}) a_ij = ∑_{i ≠ i_0} p*_i a_ij + p*_{i_0} ∑_{i ≠ i_0} ....

A(~p, ) ≥ V

Случай строгого доминирования:

Надо доказать, что p*_{i_0} = 0. Пусть p*_{i_0} ≥ 0. Тогда V=A(i_0, q*) = ∑_j a_{{i_0}j} q*_j < ∑_j (∑_{i≠i_0} α_i a_ij) q*_i = ∑_j α_i ∑_j a_ij q*_i = ... V < V — противоречие.

Пример

3 2 4 0
3 4 2 4
4 2 4 0
0 4 0 8

Первая строка меньше третьей, следовательно, она доминируется, но нестрого. Но если мы ищем хотя бы одно решение, то мы её можем вычеркнуть.

3 4 2 4
4 2 4 0
0 4 0 8

Сравним 1 и 3 столбцы. 1 ≥ 3. Имеет место доминирование столбцов, и его можно вычеркнуть.

4 2 4
2 4 0
4 0 8

Первый столбец доминирует линейную комбинацию 2 и 3 столбцов с коэффициентом 0.5. Опять первый столбец вычёркиваем.

2 4
4 0
0 8

Здесь доминирование строк. доминируется 1 строчка линейной комбинацией 2 и 3 с коэффициентом 0.5

4 0
0 8

Не объясняя, как мы ищем решение, то для последней игры решение такое: p*' = (2/3, 1/3), q*' = (2/, 1/3), w=8/3.



Теория игры и исследования операций


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16


Календарь

Сентябрь
04 11 18 25
Октябрь
02 09 16 23 30
Ноябрь
06 13 20 27
Декабрь
04 11 18



Материалы по курсу
Контрольная 1 | Контрольная 2 | Контрольная 3


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы