Редактирование: Тигры, 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, ỹ) --- | + | _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,ỹ) | ||
| Строка 17: | Строка 17: | ||
Это соотношение справедливо ∀t ∈ (0,1). Устремим t к 0. Что получится: | Это соотношение справедливо ∀t ∈ (0,1). Устремим t к 0. Что получится: | ||
| - | _w_(x*) ≥ K(x,y(x*)) (здесь мы используем доказанную в начале | + | _w_(x*) ≥ K(x,y(x*)) (здесь мы используем доказанную в начале непр.) |
| Строка 62: | Строка 62: | ||
K_{yy}'' = 2x ≥ 0 — выпукла по y. | K_{yy}'' = 2x ≥ 0 — выпукла по y. | ||
| - | Условие теоремы фон Неймана выполнено, и есть седловая точка (показать дома, | + | Условие теоремы фон-Неймана выполнено, и есть седловая точка (показать дома, чт это (1,0)) |
Теорема конструктивная и вообще говоря, ей можно пользоваться для нахождения седловой точки. | Теорема конструктивная и вообще говоря, ей можно пользоваться для нахождения седловой точки. | ||
| Строка 85: | Строка 85: | ||
'''Теорема'''. Если (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, и получаем матричную игру, и тут уже искать просто. |
Е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 | |
Таким образом мы получили алгоритм. | Таким образом мы получили алгоритм. | ||
| Строка 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 она выпукла. Отсюда по теореме фон-Неймана существует седловая точка. |
Теперь будем строить систему уравнений (*): | Теперь будем строить систему уравнений (*): | ||
| Строка 127: | Строка 127: | ||
седловая точка --- (1/4, 1/2). Дальше надо, вообще говоря, проверить все полученные седловые точки. | седловая точка --- (1/4, 1/2). Дальше надо, вообще говоря, проверить все полученные седловые точки. | ||
| - | Но поскольку мы установили, что по теореме фон Неймана есть одна седловая точка, а получили мы их максимум одну, то их ровно одна. | + | Но поскольку мы установили, что по теореме фон-Неймана есть одна седловая точка, а получили мы их максимум одну, то их ровно одна. |
== Смешанные стратегии в антагонистических играх == | == Смешанные стратегии в антагонистических играх == | ||
| Строка 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 равны. Это следствие из теоремы. | ||
