Автоматика и телемеханика, № 12, 2021

С.Д. МЕРЗЛИКИНА (sv.merzlikina@mail.ru)

(Московский авиационный институт

(национальный исследовательский университет))

ПОИСК РАВНОВЕСИЙ ПО НЭШУ В БИМАТРИЧНЫХ

ИГРАХ С ВЕРОЯТНОСТНЫМИ И КВАНТИЛЬНЫМИ

ФУНКЦИЯМИ ВЫИГРЫШЕЙ¹

Рассматривается биматричная игра со случайными выигрышами иг-

роков и смешанными стратегиями. Определяются функции вероятности

и квантили потерь игроков (выигрышей с противоположным знаком).

Для данных функций потерь рассматриваются задачи поиска равнове-

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

к биматричной игре с функциями выигрышей в форме математического

ожидания. Получены необходимые и достаточные условия существования

равновесия в игре с квантильным критерием. Доказана теорема о свя-

зи равновесий в играх с квантильными и вероятностными критериями.

Предложен алгоритм поиска равновесий в игре с квантильным критери-

ем. Алгоритм основан на последовательном решении задач поиска точек,

принадлежащих множествам, описываемым квадратичными невыпуклы-

ми ограничениями. Предлагаются подходы к нахождению данных точек.

Приведены результаты вычислений равновесных пар стратегий.

Ключевые слова: теория игр, биматричная игра, функция вероятности,

функция квантили, равновесие по Нэшу, игра с вероятностными ограни-

чениями.

DOI: 10.31857/S0005231021120072

1. Введение

Важной задачей исследования операций является описание поведения

нескольких конкурирующих лиц, одновременно принимающих решения. Для

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

игр (см., например, [1, 2]). Равновесием по Нэшу называется такая ситуация

в игре, при которой ни одному из игроков невыгодно отклоняться от вы-

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

стратегий игроков (так называемых чистых стратегий) выигрыши игроков

могут быть записаны с помощью двух матриц, поэтому такая игра называ-

ется биматричной.

Известно, что в биматричной игре не всегда существует равновесие по

Нэшу в чистых стратегиях. В связи с этим рассматривается смешанное рас-

ширение биматричной игры, состоящее в том, что игроки задают вероятно-

сти выбора чистых стратегий (смешанные стратегии). При этом функциями

¹ Работа выполнена при финансовой поддержке Российского фонда фундаментальных

исследований (проект № 20-37-70022).

105

выигрышей игроков являются математические ожидания случайного выиг-

рыша. В такой биматричной игре всегда существует равновесие по Нэшу в

смешанных стратегиях. Поиск равновесия в биматричной игре сводится к

решению конечного числа систем линейных уравнений [1]. Другой подход ос-

нован на теореме, доказанной в [3], согласно которой все равновесия по Нэшу

в биматричной игре являются глобальными оптимумами некоторой квадра-

тичной невыпуклой задачи оптимизации. Метод решения данной задачи с

помощью теории d.c.-оптимизации предложен в [4]. Способ сведения поиска

равновесия по Нэшу в полиматричной игре к невыпуклой задаче оптимиза-

ции предложен в [5].

Не всегда использование математического ожидания в качестве критери-

альной функции оправданно. Надежность функционирования моделируемой

системы целесообразно описывать с помощью функций вероятности и кван-

тили [6]. В биматричной игре можно сформулировать функции потерь иг-

роков в форме вероятности и квантили. Функция вероятности определяется

как вероятность непревышения потерями игрока заданного уровня. Значение

функции квантили показывает минимальные потери игрока, непревышение

которых гарантируется с заданной вероятностью. Данный подход был при-

менен в [7], где формулировалась игра с медианной функцией выигрыша,

представляющей собой квантиль уровня 1/2. Методы поиска минимаксной

стратегии в игре с квантильным критерием предложены в [8], а для игр со

случайными функциями выигрышей — в [9]. Задачи поиска равновесий по

Нэшу в этих работах не рассматривались.

Алгоритм поиска равновесия по Нэшу в матричной игре с квантильным

критерием предложен в [10], где предполагалось, что первый игрок макси-

мизирует свой гарантированный доход, а второй игрок стремится его мини-

мизировать. В [10] доказано существование равновесия по Нэшу в этой игре.

Следует отметить возникающую асимметрию в принятии решений согласно

этой модели. С точки зрения второго игрока более выгодна не минимиза-

ция гарантированного дохода первого игрока, а максимизация собственного

гарантированного выигрыша. В отличие от [10] в данной работе рассматрива-

ется биматричная игра, в которой каждый из игроков стремится максимизи-

ровать свой гарантированный выигрыш (или минимизировать свои потери).

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

роятностными функциями потерь.

Близкая к рассматриваемой в работе постановка изучалась в [11], где

функции выигрышей игроков определяются как квантили усредненных по

смешанным стратегиям случайных доходов игроков. Данная игра в [11] на-

зывается игрой с вероятностными ограничениями. Для некоторых распреде-

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

В [12] для биматричной игры с вероятностными ограничениями для некото-

рых распределений случайных параметров предложен метод поиска равнове-

сия по Нэшу, основанный на сведении к задаче квадратичного программиро-

вания. Обобщение данных игр на случай непрерывных стратегий приводится

в [13]. В отличие от [11, 12] в данной работе используется другой подход к

106

определению функции потерь: рассматривается не квантиль усредненных по

смешанным стратегиям случайных доходов игроков, а квантиль случайных

доходов игроков без усреднения по стратегиям.

Игры с квантильными критериями нашли свое применение при моделиро-

вании взаимодействия экономических агентов [14] и моделировании энерге-

тических рынков [15].

2. Постановка задачи

Пусть поведение первого игрока описывается случайным вектором ξ

с реализациями e₁, . . . , e_m, где e_k — m-мерный вектор, k-я компонента ко-

торого равна 1, а все остальные компоненты равны 0. Аналогично поведение

второго игрока описывается случайным вектором η с реализациями e′1, . . . , e^′n,

где e^′l — n-мерный вектор, l-я компонента которого равна 1, а все остальные

компоненты равны 0. Случайные векторы ξ и η определены на некотором

вероятностном пространстве (Ω, F, P) и являются независимыми. Распреде-

ления случайных векторов ξ и η описываются векторами x ∈ R^m, y ∈ Rⁿ,

