Теория игр: равновесия, механизмы, приложения в распределённых системах

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

Программист сталкивается с этим постоянно, даже когда не думает про «игры». Клиенты вашего API ретраят агрессивно, потому что каждому по отдельности это выгодно, — и кладут сервис. Команды в компании завышают resource requests в Kubernetes, потому что за перезаказ никто не наказывает, — и кластер стоит втрое дороже. Майнер решает, публиковать ли найденный блок сразу, — и от этого зависит безопасность блокчейна. Рекламодатель решает, какую ставку писать в форму, — и от правил аукциона зависит, соврёт он или скажет правду.

Ключевая мысль, ради которой стоит читать дальше: теория игр — это не про предсказание поведения людей, а про проектирование правил. Когда вы не можете изменить агентов (а вы обычно не можете — это чужие клиенты, чужие команды, анонимные валидаторы), у вас остаётся один рычаг: изменить игру так, чтобы желаемое поведение стало для агента выгодным. Эта инженерная дисциплина называется проектированием механизмов (mechanism design), и она — вторая половина статьи.

Формально мы опираемся на теорию множеств и логику (определения через кванторы), на линейную алгебру и выпуклость (симплекс смешанных стратегий, LP-двойственность), на вероятность (смешанные стратегии — это распределения) и на теорию сложности (вычислить равновесие — само по себе трудная задача).

Что такое игра: минимальный строгий каркас

Нормальная (стратегическая) форма

Определение. Игра в нормальной форме — это тройка G = (N, (S_i)_{i∈N}, (u_i)_{i∈N}), где:

• N = {1, ..., n} — конечное множество игроков;
• S_i — множество чистых стратегий игрока i; профиль стратегий s = (s_1, ..., s_n) ∈ S = S_1 × ... × S_n;
• u_i : S → R — функция полезности (выигрыша) игрока i.

Три вещи, которые здесь легко недооценить.

Первое: стратегия — это полный план, а не отдельный ход. В игре с несколькими стадиями стратегия — это функция «что я делаю в каждой возможной ситуации, где могу оказаться». Для программиста это ровно разница между «вызвать retry» и «политика ретраев». Стратегий поэтому экспоненциально много, и именно это делает игры вычислительно тяжёлыми.

Второе: u_i — это полезность, а не деньги. Полезность по фон Нейману–Моргенштерну определена с точностью до положительного аффинного преобразования (a·u + b, a > 0) и существует лишь при выполнении аксиом рациональности (полнота, транзитивность, непрерывность, независимость). Складывать полезности разных игроков или сравнивать их между собой математически бессмысленно — это самая частая ошибка при неформальном применении теории игр. «Общее благо» приходится определять отдельно и осторожно (см. цену анархии ниже).

Третье: игра предполагает общее знание. Стандартная модель считает, что структура игры — общее знание (common knowledge): все знают правила, все знают, что все знают, и так до бесконечности. Это сильное допущение, и от него отказывается теория игр с неполной информацией (байесовские игры Харшаньи).

Матрица выплат: читать глазами

Для двух игроков с конечными стратегиями игра — это две матрицы A (выплаты строчного игрока) и B (выплаты столбцового). Классическая дилемма заключённого в «годах тюрьмы со знаком минус»:

             молчит (C)   сдаёт (D)
молчит (C)    (-1, -1)     (-3,  0)
сдаёт  (D)    ( 0, -3)     (-2, -2)

Читаем: если оба молчат — по году каждому. Если я сдал, а он молчал — я выхожу (0), он получает 3.

Доминирование: самый сильный аргумент, какой бывает

Определение (строгое доминирование). Стратегия s_i строго доминирует s_i', если для любого профиля соперников s_{-i}:

u_i(s_i, s_{-i}) > u_i(s_i', s_{-i})

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

В дилемме заключённого D строго доминирует C: 0 > -1 и -2 > -3. Отсюда единственный рациональный исход (D, D) с выплатами (-2, -2), который хуже для обоих, чем (C, C) с (-1, -1). Никакой парадокс, никакой «иррациональности» — просто индивидуальная рациональность не обязана давать коллективный оптимум. Вся эта статья — про то, как с этим фактом жить.

Итеративное удаление строго доминируемых стратегий (IESDS) — базовая техника упрощения. Важный нюанс: порядок удаления не влияет на результат для строгого доминирования, но влияет для слабого. Слабое доминирование (≥ везде и > хотя бы где-то) может удалить равновесия — с ним нужно быть осторожнее.

from itertools import product

def iesds(A, B):
    """Итеративно удаляем строго доминируемые чистые стратегии.
    A[i][j] — выигрыш строчного игрока, B[i][j] — столбцового.
    Возвращает списки выживших индексов строк и столбцов.
    Сложность: O(k) итераций, каждая O(n^2 * m) — для учебных размеров это ничто."""
    rows = list(range(len(A)))
    cols = list(range(len(A[0])))
    changed = True
    while changed:
        changed = False
        # строчный игрок: строка i доминируется строкой k, если k строго лучше во всех выживших столбцах
        for i in list(rows):
            if any(all(A[k][j] > A[i][j] for j in cols) for k in rows if k != i):
                rows.remove(i)
                changed = True
        for j in list(cols):
            if any(all(B[i][l] > B[i][j] for i in rows) for l in cols if l != j):
                cols.remove(j)
                changed = True
    return rows, cols

PD_A = [[-1, -3], [0, -2]]   # C, D по строкам
PD_B = [[-1,  0], [-3, -2]]
print(iesds(PD_A, PD_B))     # ([1], [1]) — остаётся только (D, D)

Равновесие Нэша

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

Определение (равновесие Нэша, чистые стратегии). Профиль s* ∈ S — равновесие Нэша, если для каждого игрока i и каждой его стратегии s_i ∈ S_i:

u_i(s*_i, s*_{-i}) ≥ u_i(s_i, s*_{-i})

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

Что равновесие Нэша не означает (типичные заблуждения):

• Не значит «хороший исход»: (D, D) в дилемме заключённого — равновесие и при этом Парето-доминируемо.
• Не значит «единственный исход»: игр с несколькими равновесиями большинство, и теория не говорит, какое реализуется (проблема отбора равновесия).
• Не значит «игроки договорились»: соглашение не подкреплено ничем, кроме индивидуальной выгоды. Как раз поэтому равновесие — правильная модель для систем без доверия.
• Не значит «игроки его вычислят»: найти равновесие может быть вычислительно неподъёмно (см. раздел про PPAD).

Смешанные стратегии и теорема Нэша

В «камень-ножницы-бумага» равновесия в чистых стратегиях нет: на любой профиль есть выгодное отклонение. Решение — разрешить рандомизацию.

Определение. Смешанная стратегия игрока i — распределение σ_i ∈ Δ(S_i), где Δ(S_i) = {p ∈ R^{|S_i|} : p_k ≥ 0, Σ p_k = 1} — симплекс. Полезность продолжается по линейности как математическое ожидание: u_i(σ) = Σ_{s∈S} (Π_j σ_j(s_j)) · u_i(s).

Теорема (Нэш, 1950). Всякая конечная игра (конечное число игроков, конечные множества стратегий) имеет хотя бы одно равновесие Нэша в смешанных стратегиях.

Доказательство — применение теоремы о неподвижной точке. Схема: определяем отображение наилучших ответов BR : Δ → Δ, где Δ = Δ(S_1) × ... × Δ(S_n) — компакт и выпуклое множество. BR полунепрерывно сверху с непустыми выпуклыми значениями, значит по теореме Какутани у него есть неподвижная точка σ* ∈ BR(σ*) — а это по определению и есть равновесие. Оригинал: Nash, «Equilibrium Points in n-Person Games», PNAS 1950 — https://www.pnas.org/doi/10.1073/pnas.36.1.48

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

Разберём руками. Игра «доступ к общему ресурсу»: два клиента одновременно решают, слать запрос агрессивно (A) или бэкоффить (B). Матрица выигрышей строчного:

             A        B
   A     ( 0, 0)  ( 3, 1)
   B     ( 1, 3)  ( 2, 2)

Пусть столбцовый играет A с вероятностью q. Ожидания строчного:

E[A] = 0·q + 3·(1-q) = 3 - 3q
E[B] = 1·q + 2·(1-q) = 2 - q

Безразличие: 3 - 3q = 2 - q → 1 = 2q → q = 1/2. По симметрии p = 1/2. Ожидаемый выигрыш каждого: 2 - 1/2 = 1.5. Заметьте: это хуже, чем (B, B) = 2, и хуже, чем оба асимметричных чистых равновесия (A,B) и (B,A), дающих в среднем 2. Смешанное равновесие в играх типа «ястреб-голубь» почти всегда — худший из равновесных исходов; ровно поэтому в реальных системах хочется добавить механизм координации (см. коррелированное равновесие).

from fractions import Fraction

def mixed_2x2(A, B):
    """Внутреннее смешанное равновесие игры 2x2 по принципу безразличия.
    Возвращает (p, q): p — вероятность 1-й строки, q — вероятность 1-го столбца.
    Работает точной арифметикой, чтобы не ловить сюрпризы плавающей точки."""
    a, b, c, d = (Fraction(A[0][0]), Fraction(A[0][1]),
                  Fraction(A[1][0]), Fraction(A[1][1]))
    # строчный безразличен по q: a*q + b*(1-q) = c*q + d*(1-q)
    den_q = (a - b - c + d)
    if den_q == 0:
        return None
    q = (d - b) / den_q
    e, f, g, h = (Fraction(B[0][0]), Fraction(B[0][1]),
                  Fraction(B[1][0]), Fraction(B[1][1]))
    # столбцовый безразличен по p: e*p + g*(1-p) = f*p + h*(1-p)
    den_p = (e - f - g + h)
    if den_p == 0:
        return None
    p = (h - g) / den_p
    if not (0 <= p <= 1 and 0 <= q <= 1):
        return None            # внутреннего равновесия нет, ищите на границе
    return p, q

CONG_A = [[0, 3], [1, 2]]
CONG_B = [[0, 1], [3, 2]]
print(mixed_2x2(CONG_A, CONG_B))   # (Fraction(1, 2), Fraction(1, 2))

Общий алгоритм для 2 игроков — перебор носителей: для каждой пары подмножеств стратегий решаем линейную систему и проверяем условия равновесия. Это экспоненциально, но для малых игр практично. Классический алгоритм с лучшим поведением — Лемке–Хаусона, разновидность метода поворотов для задачи линейной комплементарности; он всегда находит хотя бы одно равновесие, но в худшем случае экспоненциален (Savani & von Stengel, 2004).

Таксономия: что вообще бывает

Игры с нулевой суммой: минимакс и линейное программирование

Определение. Игра двух лиц с нулевой суммой: u_1(s) + u_2(s) = 0 для всех s, то есть B = -A. Всё, что выигрывает один, теряет другой.

Теорема о минимаксе (фон Нейман, 1928). Для любой конечной матричной игры A:

max_{p ∈ Δ(S_1)} min_{q ∈ Δ(S_2)} p^T A q  =  min_{q ∈ Δ(S_2)} max_{p ∈ Δ(S_1)} p^T A q  =  V

Число V — цена игры. Смысл: у игрока есть смешанная стратегия, гарантирующая ему в среднем не меньше V независимо от того, что делает соперник, даже если соперник знает вашу стратегию (но не реализацию случайности). Это редчайший случай, когда теория игр даёт полноценную гарантию, а не условное предсказание.

Связь с LP-двойственностью — самая красивая часть. Задача «найти максиминную стратегию» записывается как линейная программа:

максимизировать  V
при условиях     Σ_i p_i · A[i][j] ≥ V   для каждого столбца j
                 Σ_i p_i = 1,  p_i ≥ 0

Двойственная к ней — в точности задача второго игрока, а теорема о минимаксе оказывается частным случаем теоремы двойственности линейного программирования. Значит равновесие в игре с нулевой суммой вычисляется за полиномиальное время — в отличие от игр с ненулевой суммой. Это фундаментальный водораздел, а не техническая деталь.

import numpy as np
from scipy.optimize import linprog

def zero_sum_value(A):
    """Цена игры и оптимальная смешанная стратегия строчного игрока.
    Сдвигаем матрицу в положительную область, чтобы V > 0 и можно было
    нормировать переменные (классический трюк x_i = p_i / V).
    Сложность: полиномиальная (симплекс/interior point над LP размера (n+m))."""
    A = np.asarray(A, dtype=float)
    shift = A.min() - 1.0
    M = A - shift                       # теперь все элементы > 0
    n, m = M.shape
    # минимизируем сумму x_i при M^T x >= 1, x >= 0;  V' = 1/sum(x), p = x * V'
    res = linprog(c=np.ones(n), A_ub=-M.T, b_ub=-np.ones(m),
                  bounds=[(0, None)] * n, method="highs")
    assert res.status == 0, res.message
    v_shifted = 1.0 / res.x.sum()
    p = res.x * v_shifted
    return v_shifted + shift, p

RPS = [[0, -1, 1],
       [1,  0, -1],
       [-1, 1,  0]]
v, p = zero_sum_value(RPS)
print(round(v, 6), np.round(p, 6))     # 0.0 [0.333333 0.333333 0.333333]

# Несимметричный пример: «атака/защита» двух эндпоинтов разной ценности
ATTACK = [[3, -1],
          [-1, 5]]
v, p = zero_sum_value(ATTACK)
print(round(v, 4), np.round(p, 4))     # 1.4 [0.6 0.4] — защищать дорогой чаще

Заметьте практический смысл последнего примера: если у вас два ресурса разной ценности и ограниченный бюджет мониторинга, оптимальная политика — рандомизированная, с весами, зависящими от ценностей. Детерминированное расписание проверок противник просчитает. Это буквально теория Stackelberg security games, применяемая в реальном планировании патрулей и в анти-фрод системах (Tambe, «Security and Game Theory», Cambridge University Press, 2011).

Каталог игр, которые вы уже видели в проде

Четыре канонические игры 2×2 покрывают удивительно много инженерных ситуаций. Разница между ними — только в порядке четырёх чисел, но выводы противоположные.

Дилемма заключённого — модель трагедии общин. Обобщение на n игроков: каждый выбирает нагрузку, полезность растёт от своей нагрузки и падает от общей. В равновесии система перегружена. Это точная модель retry storm: каждому клиенту ретрай выгоден (повышает его шанс), но суммарно сервис ложится. Отсюда становится понятно, почему exponential backoff — это не оптимизация, а механизм: он меняет выплаты так, что агрессия перестаёт окупаться. И почему backoff без jitter не работает: он решает проблему интенсивности, но не проблему координации (все ретраят в один и тот же момент). Инженерное изложение — AWS Builders’ Library, «Timeouts, retries, and backoff with jitter»: https://aws.amazon.com/builders-library/timeouts-retries-and-backoff-with-jitter/

Охота на оленя объясняет, почему миграции застревают. Переход на новый протокол выгоден всем, если перейдут все, и убыточен для того, кто перешёл в одиночку. Оба равновесия устойчивы — и «все на старом» тоже. Отсюда прикладной вывод: не уговаривайте по одному, а создавайте общее знание о дате перехода. Феномен «риск-доминирующего» равновесия (Харшаньи–Зельтен) объясняет, почему при неуверенности люди выбирают безопасный вариант, даже зная, что кооперативный лучше.

Повторяющиеся игры: почему кооперация всё-таки возможна

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

Модель. Бесконечно повторяющаяся игра с коэффициентом дисконтирования δ ∈ (0,1): суммарная полезность = Σ_{t=0}^∞ δ^t · u(a_t). Здесь δ — это «вероятность, что взаимодействие продолжится» или «насколько будущее важно относительно настоящего».

Стратегия «мрачный триггер» (grim trigger): кооперируй, пока другой кооперирует; при первом предательстве предавай вечно.

Проверим, когда это равновесие, на числах T=5, R=3, P=1, S=0:

Кооперировать всегда:  3 + 3δ + 3δ² + ...  = 3/(1-δ)
Предать один раз:      5 + 1δ + 1δ² + ...  = 5 + δ/(1-δ)

3/(1-δ) ≥ 5 + δ/(1-δ)
3 ≥ 5(1-δ) + δ
3 ≥ 5 - 4δ
δ ≥ 1/2

Вывод строгий и содержательный: кооперация устойчива ровно тогда, когда будущее достаточно ценно. Если δ < 1/2 — то есть взаимодействие, скорее всего, последнее — предательство рационально. Это математическое обоснование интуиции «с разовым контрагентом веди себя как с разовым контрагентом» и объяснение того, почему анонимные одноразовые аккаунты — источник злоупотреблений, а репутационные системы работают: репутация искусственно поднимает δ.

Folk theorem (неформально). При достаточно большом δ любой профиль выплат, который индивидуально рационален (каждому не меньше его maximin) и достижим, реализуется как равновесие некоторой стратегии. Это одновременно триумф и катастрофа теории: она объясняет всё — а значит, не предсказывает ничего. Повторяющиеся игры дают возможность кооперации, но не выделяют её.

Знаменитый турнир Аксельрода (1980) показал: побеждает Tit-for-Tat — «начни с кооперации, дальше повторяй последний ход соперника». Её свойства: доброжелательная (не предаёт первой), отзывчивая (наказывает сразу), прощающая (мгновенно возвращается к кооперации), понятная (соперник быстро вычисляет логику). Уточнение, которое часто теряют при пересказе: в зашумлённой среде Tit-for-Tat плоха — единственная ошибка запускает бесконечную серию взаимных наказаний. Там выигрывают «щедрый TFT» (прощает с вероятностью) и Pavlov / win-stay-lose-shift. Для инженера это прямая аналогия: политика реакции на сбои должна учитывать, что сбой мог быть шумом сети, а не злонамеренностью.

import itertools

PAY = {('C','C'): (3,3), ('C','D'): (0,5), ('D','C'): (5,0), ('D','D'): (1,1)}

def tit_for_tat(my, opp):   return 'C' if not opp else opp[-1]
def always_defect(my, opp): return 'D'
def always_coop(my, opp):   return 'C'
def grim(my, opp):          return 'D' if 'D' in opp else 'C'
def pavlov(my, opp):
    """win-stay, lose-shift: повторяем ход, если раунд закончился хорошо."""
    if not my:
        return 'C'
    good = (my[-1], opp[-1]) in (('C','C'), ('D','D'))
    return my[-1] if good else ('D' if my[-1] == 'C' else 'C')

def play(f, g, rounds=200):
    h1, h2, s1, s2 = [], [], 0, 0
    for _ in range(rounds):
        a, b = f(h1, h2), g(h2, h1)     # каждый видит свою и чужую историю
        p, q = PAY[(a, b)]
        s1 += p; s2 += q
        h1.append(a); h2.append(b)
    return s1, s2

bots = [tit_for_tat, always_defect, always_coop, grim, pavlov]
total = {b.__name__: 0 for b in bots}
for f, g in itertools.combinations_with_replacement(bots, 2):
    s1, s2 = play(f, g)
    total[f.__name__] += s1
    if f is not g:
        total[g.__name__] += s2

for name, score in sorted(total.items(), key=lambda kv: -kv[1]):
    print(f"{name:15s} {score}")
# tit_for_tat     2599
# grim            2599
# pavlov          2599
# always_coop     2400
# always_defect   1812

Обратите внимание на результат: always_defect — единственное равновесие однократной игры — приходит последним. И заметьте, что он никогда не проигрывает ни одной парной встрече: он набирает больше или столько же, сколько его конкретный соперник, но при этом набирает мало в абсолюте. Теория игр про максимизацию своего выигрыша, а не про «победить соперника» — путать эти вещи означает систематически принимать плохие решения.

Эволюционная теория игр: равновесие без рациональности

Модель «рациональный агент вычисляет наилучший ответ» неправдоподобна, когда агентов миллионы (клиенты, боты, узлы). Эволюционная теория игр заменяет расчёт отбором: стратегии, приносящие больше выигрыша, реплицируются быстрее.

Определение (репликаторная динамика). Пусть x_i — доля популяции, играющая стратегию i, f_i(x) = (A x)_i — её приспособленность, φ(x) = x^T A x — средняя. Тогда:

dx_i/dt = x_i · (f_i(x) - φ(x))

Стратегия растёт, если она лучше среднего. Это не постулат про разум, а модель имитации/отбора — и в этом её сила: она описывает системы из ботов, воркеров и автономных клиентов лучше, чем модель рационального выбора.

Определение (эволюционно устойчивая стратегия, ESS; Maynard Smith & Price, 1973). Стратегия σ эволюционно устойчива, если для любой мутантной τ ≠ σ существует ε̄ > 0 такое, что для всех ε ∈ (0, ε̄):

u(σ, ε·τ + (1-ε)·σ) > u(τ, ε·τ + (1-ε)·σ)

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

def replicator(A, x0, dt=0.01, steps=20000):
    """Дискретная аппроксимация репликаторной динамики.
    A — матрица выплат симметричной игры, x0 — начальные доли.
    Сложность на шаг: O(n^2). Не численная схема для науки, а иллюстрация."""
    n = len(x0)
    x = list(x0)
    for _ in range(steps):
        fit = [sum(A[i][j] * x[j] for j in range(n)) for i in range(n)]
        avg = sum(x[i] * fit[i] for i in range(n))
        x = [max(0.0, x[i] + dt * x[i] * (fit[i] - avg)) for i in range(n)]
        s = sum(x)
        x = [xi / s for xi in x]
    return x

# Ястреб-голубь: ценность ресурса V, цена драки C. При C > V есть внутренняя ESS.
V, C = 2.0, 3.0
HD = [[(V - C) / 2, V],
      [0.0,         V / 2]]
print([round(v, 4) for v in replicator(HD, [0.5, 0.5])])
# [0.6667, 0.3333] — доля «ястребов» сходится ровно к V/C = 2/3

Аналитически: доля ястребов в ESS равна V/C, и численный ответ совпадает — приятная проверка. Практическая интерпретация: в популяции клиентов доля «агрессивных» стабилизируется на уровне, определяемом отношением выгоды от агрессии к её цене. Хотите меньше агрессии — не уговаривайте, поднимайте C (штрафы, троттлинг, стоимость запроса). Это уже проектирование механизма.

Отдельное предупреждение: репликаторная динамика не обязана сходиться. В «камень-ножницы-бумага» траектории кружат вокруг равновесия вечно; в других играх бывают предельные циклы и хаос (см. теорию хаоса и динамические системы). Заявление «система придёт в равновесие» требует доказательства, а не веры.

Цена анархии: сколько стоит отсутствие координации

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

Определение (Koutsoupias & Papadimitriou, 1999). Пусть cost(s) — общественная стоимость профиля (например, суммарная задержка). Тогда:

Price of Anarchy  = max_{s ∈ Equilibria} cost(s) / cost(OPT)     — худшее равновесие
Price of Stability = min_{s ∈ Equilibria} cost(s) / cost(OPT)     — лучшее равновесие

PoA — это гарантия «насколько плохо может быть, если агенты действуют эгоистично». PoS — «насколько хорошо, если мы сумели их скоординировать на лучшее равновесие».

Пример Пигу. Из s в t ведут две дороги: верхняя со стоимостью 1 (константа, широкая), нижняя со стоимостью x (равна доле потока). Суммарный поток = 1.

• Равновесие: нижняя дорога всегда не хуже (x ≤ 1), все едут по ней, стоимость = 1·1 = 1.
• Оптимум: пустим долю x вниз, 1-x вверх, суммарная стоимость x² + (1-x). Минимум в x = 1/2, стоимость 0.25 + 0.5 = 0.75.
• PoA = 1 / 0.75 = 4/3.

Теорема (Roughgarden & Tardos, 2002). Для эгоистичной маршрутизации с аффинными функциями задержки (a·x + b) цена анархии не превосходит 4/3 — и эта граница достигается уже на примере Пигу. Для полиномов степени d граница растёт как Θ(d / ln d). Первоисточник: «How Bad Is Selfish Routing?», JACM 2002 — https://timroughgarden.org/papers/routing.pdf

Практический смысл этой теоремы огромен: эгоистичная маршрутизация без всякой координации теряет не более 33% при линейных задержках. Это оправдывает децентрализованные протоколы: цена простоты известна и мала. Но при резко нелинейных задержках (а очередь M/M/1 ведёт себя как 1/(μ-λ) — хуже любого полинома вблизи насыщения) гарантии рушатся, и координация становится необходимой.

Парадокс Брайеса — самая контринтуитивная иллюстрация: добавление ребра с нулевой стоимостью ухудшает равновесие для всех.

Читается это так: до перемычки поток делился поровну, каждый ехал 0.5 + 1 = 1.5. После появления бесплатного ребра a → b маршрут s→a→b→t строго доминирует оба старых, все переключаются на него, и все получают 1 + 0 + 1 = 2. Равновесие единственно и хуже прежнего на 33%.

Инженерные проявления встречаются регулярно: добавление быстрого пути в кэш может ухудшить общую латентность, потому что весь трафик хлынет через него и создаст конкуренцию за ресурс. Добавление ещё одной реплики в пул может ухудшить хвостовые задержки, если балансировщик жадный. Общий вывод: локальное улучшение топологии не обязано улучшать равновесие; проверять надо систему целиком, под нагрузкой.

Развёрнутая форма, обратная индукция и связь с игровым ИИ

Игры с ходами по очереди описываются деревом: вершины — состояния, рёбра — ходы, листья — выплаты.

Определение (совершенное в подыграх равновесие, SPE; Selten). Профиль стратегий — SPE, если он образует равновесие Нэша в каждой подыгре, а не только в игре целиком.

Зачем усиление? Потому что обычное равновесие Нэша допускает неправдоподобные угрозы. Пример: «если ты выкатишь релиз в пятницу, я снесу весь прод». Это равновесие (в ответ на угрозу вы не релизите, и угрозу исполнять не приходится), но угроза не выдержала бы проверки: исполнять её самому исполнителю невыгодно. SPE отбрасывает такие исходы: в подыгре «релиз уже выкатили» разрушать прод — не наилучший ответ.

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

Теорема Цермело (1913). В конечной игре двух лиц с совершенной информацией и без ничьих один из игроков имеет выигрышную стратегию. Для шахмат это означает, что результат при идеальной игре определён — мы просто не знаем, какой. Дерево содержит порядка 10^120 вершин, и это идеальная иллюстрация разницы между «существует» и «вычислимо», которую подробно разбирает теория сложности (обобщённые шахматы и го — EXPTIME-полные задачи).

def backward_induction(node):
    """node = ('leaf', (u1, u2)) | ('node', player, [(ход, поддерево), ...])
    Возвращает (вектор выплат, оптимальный путь).
    Сложность: O(|вершин|) по времени, O(глубина) по стеку."""
    kind = node[0]
    if kind == 'leaf':
        return node[1], []
    _, player, children = node
    best_payoff, best_path = None, None
    for move, child in children:
        payoff, path = backward_induction(child)
        # игрок максимизирует СВОЮ компоненту вектора выплат
        if best_payoff is None or payoff[player] > best_payoff[player]:
            best_payoff, best_path = payoff, [move] + path
    return best_payoff, best_path

# «Игра доверия»: инвестор передаёт капитал, партнёр решает — вернуть или присвоить.
trust_game = ('node', 0, [
    ('не вкладывать', ('leaf', (1, 1))),
    ('вложить', ('node', 1, [
        ('вернуть долю', ('leaf', (2, 2))),
        ('присвоить',    ('leaf', (0, 3))),
    ])),
])
print(backward_induction(trust_game))   # ((1, 1), ['не вкладывать'])

Результат показателен: обратная индукция предсказывает, что инвестор вообще не вложится, зная, что партнёру выгодно присвоить. Пара (2,2) недостижима без внешнего механизма. Это модель любой сделки без гаранта — и одновременно объяснение того, зачем существуют эскроу, депозиты, смарт-контракты и slashing в proof-of-stake: все они меняют выплаты в листьях, делая «присвоить» невыгодным. Экспериментально люди в этой игре кооперируют гораздо чаще, чем предсказывает теория (Berg, Dickhaut & McCabe, 1995) — важное напоминание, что модель описывает стимулы, а не всю человеческую мотивацию.

Проектирование механизмов: инженерная половина теории игр

Перевернём задачу. До сих пор мы брали игру и искали исход. Теперь берём желаемый исход и ищем игру, которая к нему приводит. Это «обратная теория игр», и именно она напрямую применима в разработке.

Постановка. Есть n агентов, у каждого — приватный тип θ_i (истинная ценность, реальная нагрузка, честная оценка задачи). Механизм — пара (f, p): правило выбора исхода f(θ̂) и правило платежей p(θ̂) по сообщённым типам θ̂. Мы хотим свойств:

• Incentive compatibility (IC): сообщать правду — доминирующая стратегия (DSIC) или хотя бы байесовское равновесие (BIC).
• Individual rationality (IR): участвовать не хуже, чем не участвовать.
• Efficiency: выбранный исход максимизирует суммарную ценность.
• Budget balance: механизм не требует внешних дотаций.

Принцип раскрытия (revelation principle). Если какой-то механизм реализует исход f в равновесии, то существует прямой правдивый механизм, реализующий тот же f. Смысл: без потери общности можно рассматривать только механизмы, где агент просто сообщает свой тип и говорить правду ему выгодно. Идея доказательства — «зашить» стратегическое поведение агента внутрь механизма: механизм сам симулирует то, как агент соврал бы.

Аукцион Викри (второй ценовой)

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

Теорема. Сообщать b_i = v_i — доминирующая стратегия.

Доказательство укладывается в одну картинку. Обозначим p = max_{j≠i} b_j — лучшую ставку конкурентов; она не зависит от вашей ставки.

Разбор случаев формально:

Случай p < v:  честная ставка v > p → выигрыш, полезность v - p > 0.
               Занизить до b < p → полезность 0. Хуже.
               Завысить → тот же выигрыш, та же цена p. Не лучше.
Случай p > v:  честная ставка v < p → проигрыш, полезность 0.
               Завысить до b > p → выигрыш, но платите p > v: полезность v - p < 0. Хуже.
               Занизить → та же полезность 0. Не лучше.

Ключевая механика: ставка определяет только “выиграл/проиграл”, а цена определяется другими. Разрыв между «что вы говорите» и «что вы платите» и есть источник правдивости. Оригинал: Vickrey, «Counterspeculation, Auctions, and Competitive Sealed Tenders», Journal of Finance, 1961.

VCG: обобщение на произвольные задачи распределения

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

p_i = W(-i)  -  W_{-i}(all)

где W(-i)      — максимальное суммарное благосостояние остальных, если бы i не было;
    W_{-i}(all)— суммарное благосостояние остальных в реально выбранном исходе.

Интуиция ясная и очень «инженерная»: вы платите ровно за ущерб, который причинили другим своим присутствием. Если ваш выигрыш никого не потеснил — платите ноль. Отсюда следует DSIC: полезность агента становится равной v_i(f(θ̂)) + W_{-i}(f(θ̂)) - W(-i), то есть с точностью до константы совпадает с общественным благосостоянием. Максимизируя своё, агент максимизирует общее — а лучший способ помочь механизму выбрать оптимум — сказать правду.

from itertools import combinations

def vcg_identical_items(bids, k):
    """VCG для k идентичных единиц ресурса (слоты, квоты, инстансы).
    Возвращает (победители, {победитель: платёж}).
    Сложность: O(n log n) на сортировку + O(k n log n) на платежи."""
    n = len(bids)
    order = sorted(range(n), key=lambda i: -bids[i])
    winners = order[:k]
    payments = {}
    for w in winners:
        # благосостояние остальных, если бы w не участвовал
        without = sorted((bids[i] for i in range(n) if i != w), reverse=True)
        w_without = sum(without[:k])
        # благосостояние остальных при текущем распределении
        w_with = sum(bids[i] for i in winners if i != w)
        payments[w] = w_without - w_with
    return winners, payments

print(vcg_identical_items([10, 7, 4], 1))       # ([0], {0: 7}) — это ровно Викри
print(vcg_identical_items([10, 7, 4, 2], 2))    # ([0, 1], {0: 4, 1: 4})

Заметьте: при k одинаковых единицах каждый победитель платит (k+1)-ю по величине ставку. Это не совпадение, а прямое следствие формулы внешнего эффекта: вытесняете вы ровно того, кто стоит первым за чертой.

Почему VCG редко встречается в чистом виде — честный разбор недостатков:

1. Вычислительная сложность. Нужно решить задачу оптимального распределения n+1 раз. Для комбинаторных аукционов она NP-трудна, а приближённое решение ломает правдивость — теорема о том, что DSIC + аппроксимация несовместимы для большинства задач (Nisan & Ronen).
2. Плохая выручка. VCG может собрать почти ноль. Пример: два предмета, два агента, каждый хочет ровно свой — оба платят 0.
3. Уязвимость к сговору и к shill bidding. Два агента могут совместно снизить платежи; продавец может завести фиктивных участников.
4. Немонотонность выручки. Добавление участника может уменьшить доход — свойство, невыносимое для бизнеса.

Ровно поэтому Google, рекламные биржи и другие практики используют GSP (generalized second-price) — который не правдив, но прост, монотонен по выручке и понятен рекламодателям. Равновесия GSP изучены (Edelman, Ostrovsky & Schwarz, 2007 — https://www.aeaweb.org/articles?id=10.1257/aer.97.1.242) и дают в «локально огибающем» равновесии те же распределения, что VCG, но большую выручку. Это образцовый пример инженерного компромисса: теоретически безупречный механизм проиграл практичному.

Границы возможного: три теоремы невозможности

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

Теорема Гиббарда–Саттертуэйта (1973–75). Если исходов больше двух, предпочтения произвольны, и механизм детерминирован, недиктаторский и с полным диапазоном исходов, то он манипулируем. Иначе: универсального правдивого правила голосования не существует. Обходные пути — денежные переводы (VCG работает как раз потому, что использует деньги и квазилинейные полезности), ограничение области предпочтений (однопиковые предпочтения → медианный избиратель правдив), рандомизация.

Теорема Майерсона–Саттертуэйта (1983). В двусторонней торговле (один продавец, один покупатель, приватные ценности с пересекающимися носителями) не существует механизма, одновременно эффективного, IC, IR и бездефицитного. Идеальные рынки невозможны в принципе — какая-то часть взаимовыгодных сделок обязательно не состоится.

Теорема Эрроу (1951). Ни одно правило агрегирования порядковых предпочтений трёх и более альтернатив не удовлетворяет одновременно единогласию, независимости от посторонних альтернатив и недиктаторству.

Практический вывод для проектировщика: когда вас просят сделать «справедливое, эффективное, неманипулируемое и самоокупаемое» распределение ресурсов — это не задача, это набор взаимоисключающих требований. Правильный ответ — выбрать, чем жертвуете, и сказать это вслух.

Оптимальный по выручке механизм: Майерсон в двух абзацах

VCG максимизирует эффективность. Если же вы хотите максимум выручки (обычная бизнес-задача), ответ даёт Майерсон (1981).

Определение (виртуальная ценность). Для распределения ценностей с плотностью f и функцией F:

φ(v) = v - (1 - F(v)) / f(v)

Теорема. Оптимальный по выручке механизм — это VCG, применённый не к ценностям, а к виртуальным ценностям, с отсечением отрицательных. Для равномерного U[0,1]: φ(v) = 2v - 1, отсечение φ(v) ≥ 0 даёт v ≥ 1/2 — то есть резервная цена 1/2, независимо от числа участников.

Два следствия, которые стоит унести:

• Резервная цена — не жадность, а математический оптимум. Отказ продать иногда выгоднее продажи.
• Теорема об эквивалентности выручки (revenue equivalence): при симметричных независимых ценностях и одинаковом правиле распределения все правдивые механизмы дают одинаковую ожидаемую выручку. Первый ценовой, второй ценовой, английский, голландский — в среднем одно и то же. Отличаются они не выручкой, а устойчивостью к манипуляциям, дисперсией и требованиями к рациональности участников.

Знаменитый практический вывод Бульова–Клемперера: привлечь одного дополнительного участника ценнее, чем идеально настроить механизм (аукцион с n+1 участниками без резервной цены даёт больше, чем оптимальный по Майерсону с n). Для продукта это означает: инвестируйте в ликвидность рынка, а не в тонкую настройку правил.

Вычислительная теория игр: насколько трудно найти равновесие

Теорема Нэша гарантирует существование равновесия. Дальше вступает теория сложности.

Теорема (Daskalakis, Goldberg, Papadimitriou, 2006; Chen & Deng). Поиск равновесия Нэша в игре двух лиц с ненулевой суммой является PPAD-полной задачей. Полный текст: https://people.csail.mit.edu/costis/simplified.pdf

Класс PPAD — это задачи поиска, чьё решение гарантированно существует по «топологическому» аргументу (лемма Спернера, теорема Брауэра о неподвижной точке). Такие задачи не могут быть NP-полными в обычном смысле (у них всегда есть ответ, поэтому нет «нет»-экземпляров), но и полиномиального алгоритма для них не известно, и его существование считается маловероятным.

Философский вывод чрезвычайно важен: если равновесие нельзя вычислить, оно теряет статус предсказания. Модель, требующая от агентов решить PPAD-трудную задачу, вряд ли описывает реальное поведение. Это аргумент Пападимитриу: «понятие равновесия должно быть вычислимым, иначе оно неубедительно».

Что вычислимо за полином:

Коррелированное равновесие (Aumann, 1974) заслуживает отдельного внимания, потому что оно и вычислимо, и практично.

Определение. Распределение p на профилях S — коррелированное равновесие, если для каждого игрока i и каждой пары стратегий a, b ∈ S_i:

Σ_{s_{-i}} p(a, s_{-i}) · [u_i(a, s_{-i}) - u_i(b, s_{-i})] ≥ 0

Модель: доверенный посредник (или общий источник случайности) тянет профиль из p и приватно сообщает каждому только его рекомендацию. Условие означает: получив рекомендацию a, вам невыгодно отклоняться на b.

Классический пример — светофор. Игра «ястреб-голубь» на перекрёстке имеет плохое смешанное равновесие с авариями. Светофор реализует p = 1/2·(проезжай, стой) + 1/2·(стой, проезжай) — лучше любого равновесия Нэша, и никому не выгодно нарушать. Это и есть математическое обоснование того, зачем распределённой системе координатор, лидер, lease или общий seed. Всё это — устройства корреляции.

Условия коррелированного равновесия — линейные неравенства относительно p, поэтому множество таких равновесий — политоп, и оптимизировать по нему можно линейным программированием. За полиномиальное время, для любого числа игроков. Практический вывод: если вы проектируете систему, проектируйте под коррелированное равновесие, а не под Нэша — оно и лучше по выплатам, и вычислимо.

No-regret learning: как равновесие возникает само

Самый практичный мост между теорией и кодом. Вместо «вычислим равновесие» — «пусть агенты учатся, и посмотрим, куда сойдётся среднее».

Определение (внешнее сожаление). После T раундов:

Regret_T = max_{a ∈ S_i} Σ_{t=1}^T u_i(a, s_{-i}^t)  -  Σ_{t=1}^T u_i(s_i^t, s_{-i}^t)

«Насколько лучше я мог бы сыграть, если бы всё время играл одну лучшую фиксированную стратегию». Алгоритм называется no-regret, если Regret_T / T → 0.

Теорема. Если все игроки используют no-regret алгоритмы, эмпирическое распределение сыгранных профилей сходится к множеству грубых коррелированных равновесий. Для игр с нулевой суммой этого достаточно: средние стратегии сходятся к минимаксному равновесию. Более сильный вариант — regret matching, дающий сходимость к коррелированному равновесию (Hart & Mas-Colell, 2000).

import random

def regret_matching(A, T=50000, seed=0):
    """Regret matching для игры двух лиц с нулевой суммой (B = -A).
    Каждый игрок играет пропорционально накопленным положительным сожалениям.
    Средние стратегии сходятся к равновесию.
    Сложность: O(T * (n + m)) времени, O(n + m) памяти — линейно, без LP."""
    rnd = random.Random(seed)
    n, m = len(A), len(A[0])
    regret1, regret2 = [0.0] * n, [0.0] * m
    sum1, sum2 = [0.0] * n, [0.0] * m

    def strategy(regret, k):
        pos = [max(r, 0.0) for r in regret]
        total = sum(pos)
        return [p / total for p in pos] if total > 0 else [1.0 / k] * k

    def sample(dist):
        x, acc = rnd.random(), 0.0
        for i, pi in enumerate(dist):
            acc += pi
            if x < acc:
                return i
        return len(dist) - 1

    for _ in range(T):
        p1, p2 = strategy(regret1, n), strategy(regret2, m)
        for i in range(n): sum1[i] += p1[i]
        for j in range(m): sum2[j] += p2[j]
        a, b = sample(p1), sample(p2)
        u = A[a][b]
        # контрфактическое сожаление: «что если бы я сыграл i вместо a»
        for i in range(n): regret1[i] += A[i][b] - u
        for j in range(m): regret2[j] += (-A[a][j]) - (-u)

    return [x / T for x in sum1], [x / T for x in sum2]

RPS = [[0, -1, 1], [1, 0, -1], [-1, 1, 0]]
p, q = regret_matching(RPS)
print([round(x, 3) for x in p], [round(x, 3) for x in q])
# [0.331, 0.335, 0.334] [0.337, 0.331, 0.331] — сходится к (1/3, 1/3, 1/3)

Двадцать строк кода находят равновесие без всякого LP — и именно этот подход, развитый до Counterfactual Regret Minimization (CFR), привёл к решению покера: Libratus (2017) и Pluribus (2019) обыграли профессионалов в безлимитном холдеме. Bowling et al., «Heads-up limit hold’em poker is solved», Science 2015 — https://www.science.org/doi/10.1126/science.1259433

Та же идея — основа современного мультиагентного обучения: self-play в AlphaZero, минимаксная формулировка GAN (min_G max_D), состязательное обучение с робастностью. Подробнее про обучение — трек машинного обучения.

Приложения в распределённых системах

Здесь всё сходится вместе. Распределённая система — это буквально игра: узлы с приватной информацией, локальные стимулы, отсутствие центрального принуждения.

Консенсус и модель BAR. Классический BFT делит узлы на честных и византийских. Модель BAR (Byzantine, Altruistic, Rational) добавляет третий тип — рациональные узлы, которые не злонамеренны, но отклоняются от протокола, если это выгодно (Aiyer et al., SOSP 2005 — https://www.cs.utexas.edu/users/dahlin/papers/bar-sosp-2005.pdf). Это ближе к реальности: узел, экономящий CPU на проверке подписей, не «византиец», а рационал. Протокол должен быть incentive-compatible, а не только устойчивым к сбоям.

Selfish mining. Эял и Сирер (2014) показали: майнер с долей хешрейта α > 1/3 (в идеализированном случае — даже меньше при хорошей сетевой связности) получает выгоду, придерживая найденные блоки, а не публикуя их сразу. То есть «честное следование протоколу» не является равновесием Нэша в Bitcoin при больших пулах. Работа: https://arxiv.org/abs/1311.0243 — образцовый пример теоретико-игрового анализа, изменившего понимание безопасности системы. Урок: «протокол корректен» и «протоколу выгодно следовать» — разные утверждения, и второе надо доказывать отдельно.

MEV и аукционы за порядок транзакций. Maximal Extractable Value — прибыль от переупорядочивания транзакций в блоке. Это чистая теория игр: у валидатора есть приватная информация (мемпул) и право выбора порядка. Инфраструктура вроде MEV-Boost — попытка превратить хаотичную гонку в структурированный аукцион с предсказуемыми свойствами. Академическая база: «Flash Boys 2.0» — https://arxiv.org/abs/1904.05234

Proof-of-Stake и slashing. Slashing — это буквально изменение выплат в листьях дерева игры. Депозит превращает «подписать два конфликтующих блока» из бесплатного действия в убыточное. Обратная индукция подсказывает, что размер депозита должен превышать максимальную выгоду от атаки, — и именно так параметры и выбираются.

Управление перегрузкой как игра популяции. TCP-совместимость — соглашение о «правилах игры»: если все используют AIMD, поток делится справедливо. Агент, реализующий более агрессивный контроль, получает больше полосы — то есть у протокола есть выгодное отклонение. Дискуссия вокруг BBR ровно об этом. Устойчивость здесь держится на том, что стек TCP реализован в ядре ОС, а не в приложении — правило принуждается технически, а не стимулами. Отличная иллюстрация третьего пути: если не можете сделать хорошее поведение выгодным, сделайте плохое невозможным.

Внутренние платформы и квоты. Завышение resource requests в Kubernetes — классическая трагедия общин. Механизмы, которые реально работают: показ фактической утилизации (превращает приватную информацию в публичную), внутренний chargeback (вводит платежи, а с ними появляется шанс на IC-механизм), автоматический VPA (убирает решение у агента вообще). Заметьте, что все три — не «уговоры», а изменения игры.

Типичные ошибки применения

1. Считать равновесие предсказанием. Равновесие — это утверждение об устойчивости, а не о том, что произойдёт. При нескольких равновесиях теория молчит о выборе; при PPAD-трудности сомнительно даже то, что агенты его найдут.

2. Складывать полезности разных игроков. Полезность определена с точностью до аффинного преобразования. «Суммарное благосостояние» законно только в квазилинейной среде с деньгами, где полезность = деньги + ценность.

3. Путать «доминирующая стратегия» и «равновесие Нэша». Первое не требует предположений о сопернике вообще, второе требует, чтобы соперник тоже играл равновесно. Разница в силе выводов колоссальна: механизм DSIC работает против кого угодно, механизм BIC — только если все верят в общую модель.

4. Забывать про обратную индукцию в конечных играх. Конечно повторяющаяся дилемма заключённого с известным горизонтом раскручивается назад к тотальному предательству. Кооперация нужен либо бесконечный (или неизвестной длины) горизонт, либо неопределённость типов.

5. Игнорировать сложность вычисления. Механизм, требующий решить NP-трудную задачу распределения на каждом запросе, не поедет в проде. Приближение при этом ломает правдивость — это не деталь, а теорема.

6. Проектировать под «идеального» злоумышленника, забыв про рационального. Большинство реальных отклонений — не атаки, а экономия. Модель BAR полезнее чистой византийской именно потому, что рациональные отклонения встречаются в тысячи раз чаще.

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

8. Забывать про шум. Стратегии, безупречные в детерминированной модели (grim trigger), катастрофичны при потерях пакетов и ложных срабатываниях. Всегда спрашивайте: что делает моя политика, если сигнал ошибочен?

Мини-итог

• Игра = игроки, стратегии, выплаты. Стратегия — полный план, а не ход.
• Строгое доминирование — самый сильный аргумент: не требует ничего от соперника. Равновесие Нэша — устойчивость к одностороннему отклонению; существует всегда (в смешанных стратегиях), но не обязано быть хорошим, единственным или вычислимым.
• Нулевая сумма — приятный частный случай: минимакс = равновесие, вычисляется LP за полином, даёт настоящую гарантию.
• Повторение делает кооперацию возможной при достаточно большом δ; folk theorem объясняет слишком многое, чтобы предсказывать.
• Цена анархии количественно оценивает потери от децентрализации: 4/3 для аффинной маршрутизации — почему децентрализованные протоколы приемлемы. Парадокс Брайеса — почему «улучшение» бывает ухудшением.
• Проектирование механизмов — инженерная часть. Vickrey/VCG показывают, что правдивость достижима, когда цена не зависит от собственной ставки. Гиббард–Саттертуэйт, Майерсон–Саттертуэйт и Эрроу показывают, чего добиться нельзя.
• Вычислимость решает. Равновесие Нэша PPAD-полно, коррелированное равновесие — в P. Проектируйте под коррелированное и под no-regret обучение.
• В распределённых системах правильный вопрос не «корректен ли протокол», а «выгодно ли ему следовать».

Источники

• Osborne, Rubinstein. A Course in Game Theory. MIT Press. Свободно доступен: https://arielrubinstein.tau.ac.il/books/CGT.pdf — строгий и компактный стандартный учебник.
• Shoham, Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Свободная версия: https://www.masfoundations.org/ — лучший вход для программиста, с алгоритмами.
• Nisan, Roughgarden, Tardos, Vazirani (ред.). Algorithmic Game Theory. Cambridge University Press, 2007. PDF: https://www.cs.cmu.edu/~sandholm/cs15-892F13/algorithmic-game-theory.pdf — каноническая книга по вычислительной стороне.
• Roughgarden. Twenty Lectures on Algorithmic Game Theory + видеокурс Stanford CS269I: https://timroughgarden.org/notes.html
• Nash. Equilibrium Points in n-Person Games. PNAS, 1950: https://www.pnas.org/doi/10.1073/pnas.36.1.48
• Roughgarden, Tardos. How Bad Is Selfish Routing? JACM, 2002: https://timroughgarden.org/papers/routing.pdf
• Daskalakis, Goldberg, Papadimitriou. The Complexity of Computing a Nash Equilibrium: https://people.csail.mit.edu/costis/simplified.pdf
• Eyal, Sirer. Majority Is Not Enough: Bitcoin Mining Is Vulnerable: https://arxiv.org/abs/1311.0243
• Daian et al. Flash Boys 2.0: Frontrunning in Decentralized Exchanges, MEV: https://arxiv.org/abs/1904.05234
• Aiyer et al. BAR Fault Tolerance for Cooperative Services. SOSP 2005: https://www.cs.utexas.edu/users/dahlin/papers/bar-sosp-2005.pdf
• Axelrod. The Evolution of Cooperation, 1984 — про турниры и Tit-for-Tat, читается за вечер.
• Библиотеки для практики: nashpy (равновесия для игр двух лиц, https://nashpy.readthedocs.io/), axelrod (турниры повторяющихся игр, https://axelrod.readthedocs.io/), open_spiel от DeepMind (CFR, self-play, https://github.com/google-deepmind/open_spiel).

Что дальше

Мы видели, что даже простая динамика наилучших ответов не обязана сходиться: репликаторная динамика в «камень-ножницы-бумага» кружит вечно, а в более сложных играх траектории ведут себя совсем дико. Это естественный мост к последней теме трека — системам, где «просто посчитать вперёд» перестаёт работать принципиально.

Теория хаоса и динамические системы: аттракторы, фракталы, чувствительность