Как теория игр обеспечивает существование блокчейна

Рыночные структуры

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

• Совершенная конкуренция
• Монополистическая конкуренция
• Олигополия
• Монополия

Совершенная конкуренция

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

Монополия

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

Монополистическая конкуренция

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

Олигополия

Олигополия характеризуется небольшим количеством игроков и высокими барьерами для входа на рынок. Одним их лучших примеров олигополии является рынок смартфонов. На нем доминируют несколько крупных игроков — Samsung (LSEIOB: SMSN), Apple (NASDAQ: AAPL), Huawei и другие.

Как и в случае монополистической конкуренции, их продукты похожи, но не идентичны. Хотя компании обладают некоторым контролем над ценами, диапазон возможных изменений невелик. Если завтра Apple решит продавать iPhone по $4000, большинство пользователей перейдут на смартфоны под управлением Android.

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

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

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

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

Теория игр

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

Теория игр стала развиваться как самостоятельная область математики и в скором времени нашла применение в различных областях.

Типичная задача теории состоит минимум из трех компонентов:

• Игроков (обычно ими выступают руководители компаний);
• Стратегий (решений, направленных на развитие бизнеса);
• Выигрышей (результатов стратегий).

В теории игры есть два типа игр:

• Игры с нулевой суммой. Это игры, в которых выигрыш одного участника означает проигрыш другого.
• Игры с ненулевой суммой. В них выигрыш какого-либо игрока не обязательно означает проигрыш другого.

Итак, как применять теорию игр? Давайте вернемся к вопросу о том, должна ли компания рекламировать некую особенность своего продукта. Предположим, есть две компании, А и Б.

Приведенная выше таблица называется «матрицей игры». В ней записаны все возможные варианты развития событий:

• Если компании А и Б решат разместить рекламу, то выигрыш каждой составит 4 и 3, соответственно.
• Если А не будет рекламировать свою продукцию, а Б решит дать рекламу, то выигрыш составит 2 и 5.
• Если А проведет рекламную компанию, а Б от нее откажется, то выигрыш составит 5 и 1.
• Если обе компании откажутся от рекламы, выигрыш первой составит 3, вторая получит 2.

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

Сначала рассмотрим компанию Б:

1. А размещает рекламу. Б получает 3 балла, если проводит рекламную кампанию, и 1 балл, если отказывается от нее. Очевидно, что для Б выгодно разместить рекламу.

2. А отказывается от рекламы. Б получает 5 баллов, размещая рекламу, и 2 — если отказывается от нее. В этом случае Б также выгодна реклама.

Вывод: Независимо от стратегии А, Б должна провести рекламную кампанию.

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

1. Б размещает рекламу. А получает 4 балла, если проводит рекламную кампанию, и 2 балла в обратном случае.

2. Б отказывается от рекламы. А получает 5 баллов, если размещает рекламу, и 3 — если нет. Снова наилучшая стратегия заключается в проведении рекламной кампании.

Вывод: Независимо от решений Б, А должна провести рекламную кампанию.

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

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

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

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

Дилемма заключенного

Предположим, что Роб и Бен попались на краже алкоголя из винного магазина. Во время расследования было установлено, что в прошлом они совершили серьезное преступление (скажем, ограбили банк). Полицейские допросили Роба и Бена и предложили им следующие варианты:

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

Давайте составим соответствующую матрицу игры и проанализируем ее:

Очевидно, Роб и Бен — закоренелые преступники, и они никого просто так не «сдадут» из-за «воровского кодекса». Это звучит романтично, однако теория игр и поведенческая психология говорят о другом.

Случаю, когда оба будут хранить молчание, соответствует ячейка (4,4). Другими словами, каждый получит по четыре года тюрьмы. Однако это очень неустойчивое состояние, поскольку оба знают, что есть более выгодные варианты. Если они настучат друг на друга, то им вовсе не придется сидеть в тюрьме.

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

Однако возникает одна проблема. Что, если оптимальные решения для обоих игроков предполагают негативные последствия для общества? Предположим, что Роб и Бен планируют ограбление банка. Матрица игры в этом случае будет выглядеть следующим образом:

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

