<< Предыдущая

стр. 151
(из 163 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

Поскольку функция ui(?) достигает максимума в точках z? и z??, то строгое неравенство
здесь невозможно. Таким образом,
?z? + (1–?)z?? ? Ri(x–i).
Докажем теперь полунепрерывность сверху отображения Ri(?). Рассмотрим последова-
n n n
- -
тельность xi сходящуюся к xi и последовательность x–iсходящуюся к x–i, причем xi
? Ri(x–i). Заметим, что в силу компактности множеств Xj xi ? Xi и x–i ? X–i . Нам нужно
n
- -
доказать, что xi? Ri(x–i). По определению отображения отклика
- -
u(xi , x–i) > u(xi, x–i) ?xi ? Xi, ?n.
n n n


Из непрерывности функции ui(?) следует, что
u(xi, x–i) > u(xi, x–i) ?xi ? Xi.
-- -
Тем самым, по введенному выше определению отображения отклика, xi ? Ri(x–i).
- -
Опираясь на доказанные только что свойства отображения Ri(?) и на теорему Какутани,
докажем существование равновесия по Нэшу, то есть такого набора стратегий x* ? X, для
которого выполнено
645
646
x* ? Ri(x–i) ? i = 1, ..., n.
*
i

Определим отображение R(?) из X в X следующим образом:
R(x) = R1(x–1) ? ... ? Rn(x–n).
Отметим, что это отображение удовлетворяет тем же свойствам, что и каждое из отобра-
жений Ri(?), так как является их декартовым произведением.
Отображение R(?) и множество X удовлетворяют свойствам, которые необходимы для
выполнения теоремы Какутани. Таким образом, существует неподвижная точка отобра-
жения R(?):
x* ? R(x*).
Очевидно, что точка x* есть равновесие по Нэшу. *

Приложение B
В этом приложении мы формально докажем утверждения о связи между равновесием Нэ-
ша и процедурой последовательного отбрасывания строго доминируемых стратегий.
Сначала определим формально процедуру последовательного отбрасывания строго доми-
нируемых стратегий. Пусть исходная игра задана как
G = ?I, {Xi}I , {ui}I ?.
[t]
Определим последовательность игр {G }t=0,1,2,..., каждая из которых получается из после-
дующей игры отбрасыванием строго доминируемых стратегий. Игры отличаются друг от
друга множествами допустимых стратегий:
G = ?I, {X i }I , {ui}I ?.
[t] [t]

[0]
Процедура начинается с G = G.
Множество допустимых стратегий i–го игрока на шаге t+1 рассматриваемой процедуры
берется равным множеству не доминируемых строго стратегий i–го игрока в игре t-го ша-
га. Множества не доминируемых строго стратегий будем обозначать через NDi (см. опре-
деление строго доминируемых стратегий (Определение 6, стр. 635)). Формально
NDi = {xi?Xi | ! ? yi?Xi : ui(yi, x–i) > ui(xi, x–i) ?x–i?X–i}.
Таким образом, можно записать шаг рассматриваемой процедуры следующим образом:
[t+1] [t]
= ND i ,
Xi
[t] [t]
где ND i — множество не доминируемых строго стратегий в игре G .
Приведем теперь доказательства Теорем 1 и 2 (стр. 640). Теорема 1 утверждает следую-
щее:


* *
Если x* = (x1, ..., xm) — равновесие Нэша в некоторой игре, то ни одна из стратегий не
может быть отброшена в результате применения процедуры последовательного отбра-
сывания строго доминируемых стратегий.


Если использовать только что введенные обозначения, то Теорема 1 утверждает, что если
x* — равновесие Нэша в исходной игре G, то на любом шаге t выполнено
x* ? X i , ? i?I, ? t = 1, 2, ...
[t]
i



646
647
или
x* ? X , ? t = 1, 2, ... .
[t]




Доказательство Теоремы 1:
Пусть есть такой шаг ?, что на нем должна быть отброшена стратегия x* некоторого игро-
i
ка i?I. Предполагается, что на предыдущих шагах ни одна из стратегий не была отброше-
на:
x* ? X , ?t = 1, ..., ?.
[t]


По определению строгого доминирования существует другая стратегия игрока i, x? ? X[?],
i
i
которая дает этому игроку в игре G более высокий выигрыш при любых выборах других
[?]

игроков:
ui(x?, x–i) > ui(x*, x–i) ?x–i?X[?] .
–i
i i

В том числе, это соотношение должно быть выполнено для x–i, поскольку мы предполо-
*

жили, что стратегии x–i не были отброшены на предыдущих шагах процедуры (x–i?X[?] ).
* *
–i
Значит,
ui(x?, x–i) > ui(x*, x–i).
* *
i i

Однако это неравенство противоречит тому, что x* — равновесие Нэша. *


Докажем теперь Теорему 2. Напомним ее формулировку:


Если в результате последовательного отбрасывания строго доминируемых стратегий у
* * *
каждого игрока остается единственная стратегия, xi , то x* = (x1, ..., xm) — равновесие
Нэша в этой игре.


Данная теорема относится к случаю, когда в процессе отбрасывания строго доминируе-
мых стратегий начиная с некоторого шага - остается единственный набор стратегий, x*,
t
т.е.
X i = {x*} , ? i?I, ?t = 1, ..., -.
[t]
t
i

Теорема утверждает, что x* является единственным равновесием Нэша исходной игры.


Доказательство Теоремы 2:
Поскольку, согласно доказанной только что теореме, ни одно из равновесий Нэша не мо-
жет быть отброшено, нам остается только доказать, что указанный набор стратегий x* яв-
ляется равновесием Нэша. Предположим, что это не так. Это означает, что существует
˜
стратегия xi некоторого игрока i, такая что
˜*
ui(x*, x–i) < ui(xi, x–i).
*
i

По предположению, стратегия xi была отброшена на некотором шаге ?, поскольку она не
˜
совпадает с x*. Таким образом, существует некоторая строго доминирующая ее стратегия
i
x??X i , так что
[?]
i



647
648
ui(x?, x–i) > ui(xi, x–i) ?x–i?X[?] .
˜ –i
i

В том числе это неравенство выполнено при x–i = x–i:
*


ui(x?, x–i) > ui(xi, x–i).
˜*
*
i

Стратегия x? не может совпадать со стратегией x*, поскольку в этом случае вышеприве-
i i
денные неравенства противоречат друг другу. В свою очередь, из этого следует, что
должна существовать стратегия x?, которая доминирует стратегию x? на некотором шаге
i i
?? > ?, т.е.
ui(x?, x–i) > ui(x?, x–i) ?x–i?X[??].
–i
i i

В том числе
ui(x?, x–i) > ui(x?, x–i).
* *
i i

Можно опять утверждать, что стратегия x? не может совпадать со стратегией x*, иначе
i i
вышеприведенные неравенства противоречили бы друг другу.
Продолжая эти рассуждения, мы получим последовательность шагов ? < ?? < ?? < ... и со-
ответствующих допустимых стратегий x?, x?, x??, ..., не совпадающих с x*. Это противоре-
i i i i
чит существованию шага -, начиная с которого множества допустимых стратегий состоят
t
только из x i . *
*




Задачи


1. Два игрока размещают некоторый объект на плоскости, то есть выбирают его коорди-
наты (x, y). Игрок 1 находится в точке (x1, y1), а игрок 2 — в точке (x2, y2). Игрок 1 выби-
рает координату x, а игрок 2 — координату y. Каждый стремиться, чтобы объект находил-
ся как можно ближе к нему. Покажите, что в этой игре у каждого игрока есть строго до-
минирующая стратегия.


2. Докажите, что если в некоторой игре у каждого из игроков существует строго домини-
рующая стратегия, то эти стратегии составляют единственное равновесие Нэша.


3. Объясните, почему равновесие в доминирующих стратегиях должно быть также равно-
весием в смысле Нэша. Приведите пример игры, в которой существует равновесие в до-
минирующих стратегиях, и, кроме того, существуют равновесия Нэша, не совпадающие с
равновесием в доминирующих стратегиях.


Найдите в следующих играх все равновесия Нэша.


4. Игра 2 (стр. 629), выигрыши которой представлены в Таблице 13.


5. «Орехи»
Два игрока делят между собой 4 ореха. Каждый делает свою заявку на орехи: xi = 1, 2 или
3. Если x1 + x2 < 4, то каждый получает сколько просил, в противном случае оба не полу-
чают ничего.
648
649


6. Два преподавателя экономического факультета пишут учебник. Качество учебника (q )
зависит от их усилий (e1 и e2 соответственно) по функции
q = 2(e1 + e2).
Целевая функция каждого имеет вид
ui = q – ei
— качество минус усилия. Можно выбрать усилия на уровне 1, 2 или 3.


7. «Третий лишний»
Каждый из трех игроков выбирает одну из сторон монеты: «орёл» или «решка». Если вы-
боры игроков совпали, то каждому выдается по 1 рублю. Если выбор одного из игроков
отличается от выбора двух других, то он выплачивает им по 1 рублю.


8. Три игрока выбирают одну из трех альтернатив: A, B или C. Альтернатива выбирается
голосованием большинством голосов. Каждый из игроков голосует за одну и только за
одну альтернативу. Если ни одна из альтернатив не наберет большинство, то будет выбра-
на альтернатива A. Выигрыши игроков в зависимости от выбранной альтернативы сле-
дующие:
u1(A) = 2, u1(B) = 1, u1(C) = 0,
u2(A) = 0, u2(B) = 2, u2(C) = 1,
u3(A) = 1, u3(B) = 0, u3(C) = 2.

<< Предыдущая

стр. 151
(из 163 стр.)

ОГЛАВЛЕНИЕ

Следующая >>