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

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

ОГЛАВЛЕНИЕ

Следующая >>

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

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

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


Задачи

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

Найдите в следующих играх все равновесия Нэша.
 670. Игра 16.2.1 (с. 625), выигрыши которой представлены в Таблице ??////??
 671. «Орехи»
Два игрока делят между собой 4 ореха. Каждый делает свою заявку на орехи: xi = 1, 2
или 3. Если x1 + x2 4, то каждый получает сколько просил, в противном случае оба не
получают ничего.
16.2. Статические игры с полной информацией 644

 672. Два преподавателя экономического факультета пишут учебник. Качество учебника (q )
зависит от их усилий (e1 и e2 соответственно) в соответствии с функцией

q = 2(e1 + e2 ).

Целевая функция каждого имеет вид

ui = q ? ei ,

т. е. качество минус усилия. Можно выбрать усилия на уровне 1, 2 или 3.
 673. «Третий лишний»
Каждый из трех игроков выбирает одну из сторон монеты: «орёл» или «решка». Если
выборы игроков совпали, то каждому выдается по 1 рублю. Если выбор одного из игроков
отличается от выбора двух других, то он выплачивает им по 1 рублю.
 674. Три игрока выбирают одну из трех альтернатив: 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.

 675. Формируются два избирательных блока, которые будут претендовать на места в законо-
дательном собрании города N-ска. Каждый из блоков может выбрать одну из трех ориентаций:
«левая» (L), «правая» (R) и «экологическая» (E). Каждая из ориентаций может привлечь 50,
30 и 20% избирателей соответственно. Известно, что если интересующая их ориентация не
представлена на выборах, то избиратели из соответствующей группы не будут голосовать. Ес-
ли блоки выберут разные ориентации, то каждый получит соответствующую долю голосов.
Если блоки выберут одну и ту же ориентацию, то голоса соответствующей группы избирате-
лей разделятся поровну между ними. Цель каждого блока — получить наибольшее количество
голосов.
 676. Два игрока размещают точку на плоскости. Один игрок выбирает абсциссу, другой —
ординату. Их выигрыши заданы функциями:
а) ux (x, y) = ?x2 + x(y + a) + y 2 , uy (x, y) = ?y 2 + y(x + b) + x2 ,
б) ux (x, y) = ?x2 ? 2ax(y + 1) + y 2 , uy (x, y) = ?y 2 + 2by(x + 1) + x2 ,
в) ux (x, y) = ?x ? y/x + 1/2y 2 , uy (x, y) = ?y ? x/y + 1/2x2 ,
(a, b - коэффициенты).
 677. «Мороженщики на пляже»
Два мороженщика в жаркий день продают на пляже мороженое. Пляж можно предста-
вить как единичный отрезок. Мороженщики выбирают, в каком месте пляжа им находиться,
т. е. выбирают координату xi ? [0, 1]. Покупатели равномерно рассредоточены по пляжу и
покупают мороженое у ближайшего к ним продавца. Если x1 < x2 , то первый обслуживают
(x1 + x2 )/2 долю пляжа, а второй — 1 ? (x1 + x2 )/2. Если мороженщики расположатся в
одной и той же точке (x1 = x2 ), покупатели поровну распределятся между ними. Каждый
мороженщик стремиться обслуживать как можно большую долю пляжа.
 678. «Аукцион»
Рассмотрите аукцион, подобный описанному в Игре 16.2.2, при условии, что выигравший
аукцион игрок платит названную им цену.
 679. Проанализируйте Игру 16.2.1 «Выбор компьютера» (с. 624) и найдите ответы на сле-
дующие вопросы:
16.2. Статические игры с полной информацией 645

а) При каких условиях на параметры a, b и c будет существовать равновесие в доминиру-
ющих стратегиях? Каким будет это равновесие?
б) При каких условиях на параметры будет равновесием Нэша исход, когда оба выбира-
ют IBM? Когда это равновесие единственно? Может ли оно являться также равновесием в
доминирующих стратегиях?
 680. Каждый из двух соседей по подъезду выбирает, будет он подметать подъезд раз в неде-
лю или нет. Пусть каждый оценивает выгоду для себя от двойной чистоты в a > 0 денежных
единиц, выгоду от одинарной чистоты — в b > 0 единиц, от неубранного подъезда — в 0, а
свои затраты на личное участие в уборке — в c > 0. При каких соотношениях между a, b и c
в игре сложатся равновесия вида: (0) никто не убирает, (1) один убирает, (2) оба убирают?
 681. Предположим, что в некоторой игре двух игроков, каждый из которых имеет 2 страте-
