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

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

Перейти к: навигация, поиск

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

Текущая версия Ваш текст
Строка 1: Строка 1:
* '''Аудиозапись:''' http://esyr.org/lections/audio/game_theory_2008_winter/GT_08_09_11.ogg
* '''Аудиозапись:''' 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)
Строка 7: Строка 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,ỹ)
Строка 15: Строка 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
Строка 38: Строка 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) — седловая точка. (доказать дома)
Строка 52: Строка 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
Строка 62: Строка 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}
Строка 83: Строка 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
Строка 99: Строка 99:
Таким образом мы доказали первую часть.
Таким образом мы доказали первую часть.
-
Вторая часть: если мы берём первое соотношение, и оно верно при ∀ x ∈ X, y ∈ Y, то оно верно и при ∀ x ∈ X^c, y ∈ Y^c
+
Втрая часть: если мы берём первое соотн, и оно верно при ∀ x ∈ X, y ∈ Y, то оно верно и при ∀ x ∈ X^c, y ∈ Y^c
-
Таким образом мы получили алгоритм.
+
Таким обр. мы получили алгоритм.
Пример.
Пример.
Строка 107: Строка 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)
Строка 115: Строка 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
Строка 125: Строка 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, ∑_{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, &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_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
Строка 143: Строка 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)
Строка 149: Строка 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
Строка 165: Строка 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)
Строка 186: Строка 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) — решение.
Пример.
Пример.
Строка 213: Строка 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. Справедливы следующие равенства:
Строка 234: Строка 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) — решение
Строка 242: Строка 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
Строка 250: Строка 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
Строка 269: Строка 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*
Строка 298: Строка 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} ....
Строка 304: Строка 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 — противоречие.
Пример
Пример
Строка 313: Строка 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}}

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!


Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://libesyr.so/wiki/%D0%A2%D0%B8%D0%B3%D1%80%D1%8B%2C_02_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_11_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29
Разделы