компоненты которых определяются по правилу

x_k ≜ P{ξ = e_k}, k ∈ {1,... ,m},

y_l ≜ P{η = e^′l}, l ∈ {1,... ,n}.

Векторы x, y называются смешанными стратегиями первого и второго игрока

соответственно. Они должны удовлетворять ограничениям:

{

}

∑

x∈X ≜

x_k = 1, x ≥ 0

k=1

{

}

∑

y∈Y ≜

y_l = 1, y ≥ 0

l=1

Стратегии, в которых только одна компонента равна единице, а остальные

компоненты равны нулю, называются чистыми.

Случайные проигрыши (или выигрыши с противоположным знаком) пер-

вого и второго игрока при использовании чистых стратегий задаются матри-

цами A ≜ (a_kl) и B ≜ (b_kl), k ∈ {1, . . . , m}, l ∈ {1, . . . , n}, составленными из

случайных величин a_kl : Ω → R, b_kl : Ω → R на вероятностном пространстве

(Ω, F, P). Таким образом, в результате игры игроки получают случайные вы-

игрыши -ξ^⊤Aη и -ξ^⊤Bη соответственно.

В данной статье предполагается, что случайные величины a_kl, b_kl являют-

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

векторы ξ, η и случайный вектор, составленный из всех случайных величин

a_kl, b_kl, независимые. Из независимости этих случайных векторов следует,

что вероятность события, состоящего в том, что проигрыш первого игрока

составит не более заданной величины ϕ ∈ R, равняется

{

}

(1)

P ξ^⊤Aη ≤ ϕ

=x^⊤

A(ϕ)y,

107

где элементы матрицы A(ϕ) = (a_kl(ϕ)) определяются по правилу:

a_kl(ϕ) ≜ P{a_kl ≤ ϕ}.

Аналогично можно определить вероятность того, что проигрыш второго иг-

рока составит не более заданной величины ψ ∈ R:

{

}

P ξ^⊤Bη ≤ ψ

= x^⊤B(ψ)y,

где B(ψ) = (b_kl(ψ)), b_kl(ψ) ≜ P{b_kl ≤ ψ}.

Таким образом, следуя принятой в [6] терминологии, можно ввести функ-

ции вероятности

{

}

P_ϕ(A,x,y) ≜ P ξ^⊤Aη ≤ ϕ

= x^⊤A(ϕ)y,

{

}

P_ψ(B,x,y) ≜ P ξ^⊤Bη ≤ ψ

= x^⊤B(ψ)y,

где ϕ, ψ — заданные числа. Функции вероятности при заданных значени-

ях x и y как функции параметров ϕ и ψ являются функциями распределе-

ния случайных величин ξ^⊤Aη, ξ^⊤Bη соответственно. Значения P_ϕ(A, x, y),

P_ψ(B,x,y) показывают вероятность благоприятного исхода игры, когда про-

игрыш оказывается меньше предельно допустимого уровня, для первого

и второго игрока соответственно. Таким образом, игроки заинтересованы

в максимизации данных вероятностей. Поэтому можно определить игру с ве-

роятностным критерием, которая будет обозначаться как P(A, B, ϕ, ψ). Для

данной игры ставится задача поиска равновесия по Нэшу.

Определение 1. Пара смешанных стратегий (x,y) ∈ X ×Y называет-

ся равновесной по Нэшу в игре P(A,B,ϕ,ψ) с вероятностным критерием,

если для всех x^′ ∈ X, y^′ ∈ Y выполнено

P_ϕ(A,x^′,y) ≤ P_ϕ(A,x,y),

P_ψ(B,x,y^′) ≤ P_ψ(B,x,y).

Введем функции квантили

(2)

ϕα(A, x, y) = min{ϕ ∈ R | Pϕ(A, x, y) ≥ α},

(3)

ϕβ (B, x, y) = min{ψ ∈ R | Pψ(B, x, y) ≥ β},

где α ∈ (0, 1), β ∈ (0, 1) — заданные значения функций вероятности. В (2) ми-

нимум корректно определен [6] по той причине, что функция ϕ → P_ϕ(A, x, y)

является функцией распределения случайной величины ξ^⊤Aη, а функция

распределения всегда является непрерывной справа. Аналогичное верно и

для (3). Таким образом, значение ϕ_α(A, x, y) показывает минимальный про-

игрыш первого игрока, непревышение которого гарантируется с вероятно-

стью α, а ϕ_β(B, x, y) — минимальный проигрыш второго игрока, непревы-

шение которого гарантируется с вероятностью β. Иными словами, значения

108

-ϕ_α(A,x,y) и -ϕ_β(B,x,y) равны максимальным гарантированным с задан-

ными вероятностями выигрышам первого и второго игрока соответственно.

Сформулируем понятие равновесия по Нэшу в игре с квантильным кри-

терием, которая будет обозначаться как Q(A, B, α, β).

Определение 2. Пара смешанных стратегий (x,y) ∈ X × Y называет-

ся равновесной по Нэшу в игре Q(A,B,α,β) с квантильным критерием, если

для всех x^′ ∈ X, y^′ ∈ Y выполнено

ϕα(A, x^′, y) ≥ ϕα(A, x, y),

ϕβ (B, x, y^′) ≥ ϕβ(B, x, y).

В статье рассматриваются задачи поиска равновесия по Нэшу в играх

P(A, B, ϕ, ψ) и Q(A, B, α, β).

Замечание 1. Отметим отличия игры Q(A,B,α,β) от других извест-

ных постановок игр с квантильными критериями. Сравнение произведем, ис-

пользуя обозначения данной статьи и заменив функции дохода на функции

потерь. В [10] функцией потерь первого игрока является ϕ_α(A, x, y), а функ-

ция потерь второго игрока равна -ϕ_α(A, x, y). Это значит, что второй игрок

не минимизирует собственные потери, а максимизирует потери соперника.

В общем случае -ϕ_α(A, x, y) = ϕ_α(-A, x, y). Поэтому специальные методы,

предложенные в [10], не могут быть применены для решения рассматривае-

мой задачи, даже когда B = -A.

В [11, 12] функция потерь определяется следующим образом: ϕ^′α(A, x, y) =

= min{ϕ ∈ R | P{xAy ≤ ϕ} ≥ α}. Заметим, что P{xAy ≤ ϕ} = P_ϕ(A,x,y) =

