Модель симметричных связей

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

Описание модели

Задана популяция игроков $V=\left\{1,2,\ldots ,N\right\}$ представленная вершинами графа. Связь между двумя вершинами $i,j\in V$ означает наличие дружеских отношений между соответствующими агентами (в данном случае, граф неориентированный, тем самым мы считаем, что двух людей можно называть друзьями только в случае их обоюдного согласия, и, что немаловажно, отношения такого рода могут быть разорваны в одностороннем порядке).

От своих «прямых» друзей, т.е. от тех агентов, т.е. от каждой из вершин в своей единичной окрестности, игрок получает полезность в размере $\delta \in \left(0;1\right)$. Оба игрока, участвующие в прямой связи, несут издержки в фиксированном размере $c$. Содержательно это можно проинтерпретировать, например, как неудобства, причиняемые тем, что друг может попросить о помощи, необходимость мириться с иной точкой зрения и т.д. Резервными, фиксированными полезностями игроки не обладают, это никак не скажется на выводах. Все игроки эгоистичны, рациональны и преследуют исключительно цель максимизации собственной полезности. В случае равенства полезностей, связь образуется. Ходы игроки делают одновременно и независимо, начиная с пустого графа, время дискретно.

$u_{i}\left(G\right)=\sum _{j\;{\text{linked to}}\;i\;{\text{in}}\;G,j\neq i}\delta ^{l\left(i;j\right)}-c\cdot deg(i)$

Здесь и далее $\deg {\left(i\right)}$ - разряд вершины $i\in V,l\left(i;j\right)$– длина кратчайшего пути между вершинами $\ i,j\in V$.

Встает вопрос: каковы равновесные и устойчивые к небольшим воздействиям состояния (графы) существуют в такой постановке? К каким практическим результатам это может нас привести? Назовём оптимальной сеть, максимизирующую сумму полезностей всех агентов. Можно заметить, что наша модель обладает всеми свойствами игры на графах в классическом понимании – полезности всех игроков зависят от сети, которая образуется под воздействием применения игроками своих стратегий.

Приступим к рассмотрению модели, начав с рассмотрения случаев соотношения параметров.

Разбор модели

Случай 1

Пусть $\delta +{\frac {(N-2)}{2}}\delta ^{2}<c\$, т.е. издержки на поддержание дружбы столь высоки, что превышают полезность от этой самой дружбы. Очевидным равновесием здесь будет граф $G_{0}|\ E_{G_{0}}=\emptyset$. Это вырожденный случай, когда дружеские связи не образуются вовсе. Левая часть неравенства может показаться неожиданной, поскольку, неравенство $\delta <c\$ уже выглядит достаточным. Дело в том, что игроки могут образовывать связи в надежде на транзитивную полезность от игроков, с которыми они не будут связаны на прямую.

Случай 2

Пусть $\delta -\delta ^{2}\geq c\ \$. Математически данное неравенство эквивалентно $\delta \geq \delta ^{2}+c\ \$. В левой части здесь находится дополнительная (в некотором смысле предельная) полезность, которую получит игрок, образовав прямую связь с другим агентом, до которого до этого он мог пройти по пути длины 2. В правой же части находятся издержки от образования этой связи (аналог предельных издержек), $c$ – явные, $\delta ^{2}$ – альтернативные. Будет полезно заметить, что если $c<\delta -\delta ^{2}$, то $c<\delta -\delta ^{n}\ \ \forall \ n\in \mathbb {N} \ |\ n\geq 2$. Этот факт следует из убывания функции $f(x)=\ a^{x}$ при $a\in (0;1)$. Тем самым, наши рассуждения относительно агентов, между которыми в графе существует путь длины 2 верны и для любой пары агентов, между которыми в графе найдется путь произвольной длины n. Итак, если мы потребуем выполнения условия $\delta -\delta ^{2}>c$, мы гарантируем, что если два агента хоть как-то связаны между собой в графе, им обоим выгодно образовать прямую связь друг с другом. В силу произвольности выбора рассматриваемой пары, равновесием будет являться граф $G_{N}\ |\ \forall \ i,j\in V\ \left(i,j\right)\in E$ Все возможные связи будут образованы.

Случай 3

