Июнь 2016

Объем 31 Номер 6

Тесты - Введение в рынок предсказаний

Джеймс Маккафри | Июнь 2016

Исходный код можно скачать по ссылке msdn.com/magazine/0616magcode.

Джеймс МаккафриДопустим, вы хотите предсказать результат предстоящего футбольного матча между командами Xrays и Yanks. Вы находите группу из 20 экспертов по футболу и выдаете каждому из них по $500 жетонами. Экспертам разрешается покупать и продавать акции каждой из двух команд в стиле, который в какой-то мере напоминает то, как работает биржа.

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

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

То, что я сейчас описал, называют рынком предсказаний (prediction market). В этой статье я расскажу о математическом аппарате, стоящем за рынком предсказаний, и покажу, как реализовать ключевые функции в коде. Маловероятно, что вам когда-нибудь понадобится создавать рынок предсказаний в своей повседневной работе, но, по моему мнению, вы сочтете эти идеи очень интересными. Кроме того, некоторые из методов программирования, представленных в этой статье, применимы и в более распространенных сценариях разработки программного обеспечения.

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

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

Пример

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

Setting liquidity parameter = 100.0

Initial number of shares owned of teams [0] and [1] are:
0 0

Initial inferred probabilities of winning are:
 0.5000  0.5000

Демонстрация рынка предсказаний
Рис. 1. Демонстрация рынка предсказаний

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

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

Следующая часть вывода демонстрации:

Current costs for one share of each team are:
 $0.5012  $0.5012

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

Следующая часть вывода демонстрации:

Update: expert [01] buys 20 shares of team [0]

Cost of transaction to expert was: $10.50

Эксперт #1 считает, что команда 0, Xrays, выиграет матч, и покупает 20 акций команды 0. Это обходится эксперту в $10.50. Заметьте, что цена за 20 акций ($10.50) — это не то же самое, что 20-кратная цена одной акции (20 * $0.5012 = $10.02). По мере покупки каждой акции цена за дополнительную акцию команды увеличивается.

Следующая часть вывода демонстрации:

New number of shares owned of teams [0] and [1] are:
20 0

New inferred probabilities of winning are:
 0.5498  0.4502

Демонстрационная программа показывает обновленное количество акций каждой команды, находящихся в обращении: (x, y) = (20, 0). Затем вычисляет и отображает обновленные прогнозируемые вероятности выигрыша каждой команды (0.55, 0.45). Поскольку эксперты купили больше акций команды 0, чем акций команды 1, прогнозируемая вероятность выигрыша команды 0 должна быть выше, чем в случае команды 1. Расчет вероятностей я поясню чуть позже.

Далее демонстрация отображает:

Current costs for one share of each team are:
 $0.5511  $0.4514

Update: expert [02] buys 20 shares of team [1]

Cost of transaction to expert was: $9.50

Вычисляется и отображается новая стоимость за акцию каждой команды. Заметьте, что цена акции команды 0 ($0.55) теперь заметно выше таковой у команды 1 ($0.45). Это дает экспертам стимул покупать акции команды 1, если они считают эту цену хорошим значением относительно вероятности команды 1 на выигрыш. В этом случае демонстрация симулирует эксперта #2, покупающего 20 акций команды 1 по цене $9.50. Затем выводит:

New number of shares owned of teams [0] and [1] are:
20 20

New inferred probabilities of winning are:
 0.5000  0.5000

Теперь у каждой команды приобретено по 20 акций, поэтому прогнозируемые вероятности каждой команды на выигрыш возвращаются к 0.50 и 0.50.

Следующая часть вывода демонстрации:

Current costs for one share of each team are:
 $0.5012  $0.5012

Update: expert [03] buys 60 shares of team [0]
Cost of transaction to expert was: $34.43

New number of shares owned of teams [0] and [1] are:
80 20

New inferred probabilities of winning are:
 0.6457  0.3543

Эксперт #3 твердо убежден, что выиграет команда 0, поэтому он покупает 60 акций этой команды за $34.43. Эта сделка меняет количество акций в обращении (outstanding shares) до (80, 20) и заметно смещает новые прогнозируемые вероятности выигрыша в сторону команды 0 (0.65, 0.35).

Далее эксперт #1 видит, что цена его акций команды 0 значительно выросла приблизительно до $0.6468 за штуку:

Current costs for one share of each team are:
 $0.6468  $0.3555

Update: expert [01] sells 10 shares of team [0]
Cost of transaction to expert was: $-6.34

New number of shares owned of teams [0] and [1] are:
70 20

New inferred probabilities of winning are:
 0.6225  0.3775