гии, существует единственное равновесие Нэша. Покажите, что в этой игре хотя бы у одного
из игроков есть доминирующая стратегия.
 682. Каждый из двух игроков (i = 1, 2) имеет по 3 стратегии: a, b, c и x, y, z соответствен-
но. Взяв свое имя как бесконечную последовательность символов типа иваниваниван. . . , за-
дайте выигрыши первого игрока так: u1 (a, x) = «и», u1 (a, y) = «в», u1 (a, z) = «а», u1 (b, x) =
«н», u1 (b, y) = «и», u1 (b, z) = «в», u1 (c, x) = «а», u1 (c, y) = «н», u1 (c, z) = «и». Подставьте
вместо каждой буквы имени ее номер в алфавите, для чего воспользуйтесь Таблицей 16.10.
Аналогично используя фамилию, задайте выигрыши второго игрока, u2 (·).
1) Есть ли в Вашей игре доминирующие и строго доминирующие стратегии? Если есть, то
образуют ли они равновесие в доминирующих стратегиях?
2) Каким будет результат последовательного отбрасывания строго доминируемых страте-
гий?
3) Найдите равновесия Нэша этой игры.

Таблица 16.10.

0 1 2 3 4 5 6 7 8 9
0 а б в г д е ё ж з
1 и й к л м н о п р с
2 т у ф х ц ч ш щ ъ ы
3 ь э ю я

 683. Составьте по имени, фамилии и отчеству матричную игру трех игроков, у каждого из
которых по 2 стратегии. Ответьте на вопросы предыдущей задачи.
 684. Заполните пропущенные выигрыши в следующей таблице так, чтобы в получившейся
игре. . .
(0) не было ни одного равновесия Нэша,
1 ?
(1) было одно равновесие Нэша,
? 2
(2) было два равновесия Нэша,
? 0
(3) было три равновесия Нэша, 4 ?
(4) было четыре равновесия Нэша.
 685. 1) Объясните, почему в любом равновесии Нэша выигрыш i-го игрока не может быть
меньше, чем
min max ui (xi , x?i ).
x?i ?X?i xi ?Xi

2) Объясните, почему в любом равновесии Нэша выигрыш i-го игрока не может быть
меньше, чем
max min ui (xi , x?i ).
xi ?Xi x?i ?X?i
16.3. Динамические игры с совершенной информацией 646

 686. Задача относится к свойствам антагонистических игр двух лиц. Антагонистической игрой
двух лиц называется игра, в которой сумма выигрышей обоих игроков постоянна:

u1 (x1 , x2 ) + u2 (x1 , x2 ) = C.

(В частном случае, когда C = 0, такая игра называется игрой с нулевой суммой.)
Объясните, почему множество седловых точек функции u1 (x1 , x2 ) в антагонистической
игре двух лиц совпадает с множеством равновесий Нэша.
(Напомним, что седловой точкой функции u1 (x1 , x2 ), называют такую точку (x? , x? ) ?
12
X1 ? X2 , что для любых x1 ? X1 и x2 ? X2 выполнено

u1 (x1 , x? ) u1 (x? , x? ) u1 (x? , x2 ).)
2 12 1


 687. Докажите, основываясь на результатах двух предыдущих задач, что в антагонистиче-
ской игре двух лиц равновесие Нэша (в чистых стратегиях) существует тогда и только тогда,
когда
min max u1 (x1 , x2 ) = max min u1 (x1 , x2 ).
x2 ?X2 x1 ?X1 x1 ?X1 x2 ?X2


Проверьте, что в следующих играх нет равновесия Нэша в чистых стратегиях. Найдите
равновесие Нэша в смешанных стратегиях.
 688. «Орел или решка»
Первый из двух игроков прячет монетку, положив ее по своему выбору вверх орлом или
решкой. Второй игрок должен угадать, как лежит монетка. Если второй игрок угадает, то
первый должен отдать ему рубль, в противном случае он должен отдать первому рубль.
 689. «Камень - ножницы - бумага»
Два игрока играют в следующую игру. Каждый называет один из трех предметов: «ка-
мень», «ножницы» или «бумага». Игрок, назвавший камень, выигрывает игрока, назвавшего
ножницы (ножницы тупятся о камень), игрок, назвавший ножницы, выигрывает игрока, на-
звавшего бумагу (ножницы режут бумагу), а игрок, назвавший бумагу, выигрывает игрока,
назвавшего камень (камень можно завернуть в бумагу). Выигравший игрок получает 1, про-
игравший получает ?1. Если названные предметы совпали, то каждый игрок получает 0.
 690. Идет война между синими и красными. Генерал синих хочет занять город красных,