= P{ξAη ≤ ϕ}, поскольку x = Mξ, y = Mη. Это значит, что постановка

[11, 12] предполагает усреднение функции потерь по смешанным стратеги-

ям игроков. Отметим, что если матрица A является детерминированной, то

данная постановка сводится к детерминированной игре. Изучаемая в данной

работе задача даже в случае детерминированной матрицы A требует разра-

ботки новых методов.

3. Условия равновесия по Нэшу в играх с вероятностным

и квантильным критериями

Рассмотрим произвольные случайные матрицы A и B, задающие игру с

вероятностным или квантильным критерием. Расположим уникальные зна-

чения реализаций элементов матрицы A в порядке возрастания и обозначим

их через ϕ₁, . . . , ϕ_M . Определим случайные величины a_kl по правилу: a_kl =

= i, если a_kl = ϕ_i. Составим случайную матрицу

A≜ (a_kl), k ∈ {1,... ,m},

)

B₌

(b_k

l ∈ {1,...,n}. Аналогично по матрице B построим матрицу

, а

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

через ψ₁, . . . , ψ_N . Для удобства будем считать, что ϕM+1 = ψN+1 = +∞. Иг-

ру с вероятностным или квантильным критерием, задаваемую полученными

случайными матрицами^A и^B, назовем игрой в стандартной форме. В по-

лученной игре элементы матриц^A и^B принимают значения во множествах

{1, . . . , M}, {1, . . . , N} соответственно.

109

Введем матрицы A(ϕ) ≜ {a_kl(ϕ)} и B(ψ) ≜ {b_kl(ψ)}, элементы которых

определяются по правилу

a_kl(ϕ) = P{a_kl ≤ ϕ}, b_kl(ψ) = P{b_kl ≤ ψ},

k ∈ {1,...,m}, l ∈ {1,...,n}.

Аналогично определяются матриц

A(ϕ) ≜ {a_kl(ϕ)} и^B(ψ) ≜ {bkl(ψ)}:

(4)

a_kl(ϕ) = P{a_kl ≤ ϕ},

bkl(ψ) = P{^bkl

≤ ψ}.

Введем обозначения

(5)

A_i

A(i), B_j ≜B

(j), i ∈ {0, 1, . . . , M}, j ∈ {0, 1, . . . , N}.

Заметим, что матрицы A₀ и B₀ являются нулевыми, а все элементы матриц

A_M и B_N равны единице.

Лемма 1. Если ϕ_i ≤ ϕ < ϕi+1, то

P_ϕ(A,x,y) = x^⊤A(ϕ)y = P_i(^A,x,y) = x^⊤A_iy.

Доказательства леммы 1 и последующих теорем, лемм и следствий вынесены

в Приложение.

Теорема 1. Пусть ϕ_i ≤ ϕ < ϕi+1, ψ_j ≤ ψ < ψj+1. Тогда следующие три

утверждения эквиваленты:

1) пара стратегий (x, y) ∈ X × Y является равновесной в игре

P(A, B, ϕ, ψ);

2) пара стратегий (x, y) ∈ X×Y является равновесной в игре P(^A,^B, i, j);

3) для всех x^′ ∈ X и y^′ ∈ Y

x^′⊤A_iy ≤ x^⊤A_iy,

x^⊤B_jy^′ ≤ x^⊤B_jy.

Таким образом, полученный критерий позволяет любую игру с вероятност-

ным критерием свести к игре в стандартной форме. Отметим, что множество

игр в стандартной форме при фиксированных m, n является конечным.

Из теоремы 1 следует, что равновесие в игре с вероятностным критерием

эквивалентно равновесию в биматричной игре с матрицами выигрышей иг-

роков A_i и B_j , определeнными в (5). Поэтому для поиска равновесия в игре с

вероятностным критерием можно применять методы, разработанные для би-

матричных игр с критерием в форме математического ожидания [1, 4]. Как

известно, такое равновесие всегда существует [1].

Перейдeм к изучению игр с квантильным критерием.

Лемма 2. Для любых стратегий (x,y) ∈ X × Y выполнено

1) ϕ_α(A, x, y) ∈ {ϕ₁, . . . , ϕ_M };

2) ϕ_α(A, x, y) = ϕ_i тогда и только тогда, когда ϕ_α(^A, x, y) = i,

i ∈ {1,...,M}.

110

Сформулируем теорему о необходимых и достаточных условиях равнове-

сия по Нэшу в игре с квантильным критерием.

Теорема 2. Пусть α,β ∈ (0,1). Тогда следующие три утверждения эк-

виваленты:

1) пара стратегий (x, y) ∈ X × Y является равновесной в игре

Q(A, B, α, β);

2) пара стратегий (x, y) ∈ X × Y является равновесной в игре

Q(^A,^B, α, β);

3) для некоторых i ∈ {1, . . . , M}, j ∈ {1, . . . , N} выполнены неравенства

(6)

x^⊤A_i

y ≥ α,

(7)

x^⊤B_j

y≥β,

(8)

∥Ai-1y∥_∞

< α,

(9)

∥B⊤j-1x∥_∞

< β,

где ∥x∥_∞ = max

|x_k|.

k∈{1,...,m}

При этом выполнены равенства

ϕα(A, x, y) = ϕi, ϕβ (B, x, y) = ψj, ϕα(^A, x, y) = i, ϕβ (^B, x, y) = j.

Таким образом, любая игра с квантильным критерием может быть сведе-

на к игре в стандартной форме. Кроме того, теорема 2 описывает простые

условия для проверки равновесности заданной пары стратегий игроков, не

требующие вычисления функций квантили. Для проверки этих условий необ-

ходимо только вычислить матрицы A_i, B_j, Ai-1, Bj-1 по формуле (5).

Сформулируем следствия из теоремы 2.

Докажем, что если в биматричной игре с матрицами выигрышей игроков

-A и -B существует ситуация равновесия в чистых стратегиях, то те же

стратегии являются равновесными в игре с квантильным критерием.

Следствие 1. Пусть для пары стратегий (e_k,e^′l) с вероятностью еди-

ница выполнены условия

e^⊤k′Ae^′l ≥ e^⊤kAe^′l,

e^⊤kBe^′l′ ≥ e^⊤kBe^′l

для всех k^′ ∈ {1, . . . , m}, l^′ ∈ {1, . . . , n}. Тогда (e_k, e^′l) — пара равновесных

