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

стр. 147
(из 165 стр.)

ОГЛАВЛЕНИЕ

Следующая >>


Таблица 16.2.

Автомобилист
A B
?102 ?20
A ?110 ?200
?120 ?100
Пешеход
B ?100 ?500


Стандартное предположение теории игр состоит в том, что если выигрыш — случайная ве-
личина, то игроки предпочитают действия, которые приносят им наибольший ожидаемый вы-
игрыш10 . Предполагается, что в описании игры случайные выигрыши даны в таком виде, что
можно рассчитать их математическое ожидание и использовать в качестве выигрышей в нор-
мальной форме игры. Таким образом, выигрыши выражены в некоторых условных единицах
(вовсе не обязательно денежных) и представляют некоторый абстрактный уровень полезности
для игрока при данном сочетании стратегий.
Пусть оба участника игры проявляют осторожность, то есть реализовался исход (A, A).
Если произойдет столкновение, то выигрыш пешехода составит (?1100), а выигрыш водите-
ля — (?300). В противном случае выигрыш пешехода составит (?100), а выигрыш водителя —
(?100). Ожидаемые выигрыши равны в этом случае:

1 99
· (?1100) + · (?100) = ?110 — для пешехода,
100 100
1 99
· (?300) + · (?100) = ?102 — для автомобилиста.
100 100
Аналогичные вычисления нужно провести для трех других исходов. Рассчитанные выиг-
рыши представлены в Таблице 16.2.
Заметьте, что полученная нормальная форма игры не содержит информацию о случайных
ходах природы, их вероятностях и соответствующих случайных выигрышах.

16.2.2 Концепция доминирования
Задача теории игр — по данному описанию игры предсказать, какие стратегии выберут
игроки и каким при этом будет исход игры, или, по крайней мере, сузить множество про-
гнозируемых исходов. В некоторых случаях предсказать исход игры можно однозначно, если
исходить из предположения о том, что каждый игрок рационален.
9
Условных единиц.
10
Здесь, как это обычно делается в экономической теории, предполагается, что определенные на лотереях
предпочтения каждого игрока удовлетворяют условиям, которые гарантируют существование представляющей
их линейной функции полезности (имеется в виду линейность по вероятностям). О линейной функции полезно-
сти (функции Неймана — Моргенштерна) см. главу ??? (ссылка). Исторически соответствующая теория была
разработана для нужд теории игр; см. Дж. фон Нейман, О. Моргенштерн, Теория игр и экономическое пове-
дение, М.: Наука, 1970.
16.2. Статические игры с полной информацией 627
Таблица 16.3.

Игрок 1
IBM Mac
1 3
IBM 3 2
0 4
Игрок 2
Mac 0 1


Пусть в Игре 16.2.1 (с. 624) выгода от совместимости программного обеспечения сравни-
тельно мала, например, a = 2, b = 3, c = 1 (Таблица 16.3). Тогда вне зависимости от того,
какой компьютер выберет 2-й игрок, 1-му игроку выгодно выбрать компьютер IBM PC, по-
скольку 3 > 0 и 2 > 1. Аналогично, 2-й игрок предпочтет Макинтош, поскольку 3 > 1 и
4 > 0. В обоих случаях имеет место так называемое строгое доминирование двух указанных
стратегий: если стратегия A при любых действиях других игроков дает больший выигрыш,
чем стратегия B , то принято говорить, что стратегия A строго доминирует стратегию B .
Дадим формальное определение строгого доминирования. Здесь и в дальнейшем мы будем
применять обозначение x?i , что означает «все элементы вектора x, кроме i-го», т. е.
x?i = (x1 , . . . , xi?1 , xi+1 , xn )
При этом будем считать, что (xi , x?i ).— это то же самое, что x. Все такие наборы стратегий
x?i являются элементами множества X?i = ?j=i Xj .
Определение 84:
Стратегия xi ? Xi игрока i строго доминирует стратегию yi ? Xi , если при любых стра-
тегиях, выбранных остальными игроками, x?i ? X?i , выполнено
ui (xi , x?i ) > ui (yi , x?i ).


u1
u1 (x1 ,x2 )




u1 (y1 ,x2 )
x2



Рис. 16.1. Стратегия x1 строго доминирует стратегию y1 .