Эксперт #1 чувствует, что шансы команды 0 на выигрыш сейчас несколько переоценены, и продает 10 из своих 20 акций, получая $6.34 (обозначается знаком «минус»). Новые прогнозируемые вероятности снова становятся немного ближе, но вероятность выигрыша команды 0 все равно составляет 0.63.

Демонстрация завершается закрытием торгов. Целью рынка предсказаний являются конечные вероятности. После матча между Xrays и Yanks экспертам заплатят за акции, которые они держат в выигравшей команде, на основе конечной цены за акцию этой команды. Выплаты поощряют экспертов давать свои реальные оценки.

Четыре ключевых уравнения рынка предсказаний

Базовый рынок предсказаний использует четыре математических уравнения (рис. 2). Потерпите минутку; эти уравнения не столь сложны, как может показаться на первый взгляд. Существует несколько математических моделей, которые можно использовать для определения рынка предсказаний. Модель, представленная в этой статье, основана на так называемом логарифмическом счетном правиле рынка (Logarithmic Market Scoring Rule, LMSR).

Четыре ключевых уравнения рынка предсказаний
Рис. 2. Четыре ключевых уравнения рынка предсказаний

Уравнение 1 — это функция стоимости (cost function), связанная с набором акций в обращении (x, y). Это уравнение, которое вовсе не очевидно, взято из экономической теории. С точки зрения разработчика, можно рассматривать это уравнение как вспомогательную функцию. Она принимает x (количество акций, приобретенных по варианту 0) и y (количество акций, приобретенных по варианту 1), а затем возвращает некое значение. Переменная b во всех четырех уравнениях — это параметр liquidity (ликвидность). Допустим, что x = 20 и y = 10. Если b = 100.0, то C(x,y) = 100.0 * ln(exp(20/100) + exp(10/100)) = 100.0 * ln(1.22 + 1.11) = 100.0 * 0.8444 = $84.44. Это возвращаемое значение используется в уравнении 2.

Уравнение 2 — это стоимость сделки для покупателя. Предположим, что текущий набор акций в обращении — (20, 10) и что эксперт покупает 30 акций по варианту 0. Стоимость этой сделки для эксперта вычисляется с помощью уравнения 2 как C(20+30, 10) – C(20, 10) = C(50, 10) – C(20, 10) = 101.30 – 84.44 = $16.86. Если эксперт продает акции, стоимость сделки будет отрицательным значением, указывающим на то, что эксперт получил оплату.

Уравнение 3, с технической точки зрения, является маргинальной ценой (marginal price) варианта 0, основанной на наборе акций в обращении (x, y). Но маргинальную цену можно вольно интерпретировать как вероятность, с которой может выиграть какой-либо вариант. Уравнение 4 — это маргинальная цена (вероятность) варианта 1. Если вы внимательно посмотрите на эти два уравнения, то заметите, что в сумме они должны давать 1.0, как это требуется для набора вероятностей.

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

static double Cost(int[] outstanding, double liq)
{
  double sum = 0.0;
  for (int i = 0; i < 2; ++i)
    sum += Math.Exp(outstanding[i] / liq);
  return liq * Math.Log(sum);
}

Метод Cost является практически точной трансляцией уравнения 1. Заметьте, что в методе Cost предполагается наличие всего двух вариантов (options). Для простоты проверка на ошибки отсутствует.

Уравнение 2 тоже довольно простое в реализации:

static double CostOfTrans(int[] outstanding, int idx, int nShares, double liq)
{
  int[] after = new int[2];
  Array.Copy(outstanding, after, 2);
  after[idx] += nShares;
  return Cost(after, liq) - Cost(outstanding, liq);
}

Массив с именем after хранит новое количество акций в обращении после сделки, и метод просто дважды вызывает вспомогательный метод Cost. Располагая методом для вычисления стоимости сделки, легко написать метод, который рассчитывает стоимость покупки одной акции по каждому варианту:

static double[] CostForOneShare(int[] outstanding, double liq)
{
  double[] result = new double[2];
  result[0] = CostOfTrans(outstanding, 0, 1, liq);
  result[1] = CostOfTrans(outstanding, 1, 1, liq);
  return result;
}

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

Метод Probabilities возвращает две маргинальные цены (прогнозируемые вероятности) по каждому побеждающему варианту в массиве:

static double[] Probabilities(int[] outstanding, double liq)
{
  double[] result = new double[2];
  double denom = 0.0;
  for (int i = 0; i < 2; ++i)
    denom += Math.Exp(outstanding[i] / liq);
  for (int i = 0; i < 2; ++i)
    result[i] = Math.Exp(outstanding[i] / liq) / denom;
  return result;
}

Если вы сравните код для метода Probabilities с уравнениями 3 и 4, то увидите, что код опять следует непосредственно математическому определению.