стратегий в игре Q(A,B,α,β) для всех α ∈ (0,1), β ∈ (0,1).

Нижеприведенные следствия определяют необходимые условия, которым

должны удовлетворять i, j, чтобы существовало решение системы неравенств

(6)-(9).

Следствие 2. Если (x,y) ∈ X×Y — пара равновесных стратегий в игре

Q(^A,^B, α, β), ϕ_α(^A, x, y) = i, ϕ_β (^B, x, y) = j, то матрица Ai-1 не содержит

строк, все элементы которых не меньше α, а матрица Bj-1 не содержит

столбцов, все элементы которых не меньше β.

111

Отметим, что если матрица Ai-1 содержит строку, все элементы которой

не меньше α, то матрицы A_i, . . . , A_M обладают тем же свойством.

Следствие 3. Если (x,y) ∈ X × Y — пара равновесных стратегий в иг-

ре Q(^A,^B,α,β), ϕ_α(^A,x,y) = i, ϕ_β(^B,x,y) = j, то хотя бы один элемент

матрицы A_i + B_j не меньше α + β.

Отметим, что если все элементы матрицы A_i + B_j меньше α + β, то таким

же свойством обладают матрицы A_i′ + B_j′ при i^′ ≤ i, j^′ ≤ j.

4. О связи игр с квантильным и вероятностным критериями

Докажем теорему о том, что равновесная пара стратегий в игре с вероят-

ностным критерием при некоторых значениях уровней надежности является

равновесной и в игре с квантильным критерием.

Теорема 3. Пусть (x,y) — пара равновесных стратегий в игре P(^A, ^B,

i - 1,j - 1), i ∈ {1,...,M}, j ∈ {1,...,N}. Тогда (x,y) — пара равновесных

стратегий в игре Q(^A,^B,α,β) для

(10)

α ∈ (x^⊤Ai-1y,x^⊤A_iy], β ∈ (x^⊤Bj-1y,x^⊤B_j

y].

К сожалению, доказать или опровергнуть существование равновесия в

произвольной игре с квантильным критерием затруднительно. Это связано с

тем, что график многозначного отображения x → Arg min

ϕα(A, x, y) не яв-

y∈Y

ляется замкнутым, что не позволяет применить теорему Какутани, исполь-

зуемую для доказательства существования равновесия в игре с критерием в

форме математического ожидания [1]. Однако теорема 3 показывает, что при

некоторых значениях α и β в игре с квантильным критерием равновесие су-

ществует. При проведении многочисленных вычислительных экспериментов

авторам не удалось найти примеров, в которых не существует равновесных

стратегий.

5. Алгоритм поиска равновесия в игре с квантильным критерием

Полученные следствия из теоремы 2 позволяют предложить алгоритм по-

иска равновесных пар стратегий в игре с квантильным критерием. Введем

обозначения:

{

}

M ≜ max i ∈ {1,...,M} | max

min

a_kl(i - 1) < α

k∈{1,...,m}

l∈{1,...,n}

{

}

N ≜ max j ∈ {1,...,N} | max

min

bkl(j - 1) < β

l∈{1,...,n}

k∈{1,...,m}

⎧

⎫

⎨

⎬

N (i) ≜ min

j ∈ {1,...,N} | max

{a_kl(i) +bkl(j)} ≥ α + β

⎩

k∈{1,...,m},

⎭

l∈{1,...,n}

112

где a_kl(i),bkl(j) определены в (4). Пусть

M ≜ min{i ∈ {1,...,M} | N(i) ≤ N}.

Для поиска равновесий по Нэшу в игре с квантильным критерием можно

предложить следующий алгоритм.

Алгоритм 1.

1. Установить i := M.

2. Если i ≤ M, установить j := N(i). В противном случае завершить вы-

полнение алгоритма.

3. Если j ≤ N, то перейти к следующему шагу. Иначе перейти к шагу 6.

4. Найти пару стратегий (x, y) ∈ X × Y , удовлетворяющую ограничениям

(6)-(9). Если такая пара (x, y) найдена, то она является равновесной.

5. j := j + 1. Перейти к шагу 3.

6. i := i + 1. Перейти к шагу 2.

Отметим, что при выполнении алгоритма перебираются только те значе-

ния i, j, для которых выполнены необходимые условия существования реше-

ния системы (6)-(9), обеспечиваемые следствиями 2, 3.

При практической реализации алгоритма могут возникать трудности с

проверкой на непустоту в общем случае незамкнутого множества, описывае-

мого ограничениями (6)-(9). Данная проблема может быть решена двумя

способами. Первый способ состоит в замене ограничений (8), (9) на ограни-

чения

(11)

∥Ai-1y∥_∞

≤ α - ε,

(12)

∥B⊤j-1x∥_∞

≤ β - ε,

где ε — малая положительная константа. Ограничения (11), (12) эквивалент-

ны линейным ограничениям

(13)

Ai-1y ≤ (α - ε)e_m,

(14)

B⊤j-1x ≤ (β - ε)e_n,

где e_m — вектор, составленный из m единиц. При использовании данного

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

линейными и квадратичными (в общем случае невыпуклыми) ограничениями

(6), (7), (13), (14). Данная задача может быть решена с помощью программ,

предназначенных для решения линейных и квадратичных задач математи-

ческого программирования с линейными и квадратичными ограничениями.

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

некоторых решений исходной задачи.

Второй подход состоит в решении задачи

(15)

θ^∗ ≜

{

}

≜ min

θ | Ai-1y ≤ αe_mθ, B⊤j-1x ≤ βe_nθ, x^⊤A_iy ≥ α, x^⊤B_jy ≥ β

θ∈R, x∈X, y∈Y

113

В задаче (15) минимум достигается, потому что множество допустимых зна-

чений (x, y) является компактом, а ограничение θ ∈ R может быть заменено_[

{

}]

на θ ∈

0, max

,¹

. Сформулированная задача также может быть реше-

на с помощью специальных программ. Нетрудно заметить, что θ^∗ < 1 в том

и только том случае, когда множество, описываемое ограничениями (6)-(9),

непусто. Если θ^∗ < 1, то пара оптимальных значений переменных (x, y) в за-

даче (15) будет являться равновесной по Нэшу в игре Q(A, B, α, β).

Следует заметить, что ограничения (6), (7) являются невыпуклыми. По-