Определение строгого доминирования можно наглядно проиллюстрировать в случае двух
игроков, множества стратегий одного из которых — действительная прямая (см. Рис. 16.1).
На рисунке стратегия x1 первого игрока строго доминирует стратегию y1 . Это выражается в
том, что график функции полезности этого игрока по стратегии x2 второго, соответствующий
x1 , лежит ниже графика, соответствующего y1 .
Стратегия называется строго доминирующей, если она строго доминирует любую другую
стратегию.
Определение 85:
Стратегия xi ? Xi игрока i является его строго доминирующей стратегией, если при лю-
бых стратегиях, выбранных остальными игроками, x?i ? X?i , она дает игроку i больший
16.2. Статические игры с полной информацией 628

выигрыш, чем любая другая его стратегия yi ? Xi , т. е.

ui (xi , x?i ) > ui (yi , x?i ) ?x?i ? X?i ?yi ? Xi : yi = xi .

В соответствии с данным определением не может существовать более одной строго доми-
нирующей стратегии. Естественно ожидать, что рациональный игрок выберет именно такую
стратегию. Поэтому при наличии у каждого игрока строго доминирующей стратегии исход
игры может быть предсказан однозначно.
Предсказание исхода игры не столь однозначно, когда у каждого игрока имеется лишь
так называемая (слабо) доминирующая стратегия, обеспечивающая этому игроку не меньший
выигрыш, чем любая другая его стратегия при любых стратегиях других игроков. Приведем
определения (слабого) доминирования.
Определение 86:
Стратегия xi ? Xi игрока i (слабо) доминирует стратегию yi ? Xi (или, другими словами,
стратегия yi доминируется стратегией xi ), если при любых стратегиях, выбранных остальны-
ми игроками, x?i ? X?i , выполнено

ui (xi , x?i ) ui (yi , x?i )

и существует хотя бы один набор стратегий других игроков, x?i ? X?i , такой что

ui (xi , x?i ) > ui (yi , x?i )


u1
u1 (x1 ,x2 )




u1 (y1 ,x2 )
x2



Рис. 16.2. Стратегия x1 (слабо) доминирует стратегию y1 .

Слабое доминирование можно проиллюстрировать на графике, аналогичном тому, который
мы использовали для иллюстрации строгого доминирования. Стратегия x1 первого игрока
слабо, но не строго доминирует его стратегию y1 (см. Рис. 16.2), поскольку график функции
полезности для x1 не везде строго выше, чем для y1 .
Определение 87:
Стратегия xi ? Xi игрока i является его (слабо) доминирующей стратегией, если при любых
стратегиях, выбранных остальными игроками, x?i ? X?i , она доминирует любую другую его
стратегию, yi ? Xi , либо эквивалентна ей, т. е.

ui (yi , x?i ) ?x?i ? X?i ?yi ? Xi
ui (xi , x?i )

Из определения следует, что если стратегия xi строго доминирует стратегию yi , то страте-
гия xi доминирует стратегию yi . Кроме того, если стратегия является строго доминирующей,
то она является доминирующей.
Определение 88:
Исход игры x? ? X является равновесием в доминирующих стратегиях, если стратегия
каждого игрока в этом исходе является его доминирующей стратегией.
16.2. Статические игры с полной информацией 629
Таблица 16.4.

Красные Красные
(А) Белые: за (Б) Белые: против
за против за против
?1 1 ?1 ?1
1 10 0
за за
1 1 1 0
Зеленые Зеленые
?1 10 0 0 00 0
против против
1 0 0 0


Естественно ожидать, что если в игре существует равновесие в доминирующих стратегиях,
то именно оно будет реализовавшимся исходом игры. Следующая игра иллюстрирует равно-
весие в доминирующих стратегиях.
Игра 3. «Парламентское голосование»
Парламент разделен на 3 фракции: «белые», «зеленые» и «красные». В каждой фракции оди-
наковое количество членов. Проходит голосование по некоторому законопроекту. Каждая из
фракций может проголосовать «за» или «против». Решение принимается большинством голо-
сов. Зеленым и красным нравится законопроект, белым — нет. Если законопроект пройдет, то
зеленые и красные получат выигрыш 1, а белые — ?1, в противном случае все получат 0.

Удобно представить исходы игры в виде двух таблиц А и Б (см. Таблицу 16.4). Белые
выбирают между таблицей А и таблицей Б. Их выигрыши записаны в левом верхнем углу
этих таблиц.
Если зеленые проголосуют за, то вектор их выигрышей будет

