Санкт-Петербургский государственный университет
Кафедра математической теории игр и статистических
решений
Белькина Юлия Тимуровна
Выпускная квалификационная работа бакалавра
Одна сетевая игра с неоднородными предпочтениями
агентов
010400
Прикладная математика и информатика
Научный руководитель,
кандидат физ.-мат. наук,
старший преподаватель
Тур А.В.
Санкт-Петербург
2016
Содержание
Введение. Обзор литературы . . . . . . . . . . . . . . . . . . . . . . .
3
Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
Глава 1. Игра с полной информацией . . . . . . . . . . . . . . . . . .
9
1.1. Стратегии в игре с полной информацией . . . . . . . . . . .
9
1.2. Равновесия по Нэшу . . . . . . . . . . . . . . . . . . . . . . .
10
Глава 2. Игра с неполной информацией . . . . . . . . . . . . . . . . .
13
2.1. Равновесия по Нэшу. Случаи с одинаковыми стратегиями
агентов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.2. Примеры ситуаций равновесия с одинаковыми стратегиями
агентов в игре с неполной информацией . . . . . . . . . . . . . .
15
2.3. Равновесия по Нэшу в игре с неполной информацией . . . .
17
2.4. Пример ситуаций равновесия по Нэшу в игре с неполной
информацией . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
Глава 3. Задача о выборе провайдера . . . . . . . . . . . . . . . . . .
23
3.1. Равновесия по Нэшу. Случаи с одинаковыми стратегиями
агентов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
3.2. Примеры ситуаций равновесия с одинаковыми стратегиями
агентов в задаче о выборе провайдера . . . . . . . . . . . . . . .
25
3.3. Равновесия по Нэшу . . . . . . . . . . . . . . . . . . . . . . .
26
3.4. Пример ситуаций равновесия по Нэшу для задачи о выборе
провайдера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
Приложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
2
Введение. Обзор литературы
Теория игр – раздел математики, изучающий процесс принятия решения в условиях конфликта. Конфликтная ситуация, в которой участвует
более одного игрока, предполагает, что каждая сторона преследует свою
цель, учитывая свои предпочтения.
В реальной жизни возможны случаи, когда игрокам становится выгодно
действовать, учитывая не только свои предпочтения, а также действия других игроков. И зачастую оказывается выгоднее поступиться своими предпочтениями, действуя как другие участники конфликта.
Тем не менее, индивидуальные предпочтения являются основой для поведения в контексте силы социального влияния на такие решения. Например,
при выборе между двумя продуктами, потенциальный покупатель гораздо
вероятнее выберет то, что ему больше нравится.
Подобная модель впервые была рассмотрена в 1957 году Данканом
Люче и Говардом Райффом. В игре "Битва полов” [1], которая предполагает участие двух игроков с разными предпочтениями, муж и жена принимают решение пойти на футбол (что является предпочтением мужа) или
пойти на балет (что является предпочтением жены). При этом игроки не
получают никакого удовлетворения от посещения мероприятия в одиночку.
Оказывается, что равновесными в этой игре оказываются ситуации, в которых одному из игроков приходится поступиться своим предпочтением.
Естественным выглядит желание обобщить эту модель на случай n
игроков. Подобная игра в 2008 г. была рассмотрена в работе Дж. Джао и
др. [2]. В данной статье для каждого из игроков определяется выигрыш,
который зависит от собственного предпочтения, выбранного действия и
количества игроков, выбравших такое же действие.
В 2013 г. П. Эрнандес и др. усложнили модель "Битва полов” n лиц,
добавив сетевую структуру игры [3]. В предложенной игре на сети выиг-
3
рыши игроков зависят только от действий соседей, но не всех игроков. Для
такой модели сформулировано правило нахождения наилучшего ответа на
известные действия его соседей (случай полной информации).
В данной работе также рассматривается сетевая игра с неоднородными предпочтениями агентов. Исследуются условия, при которых игрокам
выгодно выбирать одинаковые действия вне зависимости от личных предпочтений. А также разрабатывается алгоритм поиска всех равновесий по
Нэшу в игре с неполной информацией.
4
Постановка задачи
Рассмотрим сетевую игру с неоднородными предпочтениями агентов,
впервые определенную в работе [3].
В статье изучается социальная сеть (N, g). N = {1, .., n}, где |N | ≥ 2 –
множество агентов, взаимодействующих в игре.
g – множество связей (ребер) между агентами. Если пара агентов соединена
связью, то это обозначается,как (i , j ) ∈ g, а если никакой связи между
ними нет, то (i , j ) ∈
/ g.
Множеством потенциальных связей агентов является полная сеть,
g N , и любая конфигурация сети является подмножеством множества
G = {g : g ⊂ g N }.
Набор соседей агента i представлен, как
ki (g) = {j ∈ N : (i, j) ∈ g}, ∀j 6= i.
Для простоты полагается, что (i , i ) ∈
/ g, то есть все соседи в ki (g) будут
отличаться от i-ого. Тогда мощность множества ki (g) будет обозначаться
как ki , то есть ki – количество соседей i-го агента.
Агенты из набора N взаимодействуют в сетевой игре, обозначаемой
как Γ. Каждый агент i ∈ N изначально наделен определенным предпочтением θi ∈ {0 , 1 }. X = {0 , 1 } - множество допустимых стратегий для
каждого из агентов.
Если ki (g) = {j1 , j2 , . . . , jki }, тогда вектор стратегий соседей i-го агента
xki (g) = {xj1 , xj2 , . . . , xjki }. Вектор стратегий соседей i-го агента обозначается как xki (g) .
Линейная функция выигрыша i-го агента данной игры, ui (·), зависит
от выборов агентов, их соседей и предпочтений, а именно:
ui (θi , xi , xki (g) ) = λθxii [1 + δ
X
I{xj =xi } + (1 − δ)
j∈ki (g)
5
X
j∈ki (g)
I{xj 6=xi } ],
(1)
где
I{xj =xi } =
0, xj 6= xi ,
I{xj 6=xi } =
1, xj = xi ,
то есть
гию xi .
P
j∈k
Pi (g)
0, xj = xi ,
1, xj 6= xi ,
I{xj =xi } – количество соседей i-го агента, выбравших стратеI{xj 6=xi } – количество соседей i-го агента, выбравших противо-
j∈ki (g)
положную стратегию. Параметр λ определяется, как λθxii = α, когда игрок
выбирает стратегию, совпадающую с его предпочтением, в противном случае λθxii = β, то есть
λθxii =
α, xi = θi ,
β,
xi 6= θi ,
причем α > β > 0. Параметр δ принимает значение 0 или 1. В зависимости
от величины δ получаем два типа игры. При δ = 1 – игра типа SC (strategic
complements), при δ = 0 – игра типа SS (strategic substitutes).
Каждый агент стремится максимизировать свой выигрыш. Таким образом,
игра задается следующим набором Γ = {N , {g}(i ,j )∈N , X , {θi }i ∈N , {ui }i ∈N }.
Главной особенностью подобного задания игры является то, что оно простым способом затрагивает несколько стратегических сценариев.
В результате можно наблюдать как выигрыш агента зависит от выборов других агентов, учитывая их предпочтения. Это мотивирует нас углубиться в изучение того, как конфликт предпочтений взаимодействует с
сетевой структурой.
Кроме того, путем введения различных типов агентов расширены
границы применимости модели сетевой игры к ситуациям, в которых предпочтения разных агентов могут не совпадать.
В статье рассматривается «частичный порядок» i видов стратегий
соседей для заданного агента i. Фиксируется агент i c ki количеством соседей и предпочтением θi , где xki (g) и xk0i (g) – два вида стратегий его соседей.
P
P
Будем считать, что xki (g) i xk0i (g) , если
I{xj =1 } ≥
I{xj0 =1 } . Чем
j ∈ki (g)
j ∈ki (g)
больше соседей агента i выбирают 1, тем более вероятно, что агент i выбе-
6
рет 1.
Функция выигрыша для SC (δ = 1 ) удовлетворяет условию:
если xki (g) i xk0i (g) , то
ui (θi , 1, xki (g) ) − ui (θi , 0, xki (g) ) ≥ ui (θi , 1, x0ki (g) ) − ui (θi , 0, x0ki (g) ).
(2)
Заметим, что когда xki (g) i xk0i (g) количество выборов "0"в xk0i (g) значительно больше, чем в xki (g) . Домножая (2) на (-1), получим следующее неравенство:
ui (θi , 0 , xk0i (g) ) − ui (θi , 1 , xk0i (g) ) ≥ ui (θi , 0 , xki (g) ) − ui (θi , 1 , xki (g) ).
Исходя из обоих неравенств, приводится заключение, что агентам SC
игры более выгодно выбирать ту же стратегию, что выбрало большинство
их соседей.
Аналогично, функция выигрыша SS (δ = 0 ) удовлетворяет условию:
если xki (g) i xk0i (g) , то
ui (θi , 1, xki (g) ) − ui (θi , 0, xki (g) ) ≤ ui (θi , 1, x0ki (g) ) − ui (θi , 0, x0ki (g) ).
(3)
Аналогично случаю SC игры заключим,что агентам SS игры более выгодно
выбирать ту же стратегию, что и выбрало меньшинство их соседей.
Агенты в нашей игре Γ = {N , {g}(i ,j )∈N , X , {θi }i ∈N , {ui }i ∈N }, принимают решение в выборе стратегии из бинарного набора X.
В качестве принципа оптимальности в работе [3] рассмотрено равновесие по Нэшу [4]. Ситуация (x1∗ , ..., xn∗ ) равновесие по Нэшу, если
ui (θi , x1∗ , ..., xi∗ , ..., xn∗ ) ≥ ui (θi , x1∗ , ..., xi0 , ..., xn∗ ), ∀xi0 ∈ X , xi0 6= xi∗ .
Заметим, что действия игроков, не являющихся соседями для данного игрока, никак не влияют на его выигрыш.
В работе [3] рассмотрен случай полной информации сетевой игры, в
котором игрокам при выборе стратегии xi известен выбор всех его соседей.
В данной работе исследуются ситуации равновесия по Нэшу для игры с
7
неполной информацией, в которой игрокам до выбора ими стратегии xi
известны только лишь предпочтения игроков, но не их действия.
8
Глава 1. Игра с полной информацией
В данном разделе рассматривается сетевая игра Γ с полной информацией, описанная в [3], и для нее характеризуется набор ситуаций равновесия
по Нэшу NE(Г). Для этого проводится детальный анализ для игр типа SC.
1.1. Стратегии в игре с полной информацией
В сетевой игре Г агент выбирает стратегию из набора X = {0 , 1 }.
Сеть подразделяется на два типа:1) Все агенты выбирают одинаковые стратегии (S). 2) Обе стратегии выбираются различными агентами (H).
Принимая во внимание предпочтения агентов, существует две возможные
категории их типа: те, у которых выбор совпадает с предпочтением xi = θi
(S), и те, для которых это не так xi 6= θi (F).
Таким образом существуют 4 возможные конфигурации сети:
(i)(SS ): все агенты выбрали одинаковое действие, которое является их предпочитаемым выбором, xi = θi ;
(ii)(FS ): все агенты выбрали одинаковое действие, но один из них выбрал
действие, не соответствующего его предпочтению, xi 6= θi ;
(iii)(SH ): все агенты выбрали действие, соответствующее их предпочтению,
но не у всех из них одинаковые предпочтения. Поэтому оба действия здесь
присутствуют.
(iiii)(FH ): все агенты выбрали разные действия, и, среди них есть хотя бы
один, выбравший не предпочитаемое.
Данные конфигурации игры c SC продемонстрированы в Рисунке 1.
9
11
11
11
11
11
00
01
11
11
11
01
11
11
00
11
00
11
11
00
00
SS1 (SS0 )
FS1 (FS0 )
SH
FH
Рис. 1: Типы конфигураций. Первое число демонстрирует предпочтение агента, а второе
его выбор.
1.2. Равновесия по Нэшу
Опишем сетевые игры в отношении «односторонних отклонений» агентов.
Пусть χi - количество соседей агента i, выбравших стратегию 1.
Соответственно, ki − χi – количество соседей агента i, выбравших 0, где ki
- общее число соседей i-ого агента.
Через d. . . e и b. . . c обозначим максимальную нижнюю границу и минимальную верхнюю границу рассматриваемого вещественного числа.
Утверждение 1 демонстрирует лучшие стратегии для игры типа SC,
основываясь на порогах изменения стратегий агентов. Для SS случая связь
χi с порогами обратна.
Утверждение 1 ( [3]) Для SC игры, пусть:
τ (ki ) = d
β
α−β
ki −
e,
α+β
α+β
(4)
τ (ki ) = b
α
α−β
ki +
c,
α+β
α+β
(5)
определенные для любой степени ki ∈ {1 , ..., N − 1 }.
Лучший выбор для агента i с предпочтением θi = 1 и степенью ki ,
x∗i будет равняться
10
x∗i =
1,
если χi ≥ τ (ki ),
0,
в противном случае.
(6)
Лучший выбор для агента i c предпочтением θi = 0 и степенью ki ,
x∗i будет равняться
x∗i =
0,
если χi ≤ τ (ki ),
1,
в противном случае.
(7)
В игре типа SS лучший выбор для агента i с предпочтением θi = 1
и степенью ki , x∗i будет равняться
x∗i =
1,
если χi ≤ τ (ki ),
0,
в противном случае.
(8)
Лучший выбор для агента i c предпочтением θi = 0 и степенью ki ,
x∗i будет равняться
x∗i =
0,
если χi ≥ τ (ki ),
1,
в противном случае.
(9)
В Утверждении 1 указан лучший выбор для каждого агента в связи с
его предпочтением и выбором его соседей. Важно подчеркнуть то, что выбор агента никак не зависит от предпочтений его соседей, а только от их
выборов.
В результате это позволяет проанализировать равновесия по Нэшу и
то, как они зависят от распределения предпочтений, стратегий и характеристик сети.
Очевидно, что таких равновесий будет большое множество.
Примеры таких равновесий продемонстрированы на Рисунке 2.
11
11
11
11
11
11
11
11
11
01
11
00
00
11
11
SS1 (SS0 )
11
00
FS1 (FS0 )
11
11
10
11
11
00
00
01
00
00
FH
SH
00
00
SH (SS)
00
00
FH (SS)
Рис. 2: Примеры равновесий по Нэшу. Первое число демонстрирует предпочтение агента, а второе его выбор.
12
Глава 2. Игра с неполной информацией
В утверждении 1, рассмотренном в [3], предполагается, что агенты
делают свой выбор, зная выбор других агентов. В данном разделе рассмотрена сетевая игра Γ с неполной информацией, то есть случай, когда
агентам заранее неизвестны выборы других агентов, и охарактеризован для
нее набор равновесий по Нэшу NE(Г). Проведен детальный анализ для игр
типа SC.
Рассмотрим как влияет структура сети и распределение предпочтений агентов на наборы равновесий по Нэшу.
Для этого введем сеть с неполной информацией, где агенты знают
предпочтения всех агентов и структуру сети, но не обладают информацией по поводу выборов других агентов. Рассмотрение сети с неполной
информацией «мотивирует» нас к изучению более реалистичного подхода взаимодействий агентов с конфликтными предпочтениями, их проблем
согласования.
Четыре конфигурации сетевой игры (i,ii,iii,iiii) с полной информацией
сохранятся и для игры с неполной информацией.
13
2.1. Равновесия по Нэшу. Случаи с одинаковыми
стратегиями агентов
Рассмотрев игру с неполной информацией (Г), с SC-характеристиками,
заметим некую зависимость между выборами агентов и количеством их соседей.
В случае некоторых конфигураций сети, где предпочтения у агентов
одинаковые, им выгоднее выбирать стратегию, совпадающую с их предпочтением. Но, в связи с тем, что агенты не знают выборов других агентов,
они могут выбирать противоположные стратегии.
Утверждение 2 проиллюстрирует условия, при которых ситуации
(0, 0, . . . , 0) и (1, 1, . . . , 1) будут равновесными по Нэшу.
Утверждение 2 Если для каждого агента i ∈ N выполняется условие
ki > α/β − 1,
(10)
то ситуации (0, 0, . . . , 0) и (1, 1, . . . , 1) являются ситуациями равновесия по Нэшу, где ki - количество соседей агента i, α и β - произвольные
значения такие, что α > β > 0 .
Доказательство:
Пусть x̄ = (1, 1, . . . , 1); x̂ = (0, 0, . . . , 0).
Рассмотрим выигрыши агента i c предпочтением θi = 1 в ситуациях x̄, x̂:
1. ui (1, 1, x̄ki (g) ) = α(1 + ki ) > β(1) = ui (1, 0, x̄ki (g) ).
Так как α > β, то агенту i не выгодно отклоняться от стратегии 1.
2. ui (1, 0, x̂ki (g) ) = β(1 + ki ) > α(1) = ui (1, 1, x̂ki (g) ).
Если выполняется условие (10), то агент может сделать выбор в пользу стратегии, противоположной его предпочтению. В данном случае
стратегии 0. Отклоняться от этой стратегии ему не выгодно.
Аналогично, рассмотрим выигрыши агента i c предпочтением θi = 0
в ситуациях x̄, x̂:
14
1. ui (0, 0, x̄ki (g) ) = α(1 + ki ) > β(1) = ui (0, 1, x̄ki (g) ).
Так как α > β, то агенту i не выгодно отклоняться от стратегии 0.
2. ui (0, 1, x̂ki (g) ) = β(1 + ki ) > α(1) = ui (0, 0, x̂ki (g) ).
Если выполняется условие (10), то агент может сделать выбор в пользу стратегии, противоположной его предпочтению. В данном случае
стратегии 1. Отклоняться от этой стратегии ему не выгодно.
Таким образом, мы доказали, что игроку с любым предпочтением при выполнении условия (10) не выгодно отклоняться ни от ситуации x̄, ни от
ситуации x̂.
Значит, ситуации x̄, x̂ являются ситуациями равновесия по Нэшу.
2.2. Примеры ситуаций равновесия с одинаковыми
стратегиями агентов в игре с неполной
информацией
Рассмотрим Пример 1 сетевой игры для 5 агентов с разными предпочтениями:
Пусть α = 7 , β = 3 , N=5, a i ∈ (1 ..N ). Зададим вектор предпочтений
агентов Q = (0, 1, 0, 1, 0), матрицу смежности
0 1 0
1 0 1
P =
0 1 0
1 1 0
0 1 1
1 0
1 1
0 1
,
0 0
0 0
где pi,j = 1, если (i, j) ∈ g; p(i,j) = 0, если (i, j) ∈
/ g.
ki для каждого игрока i будет равняться сумме элементов i-ой строки.
Схематически игру демонстрирует Рисунок 3.
15
1
2
4
3
5
Рис. 3
Здесь α/β − 1=1,33.
Проверим выполнение утверждения для каждого агента:
Для 1-го агента с предпочтением 0, ki =2, 2>1,33.
Для 2-го агента с предпочтением 1, ki =4, 4>1,33.
Для 4-го агента с предпочтением 1, ki =2, 2>1,33.
3-й и 5-й агенты имеют предпочтение 0 и двух соседей ki =2, 2>1,33.
Таким образом, для всех игроков условие (10) выполняется. Приходим к
выводу, что и ситуация (0, 0, . . . , 0), и (1, 1, . . . , 1) будут являться равновесиями по Нэшу для этой игры.
Теперь рассмотрим другой пример сетевой игры, для которой ситуации одинаковых выборов не будут равновесны.
Пример 2 сетевой игры для 5 агентов с разными предпочтениями:
Пусть α = 7 , β = 3 , N = 5, i ∈ (1..N ). Зададим вектор предпочтений
агентов Q = (1, 1, 0, 0, 0), матрицу смежности
0 0 1
0 0 0
P =
1 0 0
0 1 0
0 1 0
0 0
1 1
0 0
,
0 0
0 0
Схематически игру демонстрирует Рисунок 4.
1
2
3
4
Рис. 4
Здесь α/β − 1=1,33.
16
5
Проверим выполнение утверждения для каждого агента:
Для 1-го агента с предпочтением 1, ki =1, 1<1,33.
Для 2-го агента с предпочтением 1, ki =2, 2>1,33.
Для 3-го агента с предпочтением 0, ki =1, 1<1,33.
4-й,5-й агенты имеют предпочтение 0 и одного соседа ki =1, 1<1,33.
Таким образом, только для 2-го агента выполняется условие (10).
Приходим к выводу, что в этом случае и ситуация (0, 0, 0, 0, 0), и
(1, 1, 1, 1, 1) не будут являться равновесиями по Нэшу.
2.3. Равновесия по Нэшу в игре с неполной
информацией
В предыдущем разделе мы рассмотрели только возможные равновесия по Нэшу с одинаковыми стратегиями. В данном разделе рассмотрим
все возможные ситуации равновесия.
В игре с неполной информацией, как уже говорилось ранее, агенты
знают предпочтения всех агентов и количество своих соседей, а вот выборы их соседей остаются для них неизвестными. Важно помнить о том, что
выбор агента может зависеть лишь от выборов его соседей, а остальные
агенты на это никак не влияют.
То есть, исходя из характеристик сети (количества агентов, связей, предпочтений) будут формироваться своеобразные условия выбора стратегии
для каждого агента.
При проверке на оптимальность выбора агента будем ссылаться на
Утверждение 1.
В Утверждении 1 доказано, что при выполнении (6) и (7) ситуация X ∗
являeтся равновесием по Нэшу.
Докажем, что обратное тоже верно, то есть если X ∗ – ситуация равновесия по Нэшу, то (6) и (7) выполняются. Будем использовать этот факт в
алгоритме поиска равновесий по Нэшу.
Пусть (x∗1 , . . . , x∗n ) – ситуация равновесия по Нэшу.
1). Пусть θi = 1.
17
a). Если x∗i = 1, то
u(1, 1, x∗ki (g) ) ≥ u(1, 0, x∗ki (g) ),
так как X ∗ – ситуация равновесия по Нэшу. Тогда
α(1 + χ∗i ) ≥ β(1 + ki − χ∗i ),
откуда получаем следующее условие
χ∗i ≥
β
α−β
ki −
.
α+β
α+β
б). Если x∗i = 0, то
u(1, 0, x∗ki (g) ) ≥ u(1, 1, x∗ki (g) ),
так как X ∗ – ситуация равновесия по Нэшу. Тогда
β(1 + ki − χ∗i ) ≥ α(1 + χ∗i ),
откуда получаем следующее условие
χ∗i ≤
α−β
β
ki −
.
α+β
α+β
Таким образом, для игрока с предпочтением 1 условие (6) выполнено.
2).Пусть θi = 0.
а). Если x∗i = 0, то
u(0, 0, x∗ki (g) ) ≥ u(0, 1, x∗ki (g) ),
так как X ∗ – ситуация равновесия по Нэшу. Тогда
α(1 + ki − χ∗i ) ≥ β(1 + χ∗i ),
откуда получаем следующее условие
χ∗i ≤
α
α−β
ki +
.
α+β
α+β
18
б). Если x∗i = 1, то
u(0, 1, x∗ki (g) ) ≥ u(0, 0, x∗ki (g) ),
так как X ∗ – ситуация равновесия по Нэшу. Тогда
β(1 + χ∗i ) ≥ α(1 + ki − χ∗i ),
откуда получаем следующее условие
χ∗i ≥
α
α−β
ki +
.
α+β
α+β
Таким образом, для игрока с предпочтением 0 условие (7) выполнено.
Тогда алгоритм нахождения ситуаций равновесия по Нэшу будет выглядеть следующим образом:
1. Для всех возможных ситуаций находим значения χi для каждого агента
i ∈ N;
2. Проверяем выполнение условий (6) и (7). Если условия не выполняются,
то данная ситуация не является равновесной и она должна быть исключена из набора всех стратегий.
3. Множество стратегий после исключения стратегий на п.2 является множеством ситуаций равновесия по Нэшу.
2.4. Пример ситуаций равновесия по Нэшу в игре с
неполной информацией
Рассмотрим Пример 3 :
Пусть наша сетевая игра с неполной информацией представлена игрой следующего вида (Рисунок 5):
19
10
1
2
3
8
7
4
9
6
5
Рис. 5
Из данного изображения, мы видим, что участвует в сети всего 10
игроков (N=10).
У каждого есть свое предпочтение, и вектор предпочтений всех агентов
будет выглядеть как Q = (0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 1 ).
Пусть χi – количество соседей, выбравших действие 1, i ∈ N . К примеру,
если агент i имеет соседей i1 и i3 , и один из них выбрал 1, а другой 0, то
χi =1. Если же и тот, и другой сосед выберут 1, то χi =2.
Пусть α = 5 , 5 , β = 4 , 5 . Сразу посчитаем пороговые значения для
каждого возможного количества соседей агента:
Если ki = 1 , то τ (ki )=1; если ki = 2 , то τ (ki )=1; если ki = 3 , то τ (ki )=2;
Далее рассматривать не имеет смысла, так как максимальное число связей
в данной сети равно 3.
Если ki = 1 , то τ (ki )=0; eсли ki = 2 , то τ (ki )=1; если ki = 3 , то
τ (ki )=1.
После вычислений пороговых значений можем перейти непосредственно к проверке условий (6) и (7).
Так как каждый агент наделен своим предпочтением и связями, то мы
можем выделить для каждого оптимальный выбор в зависимости от его
характеристик.
Начнем с 1-го агента. Он обладает предпочтением 0 и связью со 2-ым
20
агентом. Таким образом, τ (ki )=0. Получаем такое условие для 1-го агента:
1, χ1 = 1,
∗
x (1) =
0, χ = 0.
1
У второго агента предпочтение 0 и его соседями являются 1-й и 3-й
агенты. Таким образом, τ (ki )=1. Получаем следующее условие для него:
1, χ2 = 2,
∗
x (2) =
0, χ = 0, 1.
2
Далее для следующих агентов условия будут выглядеть так:
x∗ (3) =
x∗ (5) =
x∗ (7) =
1, χ3 = 1, 2,
x∗ (4) =
0, χ3 = 0.
0, χ4 = 0, 1.
1, χ5 = 2,
1, χ6 = 2,
x∗ (6) =
0, χ5 = 0, 1.
0, χ6 = 0, 1.
1, χ7 = 2, 3,
1, χ8 = 2, 3,
x∗ (8) =
0, χ7 = 0, 1.
x∗ (9) =
1, χ4 = 2, 3,
1, χ9 = 2,
0, χ8 = 0, 1.
x∗ (10) =
0, χ9 = 0, 1.
1, χ10 = 1, 2,
0, χ10 = 0.
Таким образом, у нас уже будет дан набор всевозможных ситуаций. И
далее, с помощью алгоритма будем отсеивать не соответствующие, оставляя лишь равновесия по Нэшу.
Начиная со стратегии первого агента будем проверять выполняются ли для него условия (6),(7), если нет - то рассматриваемую ситуацию
исключаем из набора всех ситуаций. И так далее будем проверять выполнение утверждение для выбора каждого агента. В итоге мы получим 10
ситуаций равновесия по Нэшу:
21
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0), (1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
(0, 0, 1, 1, 1, 1, 1, 0, 0, 0), (1, 1, 1, 1, 1, 1, 1, 0, 0, 0),
(0, 0, 0, 0, 0, 0, 0, 1, 1, 1), (1, 1, 1, 0, 0, 0, 0, 1, 1, 1),
(0, 0, 1, 1, 0, 0, 1, 1, 1, 1), (1, 1, 1, 1, 0, 0, 1, 1, 1, 1),
(0, 0, 1, 1, 1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 1, 1, 1, 1, 1).
Также была написана программа, которая реализует описанный алгоритм и находит все ситуации равновесия по Нэшу для сетевой игры с
неполной информацией в зависимости от характеристик сети. Она продемонстрирована в Приложении 1.
При вводе таких входных параметров, как α, β, количество агентов,
вектор предпочтений и матрица смежности, и нажатии кнопки « Расчет»
программа посредством алгоритма выводит все ситуации равновесия по
Нэшу.
Рис. 6: Поиск равновесий по Нэшу в игре с неполной информацией.
22
Глава 3. Задача о выборе провайдера
Рассмотрим модификацию модели, предложенной в [3]. Предположим, что в некотором районе предлагают свои услуги по подключению к
сети Интернет два провайдера. Пусть имеется N потенциальных клиентов.
Каждый клиент (игрок) i ∈ N имеет некоторое предпочтение θi ∈ {0, 1}.
θi = 0, если клиент i склонен выбрать первого провайдера, θi = 1 – если
второго.
Будем считать, что задана сеть (N, g), где N = {1, .., n}, g – множество ребер в сети. Наличие ребра (i, j) в сети означает знакомство клиентов
i и j. Если (i, j) ∈
/ g, то клиенты i и j незнакомы. Тогда ki (g) – множество
знакомых i-го клиента, ki – количество знакомых i-го клиента. X = {0, 1}
– множество допустимых стратегий для каждого из клиентов, xi = 0, если
клиент выбирает первого провайдера, xi = 1 – если второго.
Пусть стоимость пакета подключения у каждого из провайдеров для
i-го клиента равна l +
1+
Pm
I{xj =xi } .
Первое слагаемое l > 0 в этой сумме
j∈ki (g)
означает
1+
некоторую
Pm
I{xj =xi } ,
фиксированную
стоимость,
второе
слагаемое
где m > 0, зависит от количества знакомых i-го клиента,
j∈ki (g)
выбравших этого провайдера. Заданную таким образом функцию можно
интерпретировать как популярную в последнее время акцию "Приведи друга”, при которой размер скидки конкретного клиента зависит от количества
приведенных им новых клиентов. В нашем случае стоимость m делится
между знакомыми i-го клиента, выбравших того же провайдера.
Таким образом, затраты i-го клиента можно представить следующей
функцией vi (·):
vi (θi , xi , xki (g) ) = µθxii [l +
1+
m
P
I{xj =xi }
].
(11)
j∈ki (g)
Здесь µθxii = ν, если xi = θi , т.е. клиент выбирает провайдера согласно
своему предпочтению, и µθxii = η, если xi 6= θi (выбор не соответствует
предпочтению), 0 < ν < η. Параметр µθxii можно интерпретировать как
23
меру неудовлетворенности клиента от выбора провайдера.
Каждый клиент стремится минимизировать свои затраты.
3.1. Равновесия по Нэшу. Случаи с одинаковыми
стратегиями агентов
Для такой модели сетевой игры c неполной информацией сформулируем Утверждение 3, которое проиллюстрирует условия, при которых
ситуации с одинаковыми стратегиями агентов будут равновесными по Нэшу.
Утверждение 3 Если для каждого агента i ∈ N выполняется условие
ki >
ηm
− 1,
ν(l + m) − ηl
(12)
то ситуации (0, 0, . . . , 0) и (1, 1, . . . , 1) являются ситуациями равновесия
по
Нэшу,
где
ki
-
количество
знакомых
клиента
i;
m, l, µ, ν — произвольные значения такие, что η > ν > 0 , a m, l > 0.
Доказательство: Пусть x̄ = (1, 1, . . . , 1); x̂ = (0, 0, . . . , 0).
Рассмотрим выигрыши агента i c предпочтением θi = 1 в ситуациях x̄, x̂:
1. ui (1, 1, x̄ki (g) ) = ν(l +
m
1+ki )
< η(l + m) = ui (1, 0, x̄ki (g) ).
Так как ν < η, то клиенту i не выгодно отклоняться от стратегии 1.
2. ui (1, 0, x̂ki (g) ) = η(l +
m
1+ki )
< ν(l + m) = ui (1, 1, x̂ki (g) ).
Если выполняется условие (12), то клиент может выбрать стратегию,
не совпадающую с его предпочтением. В данном случае стратегию 0.
Отклоняться от этой стратегии ему не выгодно.
Аналогично, рассмотрим выигрыши клиента i c предпочтением
θi = 0 в ситуациях x̄, x̂:
1. ui (0, 0, x̄ki (g) ) = ν(l +
m
1+ki )
< η(l + m) = ui (0, 1, x̄ki (g) ).
Так как ν < η, то клиенту i не выгодно отклоняться от стратегии 0.
24
2. ui (0, 1, x̂ki (g) ) = η(l +
m
1+ki )
< ν(l + m) = ui (0, 0, x̂ki (g) ).
Если выполняется условие (12), то клиент может сделать выбор в пользу стратегии, противоположной его предпочтению. В данном случае
стратегии 1.
Отклоняться от этой стратегии ему не выгодно.
Таким образом, мы доказали то, что игроку с любым предпочтением
при выполнении условия (12) не выгодно отклоняться ни от ситуации x̄,
ни от ситуации x̂.
Значит, ситуации x̄, x̂ являются ситуациями равновесия по Нэшу.
3.2. Примеры ситуаций равновесия с одинаковыми
стратегиями агентов в задаче о выборе провайдера
Рассмотрим Пример 4 сетевой игры для 6 клиентов с разными предпочтениями:
Пусть ν = 3 , η = 7 , m = 10, N = 6, l = 1, a i ∈ (1 ..N ). Зададим
вектор предпочтений клиентов Q = (0, 0, 1, 1, 0, 0), матрицу смежности
P =
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 1 0 0
0 0 1 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0
.
Схематически игру демонстрирует Рисунок 7.
6
2
1
3
4
Рис. 7
25
5
.
ηm
− 1=1,68.
ν(l + m) − ηl
Проверим выполнение утверждения для каждого клиента:
В нашем случае
Для 1-го клиента с предпочтением 0, ki =2, 2>1,68.
Для 2-го клиента с предпочтением 0, ki =2, 2>1,68.
Для 3-го клиента с предпочтением 1, ki =3, 3>1,68.
Для 4-го клиента с предпочтением 1, ki =3, 3>1,68.
Для 5-го,6-го клиентов с предпочтением 0, ki =2, 2>1,68.
Таким образом, для всех игроков условие (12) выполнено. Приходим к выводу, что в этой игре и ситуация (0, 0, . . . , 0), и (1, 1, . . . , 1) будут являться
равновесиями по Нэшу.
3.3. Равновесия по Нэшу
В данной задаче нам нужно минимизировать функцию выигрыша,
а не максимизировать, как в модели сетевой игры, рассмотренной в двух
первых главах. Для этого введем новые переменные
m
γ1 =
– частичная стоимость пакета подключения к сети Интернет у
1 + χ∗i
второго провайдера в зависимости от количества знакомых χi , выбравших
этого же провайдера.
m
γ2 =
– частичная стоимость пакета подключения к сети Интер1 + ki − χ∗i
нет у первого провайдера в зависимости от количества знакомых, выбравших этого же провайдера.
Утверждение 4 Пусть:
τ (γ2 ) = b
η(l + γ2 ) − νl
c,
ν
(13)
τ (γ2 ) = d
ν(l + γ2 ) − ηl
e,
η
(14)
а ситуация X ∗ = (x∗1 , x∗2 , . . . , x∗n ) является ситуацией равновесия по Нэшу.
Тогда выполняются следующие условия:
1). Для клиента i с предпочтением θi = 1
26
x∗i =
1,
если γ1 ≤ τ (γ2 ),
0,
в противном случае.
(15)
2). Для клиента i с предпочтением θi = 0
x∗i =
0,
если γ1 ≥ τ (γ2 ),
1,
в противном случае.
(16)
Доказательство:
Докажем, что если X ∗ – ситуация равновесия по Нэшу, то (15) и (16)
выполняются.
Будем использовать этот факт в алгоритме поиска равновесий по Нэшу.
Пусть (x∗1 , . . . , x∗n ) – ситуация равновесия по Нэшу.
1). Пусть θi = 1.
a). Если x∗i = 1, то
u(1, 1, x∗ki (g) ) ≤ u(1, 0, x∗ki (g) ),
так как X ∗ – ситуация равновесия по Нэшу. Тогда
ν(l +
m
m
)
≤
η(l
+
),
1 + χ∗i
1 + ki − χ∗i
откуда получаем следующее условие
γ1 ≤
η(l + γ2 ) − νl
.
ν
б). Если x∗i = 0, то
u(1, 0, x∗ki (g) ) ≤ u(1, 1, x∗ki (g) ),
так как X ∗ – ситуация равновесия по Нэшу. Тогда
η(l +
m
m
)
≤
ν(l
+
),
1 + ki − χ∗i
1 + χ∗i
27
откуда получаем следующее условие
γ1 ≥
η(l + γ2 ) − νl
.
ν
Таким образом, для игрока с предпочтением 1 условие (15) выполнено.
2). Пусть θi = 0.
а). Если x∗i = 0, то
u(0, 0, x∗ki (g) ) ≤ u(0, 1, x∗ki (g) ),
так как X ∗ – ситуация равновесия по Нэшу. Тогда
m
m
) ≤ η(l +
),
∗
1 + ki − χi
1 + χ∗i
ν(l +
откуда получаем следующее условие
γ1 ≥
ν(l + γ2 ) − ηl
.
η
б). Если x∗i = 1, то
u(0, 1, x∗ki (g) ) ≤ u(0, 0, x∗ki (g) ),
так как X ∗ – ситуация равновесия по Нэшу. Тогда
η(l +
m
m
)
≤
ν(l
+
),
1 + χ∗i
1 + ki − χ∗i
откуда получаем следующее условие
γ1 ≤
ν(l + γ2 ) − ηl
.
η
Таким образом, для игрока с предпочтением 0 условие (16) выполнено.
Утверждение 4 необходимо нам для построения алгоритма поиска
всевозможных равновесий по Нэшу для рассматриваемой задачи.
Алгоритм нахождения стратегий равновесия по Нэшу будет выглядеть следующим образом:
1. Для всех возможных ситуаций находим значения χi для каждого клиента i ∈ N ;
28
2. Вычисляем значения γi .
3. Проверяем выполнение условий (15) и (16). Если условия не выполняются, то данная ситуация не является равновесной и она должна быть
исключена из набора всех стратегий.
4. Множество стратегий после исключения стратегий на п.2 является множеством равновесных по Нэшу стратегий.
3.4. Пример ситуаций равновесия по Нэшу для
задачи о выборе провайдера
Рассмотрим Пример 5 :
Пусть наша сетевая игра с неполной информацией представлена игрой следующего вида (Рисунок 8):
2
1
7
4
3
6
5
Рис. 8
Из данного изображения, мы видим, что участвует в сети всего 7 игроков (N=7).
У каждого есть свое предпочтение, и вектор предпочтений всех клиентов
будет выглядеть как Q = (0 , 0 , 1 , 1 , 1 , 0 , 0 ).
Пусть χi – количество знакомых, выбравших 1 действие. К примеру, если
клиент i имеет знакомых i1 и i3 , и один из них выбрал 1, а другой 0, то
χi =1. Если же и тот, и другой знакомый выберут 1, то χi =2.
m
γ1 =
– частичная стоимость пакета подключения к сети Интернет
1 + χ∗i
у второго провайдера в зависимости от количества знакомых, выбравших
такого же провайдера.
m
γ2 =
– частичная стоимость пакета подключения к сети Интер1 + ki − χ∗i
29
нет у первого провайдера в зависимости от количества знакомых, выбравших такого же провайдера.
Пусть ν = 5 , 5 , η = 4 , 5 , m = 10, l = 1. Сразу посчитаем пороговые
значения для каждого возможного количества знакомых клиента:
10
Если γ2 =
, то τ (γ2 )=12;
1
10
если γ2 =
, то τ (γ2 )=6;
1 +1
10
если γ2 =
, то τ (γ2 )=4;
1 +2
10
, то τ (γ2 )=3;
если γ2 =
1 +3
10
если γ2 =
, то τ (γ2 )=2;
1 +4
Далее рассматривать не имеет смысла, так как максимальное число связей
в данной сети равно 4.
10
Если γ2 =
, то τ (γ2 )=8;
1
10
eсли γ2 =
, то τ (γ2 )=4;
1 +1
10
, то τ (γ2 )=3;
если γ2 =
1 +2
10
, то τ (γ2 )=2;
если γ2 =
1 +3
10
если γ2 =
, то τ (γ2 )=2;
1 +4
После вычислений пороговых значений можем перейти непосредственно к проверке стратегий на равновесие по Нэшу.
Так как каждый клиент наделен своим предпочтением и связями, то мы
можем выделить для каждого оптимальный выбор в зависимости от его
характеристик.
Начнем с 1-го клиента. Он обладает предпочтением 0 и связью с
2-ым, 3-им и 4-ым клиентами. Таким образом, τ (γ2 ) может равняться от 2
до 8. Получаем такое условие для 1-го клиента:
1, χ1 = 2, 3,
∗
x (1) =
0, χ1 = 0, 1.
У второго клиента предпочтение 0 и его знакомыми являются 1-й и
30
7-й клиенты. Таким образом, τ (γ2 ) равняется от 3 до 8. Получаем следующее условие для него:
x∗ (2) =
0, χ2 = 0, 1,
1, χ2 = 2.
Далее для следующих клиентов условия будут выглядеть так:
x∗ (3) =
1, χ3 = 1, 2,
x∗ (4) =
0, χ3 = 0.
x∗ (5) =
1, χ4 = 2, 3, 4,
0, χ4 = 0, 1.
1, χ5 = 1, 2,
x∗ (6) =
0, χ5 = 0.
x∗ (7) =
0, χ6 = 0,
1, χ6 = 1.
0, χ7 = 0, 1,
1, χ7 = 2.
Таким образом, у нас уже будет дан набор всевозможных стратегий
клиентов. И далее, с помощью алгоритма будем отсеивать не соответствующие стратегии, оставляя лишь равновесия по Нэшу.
Начиная с выбора первого клиента будем проверять выполняются ли
для него условия (15) и (16), если нет - то рассмотренную ситуацию исключаем из набора всех стратегий. И так далее будем проверять выполнение
условий для выбора каждого клиента. В итоге мы получим 4 ситуации равновесия по Нэшу:
(0, 0, 0, 0, 0, 0, 0);
(0, 0, 1, 0, 1, 0, 0);
(1, 0, 1, 1, 1, 1, 0);
(1, 1, 1, 1, 1, 0, 1).
Также была написана программа, которая реализует описанный алгоритм и находит все ситуации равновесия по Нэшу для задачи о выборе
провайдера. Она продемонстрирована в Приложении 2.
31
При вводе таких входных параметров, как η, ν, m, l, количество агентов, вектор предпочтений и матрица смежности, и нажатии кнопки
« Расчет» программа посредством алгоритма выводит все ситуации равновесия по Нэшу.
Рис. 9: Поиск равновесий по Нэшу в задаче о выборе провайдера.
32
Заключение
В данной работе изучена модель сетевой игры с разнородными предпочтениями агентов с неполной информацией. Доказано утверждение об
условии, при котором ситуации одинаковых действий агентов являются ситуациями равновесия по Нэшу. Рассмотрены примеры, которые иллюстрируют возможность применения данного утверждения для частных примеров. Разработан алгоритм, позволяющий находить все равновесные стратегии. Проведены численные эксперименты по поиску ситуаций равновесия
по Нэшу, которые демонстрируют выполнение условия утверждения.
Изучена задача о выборе провайдера, для которой определено условие, при котором ситуации одинаковых выборов клиентов являются ситуациями равновесия по Нэшу. На примерах показано влияние параметров
модели на стратегии клиентов. Сформулировано утверждение для поиска
оптимальных стратегий клиентов. Разработан алгоритм поиска всевозможных ситуаций равновесия по Нэшу для конкретной задачи, основанный на
условиях, определенных в утверждении для поиска оптимальных стратегий
игроков. В примерах иллюстрируется работа алгоритма для нахождения
ситуаций равновесия в рассматриваемой игре с неполной информацией, а
также выполнение утверждения для ситуаций одинакового выбора игроков.
33
Список литературы
[1] Luce, R.D. and Raiffa, H. An Introduction and Critical Survey, 1957.
[2] Jijun Zhao, Miklos N. Szilagyi, Ferenc Szidarovszky. An N-person Battle of
Sexes Game, 2008. Т. 14, Вып. 1. С. 3669 – 3677.
[3] P enélope Hernández, M anuel M uñoz − Herrera, Ángel Sánchez.
Heterogeneous network games: Conflicting preferences, 2013. T. 79, С. 56 –
66.
[4] Nash J. Non-cooperative Games. Ann. of Math, 1951. Vol. 54. N 2. P. 286—
295.
[5] Andrew J. Monaco, Tarun Sabarwal. Games with Strategic Complements
and Substitutes January 26, 2015.
[6] F. Bean, A. Kerckhoff. Personality and Perception in Husband-Wife
Conflicts, 1971. T. 33, Вып. 2. C. 351 – 359.
[7] Cooper, R., D. DeJong, R. Forsythe and T. Ross. Communication in the
Battle of the Sexes Game: Some Experimental Results, 1989. T. 20, Вып. 4
C. 568 – 587.
[8] Galeotti, Andrea, Goyal, Sanyeev, Kamphorst, Jurjen. Network formation
with heterogeneous players, 2006. T. 54, C. 353 – 372.
[9] Galeotti, Andrea, Goyal, Sanyeev, Jackson, Matthew O., Yariv, Leaat, VegaRedondo, Fernando. Network games, 2010. T. 77, C. 218 – 244.
[10] Jackson, Matthew O. Social and Economic Networks, 2008.
[11] Петросян Л.А., Зенкевич Н.А., Шевкопляс Е.В. Теория игр БХВПетербург, 2012. 432.
34
Приложение
Приложение 1.
Программа для равновесий по Нэшу в сетевой игре с неполной информацией.
m = 2^n;
q = zeros(m,1);
for j = 1:m
q(j) = j-1;
end
Q = de2bi(q);
khi = zeros(n,1);
l = zeros(m,n);
for i=1:n
for j=1:m
khi = zeros(n,1);
for k=1:n
if S(k,i)==1
if Q(j,k)==1
khi(i)=khi(i)+1;
end
end
end
if D(i)==0
suma=sum( S(:,i));
tk=floor(((alpha*(1+suma))-beta)/(alpha+beta));
if khi(i) <= tk && Q(j,i) == 0
l(j,i) = 1;
elseif khi(i) > tk && Q(j,i) == 1
35
l(j,i) = 1;
end
else
suma=sum(S(i,:));
tn=ceil(((beta*(suma+1))- alpha)/(alpha+beta));
if khi(i) >= tn && Q(j,i) == 1
l(j,i) = 1;
elseif khi(i) < tn && Q(j,i) == 0
l(j,i) = 1;
end
end
end
end
k = 1;
z = zeros(m,1);
for j = 1:m
if sum(l(j,:)) == n
z(j) = 1;
end
end
for i = 1:m
if z(i) == 1
l1(k) = i;
k = k+1;
end
end
Q(l1,:)
36
Приложение 2.
Программа для равновесий по Нэшу в задаче о выборе провайдера.
m = 2^n;
q = zeros(m,1);
for j = 1:m
q(j) = j-1;
end
Q = de2bi(q);
khi = zeros(n,1);
l = zeros(m,n);
for i=1:n
for j=1:m
khi = zeros(n,1);
for k=1:n
if S(k,i)==1
if Q(j,k)==1
khi(i)=khi(i)+1;
end
end
end
if D(i)==1
suma=sum( S(:,i));
tn=floor(((eta*(t/(suma+l-khi(i)))- nu*l)/nu));
if t/(1+khi(i)) <= tn && Q(j,i) == 1
l(j,i) = 1;
elseif t/(1+khi(i)) > tn && Q(j,i) == 0
l(j,i) = 1;
end
else
37
suma=sum(S(i,:));
tk=ceil((nu*(t/(suma+l-khi(i)))-eta*l)/eta);
if t/(1+khi(i)) >= tk && Q(j,i) == 0
l(j,i) = 1;
elseif t/(1+khi(i)) < tk && Q(j,i) == 1
l(j,i) = 1;
end
end
end
end
k = 1;
z = zeros(m,1);
for j = 1:m
if sum(l(j,:)) == n
z(j) = 1;
end
end
for i = 1:m
if z(i) == 1
l1(k) = i;
k = k+1;
end
end
Q(l1,:)
38
Отзывы:
Авторизуйтесь, чтобы оставить отзыв