этому проверка на совместность системы неравенств (6), (7), (13), (14) или

решение задачи (15) является трудоемким. В связи с этим представляют ин-

терес быстрые методы поиска пар стратегий (x, y), удовлетворяющих огра-

ничениям (6)-(9). Предлагается следующий алгоритм, с помощью которого

могут быть найдены решения системы неравенств (6)-(9).

Алгоритм 2.

1. Задать начальное значение стратегии второго игрока y⁽⁰⁾ ∈ Y , ν := 0.

2. Решить задачу линейного программирования:

{

}

(16) θ(ν)1 ≜ max

θ | x^⊤A_iy(ν) ≥ αθ, x^⊤B_jy(ν) ≥ βθ, B^⊤

x ≤ (β - ε)e_n

j-1

θ∈R, x∈X

Оптимальное значение переменной x в задаче (16) обозначим через x(ν). Если

у этой задачи нет решений, то система неравенств (6), (7), (13), (14) несов-

местна. Если ν > 0 и θν1 ≥ 1, то (x(ν), y(ν)) — пара равновесных стратегий в

игре Q(A, B, α, β). Если ν > 1 и θ(ν)1 ≤ θ(ν-1)1, завершить выполнение алго-

ритма.

3. Решить задачу линейного программирования:

{

}

(17) θ(ν)2 ≜ max

θ | x(ν)⊤A_iy ≥ αθ, x(ν)⊤Bjy ≥ βθ, Ai-1y ≤ (α - ε)em

θ∈R, y∈Y

Оптимальное значение переменной y в задаче (17) обозначим через y(ν+1).

Если у этой задачи нет решений, то система неравенств (6), (7), (13), (14)

несовместна. Если θν2 ≥ 1, то (x(ν), y(ν+1)) — пара равновесных стратегий в

игре Q(A, B, α, β).

4. Присвоить ν := ν + 1 и перейти к шагу 2.

При ν = 0 в результате применения алгоритма находится пара стратегий

(x⁽⁰⁾, y⁽¹⁾), удовлетворяющая неравенствам (13), (14). Затем получается воз-

растающая последовательность θ⁽¹⁾¹ ≤ θ⁽¹⁾² ≤ θ⁽²⁾¹ ≤ θ⁽²⁾² ≤ . . . ≤ θqν), где q = 1

или q = 2. Если θ(ν)1 ≥ 1 и ν > 0, то (x(ν), y(ν)) — пара равновесных стратегий в

игре Q(A, B, α, β). Если θ(ν)2 ≥ 1, то (x(ν), y(ν+1)) — пара равновесных страте-

гий в игре Q(A, B, α, β). Если θ(ν)1 < 1 или θ(ν)2 < 1, то для поиска равновесной

пары стратегий можно снова воспользоваться алгоритмом 2, задав другую

начальную стратегию y⁽⁰⁾. В силу невыпуклой структуры рассматриваемой

задачи нельзя гарантировать, что в результате применения алгоритма будет

114

найдено решение системы неравенств (6), (7), (13), (14), если оно существу-

ет. Однако в случае успешного применения алгоритма 2 нет необходимости

решать задачу невыпуклой оптимизации.

Предложим алгоритм поиска начальной стратегии y⁽⁰⁾ ∈ Y для примене-

ния алгоритма 2.

Алгоритм 3.

1. Найти максимальные элементы матриц A_i - Ai-1 и B_j - Bj-1. Обозна-

чим индексы этих элементов через (k₁, l₁), (k₂, l₂) соответственно.

2. Если k₁ = k₂, l₁ = l₂, то при выполнении условий ak1l₁ ≤ akl₁ для всех

k ∈ {1,...,m}, bk2l₂ ≤ bk₂l для всех l ∈ {1,... ,n} определить y⁽⁰⁾ = e^l . Если₁

k₁ = k₂, l₁ = l₂, но указанные условия не выполнены, то найти

l^∗ = arg max

{ak1l | ak₁l + ak₁l₂ ≤ 1}.

l∈{1,...,j}

Если для всех l выполнено ak1l + ak₁l₂ > 1, определить l^∗ произвольно. Задать

y(0)l

= α - ε, y(0)l∗ = 1 - α + ε, где ε — малая положительная константа.

3. Если k₁ = k₂, l₁ = l₂, то найти такой индекс l^∗ = l₁, для которого при

всех k выполнено a_kl∗ + akl1 ≤ 1. Если такого индекса нет, то определить l^∗

произвольно.

4. Если l₁ = l₂, то y(0)l

= y⁽⁰⁾ = 1/2._l

Идея предлагаемого алгоритма 3 состоит в том, чтобы увеличить левые

части неравенств (6), (7), но при этом по возможности не нарушить неравен-

ства (8), (9).

6. Примеры

6.1. Игра 2 × 2

При m = n = 2 наибольший интерес представляют игры, в которых не су-

ществует равновесия в чистых стратегиях. Таковой является игра в стандарт-

ной форме с детерминированными матрицами

(

)

(

)

Пусть¹² < α ≤ β < 1. Тогда для i = j = 3 система неравенств (6)-(9) примет

вид

x₁y₁ + x₂y₁ + x₂y₂ = 1 - x₁y₂ ≥ α,

x₁y₂ + x₂y₁ + x₂y₂ = 1 - x₁y₁ ≥ β,

y₁ < α, y₂ < α,

x₁ < β, x₂ < β.

115

Как нетрудно проверить, данной системе неравенств удовлетворяет пара

стратегий (x, y), если

(

)

(

)

x₁

1/2

x₁ ∈ (1 - β,min{β,2(1 - β)}).

1-x₁

1/2

Если α < β < 1, β >¹² , то первый игрок может уменьшить свои потери до

i = 2, при этом j = 3. Соответствующая система неравенств (6)-(9) принима-

ет вид

x₁y₁ + x₂y₂ ≥ α,

x₁y₂ + x₂y₁ + x₂y₂ ≥ β,

y₁ < α,

x₁ < β, x₂ < β.

Данной системе неравенств удовлетворяют пары стратегий (x, y), если

(

)

(

)

1-x₂

x₂ ∈ (max{α,1 - β},β).

x₂

6.2. Игры 3 × 3

Разработанный алгоритм поиска равновесия в игре с квантильным крите-

рием был программно реализован на языке matlab с использованием реша-

