.RU
Карта сайта

Концепция доминирования: Задача теории игр — по данному описанию игры, предсказать, какие

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

Пусть в Игре 1 (стр. 6) выгода от совместимости программного обеспечения сравнительно мала, например, а= 2, 6= 3, с= 1 (Таблица 3).

Тогда вне зависимости от того, какой компьютер выберет 2-й игрок, 1-му игроку выгодно выбрать компьютер IBM PC, по-

Таблица 3

Игрок 2 IBM Mac

IBM

Игрок 1

Мае со со

сч 0

0 4

1 скольку 3 >0 и 2 > 1. Аналогично, 2-й игрок предпочтет Макинтош, поскольку 3 > 1 и 4 > 0. В обоих случаях имеет место так называемое строгое доминирование двух указанных стратегий: если стратегия А при любых действиях других игроков дает больший выигрыш, чем стратегия В, то принято говорить, что стратегия А строго доминирует стратегию В.

Дадим формальное определение строгого доминирования. Здесь и в дальнейшем мы будем применять обозначение x_t, что означает «все элементы вектора х, кроме г-го», т.е.

X— (Ж], ..., Х„).

При этом будем считать, что (хь жч).— это то же самое, что х.

Определение 1.

Стратегия х, е Л", игрока г строго доминирует стратегию у, е Xt, если при любых стратегиях, выбранных остальными игроками, ж ,е Л" ,, выполнено

иг(Хг, Х-г) > Щ{Уг, Х-г), хл-.

где Л"

Определение строгого доминирования можно наглядно проиллюстрировать в случае двух игроков, множества стратегий одного из которых — действительная прямая (см. Рис 1). На рисунке стратегия хл первого игрока строго доминирует стратегию ух. Это выражается в том, что график функции полезности этого игрока по стратегии х2 второго, соответствующий хл, лежит ниже графика, соответствующего ух.

Рисунок L Стратегия ж, строго доминирует стратегию 2/1-

Стратегия называется строго доминирующей, если

она строго доминирует любую другую стратегию.

Определение 2.

Стратегия х, е Л", игрока г является его строго доминирующей стратегией, если при любых стратегиях, выбранных остальными игроками, жче она дает игроку г больший выигрыш, чем любая другая его стратегия у;е Л",, т.е.

Щ(Хг, Ж-г) > Щ{Уг, ) Vi/; ? Л";! Ф Х{.

В соответствие с данным определением не может существовать более одной строго доминирующей стратегии. Естественно ожидать, что рациональный игрок выберет именно такую стратегию. Поэтому при наличии у каждого игрока строго доминирующей стратегии исход игры может быть предсказан однознач-

Предсказание исхода игры не столь однозначно, когда у каждого игрока имеется лишь так называемая (слабо) доминирующая стратегия, обеспечивающая этому игроку не меньший выигрыш, чем любая другая его стратегия при любых стратегиях других игроков. Приведем определения (слабого) доминирования.

Определение 3.

Стратегия х, е Л", игрока г (слабо) доминирует стратегию у, е Л', (или, другими словами, стратегия у{ доминируется стратегией xj, если при любых стратегиях, выбранных остальными игроками, х ,е Л" ,, выполнено

иг{Хг, Х-г) ' Щ(Уг, Ж-гЬ

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

Щ{Хг, -I' ' ! > II.i!l- ¦'¦'.)¦

Рисунок 2 Стратегия ж, (слабо) доминирует стратегию Vi-

Слабое доминирование можно проиллюстрировать на графике, аналогичном тому, который мы использовали для иллюстрации строгого доминирования. Стратегия Ж) первого игрока слабо, но не строго доминирует его стратегию у1 (см. Рис. 2), поскольку график функции полезности для хх не везде строго выше, чем для уг. Определение 4.