Демонстрационная программа

Чтобы создать демонстрационную программу, я запустил Visual Studio, выбрал шаблон C# Console Application и назвал проект PredictionMarket. В этой программе нет значимых зависимостей от .NET Framework, поэтому подойдет любая версия Visual Studio.

После загрузки кода шаблона в окно редактора я переименовал в окне Solution Explorer файл Program.cs в более описательный PredictionMarketProgram.cs, и Visual Studio автоматически переименовала класс Program за меня. В начале кода я удалил все лишние выражения using, оставив только ссылку на пространство имен верхнего уровня System.

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

Рис. 3. Демонстрационная программа рынка предсказаний

using System;
namespace PredictionMarket
{
  class PredictionMarketProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin prediction market demo ");
      Console.WriteLine("Goal is to predict winner of Xrays");
      Console.WriteLine("vs. Yanks using expert opinions");
      double liq = 100.0;
      Console.WriteLine("Setting liquidity parameter = " +
        liq.ToString("F1"));
      int[] outstanding = new int[] { 0, 0 };
      Console.WriteLine("Initial number of shares owned are:");
      ShowVector(outstanding);
      double[] probs = Probabilities(outstanding, liq);
      Console.WriteLine("Initial probabilities of winning:");
      ShowVector(probs, 4, " ");
      Console.WriteLine("=================================");
      double[] costPerShare = CostForOneShare(outstanding, liq);
      Console.WriteLine("Current costs for one share are: ");
      ShowVector(costPerShare, 4, " $");
      Console.WriteLine("Update: expert [01] buys 20 shares " +
        "of team [0]");
      double costTrans = CostOfTrans(outstanding, 0, 20, liq);
      Console.WriteLine("Cost of transaction to expert was: $" +
        costTrans.ToString("F2"));
      outstanding = new int[] { 20, 0 };
      Console.WriteLine("New number of shares owned are: ");
      ShowVector(outstanding);
      probs = Probabilities(outstanding, liq);
      Console.WriteLine("New inferred probs of winning:");
      ShowVector(probs, 4, " ");
      Console.WriteLine("=================================");
      costPerShare = CostForOneShare(outstanding, liq);
      Console.WriteLine("Current costs for one share are:");
      ShowVector(costPerShare, 4, " $");
      Console.WriteLine("Update: expert [02] buys 20 shares " +
        "of team [1]");
      costTrans = CostOfTrans(outstanding, 1, 20, liq);
      Console.WriteLine("Cost of transaction to expert was: $" +
        costTrans.ToString("F2"));
      outstanding = new int[] { 20, 20 };
      Console.WriteLine("New number of shares owned are:");
      ShowVector(outstanding);
      probs = Probabilities(outstanding, liq);
      Console.WriteLine("New inferred probs of winning:");
      ShowVector(probs, 4, " ");
      Console.WriteLine("=================================");
      costPerShare = CostForOneShare(outstanding, liq);
      Console.WriteLine("Current costs for one share are:");
      ShowVector(costPerShare, 4, " $");
      Console.WriteLine("Update: expert [03] buys 60 shares " +
        "of team [0]");
      costTrans = CostOfTrans(outstanding, 0, 60, liq);
      Console.WriteLine("Cost of transaction to expert was: $" +
        costTrans.ToString("F2"));
      outstanding = new int[] { 80, 20 };
      Console.WriteLine("New number of shares owned are:");
      ShowVector(outstanding);
      probs = Probabilities(outstanding, liq);
      Console.WriteLine("New inferred probs of winning:");
      ShowVector(probs, 4, " ");
      Console.WriteLine("=================================");
      costPerShare = CostForOneShare(outstanding, liq);
      Console.WriteLine("Current costs for one share are: ");
      ShowVector(costPerShare, 4, " $");
      Console.WriteLine("Update: expert [01] sells 10 shares " +
        "of team [0]");
      costTrans = CostOfTrans(outstanding, 0, -10, liq);
      Console.WriteLine("Cost of transaction to expert was: $" +
        costTrans.ToString("F2"));
      outstanding = new int[] { 70, 20 };
      Console.WriteLine("New number of shares owned are:");
      ShowVector(outstanding);
      probs = Probabilities(outstanding, liq);
      Console.WriteLine("New inferred probs of winning:");
      ShowVector(probs, 4, " ");
      Console.WriteLine("=================================");
      Console.WriteLine("Update: Market Closed");
      Console.WriteLine("\nEnd prediction market demo \n");
      Console.ReadLine();
    } // Main()
    static double[]Probabilities(int[] outstanding,
      double liq)
    {
      double[] result = new double[2];
      double denom = 0.0;
      for (int i = 0; i < 2; ++i)
        denom += Math.Exp(outstanding[i] / liq);
      for (int i = 0; i < 2; ++i)
        result[i] = Math.Exp(outstanding[i] / liq) / denom;
      return result;
    }
    static double Cost(int[] outstanding, double liq)
    {
      double sum = 0.0;
      for (int i = 0; i < 2; ++i)
        sum += Math.Exp(outstanding[i] / liq);
      return liq * Math.Log(sum);
    }
    static double CostOfTrans(int[] outstanding, int idx,
      int nShares, double liq)
    {
      int[] after = new int[2];
      Array.Copy(outstanding, after, 2);
      after[idx] += nShares;
      return Cost(after, liq) - Cost(outstanding, liq);
    }
    static double[] CostForOneShare(int[] outstanding,
      double liq)
    {
      double[] result = new double[2];
      result[0] = CostOfTrans(outstanding, 0, 1, liq);
      result[1] = CostOfTrans(outstanding, 1, 1, liq);
      return result;
    }
    static void ShowVector(double[] vector, int dec, string pre)
    {
      for (int i = 0; i < vector.Length; ++i)
        Console.Write(pre + vector[i].ToString("F" + dec) + " ");
      Console.WriteLine("\n");
    }
    static void ShowVector(int[] vector)
    {
      for (int i = 0; i < vector.Length; ++i)
        Console.Write(vector[i] + " ");
      Console.WriteLine("\n");
    }
  } // класс Program
} // ns