теля задач квадратичного программирования gurobi. Исходные данные этих

задач и найденные точки равновесия в игре с квантильным критерием при-

ведены в табл. 1.

В первой строке таблицы приведено решение задачи для игры с нуле-

вой суммой. При равных значениях α и β было найдено две пары равновес-

ных стратегий, соответствующих различным потерям второго игрока: j = 6 и

j = 7. Потери первого игрока для каждой из полученных стратегий одинако-

вы и равны i = 5. Если α < β, то в игре имеется три равновесных стратегии с

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

имеет возможность уменьшить свои потери до i = 3. Это связано с умень-

шением уровня его доверительной вероятности. Оставшиеся две равновесные

точки обеспечивают те же потери, что и в случае α = β.

Во второй строке табл. 1 приведено решение для игры с ненулевой сум-

мой. Для уровней вероятности α = β = 0,9 и α = 0,8, β = 0,9 были найдены

три равновесные стратегии. Отметим, что при уменьшении доверительной

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

возможных.

В третьей строке табл. 1 приведены результаты вычислений для случай-

ных матриц A, B. Случайная величина τ принимает 4 равновероятных зна-

чения: 0, 1, 2, 3.

Приведенные решения были найдены менее чем за одну секунду.

116

Таблица 1. Равновесные стратегии в игре

3×3

)

⁽1

⁽9

⁽ 0,0999

⁽ 0,8999

0,9

0,1001

0,8000

)

⁽ 0,1461

⁽ 0,5005

0,8476

0,4752

0,0063

0,0243

)

⁽ 0,1078

⁽ 0,0399

0,8

0,9

0,8844

0,8998

0,0078

0,0603

)

⁽ 0,0998

⁽ 0,7999

0,1001

0,8001

0,2001

)

⁽ 0,1462

⁽ 0,2001

0,7538

0,7999

0,1000

)

⁽1

⁽5

⁽ 0,0077

⁽ 0,8968

0,9

0,8935

0,1032

0,0988

)

⁽ 0,1001

⁽ 0,8902

0,8999

0,0110

0,0988

)

⁽ 0,8973

⁽ 0,8092

0,0923

0,0906

0,0104

0,1002

)

⁽ 0,8999

⁽ 0,8891

0,8

0,9

0,1001

0,0987

0,0122

)

⁽ 0,6284

⁽ 0,7877

0,3716

0,0334

0,1789

)

⁽ 0,7938

⁽ 0,7866

0,0769

0,0133

0,1293

0,2001

)

⁽1

⁽5

⁽0

⁽ 0,9001

0,9

0,0999

(

)

(

)

⁽ -1 0 0

⁽1

+τ

0,8668

−2

0,1332

)

(

)

⁽ 0,1707

0,1707

0,8293

(

)

(

)

0,1998

0,5000

0,8002

0,5000

)

⁽ 0,3592

⁽ 0,8756

0,5947

0,0461

0,1244

)

⁽ 0,1214

⁽ 0,3340

0,0456

0,8330

0,6660

(

)

⁽ 0,4000

0,2000

0,8000

0,6000

117

Все эти решения, кроме одного, были найдены как с помощью точного

решения систем неравенств (6), (7), (13), (14), так и с помощью быстрых

алгоритмов 2 и 3. Во втором примере не удалось найти стратегию, соответ-

ствующую i = 4, j = 5, при α = 0,8, β = 0,9.

6.3. Игра 6 × 8

Рассматривается игра Q(A, B, 0,9, 0,9), задаваемая детерминированными

матрицами

⎛

⎞

⎛

⎞

30 11

30 25 26 26 28

28 20 30 23 34

21 12

⎜13 20 18 11 28

12 29⎟

⎜10

18 11

17 20⎟

⎜

⎟

⎜

⎟

⎜

29 24 27 10 35

⎟

⎜19

25 13 32 16

⎟

⎜

⎟

⎜

⎟

⎜32 35 19 21 15

18⎟

⎜26 10 13 30 15 29 13 22⎟.

⎜

⎟

⎜

⎟

⎝₂₃₆

16 31 24

22 17⎠

⎝₃₃₃₁

22 14 34

10⎠

35 33 34

30 14 24

36 20 21 27 29 24

Для поиска равновесных стратегий применялся разработанный алгоритм.

Во избежание возможных ошибок округления вместо системы неравенств

(6)-(9) решалась система неравенств

x^⊤A_iy ≥ α + ε,

x^⊤B_jy ≥ β + ε,

∥Ai-1y∥_∞ ≤ α - ε,

∥B⊤j-1x∥_∞ ≤ β - ε,

где ε = 10-4.

В данной игре удалось найти 86 пар равновесных стратегий, соответст-

вующих различным значениям целевых функций игроков. Соответствующие

значения отражены в табл. 2. По строкам расположены значения функции

квантили первого игрока, а по столбцам — второго игрока. Знаками * и +

отмечены те пары значений (i, j), для которых удалось найти равновесные

стратегии, при этом знаком + отмечены те значения (i, j), для которых уда-

лось найти решение с помощью быстрого алгоритма 2 с начальным решением,

получаемым с помощью алгоритма 3. Алгоритм 2 позволил найти 49 решений

задачи.

Приведем решение, оптимальное по Парето (соответствующее значениям

(i, j) = (5, 6)):

⎛

⎞

0,0963

⎛

⎞

⎜

⎟

⎜0,8999⎟

⎜

⎟

⎜

⎟

0,0630

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

0,8999

⎜

⎟,

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎝

⎠

⎜

⎟

⎜

⎟

0,0371

⎝0,0038⎠

118

Таблица 2. Найденные равновесия в игре 6 × 8

i\j

Вычисления проводились на ЭВМ с процессором Intel(R) Core(TM)

i5-6300U, 2,4 ГГц, 8 ГБ ОЗУ. Вычислительное время при применении ал-

горитма 1 составило 6363 с, а при применении быстрого алгоритма 2 — всего

лишь 7,5 с.

Приведенный пример показывает, что в игре небольшой размерности мо-

жет существовать большое количество пар равновесных стратегий, соответ-

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

значительного объема вычислений, однако большая часть решений может

быть найдена достаточно быстро с помощью алгоритмов 2 и 3.

7. Заключение

В работе были рассмотрены задачи поиска равновесия в играх с вероят-

ностными и квантильными критериями. Задача с вероятностным критерием

