Тема 2. Лекция 5-6. Равновесия Нэша в смешанных стратегиях.

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

Определение 12: Ситуация x^*=(x₁^*,x₂^*,…,x_n^*) называется ситуацией равновесия по Нэшу (в чистых стратегиях),если для всех х_i, Х_i„ i N справедливо неравенство K_i (x_i^*,x_-i^*) K_i (x_i^*,x_-i^*)

Определение 13: Совокупность всех равновесных по Нэшу ситуаций игры называется множеством равновесий Нэша.

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

Определение 14: Набор смешанных стратегий из (

называется ситуацией равновесия Нэша в смешанных стратегиях, если для произвольной смешанной стратегии χ, любого игрока справедливо неравенство (χ₁^*,χ_-i^*) (χ₁^*,χ_{- i}^*),

где (.) – результат усреднения функций выигрыша игроков по используемым ими смешанным стратегиям.

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

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

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

R_i(χ_-i) =Arg (8)

По теореме 2, это множество представляет собой множесг всех вероятностных распределений на множестве чистых стратегий – наилучших ответов на заданную обстановку. Поэтому R_i выпуклое множество, так как оно представляет собой ограниченное линейными неравенствами подмножество выпуклого множества смешанных стратегий. Определим многозначное соответствие

R(χ) =(R₁(x_-1),…,R_n(x_-n)), (9)

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

Для дальнейшего доказательства воспользуемся теоремой Какутани. Введем сначала определение:

Определение 15: Многозначное отображение F компакта S в себя называется полунепрерывным сверху, если для любых сходящихся последовательностей χ^k S (χ^k χ), и таких что ρ^k F(χ^k), ρ принадлежит F(χ)

Теорема 4 (теорема Какутани о неподвижной точке). Пусть S есть непустой, выпуклый компакт конечномерного пространства. Если F - полунепрерывное сверху многозначное соответствие, которое ставит в соответствие каждой точке S непустое выпуклое подмножество S, то существует такой χ^* S, χ^* F(χ^*).

Покажем, что отображение R полунепрерывно сверху. Для этого рассмотрим произвольные сходящиеся последовательности χ^k и из определения полунепрерывности сверху.

Из того, что (χ^k) следует, что для произвольной смешанной σ_i (ρ^k, χ^k_-i) ≥ (σ_i, χ_-i^k). По лемме 1 функция ожидаемого выигрыша непрерывна по совокупности переменных, поэтому (ρ_i, χ_-i) ≥ (σ_i, χ_-i), то есть ρ R(χ).

По теореме Какутани, существует неподвижная точка – ситуация χ^*, такая, что χ^* R(χ^*).

Значит, для всех игроков (χ^*, χ^*_-i) ≥ (χ_i, χ_-i^*), где χ_i –произвольная смешанная стратегия. То есть χ^*– это равновесие Нэша.

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

Теорема 5. Если множества стратегий игроков компактны, а функции выигрыша непрерывны по совокупности переменных (чистых стратегий игроков), то в игре существует, по крайней мере, одно равновесие Нэша в смешанных стратегиях.

На основании полученных результатов можно сформулировать одно из возможных достаточных условий существования равновесия в чистых стратегиях:

Теорема 6. Если в непрерывной игре множества стратегий X_i - выпуклые подмножества линейных метрических пространств, для каждого игрока i функция выигрыша К_i непрерывна по всем переменным и строго вогнута по переменной х_i,то в этой игре существует равновесие Нэша в чистых стратегиях.

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

Введем обозначение Х^*(χ_-i) = Arg max К_i (х_i,χ_-i) - множество чистых стратегий, которые являются наилучшими ответами на обстановку χ_-i. Пусть имеются два наилучших ответа x ^*_i X^*_i и x_i^** X_i ^*. Так как оба они являются лучшими ответами на обстановку χ_-i значит К_i (x_i^*, χ_-i) = К_i (х_i^**, χ_-i), то есть

M: =∫K_i (x_i^*,x_-i)χ_-i(x_-i)dx_-i = ∫ K_i (x_i^**, x_-i)χ_-i(x_-i)dx_-i.

Рассмотрим стратегию = αx_i^* + (1-α)x_i^**, где α (0,1).В силу выпуклости Х_i,, X_t. Ожидаемая полезность от применения этой стратегии:

K_i ( , χ_-i) = ∫ K_i ( , x_-i) χ_-i(x_-i)dx_-i =∫ K_i ( x_i^*+(1-α) x_i^**,x_-i) χ_-i(x_-i)dx_-i.

В силу строгой вогнутости целевой функции К_i, имеем К_i ( ,χ_-i)>α∫K_i (x_i^*,x_-i)χ_-i(x_-i)dx_-i +(1-α) ∫K_i (x_i^**,x_-i)χ_-i(x_-i)dx_-i.

Следовательно, K_i ( , χ_-i) > αM + (1-α)M = M, что невозможно, так как М- это максимальный ожидаемый выигрыш. Таким образом, наилучший ответ всегда один, а, значит, и равновесие Нэша будет равновесием в чистых стратегиях.

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

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

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

Пример 12. «Решение задачи стимулирования».

Опишем решение задачи стимулирования в многоэлементной ОС. Относительно параметров ОС введем сле­дующие предположения:

А.1.

А.2. N 1) функция с_i (.) непрерывна по всем переменным; 2) у_i A_i с_i(у) не убывает по у_i, i N; 3) у е A’ c_i(у) ≥ 0; 4) y_-i A_-i c_i(0,y_-i) = 0.