Основной интерес представляет нерассмотренный промежуток $c\in [\delta -\delta ^{2}\ ;\ \delta +{\frac {N-2}{2}}\delta ^{2}]$ Для аккуратности в решении введем дополнительную предпосылку о том, что агенты за 1 ход могут разорвать, добавить или и разорвать и добавить (сменить) единственную связь. В работе непосредственно показано, что единственной оптимальной сетью в рассматриваемом диапазоне полезности будет star-network, в которой все игроки, кроме одного, связаны с центральным и только с ним. Последний же, центральный агент, связан только с крайними агентами.

Абсолютно строгое доказательство этого факта представлено в этой работе. Интересно, что рано или поздно, вне зависимости от числа игроков и того, как ходы распределятся при переходе $t_{0}\rightarrow t_{1}$ связи распределяются в некотором смысле случайно, для любого игрока связь с любым другим равносильна. Стоит отметить, что если $i\in V\$ выбирает $j\in V\$ для образования связи, и наоборот, в течение одного хода, между ними образуется одна связь.

В результате такого случайного распределения $N$ связей, найдется вершина (или вершины), у которых разряд окажется максимальным, и граф на этом этапе, вообще говоря, не обязан быть связным. Однако, можно утверждать, что найдется такая итерация $t_{n^{\ast }}\$ такая, что начиная с нее граф связным будет. Предположим, что в сети более одной компоненты связности. Рассмотрим случайного агента в одной из этих компонент. Выгодно ли для него стать «связующим» между двумя компонентами? Конечно, да. Образование прямой связи с представителем (еще вопрос с каким именно*) иной компоненты даст ему положительную надбавку в размере $\delta -c\$, что уже наращивает его полезность, и «транзитивную» надбавку от косвенных связей, неотрицательную по определению. Тем самым, существование двух различных компонент связности (а значит, и большего числа) опровергнуто. Эта модель уже учит нас тому, что рано или поздно рациональный игрок присоединяется к обществу, заводит какие-то дружеские связи.

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

$U_{mid}^{+}=\left(N-1\right)+\delta -c>\delta -c+\delta ^{2}+\left(N-2\right)\delta =U_{out}^{+}$

Рассуждения для случаев полного и пустого графов вообще не зависят от количества игроков и расширяются на случай растущей популяции.

Обоснование случая 3

На самом деле, речь идет об обычном сравнении полезностей. Рассмотрим связную компоненту сети, в которой участвует ровно $A$ игроков. Пусть среди них распределено $p\geq A-1$ связей. Каждая из этих связей дает прибавку к суммарной полезности компоненты в размере $2\cdot \left(\delta -c\right)$, т.е. от совокупная полезность от прямых связей составляет $2p\left(\delta -c\right)$. Максимально возможное количество косвенных связей, которое может образоваться в таких условиях составляет ${\binom {A}{2}}-p={\frac {A\left(A-1\right)}{2}}-p$. Максимально возможная добавка к совокупной полезности от такой связи составляет $2\delta ^{2}$. Суммарная полезность сети на $A$ вершинах с $p$ распределенными связями может составить $U_{\Sigma }=2p\left(\delta -c\right)+2\delta ^{2}(\ {\frac {A\left(A-1\right)}{2}}-p)$ Подсчитаем суммарную полезность в конфигурации star-network. Полезность центральной вершины составит $U_{mid}=\left(A-1\right)\left(\delta -c\right)$. Полезность каждой из $A-1$ краевых составит $U_{out}=\delta -c+\left(A-2\right)\delta ^{2}$. Итого $U_{star}=\left(A-1\right)\left(\delta -c\right)+(A-1)(\delta -c+\left(A-2\right)\delta ^{2})$ $U_{star}=(A-1)(2\left(\delta -c\right)+\left(A-2\right)\delta ^{2})$ $U_{star}=\left(A-1\right)\left(2\delta -2c\right)+\left(A-1\right)\left(A-2\right)\delta ^{2}$ Вычитая из $U_{\Sigma }$ третье из полученных представлений, получаем $U_{\Sigma }-U_{star}=\left(2\delta -2c\right)\left(p-\left[A-1\right]\right)+\delta ^{2}[A\left(A-1\right)-2p-(A-1)(A-2)]$ Преобразовав слагаемое в последних скобках, получим, что оно эквивалентно $2(A-1-p)$. $U_{\Sigma }-U_{star}=\left(2\delta -2c\right)\left(p-\left[A-1\right]\right)-{2\delta }^{2}(p-[A-1])$ $U_{\Sigma }-U_{star}=\left(2\delta -2c-{2\delta }^{2}\right)\left(p-\left[A-1\right]\right)\$ Вспомнив, что $\ p\geq A-1\$ и рассматривая случай $c\geq \delta -\delta ^{2}\$, мы приходим к выводу, что величина $U_{\Sigma }-U_{star}\leq \ 0$, причем равенство достигается лишь если мы можем добраться из любой вершины в любую другую по пути не длиннее 2 (иначе мы не получим максимальную транзитивную полезность от косвенных связей). Вывод из этих выкладок следующий: при определенных значениях параметра оптимальным устройством обладает star-network и только она. Сравнив $U_{star}$ с полезностью пустого графа (с нулем), получим следующее ограничение: $U_{star}=\left(A-1\right)\left(2\delta -2c\right)+\left(A-1\right)\left(A-2\right)\delta ^{2}\geq 0$ $U_{star}=\left(2\delta -2c+\left[A-2\right]\delta ^{2}\right)\geq 0$ $c\leq \delta +\ {\frac {A-2}{2}}\delta ^{2}$ Соответственно, если издержки превышают эту границу, связи не образуются. Под этой границей единственной оптимальной сетью является звезда. Связность сети в модели доказывалась независимо, значит рассуждения про компоненту графа могут быть без потери общности расширены на все множество вершин.

