РАВНОВЕСИЕ НЭША

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

Упражнение 11.2**. Продавец имеет для продажи одну неделимую единицу продукта, п покупателей предлагают за него 0 < «1 < < ... < vn, ъ эти оценки общеизвестны. Покупатели одновременно подают свои требования Ь{. Покупатель, оценивший продукт выше всех, получает его, т. е. если г выигрывает, он получит полезность

П* = VI — шах 6,.

Другие ничего не получают. 1.

Покажите, что оценка первого предложения (6; = является доминирующей стратегией покупателя г. 2.

Сделайте вывод, что п-й покупатель выигрывает и получает излишек V« ^п—1 • 3.

Повлияло бы на результаты знание каждым участником торгов только собственной оценки, но не оценок других участников?

Упражнение 11.3**. Функции полезности п потребителей имеют вид

П* = и + 0»(М*),

где ti — доход г-го потребителя; а — общественное решение (например, количество общественного блага); <^(а,0;) — оценка г-м покупателем решения а; 0; — параметр полезности. Функции д{ общеизвестны. Денежная стоимость решения а есть С (а). 1.

Покажите, что для плановика, который знает параметры социально оптимальное решение, а*{0\,..., 0П), максимизирует

$^5*(М«) “ С (а)

г

(правило Самуэльсона). 2.

Предположим, что 0,- известна только г-му потребителю. Плановик хочет выработать механизм, который склоняет потребителей честно открыть свои оценки и осуществить социально оптимальное решение. Рассмотрим следующую игру. Потребителей просят одновременно объявить свои оценки. — сообщение г-го потребителя (оно может быть ложным). Плановик осуществляет решение а*(Ох,..., 9п) (т. е. решение, являющееся оптимальным, если все потребители говорят правду) и производит трансферты:

?,(01,... ,0п) = К{ + <7/(а*(0ъ • • • — С(а*(0х,..., 0П)),

где К{ — константа. Покажите, что объявление правды (вi = в{) является доминирующей стратегией г-го потребителя. Сделайте вывод, что плановик может осуществить первое наилучшее (при полной информации) распределение.

К сожалению, во многих играх устранение доминируемых стратегий не способствует отбору единственного «разумного* исхода игры (или ограниченного набора исходов). Примером служит одновременная игра 2. Ни одна из четырех стратегий не является доминируемой, а этот метод приводит нас к неопределенному исходу. Точно так же в играх одновременного выбора цен и количеств Бертрана и Курно (глава 5) оптимальный ход одной фирмы зависит от оптимального хода другой фирмы, что означает наличие большого количества недоминируемых стратегий.

Два других знаменитых примера одновременного выбора двух игроков представлены в табл. 11.3, 11.4. В «Подбрасывании монет» игроки должны выбрать «орла» или «решку». Если выбор выполняется, игрок 1 получает 1 от игрока 2 и наоборот, если он не выполняется. В «Войне полов» каждый игрок выбирает между походом в кино или театр. Два игрока всегда предпочтут пойти куда- либо вместе, нежели в другое место в одиночку, однако игрок 1 предпочитает кино, а игрок 2 — театр.

В таких случаях понятие равновесия Нэша дает слабую концепцию «разумного исхода».

Определение. Набор стратегий {а*}"_1 есть равновесие чистых стратегий Нэша тогда и только тогда, когда для всех а,- из А,-

ПЧ«*,а!.-)>ПЧ<Ч,а1Л,

где a^i ~ (а*,..., а*_1, а*+1,..., а*).

«Подбрасывание монет» иллюстрирует возможность несуществования равновесия чистых стратегий. Если игрок 1 играет Н, игрок 2 играет Г, что вынуждает игрока 1 захотеть сыграть Т, и т. д. Но здесь существует равновесие смешанных стратегий: каждый игрок играет Н и Т с равными вероятностями. Чтобы это было равновесием, обе чистые стратегии должны давать одинаковые выплаты каждому игроку. Игрок 1, играющий Я, получает

|(1)+|(-1) = 0;

если же он играет Т, то получает

|(-1) + |(1) = 0.

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

«Война полов» иллюстрирует возможность множества равновесий. {М, М) и {Р, Р} — два равновесия чистых стратегий. Существует также и равновесие смешанных стратегий, при котором игрок 1 играет М с вероятностью 2/3 (и Р с вероятностью 1/3), а игрок 2 играет Р с вероятностью 2/3 (и М с вероятностью 1/3). В таких случаях неясно, что именно следует предвидеть. Ни одно

Таблица 11.4 Игра «Война полов»

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

Часто А{ является непрерывным пространством (скажем, Ж), а функция П* обладает приятным свойством дифференцируемости. Тогда можно получить рав» новесие чистых стратегий, дифференцируя функции выигрыша каждого игрока по его собственному действию. Таким образом, условие первого порядка:

nj«,a!,) = 0,

где П) = dW/да{ — частная производная по собственному действию (локальное условие второго порядка — Щ • < 0). Условия первого порядка дают систему п уравнений с п неизвестными, которые, если решения существуют и для каждого игрока выполняется условие второго порядка, дают равновесие (равновесия) чистых стратегий Нэша. К примеру, представьте, что две фирмы (производящие разные товары) конкурируют по ценам, а; — рг. Спрос на товар, произведенный фирмой г, составит

qi = Di(pi,pj) = 1 - bpi -|- dpj, где 0 < d < b. Если фирма i имеет удельные затраты с, то

1Г = (pi - с)( 1 - bpi + dpj).

Заметьте, что П* вогнута по р». Условиями первого порядка для i = 1,2 являются

1 -{- dpj + 6с - 2bpi = 0.

Равновесие чистых стратегий Нэша единственно и симметрично:

1 -1- 6с 26-d*

Теперь давайте вернемся к играм 1 и 2. В игре с одновременными ходами (игре 2) есть два равновесия чистых стратегий: и {а1>а2}- ® игре с

последовательными ходами (игре 1) кроме этих двух равновесий Нэша есть и третье: {а2, а3}» которое приводит к тем же ходам (и, следовательно, к тем же выплатам), что и второе. При одновременной игре оба равновесия Нэша кажутся разумными.657 Это не так в случае игры с последовательными ходами, при которой, как утверждалось, существует единственное разумное решение (после устранения доминируемых стратегий). Вопрос, как мы увидим, состоит в том, что понятие равновесия Нэша приемлемо только тогда, когда все решения принимаются одновременно (единожды и для всех); оно обычно слишком слабо при последовательных решениях.

Упражнение 11.4*. Найдите равновесие чистых стратегий Нэша для игры, описанной в упражнении 11.1.

Упражнение 11.5**. Потребители размещены равномерно по линейному городу протяженностью 1. Каждый потребитель хочет купить у одной из существующих фирм единицу товара. Затраты потребителя по транспортировке пропорциональны расстоянию до фирмы. Закон запрещает любой вид ценовой и сервисной конкуренции (кроме конкуренции местоположения); таким образом, потребитель обращается в близлежащую фирму. Полезность фирмы равна количеству ее клиентов. Фирмы, расположенные на одинаковом расстоянии, имеют одинаковое количество покупателей. 1.

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

Покажите, что при наличии трех фирм равновесия чистых стратегий Нэша не существует.

Упражнение 11.6**. Существует п потребителей. Каждый г-й потребитель тратит денег на общественное благо. Выбор делается всеми одновременно. Полезность г-го потребителя:

где ^(0) = 0; <7*(0) > 1; д' > 0; д" < 0, < 1. Вычислите равновесие

Нэша. Обсудите множественность. Покажите, что общественные расходы здесь слишком малы. 11.3.

СОВЕРШЕННОЕ РАВНОВЕСИЕ

При равновесии Нэша игроки принимают стратегии своих оппонентов как данные; следовательно, они не рассматривают возможности влияния на них. В играх, гце игрок делает ходы, рассмотрев действия своих оппонентов (что мы называем динамическими играми), это предположение наивно и приводит к некоторому абсурдному равновесию Нэша, как мы видели в предыдущем разделе. В этом разделе представлено усовершенствование равновесия Нэша для динамических игр, которое смягчает его недостатки. Рассмотрим вновь последовательную игру 1 (рис. 11.1) и равновесие Нэша {а*, а^}. Игрок 1 не играет К, так как игрок 2 угрожает в этом случае сыграть /. Но предположим, что игрок 1 играет Д. Тогда игрок 2, столкнувшись со свершившимся фактом, выиграет, играя г, так как тогда он получит 1 вместо 0.

Таким образом, угроза игрока 2 не заслуживает доверия. Игрок 1, который должен это предвидеть, играет А, что дает ему выплату, равную 3, — большую, чем он бы получил, играя Ь. Поэтому предложенное равновесие Нэша базируется на не заслуживающей доверия угрозе, т. е. угрозе, которую игрок бы не выполнил, если бы его поставили перед необходимостью сделать это.

Главный смысл совершенного равновесия состоит в том, чтобы выбрать такое равновесие Нэша, которое не связано с не заслуживающими доверия угрозами. Для этого нужно, чтобы поведение игроков было оптимальным даже в ситуациях, не достигаемых на траектории равновесия. Например, решение игрока 2 сыграть I после того, как игрок 1 сыграл .й, не является оптимальным; причина, по которой {а*, <4} есть равновесие Нэша, состоит в том, что это субоптимальное решение не стоит игроку 2 ничего, потому что игрок 1 должен играть Ь (на языке теории игр можно сказать, что игра Я игрока 1 имеет нулевую вероятность). Наоборот, совершенное равновесие требует, чтобы игрок 2 играл оптимально, независимо от того, как сыграет игрок 1: Я или X. Это равносильно устранению доминируемых стратегий для игрока 2; вот почему усовершенствование дает тот же ответ, что и устранение доминируемых стратегий для этой игры (см. ниже класс игр, в которых два метода дают одинаковый ответ).

Чтобы получить совершенное равновесие, мы \1) работаем «назад». Зная оптимальную реакцию

игрока 2 на каждый из потенциальных ходов игрока 1, мы можем «свернуть дерево», как показано на рис 11.4. Оценки игрока 1 (соответственно игрока 2) равны 2 и 3 (соответственно 0 и 1) после того, как игрок 1 сыграл / или г. (Оценки представляют собой выплаты, которые получают игроки по достижении определенного положения на дереве игры). Затем игра сокращается до про- д J блемы выбирающего единственное решение, когда 0

~ ^ игрок 1 выбирает Д. Процесс обратной индукции

на дереве называется алгоритмом Куна [40]. с* ’ * Для более общих игр определим (правильную)

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

В частности, сама игра является одной из ее субигр. Например, игра 1 имеет три субигры: саму себя и две другие, начинающиеся после хода игрока 1. Наоборот, игра 2 является единственной субигрой из-за требования 1. Совершенное равновесие субигры [61] — это такой набор стратегий для каждого игрока, что в любой субигре стратегии формируют равновесие Нэша. Таким образом, совершенство требует, чтобы стратегии были в равновесии, независимо от положения (читай, субигры) на дереве игры, и не только вдоль траектории равновесия. Совершенное равновесие — обязательно равновесие Нэша (рассмотрите большую субигру, представленную самой игрой). В игре 1 две субигры второго периода являются проблемами принимающего единственное решение. Равновесие Нэша в этих субиграх означает, что принимающий решение (игрок 2) выбирает свой лучший ход.

Существуют два вида широко используемых игр, для которых совершенство очень сильно: игры с совершенной информацией и игры с «почти совершенной» информацией. 11.3.1.