Стратегия х{ е Л', игрока г является его (слабо) доминирующей стратегией, если при любых стратегиях, выбранных остальными игроками, ж , е Л" ,, она доминирует любую другую его стратегию, yte Xit либо эквивалентна ей, т.е.

Х-г) ¦ U.(у.. X ) Ух ( Л . У У. ( Л,

Из определения следует, что если стратегия х{ строго доминирует стратегию у,, то стратегия xi доминирует стратегию у,.

Кроме того, если стратегия является строго доминирующей, то она является доминирующей.

Определение 5.

Исход игры х*е X является равновесием в доминирующих

стратегиях, если стратегия каждого игрока в этом исходе является его доминирующей стратегией.

Естественно ожидать, что если в игре существует равновесие в доминирующих стратегиях, то именно оно будет реализовавшимся исходом игры. Следующая игра иллюстрирует равновесие в доминирующих стратегиях.

Игра 3. «Парламентское голосование»

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

Таблица 4 (А) Белые: за

Красные

За против

Зеленые -1 1 -1 1 за 1 1 -1 1 0 0 против 1 0 против

(В) Белые: ПРОТИВ

За

Красные

Зеленые

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

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

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

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

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

против (-1, 0, 0, 0).

Таким образом, голосовать против законопроекта является доминирующей стратегией белых (хотя, заметим, эта стратегия не сможет им помочь выиграть).

Тем самым, в этой игре существует равновесие в доминирующих стратегиях. В нем зеленые и красные голосуют «за», а белые — «против».

Приведем теперь пример игры с непрерывными стратегиями, в который есть равновесие в доминирующих стратегиях.

Игра 4. «Аукцион Вйкри».

Некий предмет продается с аукциона по следующим правилам. Каждый из участников аукциона (г = 1,...,«.) подает в тайне от других свою заявку — предлагаемую им цену pt. Побеждает участник, предложивший самую высокую цену, но платит он следующую по порядку убывания цену. Если самую высокую цену предложат сразу несколько участников, то победитель определяется жребием. Если г-й участник окажется победителем, то его выигрыш составит vi - р, где vt — ценность для него данного предмета, р — цена, которую он должен заплатить; выигрыш всех остальных участников будет равен нулю. ^

Особенность аукциона Викри состоит в том, что «правдивая» стратегия является доминирующей стратегией для каждого участника. Под «правдивой» стратегией понимается стратегия, заключающаяся в том, что участник называет цену, совпадающую с ценностью для него данного предмета, (pt = vt). Проверим это. Проанализируем данную игру при п = 2. (При большем количестве участников рассуждения будут аналогичными). Поскольку участники входят в данную игру симметрично, то достаточно рассмотреть мотивацию только одного из них, например, 1-го.

Вычислим сначала выигрыши 1-го игрока при разных исходах. Если 1-й участник назовет более высокую цену, чем 2-й (.Pi > Р2)' то он выиграет аукцион и заплатит р2. При этом его выигрыш составит г\-р2. Если 1-й участник назовет более низкую цену, чем 2-й (р1 < р2), то он проиграет аукцион и получит выигрыш 0. Если цены совпадут (р1=р2), то с вероятностью 1/2 1-й участник выиграет и получит выигрыш г'! - р2, ас вероятностью 1/2 он проиграет и получит выигрыш 0. Таким образом, его ожидаемый выигрыш составит (i\-p2)/2. Окончательно запишем функцию выигрыша 1-го участника:

i\-p2, если рг > р2 Щ(Р1,Р2) =

vi ~ Р>

—9 если р1 = р2 0, еслир1 i\. р2 = г и р2<

[Р2 > Если 2-й участник назовет цену, превышающую vt, то 1-му участнику не выгодно выигрывать аукцион; его выигрыш (полезность) в этом случае был бы отрицательный, а в случае проигрыша он получит 0. Поскольку в рассматриваемом случае при выборе «правдивой» стратегии 1-й участник проиграет аукцион, то «правдивая» стратегия является одной из оптимальных.

fe = Если 2-й участник назовет цену, совпадающую с vt, то 1-й участник при любом выборе получит 0. Значит, «правдивая» стратегия даст ему выигрыш не меньший, чем любая другая.

[р2 < t'j] Если 2-й участник назовет цену, меньшую vt, то для 1-го участника выгодно выиграть аукцион, поскольку в этом случае его выигрыш будет положительным. «Правдивая» стратегия обеспечивает ему победу на аукционе, и приносит максимальный ВЫИГРЫШ, T'J - Р2.

Мы видим, что «правдивая» стратегия в самом деле является доминирующей для 1-го участника. Более того, как несложно увидеть, это единственная доминирующая стратегия. Если он назовет цену ниже или выше своей оценки г>ь то можно подобрать такую цену 2-го участника, что 1-й участник потеряет по сравнению с р1 = г .

Проведя аналогичные рассуждения для 2-го участника, мы сделаем вывод, что в этой игре существует (единственное) равновесие в доминирующих стратегиях.

Р\ = Щ> P2 = V 2-

2014-07-19 18:44

  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • © sanaalar.ru
    Образовательные документы для студентов.