После отображения некоторых предварительных сообщений выполнение программы в методе Main начинается с:

double liq = 100.0;
int[] outstanding = new int[] { 0, 0 };
ShowVector(outstanding);

Переменная liq — это параметр ликвидности (liquidity). Значение 100.0 является типичным, но, поэкспериментировав с варьированием этого значения, вы увидите, как оно влияет на изменение стоимости акций после какой-либо сделки. Более высокие значения ликвидности дают меньшие изменения. Массив с именем outstanding содержит общее количество акций (каждой из двух команд) во владении всех экспертов. Обратите внимание на то, что параметр ликвидности должен передаваться четырем статическим методам рынка предсказаний. Альтернатива — инкапсулировать методы в C#-класс и определить ликвидность как поле класса.

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

double[] probs = Probabilities(outstanding, liq);
Console.WriteLine("Initial probabilities of winning:");
ShowVector(probs, 4, " ");

Далее в демонстрации отображаются цены покупки одной акции каждой из двух команд:

double[] costPerShare = CostForOneShare(outstanding, liq);
Console.WriteLine("Current costs for one share are: ");
ShowVector(costPerShare, 4, " $");

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

Демонстрационная программа симулирует одного из экспертов, покупающего некие акции:

Console.WriteLine("Update: expert [01] buys 20 shares of team [0]");
double costTrans = CostOfTrans(outstanding, 0, 20, liq);
Console.WriteLine("Cost of transaction to expert was: $" +
  costTrans.ToString("F2"));

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

Потом количество акций в обращении обновляется следующим образом:

outstanding = new int[] { 20, 0 };
Console.WriteLine("New number of shares owned on teams [0] " +
  "and [1] are: ");
ShowVector(outstanding);

Если вы вернетесь к математическим уравнениям на рис. 2, то заметите, что количество акций в обращении для каждой команды/варианта, (x, y), требуется во всех уравнениях.

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

probs = Probabilities(outstanding, liq);
Console.WriteLine("New inferred probabilities of
  winning are: ");
ShowVector(probs, 4, " ");

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

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

  • отображение текущей стоимости одной акции каждой команды;
  • выполнение сделки на покупку или продажу;
  • отображение стоимости сделки;
  • обновление общего количества акций в обращении;
  • обновления вероятности каждой команды на выигрыш.

Заметьте, что демонстрационная программа начинает с равных вероятностей каждой команды на выигрыш. Это не реалистично на многих настоящих рынках предсказаний. Можно инициализировать рынок предсказаний неравными вероятностями, решая уравнения 3 и 4 для x и y.

Заключение

Информация в этой статье основана на научной статье Робина Хансона (Robin Hanson) «Logarithmic Market Scoring Rules for Modular Combinatorial Information Aggregation» за 2002 год. Вы можете найти ее PDF-версию в нескольких местах в Интернете, используя любой инструмент поиска.

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

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


Джеймс Маккафри (Dr. James McCaffrey) работает на Microsoft Research в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и Bing. С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи экспертам Microsoft Паллави Чоудхури (Pallavi Choudhury), Газу Икбалу (Gaz Iqbal), Умешу Мадану (Umesh Madan) и Тину Суванди (Tien Suwandy).


Discuss this article in the MSDN Magazine forum