А.З. Функции стимулирования кусочно-непрерывны и принимают неотрицательные значения.

А.4. Функция дохода центра непрерывна по всем переменным и достигает максимума при ненулевых действиях агентов.

Если стимулирование каждого агента зависит от действий всех агентов, то определения множества равновесий Нэша P_N ( ) имеет вид:

P_N(σ) = {y^N A| i N y_i A_i σ_i(y^N) – c_i(y^N) ≥ σ_i (y_i, y_-i^N) – c_i(y_i, y_-i^N)};

РДС y_id А определяется условием: y_id A_i – доминантная стратегия i- го агента тогда и только тогда, когда

у_i А_i у_-i А_-i σ_i (у_id, у_-i) – с_-i(у_id, у_-i) ≥ σ_i (у_i, у_-i) – с_i(у_i, у_-i).

Если при заданной системе стимулирования у всех агентов имеется доминантная стратегия, то говорят, что данная система стимулирования реализует соответствующий вектор действий как РДС.

Если стимулирование каждого агента зависит только от его собственных действий, то определения множества равновесий Нэша P_N(σ) имеет вид:

E_N(σ) = {y^N A | i N y_i A_i σ_i(y_i^N) –c_i(y^N) ≥ σ_i(y_i) – c_i(y_i, y_-i^N)},

РДС у_d ∈ А определяется условием: у_id А_i - доминантная стратегия i -го агента тогда и только тогда, когда

у_i А_i у_-i А_-i σ_i (у_id, у_-i) – с_-i(у_id, у_-i) ≥ σ_i (у_i,) – с_i(у_i, у_-i).

Фиксируем произвольный вектор действий агентов у^* А' и рассмотрим следующую систему стимулирования:

σ^*_i(y^*,y) =

Если стимулирование каждого агента зависит только от его собственного действия, то, фиксировав для каждого агента обстановку игры, перейдем от σ^* ксистеме индивидуального стимулирования следующим образом: фиксируем произвольный вектор действий агентов у^* А' и определим систему стимулирования:

σ^**_i(y^*,y_i) =

Справедливы следующие утверждения:

1) При использовании центром системы стимулирования σ^*вектор действий у^* является РДС. Более того, если δ_i > 0, i N, то у - единственное РДС.

2) При использовании центром системы стимулирования σ^**вектор действий y^* является равновесием Нэша. Более того:

2.1) если выполнено условие:

y¹≠y² A’ I N: y_i¹ ≠ y_i²

и c_i(y¹) + c_i(y²) > c_i (y_i¹, y_-i²) – δ_i ,

то y^* –единственное равновесие Нэша;

2.2) если выполнено условие:

y¹≠y² A’ c_i(y¹) + c_i(y²) ≥ c_i (y_i¹, y_-i²) – δ_i,

то вектор действий у^* является РДС;

3) если выполнено предыдущее условие и δ_i > 0, i N, то вектор действий y^* является единственным РДС.

4) Вектор оптимальных реализуемых действий агентов у^*, фигурирующий в качестве параметра в системах стимулирования σ^* и σ^** определяется в результате решения следующей задачи: y^* Arg max {H(t)– },

а эффективность этих систем стимулирования равна следующей величине:

K^* = H(y^*) – –δ, где δ: =

5) Класс (с параметром у^*) систем стимулирования σ^*и σ^** является δ – оптимальным.

Содержательно, при использовании системы стимулирования σ^*центр использует следующий принцип декомпозиции: он предлагает i -му агенту: «выбирай действие y_i^*, а я компенсирую тебе затраты, независимо от того какие действия выбрали ос­тальные агенты, если же ты выберешь любое другое действие, то вознаграждение будет равно нулю». При использовании системы стимулирования σ^** центр предлагает i -му агенту: «выбирай дей­ствие у_i^*, а я компенсирую тебе затраты, считая, что остальные агенты также выбрали соответствующие компоненты – y_-i^*, если же ты выберешь любое другое действие, то вознаграждение будет равно нулю». Используя такую стратегию, центр декомпозирует игру агентов.