была сведена к биматричной игре с функциями выигрышей в форме матема-

тических ожиданий. Для решения задачи с квантильным критерием предло-

жен алгоритм, основанный на последовательном решении задач поиска точек

множеств, описываемых квадратичными невыпуклыми ограничениями. Од-

нако вопрос о существовании равновесия в произвольной игре с квантильным

критерием остается открытым. Авторы провели большое количество вычис-

лений на случайно моделируемых данных, в результате которых не удалось

119

обнаружить примеров, когда не существует равновесных стратегий. К сожа-

лению, поиск равновесных стратегий в игре с квантильным критерием раз-

мерности 6 × 8 продолжался более часа. По этой причине был предложен

быстрый метод поиска равновесий, с помощью которого удалось найти 49 из

86 решений задачи. Отметим, что многие из рассмотренных в работе подхо-

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

Также представляют интерес игры с квантильным критерием и непрерыв-

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

разработка новых методов.

ПРИЛОЖЕНИЕ

Доказательство леммы 1. Первое равенство следует из независи-

мости ξ и η и установлено в (1). Из определения величин ϕ_i и неравенства

ϕi ≤ ϕ < ϕi+1 следует, что akl(ϕ) = akl(i). Поэтому

x^⊤A(ϕ)y = x^⊤A_iy = P_i(^A,x,y).

Лемма 1 доказана.

Доказательство теоремы 1. Теорема следует из определения 1 рав-

новесия по Нэшу в игре с вероятностным критерием и из леммы 1, согласно

которой

P_ϕ(A,x,y) = P_i(^A,x,y) = x^⊤A_iy,

P_ψ(B,x,y) = P_j(^B,x,y) = x^⊤B_jy.

Теорема 1 доказана.

Доказательство леммы 2. Докажем утверждение 1) леммы. Пред-

положим противное. Тогда возможны две ситуации: ϕ_α(A, x, y) < ϕ₁ или

ϕi < ϕα(A, x, y) < ϕi+1 для некоторого i ∈ {1, . . . , M}. В первом случае

P_ϕ(A,x,y) = 0, что противоречит неравенству P_ϕ(A,x,y) ≥ α в определе-

нии квантили, так как α > 0. Во втором случае α ≤ P_ϕ(A, x, y) = Pϕi (A, x, y),

откуда следует, что ϕ_α(A, x, y) ≤ ϕ_i. Полученное противоречие доказывает

утверждение 1) леммы.

Утверждение

2) леммы следует из леммы

1, согласно которой

Pϕi(A,x,y) = P_i(^A,x,y). Лемма 2 доказана.

Доказательство теоремы 2. Из леммы 2 и упорядоченности вели-

чин ϕ_i и ψ_j следует эквивалентность утверждений 1) и 2).

Отметим, что

{

}

ϕα(^A, x, y) = min i ∈ {1, . . . , M} | x^⊤Aiy ≥ α ,

{

}

ϕβ (^B, x, y) = min j ∈ {1, . . . , N} | x^⊤Bjy ≥ β

Докажем, что из утверждения 2) следует утверждение 3). Пусть для за-

данной пары (x, y) ∈ X × Y выполнено ϕ_α(^A, x, y) = i, ϕ_β(^B, x, y) = j. Это

120

значит, что

x^⊤A_iy ≥ α, x^⊤B_jy ≥ β.

Неравенства (6), (7) доказаны. Из определения равновесия по Нэшу следует,

что для всех x^′ ∈ X, y^′ ∈ Y выполнено

(Π.1)

ϕα(^A, x^′, y) ≥ ϕα(A,x,y) = i,

(Π.2)

ϕβ(^B, x, y^′) ≥ ϕβ (B,x,y) = j.

Докажем, что для всех x^′ ∈ X, y^′ ∈ Y

(Π.3)

x^′⊤Ai-1

y < α,

(Π.4)

x^⊤Bj-1y^′

< β.

Предположим противное. Пусть для определенности нарушается неравен-

ство (Π.3) при некотором x^′ ∈ X. Это значит, что Pi-1(^A, x^′, y) ≥ α, но тогда

в силу определения функции квантили ϕ_α(^A, x^′, y) ≤ i - 1, что противоре-

чит неравенству (Π.1). Аналогично устанавливается, что при x^⊤Bj-1y^′ ≥ β

нарушается неравенство (Π.2). Таким образом, неравенства (Π.3) и (Π.4) до-

казаны.

В силу того, что множества X и Y компактны, выполнение неравенств

(Π.3) и (Π.4) для всех x^′ ∈ X, y^′ ∈ Y эквивалентно неравенствам

(Π.5)

maxx′⊤Ai-1y < α, max

x^⊤Bj-1y^′

< β.

x^′∈X

y^′∈Y

∑

Заметим, что ∥x∥₁ ≜

|x_k| = 1, ∥y∥₁ = 1. Поэтому

k=1

max

x^′⊤Ai-1y ≤ ∥Ai-1y∥_∞∥x∥₁ = ∥Ai-1y∥_∞,

x^′∈X

max

x^⊤Bj-1y^′ ≤ ∥B⊤j-1x∥_∞∥y∥₁ = ∥B⊤j-1x∥_∞.

y^′∈Y

Верхние оценки данных максимумов достигаются, если x^′ = e_k∗ , y^′ = e_l∗ , где

k^∗ и l^∗ номера максимальных компонент векторов Ai-1y и B⊤j-1x соответ-

ственно. Поэтому

(Π.6)

max

x^′⊤Ai-1y = ∥Ai-1y∥_∞,

x^′∈X

(Π.7)

max

x^⊤Bj-1y^′ = ∥B⊤j-1x∥_∞.

y^′∈Y

Доказываемые неравенства (8), (9) следуют из полученных равенств (Π.6),

(Π.7) и неравенств (Π.5).

Пусть теперь выполнено утверждение 3). Из неравенств (6)-(9) следует,

что x^⊤A_iy ≥ α и x^⊤Ai-1y < α, x^⊤B_j y ≥ β и x^⊤Bj-1y < β. Значит,

(Π.8)

ϕα(^A, x, y) = i, ϕβ (B,x,y) = j.

121

Из неравенств (8), (9) следует, что при любых x^′ ∈ X, y^′ ∈ Y выполнено

x^′⊤Ai-1y < α, x^⊤Bj-1y^′ < β. Поэтому