Наказание

Мир нельзя назвать добрым и справедливым местом. Люди, как правило, легко поддаются искушениям и совершают действия, которые вредят обществу. Контролировать их как раз и помогает концепция наказания.

Предположим, что в приведенном выше примере стратегия наказания выглядит следующим образом:

«За каждые 0,5 ресурсов, похищенных у общества, последует наказание в 7 единиц».

Другими словами, за любое действие, наносящее вред публичным интересам в размере 0,5, последует наказание в 7 единиц. Чтобы предотвратить потерю полезности (денег, времени и других ресурсов), общество грозит преступникам серьезными карами.

Эта концепцию давно интегрирована в нашу жизнь. Фактор наказания снижает выигрыш от «плохих» поступков и меняет матрицу игры:

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

Какой смысл обществу тратить ресурсы на наказание? Ответ на этот вопрос заключается в его неотвратимости. Другими словами, если кто-то совершил правонарушение, он обязательно будет наказан. Если кто-то не желает вносить свой вклад в систему, он также становится преступником и подлежит преследованию.

Полиция финансируется за счет налогов, взимаемых с населения, и занимается поиском и наказанием преступников. Если кто-то не платит налоги (не принимает участия в системе наказания), то он также становится преступником.

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

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

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

Фокальные точки

Экономист Томас Шеллинг провел один интересный эксперимент. У группы студентов он поинтересовался:

«Предположим, завтра вам необходимо встретиться с незнакомцем в Нью-Йорке. Где и когда вы назначите встречу?».

Самым популярным ответом был: «В полдень в Центральном вокзале Нью-Йорка».

Для обитателей Нью-Йорка Центральный вокзал — естественная фокальная точка, также известная как точка Шеллинга.

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

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

Заключенным предлагается следующая последовательность чисел:

7816239, 676716313, 100000000 и 871823719

Как вы думаете, какое они выберут? Правильно, 100000000. Почему? Потому что оно выделяется и кажется особым по сравнению с остальными числами. Другими словами, это число — фокальная точка. На протяжении всей истории люди бессознательно собирались в различных местах (барах, церквях, социальных центрах и т. д.), поскольку обычно они являлись точками Шеллинга.

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

В этой игре есть два аварийных сценария:

• Оба водителя решили не сворачивать.
• Один свернул влево, другой — вправо.

Томас Шеллинг нашел решение этой игры с помощью фокальных точек. По его словам, не надо смотреть в глаза другому водителю (то есть прервать любое общение) и сосредоточиться на собственных инстинктах. В странах с правосторонним движением люди непроизвольно выворачивают руль вправо, к обочине, поскольку именно там находится точка Шеллинга.

Стратегия вечной кары

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

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

Остановить этот порочный круг невозможно — можно только не убивать царя с самого начала и всеми силами поддерживать понятие божественного права. Это и есть стратегия вечной кары.

Проблема координации

Рассмотрим матрицу:

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

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

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

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

Предположим, мы хотим изменить обычный язык на символьный. Например:

• Оригинальное предложение: «Скажите мне свой номер».
• Новое предложение: «#?»

Если вы говорите только на этом символьном языке, большинство вас не поймет, и вы будете избегать общения. Проще говоря, в этом случае никакого стимула к переменам у вас нет.

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

Именно поэтому никто не говорит, к примеру, на старославянском.

Концепция ограниченной рациональности

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

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

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

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

Блокчейн и криптовалюты

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

Некоторые термины:

• Генезис-блок — первый блок блокчейна.
• Доказательство работы — объем вычислений, необходимый для создания блока.
• Родительский блок — блок, непосредственно предшествующий текущему; на диаграмме выше блок 50 является родительским блоком блока 51.

Для каждого блока в блокчейне можно подсчитать оценку.

• Оценка (генезис-блок) = 0
• Оценка (блок) = Оценка (родительский блок) + Доказательство работы

Текущий блок — это блок с максимальной оценкой.

В основанной на блокчейне биткоин-сети есть две роли:

• Пользователи
• Майнеры

У пользователей есть только две возможности:

• Отправлять монеты
• Получать монеты

Для этого им нужны два ключа, публичный и закрытый. Майнеры делают две вещи:

• Подтверждают транзакции
• Рассчитывают новые блоки

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

Майнинг блоков

Проведя ряд вычислений, майнеры находят блок и добавляют его к блокчейну. В системе Ethereum за добавление блока майнер получает пять эфиров (ETH/USD), а в биткоин-сети — 12,5 биткоина (Bitcoin) (по состоянию на 30 августа 2017 года). Майнеры в системе блокчейна наделены большой властью, и, если они решат нарушить правила ради личной выгоды, система может погрузиться в хаос.

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

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

Теория игр в приложении к криптовалютам

Как майнеры могут жульничать?

• Они могут включить в блокчейн недействительную транзакцию и получить дополнительные монеты.
• Добавлять блоки случайным образом, не предъявляя доказательство работы.
• Майнить недопустимые блоки для получения дополнительных биткоинов.
• Майнить блоки с неоптимальной оценкой.

Давайте рассмотрим пример.

Зеленые блоки — это основной блокчейн. Теперь предположим, что некий майнер в зеленом блоке купил 500 лайткоинов (LTC/USD) за 20 биткоинов. И теперь он хочет создать параллельную цепочку с новым блоком 51 (красным), где он такой транзакции никогда не совершал. Итак, еще раз:

• В зеленом блоке 51 тратится 20 биткоинов в обмен на 500 лайткоинов.
• Создается новая цепочка (ветвление) от блока 50, и в альтернативном блоке 51 транзакции с лайткоином не было.
• Майнер оказывается владельцем и 20 биткоинов и 500 лайткоинов.

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

Так почему же майнеры этого не делают? Потому что они такие честные и хорошие?

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

Равновесие Нэша в майнинге и система наказаний

• Если майнер создает недопустимый блок, другие не будут продолжать неверную цепочку, поскольку любой блок, добавляемый поверх недопустимого блока, становится недопустимым. Это правило предписывает майнерам просто игнорировать такой блок и продолжать зеленую цепочку из нашего примера.
• Аналогичное правило касается блоков с неоптимальной оценкой. Взгляните на иллюстрацию. Ни один майнер не захочет добавлять красный блок 52, потому что у зеленого блока 53 будет более высокая оценка (больше баллов).

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

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

Что заставляет пользователей использовать основную, а не альтернативную цепочку?

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

• Ценность криптовалюте придают люди. Почему же обычный пользователь должен ценить монеты, генерируемые зеленой, а не красной цепочкой? Все просто: с точки зрения пользователей, основная цепочка — это точка Шеллинга.
• Вторая причина иллюстрируется принципом ограниченной рациональности. Мы помним, что люди склонны выбирать самое простое решение. Смена цепочки — это ненужное усложнение ситуации.

Проблема захвата доказательства работы?

Давайте посмотрим на диаграмму.

Виталик Бутерин, создатель Ethereum, показал отличный пример проблемы захвата. Предположим, некто создает смарт-контракт на определенное действие. Условия контракта следующие:

• Любой майнер может присоединиться к этой деятельности, отправив в контракт очень большой депозит;
• Майнеры должны отправлять в контракт фрагменты частично созданных блоков, после чего контракт их проверяет и удостоверяет, что пославший является майнером и что у него есть достаточная хеш-мощность;
• Пока к контракту не присоединились 60% майнеров системы, из него можно в любой момент выйти;
• После того как 60% майнеров присоединятся, все майнеры будут связаны контрактом, пока к альтернативной (красной) цепочке не будут добавлены 20 блоков.

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

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

Давайте рассмотрим их стимулы.

• Возможная награда в итоге
• Никакого риска в момент присоединения

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

• Внесенный огромный депозит
• Возможность получить вознаграждение

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

На помощь спешит вечная кара

Давайте вспомним разговор о стратегии вечной кары. Если царь убит, а трон узурпирован, нет никакого повода не убить нового царя, и так до бесконечности. Единственное, что можно сделать — не убивать первого царя.

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

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

Выводы

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