Доминирование стратегий

Кратка теория к контрольной № 2

Доминирование стратегий

В общем случае две стратегии игрока несравнимы - в одних ситуациях лучше одна, в других - другая. Однако встречаются ситуации, когда одна стратегия несомненно лучше другой. Мы уже встречались с подобной ситуацией, когда обсуждали игры с нулевой суммой.

Определение. Стратегия игрока i сильно доминирует стратегию , если

Если всюду стоят знаки , то говорят о слабом доминировании.

Доминирующие стратегии. Определение. Стратегия игрока i называется доминирующей (или доминантной), если она (слабо) доминирует любую стратегию из .

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

Определение. Исход в игре в нормальной форме доминирует по Парето исход , если

Исход х назовем Парето-оптимальным, если он не доминируем по Парето.

Метод исключения доминируемых стратегий. Рассмотрим игру

	y1	y2	y3
x1	4, 3	2, 7	0, 5
x2	5, 5	5, 0	-4, -1

Видно, что стратегия y3 явно плохая для второго игрока; более точно, она доминируется (сильно) стратегией y2. Поэтому 2-й игрок ее применять не будет. У 1-го игрока доминируемых стратегий нет. Однако если он знает полезности 2-го, то он понимает, что 2-й не будет применять y3. Но тогда игра редуцируется к

	y1	y2
x1	4, 3	2, 7
x2	5, 5	5, 0

Но в этом случае у игрока 1 стратегия x2 сильно доминирует стратегию x1, и он будет использовать только x2. Наконец, так как 2-й игрок знает полезности 1-го и знает, что 1-й знает его (2-го) полезности, он может заключить, что первый использует x2, а значит ему нужно применять y1.

Подводя итог, мы видим, что в этой игре есть естественное решение (x2, y1) с неплохими выигрышами [5,5]. Подчеркнем лишний раз, что предложенный способ рассуждения очень сильно опирается на информационные гипотезы: решение второго игрока применять y1 основано на его уверенности в том, что первый будет использовать x2. Но почему второй уверен в этом? Потому что он знает, что первый знает его (второго) полезности и понимает, что второй не будет использовать y3, а тогда для первого лучше всего x2.

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

Определение. Ситуация х* называется ситуацией равновесия по Нэшу, если для любого игрока и любой его стратегии имеет место неравенство

Множество ситуаций, равновесных по Нэшу в игре G, будем обозначать NE(G). Тот факт, что х* равновесна по Нэшу будем записывать как .

Из определения ситуации равновесия по Нэшу следует, что ни один из игроков i не заинтересован в одностороннем отклонении от стратегии , входящей в эту ситуацию (согласно его выигрыш при использовании другой стратегии разве лишь уменьшится при условии, что остальные игроки придерживаются стратегий, образующих ситуацию равновесия х*). Таким образом, если игроки договорились предварительно об использовании стратегий, входящих в ситуацию равновесия х*, то индивидуальное отклонение от договора невыгодно отклонившемуся игроку. В этом смысле стратегия является наилучшим ответом (Best Response)игрока i на совместный выбор остальных:

Определение. Стратегия называется равновесной, если она входит хотя бы в одну ситуацию равновесия по Нэшу.

Для биматричной -игры G(A, В) пара (i*, j*) будет ситуацией равновесия по Нэшу (), если неравенства

выполняются для всех номеров строк и столбцов .

Определение. Ситуация х* называется сильно равновесной, если, выполняются неравенства

Отыскание равновесий по Нэшу

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

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

Каков наилучший ответ первого игрока на выбор вторым первого столбца? Выбор второй строки (3). Именно вторая строка доставляет функции выигрыша первого игрока максимум в первом столбце. На выбор второго столбца наилучшие ответы – выбор второй или третьей строки (4). На выбор третьего столбца – выбор третьей строки (4).

Рассуждая аналогичным образом за второго игрока, получаем, что его лучший ответ на выбор первой строки – первый столбец (5). А второй столбец является наилучшим ответом на выбор второй (5) или третьей (4) строки.

Подчеркивания «сходятся» в двух ячейках матрицы, находящихся во втором столбце, второй и третьей строках. Таким образом, в приведенной биматричной игре имеется две ситуации равновесия (2, 2) и (3, 2) с векторами выигрышей [4, 5] и [4, 4], соответственно.

Если подчеркивания не сходятся ни в какой ячейке, то биматричная игра не имеет ситуаций равновесия в чистых стратегиях.

Существование NE

Теорема. Пусть G – биматричная игра. Тогда существуют смешанные стратегии x* и y* игроков 1 и 2 соответственно, такие, что пара (x*,y*) является ситуацией равновесия по Нэшу .

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

Теорема. Пусть G(A, B) – биматричная игра с матрицами выигрышей игроков А и В, и пусть - ситуация равновесия в смешанных стратегиях. Тогда выполняются равенства:

где i и j – любые существенные стратегии игроков 1 и 2.

Данная теорема дает способ нахождения оптимальных смешанных стратегий игроков в игре G(A, B). Действительно, предположим, что мы ищем ситуацию равновесия (X,Y), считая множества существенных стратегий игроков (спектры) заданными. Тогда оптимальные стратегии должны удовлетворять системе линейных уравнений:

где - i-ая строка матрицы А, - j-ый столбец матрицы В, а - некоторые числа. Если же ситуация равновесия вполне смешанная, то есть все чистые стратегии являются существенными, то система принимает вид:

где - выигрыши игроков в ситуации равновесия (X,Y), - вектор-строка размерности m, состоящий из единиц, - вектор-столбец размерности n, состоящий из единиц.

Теорема. Пусть G(A, B) – биматричная квадратная игра и матрицы А и В – невырожденные (). Если игра G(A, B) имеет вполне смешанную ситуацию равновесия, то она единственная и вычисляется по формулам:

где

(Величины являются суммами элементов обратных матриц соответственною)

Равновесия Нэша в бесконечных играх

Теорема (Нэш [1951]). Предположим, что для любого множество стратегий есть выпуклое и компактное подмножество топологического векторного пространства (вообще говоря, своего для каждого i). Пусть для всех - непрерывная действительная функция на XN, определенная так, что для всех функция вогнута по на . Тогда множество NE(G) равновесий по Нэшу игры непусто и компактно.

Теорема Нэша позволяет утверждать, что множество NE(G) не пусто. Для того чтобы его вычислить, требуется решить следующую систему уравнений:

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

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

Проиллюстрируем метод вычисления, описанный в общих чертах, на некоторых примерах и задачах.

Пример 1. Олигополия с назначением выпуска

Пусть имеется n производителей с нулевыми затратами, которые регулируют предложение некоторого насыщаемого по потреблению товара. Производители поставляют свой товар на рынок. Общее предложение равно , а цена есть , где р — убывающая вогнутая функция на положительной полуоси:

Эту ситуацию можно представить как следующую игру:

Из наших условий на р получается, что функция вогнута по .

Поскольку не компактные множества, положим, , где S есть предложение, порождающее нулевую цену: p(s)=0. Для усеченной игры применима теорема Нэша, которая позволяет утверждать существование NE-исхода х в усеченной игре. На самом деле исход х есть равновесие по Нэшу в исходной игре. Действительно, гарантированный выигрыш каждого игрока в усеченной игре есть 0, поэтому

В силу вогнутости и дифференцируемости ui на множестве

NE-исход х удовлетворяет системе :

Таким образом, в силу симметрии задачи наша игра имеет единственный NE-исход на диагонали:

Пример. Дуополия с назначением выпуска. Предпожим, что цена меняется по закону

Рассмотрим дуополию, которая формализуется как игра двух лиц, в которой множество стратегий каждого игрока есть отрезок [0, 1/2]. Нетрудно убедиться в том, что все условия выполнены. Условие не имеет смысла, так как точка не входит в ОДЗ. Однако, это условие служит лишь для обеспечения положительности цены в некоторой окрестности точки 0. С учетом того, что , положительность цены в некоторой окрестности точки 0 обеспечена.

В силу вышеизложенного мы можем воспользоваться для определения исхода, равновесного по Нэшу:

Экономические модели, использующие равновесие Нэша

Модель Курно(1938).

Равновесия Нэша незаменимы при изучении олигополии, когда несколько фирм конкурируют на одном рынке.

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

Каждая фирма стремится максимизировать свою прибыль. Необходимым условием максимума является равенство нулю частных производных:

Упростим все, считая издержки и цены линейными и одинаковыми для обеих фирм,

(так что М - это максимальная цена, по которой можно продать товар). Тогда

Функция является вогнутой квадратичной функцией по переменным . Таким образом, максимизация сводится к условию стационарности точки решения. Найдем лучший ответ 1-й фирмы на выбор .

Аналогично для второй фирмы. Равновесие получается в точке пересечения кривых реакций, то есть как решение системы:

и . Цены равны .

Этот же результат можно получить графически. Положим для простоты с=0, тогда:

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

И прибыль максимальна при

То есть, при монополии цены выше, а выпуски меньше.

Модель Бертрана (1883).

Модель Бертрана также является моделью дуополии, но имеет другие стратегические множества и функции выигрыша. В модели Бертрана фирмы выбирают не выпуски, а цены. Выпуск же считается возможным обеспечить в любом требуемом количестве. Будем считать, что фирмы выпускают один и тот же продукт. Фирмы независимо выбирают цены, после чего игра разыгрывается. Считается, что покупатели приобретают товар у той фирмы, у которой цена ниже. В случае равенства цен, покупают поровну у обеих. Функция полезности 1-го игрока:

Для второго игрока функция аналогична. Игра имеет структуру, аналогичную ДЗ. Если игроки кооперируют, то могут установить монопольную цену и поделить монопольную выгоду. Но каждый имеет соблазн чуть-чуть снизить цену и завладеть всем рынком.

Пусть издержки на выпуск единицы продукции равны для фирм и , и пусть для определенности . Что является равновесием Нэша в этой игре? Если первая фирма назначит цену выше , это не может быть равновесием. Вторая фирма может с выгодой для себя назначить цену и обратить выигрыш первой фирмы в 0. Назначение цены ниже не эффективно. Остается единственное: . При этом первая фирма выигрывает , а прибыль второй фирмы равна нулю.

Поведение лидера и ведомого. Модель Штакельберга

Мы рассмотрели ситуации, в которых все игроки находятся на одном и том же уровне информированности. В ряде экономических приложений, в частности при олигополистической конкуренции с доминирующей фирмой, естественным образом возникает несимметричное распределение информации. Мы исследуем простейшую модель такого сорта: поведение типа лидер — ведомый в игре двух лиц[1].

Для данной игры двух лиц обозначим через график отображения наилучших ответов i-го игрока:

(симметричное определение для BR2).

Определение 1. Назовем i-равновесием по Штакельбергу в игре , если

где

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

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

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

Пример 1. Дуополия лидер-ведомый.

Пусть полный выпуск двух фирм есть . Издержки фирм . Цена . Первая фирма (лидер) объявляет второй свой выпуск . Вторая фирма с учетом полученной информации оптимизирует свой выпуск:

Предвидя, первая фирма перед объявлением своего выпуска решает задачу оптимизации:

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

Таким образом, прибыль ведомого в два раза меньше прибыли лидера.

Пример 2. Процедура голосования по Ролсу

Пусть А = {1, 2, . . ., 7} есть множество из 7 кандидатов, среди которых 2 игрока должны выбрать единственного.

Каждый игрок в качестве своего предложения может расставить кандидатов в некотором порядке. Следовательно, стратегия есть взаимно однозначное отображение из А на А, причем если , то а — это наилучший по мнению игрока i кандидат (обман, конечно, разрешен). Обозначим через X множество стратегий игроков 1 и 2. Для данной пары выбирается кандидат , где

Очевидно, что состоит не более чем из двух кандидатов. Данное правило подобрано так, чтобы выбирался кандидат, чья наихудшая оценка среди двух избирателей является наиболее высокой. Поскольку игроки могут выбрать любую расстановку кандидатов, то возникает стратегическая игра. Обозначим через истинные мнения игроков 1 и 2. Тогда избиратели являются участниками следующей игры в нормальной форме:

(В качестве выигрыша игрока берется ранг избранного кандидата с отрицательным знаком. Напомним, что игроки стремятся к максимизации своих функций выигрыша.)

Вычислим теперь 1-равновесие по Штакельбергу в игре. Фиксируем стратегию игрока 1. Заметим, что для всех выполнено

Другими словами, предлагая , игрок 1 отводит кандидатов . Это справедливо, поскольку из 4 кандидатов, стоящих на первых четырех местах в списке первого игрока, второй игрок может отвести не более 3, присвоив им ранги 5, 6 и 7. Хотя бы один кандидат из первой четверки получит у второго игрока ранг не менее 4.

Отметим далее, что при данном игрок 2 может обеспечить избрание любого кандидата из :

Например, для того чтобы обеспечить избрание , игрок 2 объявляет свое предпочтение так:

высший ранг	a	d*
	b	e
	c	f
	d*	g
	e	a
	f	b
низший ранг	g	c

Из и получаем, что любая стратегия наилучшего ответа на такова, что

Отсюда, в частности, следует, что

(так как множество состоит из 4 элементов).

Следовательно, игрок 1 как лидер может обеспечить избрание кандидата из множества . На самом деле, он может гарантировать выбор любого кандидата из за счет подходящего сообщения. Например, для того чтобы обеспечить выбор , игрок 1 объявляет:

высший ранг	b	a
	c	e
	a	f
	d	g
	e	b
	f	c
низший ранг	g	d

Это сообщение вызывает наилучший ответ , такой, что в силу .

Наконец, заключаем, что выигрыш игрока 1 (выраженный в ранге избираемого кандидата) в любом 1-равновесии по Штакельбергу равен

Если игроки поменяются ролями, то в силу симметрии получаем, что выигрыш (ранг избираемого кандидата) игрока 2 в любом 2-равновесии по Штакельбергу равен

Интересное следствие состоит в том, что, вообще говоря, ранги и несовместны в следующем смысле:

Более точно, пара либо удовлетворяет, либо такова, что условия и выполнены в точности для одного кандидата а*. Тогда

Если для пары функций выполнено условие, то игра представляет типичную борьбу за лидерство: если игроки информированы о предпочтениях друг друга, то оказывается выгодным иметь первый ход и вынудить другого игрока занять позицию ведомого.

[1] Гермейер