имея две роты. К городу можно подойти по одной из двух дорог. Генерал синих каждую
свою роту может послать по любой из дорог. Генерал красных располагает тремя ротами и
может приказать любой роте оборонять любую дорогу. Синие займут город в том случае,
если на одной из дорог у них будет больше рот, чем у красных. При этом синие получат 1, а
красные — ?2. Если синие не займут город, то выигрыши составят ?1 и 1 соответственно.
 691. В некоторой игре двух игроков, каждый из которых имеет 2 стратегии, у каждого из
игроков все выигрыши различны, и существует ровно два равновесия Нэша. Покажите, что в
этой игре есть еще равновесие в невырожденных смешанных стратегиях.



16.3 Динамические игры с совершенной информацией
Многие ситуации, включающие взаимодействие индивидуумов, являются по своему смыслу
динамическими. Люди взаимодействуют друг с другом во времени и действуют, реагируя на
те решения, которые ранее приняли другие. Другими словами, принимая решения, каждый
игрок располагает определенной информацией о решениях, принятых другими игроками, что
предполагает очередность принятия решений (ходов).
16.3. Динамические игры с совершенной информацией 647

Динамической будем называть такую игру, в которой каждый игрок может сделать несколь-
ко ходов и по крайней мере один из игроков, делая ход, знает, какой ход сделал другой игрок
(возможно, он сам). В этой ситуации он стоит перед свершившимися фактами (уже сделан-
ными ранее и известными ему ходами) и должен учитывать их при выборе своих действий.
Приведем пример динамической игры.
Игра 7. «Террорист»
В самолет, который должен лететь из Майами в Нью-Йорк, сел террорист. Террорист требует,
чтобы пилот летел на Кубу, угрожая в противном случае взорвать самолет. Предположим, что
террорист не может определить, куда действительно летит самолет. Первый ход в этой игре
тогда делает пилот. Он может лететь либо на Кубу, либо в Нью-Йорк. Если пилот посадит
самолет на Кубе, то его выигрыш составит ?1, а выигрыш террориста составит 1. Если же
самолет сядет в Нью-Йорке, то делает свой ход террорист. Он может либо взорвать бомбу, либо
не взрывать. Если бомба взорвется, то выигрыши обоих игроков составят ?100, в противном
случае выигрыш пилота составит 1, а выигрыш террориста составит ?1.

Данную игру удобно представить в виде диаграммы, изображающей дерево игры (см.
Рис. 16.6)20 .

Пилот

Куба Нью-Йорк

?1
Террорист
1
взорвать
не взрывать
?100 1
?100 ?1

Рис. 16.6. Игра «Террорист»

Решение игры можно найти, в предположении, что игроки рациональны и что рациональ-
ность и структура игры являются общеизвестными фактами. При этом естественно восполь-
зоваться методом обратной индукции.
В соответствии с этим методом игру «разматывают» с конца. Рассмотрим последнюю вер-
шину игры, в которой один из игроков делает выбор. В данном случае нам надо спрогнозиро-
вать как поступит террорист, оказавшись в Нью-Йорке. От решения террориста в этой ситуа-
ции (вершине) зависит исход игры, поскольку пилот уже сделал свой ход, и не может «взять
обратно». Если террорист рационален, то он примет решение не взрывать бомбу, поскольку
?1 больше ?100. Таким образом, действия террориста можно однозначно предсказать.
Поскольку, как мы предположили, рациональность террориста является общим знанием,
то пилот может «просчитать» действия террориста и, тем самым, будет знать, что случиться,
если он прилетит в Нью-Йорк.
Чтобы было более понятно, какой выбор стоит перед пилотом, удобно частично «свернуть»
дерево игры, учитывая то, что действия террориста в Нью-Йорке известны. Полученная усе-
ченная (редуцированная) игра показана на Рис. 16.7.
В этой игре действия пилота несложно предсказать — он полетит в Нью-Йорк, посколь-
ку предпочитает выигрыш 1 выигрышу ?1. Таким образом, исход игры однозначен: пилот
посадит самолет в Нью-Йорке, а террорист не станет взрывать бомбу.
20
Нам удобнее изображать дерево «кроной вниз». Сам термин дерево взят из теории графов.
16.3. Динамические игры с совершенной информацией 648

Пилот

Куба Нью-Йорк

?1 1
1 ?1

Рис. 16.7. Ситуация выбора пилота


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

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

ОГЛАВЛЕНИЕ

Следующая >>