(Π.9)

ϕα(^A, x^′, y) ≥ i, ϕβ (^B, x, y^′) ≥ j.

Из равенств (Π.8) и неравенств (Π.9) следует, что пара стратегий (x, y) явля-

ется равновесной. Эквивалентность утверждений 2) и 3) доказана.

Равенства ϕ_α(A, x, y) = ϕ_i, ϕ_β(B, x, y) = ψ_j следуют из (Π.8) и леммы 2.

Теорема 2 доказана.

Доказательство следствия 1. Из условий следствия и леммы 1

вытекает, что при всех i ∈ {0, 1, 2, . . . , M}, j ∈ {0, 1, 2, . . . , N}, ϕ ∈ [ϕ_i, ϕi+1),

ψ ∈ [ψ_j,ψj+1) выполнены неравенства

{

}

{

}

(Π.10)

e^⊤k′ A_ie^′l = P e^⊤k′Ae^′l ≤ ϕ

≤ P e⊤k Ae^′l ≤ ϕ

=e^⊤kA_ie^′l,

{

}

{

}

(Π.11)

e^⊤kB_je^′l′ = P e^⊤kBe^′l′ ≤ ψ

≤ P e⊤k Be^′l ≤ ψ

=e^⊤kB_je^′l.

Пусть i^∗ = ϕ_α(^A, e_k, e^′l), j^∗ = ϕ_β(^B, e_k, e^′l). Тогда по определению (2) квантили

e^⊤kA_i∗e^′l ≥ α, e^⊤kB_j∗e^′l ≥ β, e^⊤kA_i∗-1e^′l < α, e^⊤kB_j∗-1e^′l < β. Из этих неравенств

и неравенств (Π.10) и (Π.11) следует, что

∥A_i∗-1e^′l∥_∞ =

max

e^⊤k′ A_i∗-1e^′l < α,

k^′∈{0,1,...,m}

∥B_j∗-1e^′l∥_∞ = max

e^⊤kB_j∗-1e^′l′ < β.

l^′∈{0,1,...,n}

Таким образом, из теоремы 2 следует, что (e_k, e^′l) — пара равновесных страте-

гий в игре Q(A, B, α, β) для всех α ∈ (0, 1), β ∈ (0, 1). Следствие 1 доказано.

Доказательство следствия

Если Ai-1 содержит строку, все

∑

элементы которой не меньше α, то ∥Ai-1y∥_∞ ≥ αy_l = α, что противоречит

l=1

неравенству (8). Аналогично, если Bj-1 имеет столбец, все элементы которого

не меньше β, то ∥B⊤j-1x∥_∞ ≥ β, что противоречит (9). Следствие 2 доказано.

Доказательство следствия 3. Предположим противное: все элемен-

ты матрицы A_i + B_j меньше α + β. Тогда

∑∑

(Π.12)

x^⊤(A_i + B_j)y < (α + β)

x_ky_l

=α+β.

k=1 l=1

С другой стороны, складывая неравенства (6) и (7), получаем

x^⊤(A_i + B_j)y ≥ α + β,

что противоречит неравенству (Π.12). Следствие 3 доказано.

122

Доказательство теоремы 3. Пусть (x,y) — пара равновесных стра-

тегий в игре P(^A,^B, i - 1, j - 1). Тогда

∥Ai-1y∥_∞ = x^⊤Ai-1y,

∥B⊤j-1x∥_∞ = x^⊤Bj-1y.

Таким образом, при α и β, удовлетворяющих условию (10), выполнены нера-

венства (6)-(9), сформулированные в критерии равновесия в квантильной

игре. Теорема 3 доказана.

СПИСОК ЛИТЕРАТУРЫ

Петросян Л.А., Зенкевич Н.А., Шевкопляс Е.В. Теория игр. СПб.: БХВ-

Петербург, 2012.

Воробьев Н.Н. Основы теории игр. Бескоалиционные игры. М.: Наука, 1984.

Mills H. Equilibrium points in finite games // J. Soc. Industr. Appl. Math. 1960.

V. 8. No. 2. P. 397-402.

Орлов А.В., Стрекаловский А.С. О численном поиске ситуаций равновесия в би-

матричных играх // Ж. вычисл. матем. и матем. физики. 2005. Т. 45. № 6.

С. 983-997.

Orlov A.V., Strekalovskii A.S. Numerical search for equilibria in bimatrix games //

Computational Mathematics and Mathematical Physics. 2005. V.

45. No.

P. 947-960.

Стрекаловский А.С., Энхбат Р. Полиматричные игры и задачи оптимизации //

АиТ. 2014. № 4. С. 51-66.

Strekalovskii A.S., Enkhbat R. Polymatrix Games and Optimization Problems //

Autom. Remote Control. 2014. V. 75. P. 632-645.

Кибзун А.И., Кан Ю.С. Задачи стохастического программирования с вероят-

ностными критериями. М.: Физматлит, 2009.

Walsh J.E. Median Two-Person Game Theory for Median Competitive Games //

J. Oper. Res. Soc. Jpn. 1969. V. 12. No. 1. P. 11-20.

De Vries H. Quantile Criteria for the Selection of Strategies in Game Theory // Int.

J. Game Theory. 1974. V. 3. No. 2. P. 105-114.

Cassidy R.G., Field C.A., Kirby M.J.L. Solution of a Satisficing Model for Random

Payoff Games // Manage. Sci. 1972. V. 19. No. 3. P. 266-271.

10.

Popov L.D. Methods for Matrix Games with Mixed Strategies and Quantile

Payoff Function / Bykadorov I., Strusevich V., Tchemisova T. (eds) Mathematical

Optimization Theory and Operations Research. MOTOR 2019. Communications in

Computer and Information Science, v. 1090. Cham: Springer, 2019. P. 304-318.

11.

Singh V.V., Jouini O., Lisser A. Existence of Nash Equilibrium for Chance-

Constrained Games // Oper. Res. Lett. 2016. V. 44. P. 640-644.

12.

Singh V.V., Lisser A. A Characterization of Nash Equilibrium for the Games with

Random Payoffs // J. Optimiz. Theory App. 2018. V. 178. P. 998-1013.

13.

Singh V.V., Lisser A. Variational inequality formulation for the games with random

payoffs // J. Global Optim. 2018. V. 72. P. 743-760.

123