Попарная устойчивость

Авторы исследования вводят также несколько иную концепцию равновесия: pairwise stability (PS, попарная устойчивость). Сеть, образовавшаяся в результате взаимодействия в рамках модели относится к классу PS, если ни один игрок не может увеличить свою полезность разорвав, добавив, или заменив связь. Понятие чем-то похоже на неформальное определение равновесия по Нэшу в теории игр, где профиль стратегий считается равновесным тогда и только тогда, когда ни одному из игроков не выгодно единолично отклониться.

Позволим себе опустить доказательство соответствующей теоремы, и заметим только, что, при $\delta <c\$ единственная попарно устойчивая сеть – пустая. При $c>\delta -\delta ^{2}$ тем же свойством обладает лишь полный граф. При остальных же значениях $c\$ попарно устойчивой (хоть и неединственной!) является star-network.

Применение

Начиная с определенного момента сеть связна и новые агенты, входящие в игру на более поздних шагах, эту тенденцию не нарушают. В долгосрочной перспективе невыгодно находиться вне системы дружеских отношений. Во всех нетривиальных случаях соотношения параметров оптимальным (с точки зрения максимизации совокупной полезности) является структура звезды. Это означает, что обществу выгоднее всего выбрать некоторого «связующего», который будет выполнять роль срединного звена и по сути обладать монополией на всякого рода коммуникации в сети. Модель симметричных связей представляется удобной при рассмотрении, например, концепции «всеобщего языка», функцию которого в настоящее время выполняет английский, чуть раньше это была латынь. Большинство торговых операций совершается в какой-то конкретной выбранной валюте. Само слово «связующий» заставляет вспомнить об операторах сотовой связи, которые в наше время ровно такую роль и выполняют. В этом контексте, между прочим, интересно рассмотреть игру, в которой центральный игрок («оператор»), обладающий, кстати, меньшей полезностью в сети: $U_{mid}=\left(N-1\right)\left(\delta -c\right)<\left(\delta -c\right)+\left(N-2\right)\delta ^{2}=U_{out}\$ т.к. $c>\delta -\delta ^{2}$ – условие, при котором мы вообще звезду рассматриваем, начинает взимать некоторую плату (скажем, какую-то долю в разности полезностей) с «абонентов», роль которых играют периферийные вершины, а также исследование вопроса о входе в эту сеть нового оператора и выбор его тарифной политики.

К набору ситуаций, которые этим выводом объясняются можно отнести и игру, описанную в работе, под названием «Помощь в людном месте». Все «хорошие» равновесия, которые могут быть достигнуты носят именно характер выбора какого-то ответственного, который поможет пострадавшему, а остальные, наблюдавшие это, получат свою косвенную полезность.

См. также

• Граф (математика)
• Равновесие по Нэшу