(1 (за, за), 1 (за, против), 1 (против, за), 0 (против, против))

В скобках указано, как голосуют другие фракции. Если же они проголосуют против, то вектор
выигрышей будет

(1 (за, за), 0 (за, против), 0 (против, за), 0 (против, против))

Очевидно, что голосовать за законопроект является доминирующей стратегией зеленых. То
же самое можно сказать и о красных.
Белые имеют следующие выигрыши (при аналогичных предположениях о том как голосуют
другие фракции):

(?1, ?1, ?1, 0)
за:
против: (?1, 0, 0, 0)

Таким образом, голосовать против законопроекта является доминирующей стратегией бе-
лых (хотя, заметим, эта стратегия не сможет им помочь выиграть).
Тем самым, в этой игре существует равновесие в доминирующих стратегиях. В нем зеленые
и красные голосуют «за», а белые — «против».
Приведем теперь пример игры с непрерывными стратегиями, в который есть равновесие в
доминирующих стратегиях.
Игра 4. «Аукцион Викри»11
?
Некий предмет продается с аукциона по следующим правилам. Каждый из участников аукцио-
на (i = 1, . . . , n) подает в тайне от других свою заявку — предлагаемую им цену pi . Побеждает
11
W. Vickrey: Counterspeculation, Auctions, and Competitive Sealed Tenders, Journal of Finance 16 (1961):
8–37. Уильям Викри стал Нобелевским лауреатом по экономике за 1996 г.
16.2. Статические игры с полной информацией 630

участник, предложивший самую высокую цену, но платит он следующую по порядку убыва-
ния цену. Если самую высокую цену предложат сразу несколько участников, то победитель
определяется жребием. Если i-й участник окажется победителем, то его выигрыш составит
vi ? p, где vi — ценность для него данного предмета, p — цена, которую он должен заплатить;
выигрыш всех остальных участников будет равен нулю.

Особенность аукциона Викри состоит в том, что «правдивая» стратегия является доми-
нирующей стратегией для каждого участника. Под «правдивой» стратегией понимается стра-
тегия, заключающаяся в том, что участник называет цену, совпадающую с ценностью для
него данного предмета, (pi = vi ). Проверим это. Проанализируем данную игру при n = 2.
(При большем количестве участников рассуждения будут аналогичными.) Поскольку участ-
ники входят в данную игру симметрично, то достаточно рассмотреть мотивацию только одного
из них, например, 1-го.
Вычислим сначала выигрыши 1-го игрока при разных исходах. Если 1-й участник назовет
более высокую цену, чем 2-й (p1 > p2 ), то он выиграет аукцион и заплатит p2 . При этом
его выигрыш составит v1 ? p2 . Если 1-й участник назовет более низкую цену, чем 2-й (p1 <
p2 ), то он проиграет аукцион и получит выигрыш 0. Если цены совпадут (p1 = p2 ), то с
вероятностью 1/2 1-й участник выиграет и получит выигрыш v1 ? p2 , а с вероятностью 1/2
он проиграет и получит выигрыш 0. Таким образом, его ожидаемый выигрыш составит (v1 ?
p2 )/2. Окончательно запишем функцию выигрыша 1-го участника:
?
?v1 ? p2 , если p1 > p2
?
?
?
?v ? p
?
1 2
u1 (p1 , p2 ) = , если p1 = p2
2
?
?
?
?
?0, если p1 < p2 .
?


Чтобы показать, что «правдивая» стратегия, p1 = v1 , является доминирующей, нужно по-
казать, что она дает не меньший выигрыш, чем любая другая стратегия. Следует рассмотреть
3 случая: p2 > v1 , p2 = v1 и p2 < v1 .
[p2 > v1 ] Если 2-й участник назовет цену, превышающую vi , то 1-му участнику не выгод-
но выигрывать аукцион; его выигрыш (полезность) в этом случае был бы отрицательный, а в
случае проигрыша он получит 0. Поскольку в рассматриваемом случае при выборе «правди-
вой» стратегии 1-й участник проиграет аукцион, то «правдивая» стратегия является одной из
оптимальных.
[p2 = v1 ] Если 2-й участник назовет цену, совпадающую с vi , то 1-й участник при любом
выборе получит 0. Значит, «правдивая» стратегия даст ему выигрыш не меньший, чем любая
другая.

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

стр. 147
(из 165 стр.)

ОГЛАВЛЕНИЕ

Следующая >>