---

Juin 2016

Volume 31, numéro 6

Cet article a fait l'objet d'une traduction automatique.

Série de tests - Présentation des marchés de prédiction

Par James McCaffrey

Supposons que vous souhaitiez prédire le résultat d’un match de football championnat à venir entre le Xrays et les Yanks. Vous trouvez un groupe d’experts de football 20 et donner à chacun d’eux, 500 $ dans les jetons. Les experts sont autorisés à acheter et vendre des actions de chacun des deux équipes, d’une manière quelque peu semblable au fonctionnement de la bourse.

Lorsqu’un expert achète partages dans une équipe, par exemple le Xrays, le prix d’un partage de l’équipe augmente et diminue le prix d’un partage de l’autre équipe. Au fil du temps, les experts seront acheter et vendre des actions des deux équipes jusqu'à stabilisent les prix, vous serez alors en mesure de déduire la probabilité de gagner de chaque équipe.

Vous interrompre commerciaux le jour précédant le jeu championnat. Une fois le jeu et le vainqueur est déterminé, vous payez des experts qui ont des partages dans l’équipe gagnante selon le dernier prix de l’équipe de la fermeture de commerciaux. Étant donné que les experts savent qu’ils amèneront payer, ils ont motivés afin de donner leur avis trues lors de la négociation.

Ce que je viens de décrire, un marché de prédiction est appelée. Dans cet article, je vais décrivent les mathématiques qui sous-tendent les marchés de prédiction et vous montrer comment implémenter les fonctions clées dans le code. Il est peu probable que vous devrez jamais créer un marché de prédiction dans votre travail quotidien, mais je pense que vous trouverez les idées très intéressante. En outre, certaines techniques de programmation présentées dans cet article peuvent servir dans des scénarios de développement logiciel plus courants.

Cet article suppose que vous avez des compétences de codage de niveau débutant au moins, mais ne suppose pas que vous avez des connaissances sur les marchés de prédiction. Je présente un programme de démonstration complète, et vous pouvez également obtenir le code source à partir du téléchargement qui accompagne cet article. Cette démonstration met en c#, mais vous ne devez avoir aucun mal à refactoriser le code dans un autre langage si vous le souhaitez.

Notez qu’il s’agit d’une présentation informelle des marchés de prédiction, principalement destinées aux développeurs de logiciels. Je prends quelques libertés avec la terminologie et les définitions pour garder les idées principales plus clair possible.

un exemple

PRÉDICTION marchés sont peut-être meilleures expliqué avec un exemple concret. Jetez un oeil sur le programme de démonstration en Figure 1. Après quelques messages préliminaires, la sortie de démonstration commence par :

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

Figure 1 une prédiction marché démo

Le paramètre de liquidités sera bientôt expliqué en détail, mais pour le moment il suffit de savoir que les contrôles de liquidités combien prix du marché réagir à l’achat et la vente. Des valeurs plus élevées de liquidité produisent plus petites variations de prix.

Au départ, aucun partage n’est détenus par des experts. Étant donné que le nombre d’actions pour chaque équipe est le même (zéro), il est raisonnable qu’initial déduit la probabilité de qu'une équipe gagne est 0,50.

La partie suivante de la sortie de démonstration est :

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

À tout moment, un partage de chaque équipe possède un prix. Les experts doivent connaître ce prix car jouent argent réel. Étant donné que les probabilités de gain initiales sont égales, il est raisonnable que les prix pour un partage de chaque équipe sont également les mêmes.

La partie suivante de la sortie de démonstration est :

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

Cost of transaction to expert was: $10.50

Expert #1 pense que l’équipe 0, le Xrays, gagnez et achète 20 actions d’équipe 0. Le coût de l’expert est $10.50. Notez que le prix de 20 partages ($10,50) n’est pas identique à 20 fois le prix d’un seul partage (20 * $0.5012 = $10.02). Chaque action est achetée, augmente le prix d’un partage supplémentaire de l’équipe. La partie suivante de la sortie de démonstration est :

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

New inferred probabilities of winning are:
 0.5498  0.4502

La démonstration affiche le nombre d’actions en circulation mis à jour sur chaque équipe, (x, y) = (20, 0) et calcule et affiche mis à jour déduit les probabilités de chaque gain d’équipe (0,55, 0,45). Étant donné que les experts ont acheté plusieurs partages de 0 à 1 de l’équipe d’équipe, la probabilité de gagner de l’équipe 0 déduite doit être supérieure à celle de l’équipe 1. Le calcul des probabilités sera bientôt expliqué.

Ensuite, la démonstration affiche :

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

Le nouveau coût unitaire pour chaque équipe est calculé et affiché. Notez que le prix d’une part de l’équipe 0 (0,55$) est désormais plus coûteux que celui de l’équipe 1 (0,45$). Ainsi, les experts inciter à acheter des actions de l’équipe 1 si elles pensent que le prix est une bonne valeur par rapport à la probabilité de gagner de l’équipe 1. Dans ce cas, la démonstration simule expert #2 achat de 20 actions d’équipe 1 pour un coût de $9,50. Suivant :

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

New inferred probabilities of winning are:
 0.5000  0.5000

Il existe désormais 20 actions en attente pour chaque équipe, afin de rétablir les probabilités de gain de chaque équipe déduites 0,50 et 0,50.

La partie suivante de la sortie de démonstration est :

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

Expert #3 pense fortement que gagnez équipe 0, donc il achète 60 partages d’équipe 0 pour un coût de $34.43. Cette opération modifie le nombre d’actions en circulation à (80, 20) et les probabilités nouvelle déduites de gagner à adopter fortement équipe 0 (0,65, 0,35).

Ensuite, expert #1 constate que la valeur de ses actions dans l’équipe 0 ont considérablement augmenté à environ 0.6468 $ par action :

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

Expert #1 estime que l’équipe 0 est maintenant un peu hors de prix par rapport à ses chances de gagner fabrique et vend des 10 ses parts 20, mise en route de $6.34 (indiqué par le signe négatif). Le nouveau déduit probabilités ajuster à un peu plus égal, mais team 0 est toujours prédite avec une probabilité respectivement 0,63.

La démonstration se termine en fermant des commerciaux. Les probabilités finales sont l’objectif du marché de prédiction. Une fois le jeu entre le Xrays et les Yanks est lu, experts seraient payés parts qu’ils détiennent dans l’équipe gagnante, basée sur le prix final de l’équipe gagnante. Les paiements encourager la part des experts afin de donner leur avis trues.

Les équations de marché quatre clés de prédiction

Un marché de prédiction de base utilise quatre des équations mathématiques, comme indiqué dans Figure 2. Laissez-moi m’expliquer ; les équations ne sont pas presque aussi compliquées qu’ils peuvent apparaître tout d’abord. Il existe plusieurs modèles mathématiques qui peuvent être utilisés pour définir un marché de prédiction. Le modèle présenté dans cet article est basé sur ce que l'on appelle le logarithmique marché score règle (LMSR).

Figure 2 les équations de marché quatre clés de prédiction

Équation 1 est la fonction de coût associée à un ensemble d’actions en circulation (x, y). L’équation, ce qui n’est pas du tout évidente, provient de la théorie de l’économie. Du point de vue de développeur, vous pouvez considérer l’équation comme une fonction d’assistance. Il accepte x, qui est le nombre d’actions détenu d’option de 0, et y, qui est le nombre d’actions détenu de l’option 1 et retourne une valeur. Variable b dans toutes les équations de quatre est le paramètre de liquidité. Supposons que x = 20 et y = 10. Si b = 100.0, puis C(x,y) = 100.0 * ln(exp(20/100) + exp(10/100)) = 100.0 * Log (1.22 + 1.11) = 100.0 * 0.8444 = 84.44 $. La valeur de retour est utilisée dans l’équation 2.

Équation 2 est le coût d’une transaction pour l’acheteur. Supposons qu’un ensemble d’actions en circulation actuel est (20, 10) et un expert achète 30 partages d’option de 0. Le coût de cette transaction à l’expert est calculé à l’aide de l’équation 2 c (20 + 30, 10) - C (20, 10) = C (50, 10) - C (20, 10) = 101.30-84.44 = 16.86 $. Si un expert vend des partages, le coût de la transaction sera une valeur négative indiquant que l’expert est payé.

Équation 3 est techniquement le prix marginal d’option 0 selon un ensemble d’actions en circulation (x, y). Mais un prix marginal peut être faiblement interprété comme la probabilité qu’une option pour gagner. Équation 4 est le prix marginal (probabilité) de l’option 1. Si vous examinez attentivement les deux équations, vous remarquerez qu’ils doivent égale à 1.0, est requis pour un ensemble de probabilités.

L’implémentation les équations de marché quatre clés de prédiction est simple. Le programme de démonstration met en œuvre le coût, l’équation 1, en tant que :

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);
}

La méthode de coût est presque une traduction exacte de l’équation 1. Méthode avis coût suppose que deux options sont disponibles. Pour plus de simplicité, aucune vérification des erreurs n’est effectuée.

Équation 2 est également relativement simple à implémenter :

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);
}

Le tableau nommé après contient le nouveau nombre d’actions en circulation après une transaction et la méthode puis appelle simplement la méthode d’assistance de coût à deux reprises. Une méthode pour calculer le coût d’une transaction en cours, il est facile d’écrire une méthode qui calcule le coût de l’achat d’un seul partage de chacune des deux options :

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;
}

Le coût d’un partage unique peut être utilisé par des experts pour obtenir une approximation de quel serait le coût pour acheter n actions d’une option.

Méthode probabilités renvoie les deux prix marginal (probabilités déduites) de chaque option gagnante dans un tableau :

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;
}

Si vous comparez le code de la méthode probabilités avec des équations 3 et 4, vous verrez que, là encore, le code suit directement à partir de la définition de mathématiques.

Le programme de démonstration

Pour créer le programme de démonstration, j’ai lancé Visual Studio et sélectionné le c# programme modèle d’application console. J’ai nommé le projet PredictionMarket. La démonstration n’a aucune dépendance significative de Microsoft .NET Framework, pour n’importe quelle version de Visual Studio fonctionne.

Une fois le code du modèle chargé, dans la fenêtre Explorateur de solutions j’ai renommé le fichier Program.cs pour le PredictionMarketProgram.cs plus descriptif et autorisé Visual Studio renommer automatiquement la classe Program pour moi. En haut du code source, j’ai supprimé toutes les instructions using qui référence les espaces de noms .NET, en laissant uniquement la référence à l’espace de noms système supérieur.

Le code de démonstration complet, avec quelques modifications mineures et certaines instructions WriteLine supprimées pour économiser de l’espace, est présenté dans Figure 3. Toute la logique de contrôle de programme est dans la méthode Main. Toutes les fonctionnalités de marché de prédiction sont en quatre méthodes statiques, et il existe deux méthodes d’affichage d’assistance ShowVector.

Figure 3 prédiction marché démo

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 class
} // ns

Après avoir affiché certains messages préliminaires, l’exécution du programme dans la méthode Main commence ainsi :

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

Variable liq est le paramètre de liquidité. La valeur 100,0 est typique, mais si vous testez en ajustant la valeur, vous verrez comment il affecte la modification de prix de partage après une transaction. De plus grandes valeurs liquidités produisent plus petites modifications. Le tableau nommé en attente contient le nombre total d’actions appartenant à tous les experts, sur chacun des deux équipes. Notez que le paramètre de liquidités doit être passé pour les quatre méthodes de prédiction de marché statique. Une conception alternative consiste à encapsuler les méthodes dans une classe c# et définir des liquidités sous la forme d’un champ de membre.

Ensuite, le nombre d’actions en attente est utilisé pour déterminer les probabilités de gain de chaque équipe déduites :

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

Ensuite, la démonstration affiche les coûts de l’achat d’un seul partage de chacune des deux équipes :

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

Dans un marché prédiction réaliste, cette information peut être utile à la part des experts du marché pour les aider à évaluer si le prix de l’équipe est trop élevé ou trop faible par rapport à la perception par l’expert pour gagner l’équipe.

Le programme de démonstration simule un des experts achat certaines actions, comme suit :

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"));

Dans un marché de prédiction réelle, le système devra conserver un peu d’informations sur les soldes experts et le nombre d’actions.

Ensuite, le nombre d’actions en circulation est mis à jour, comme suit :

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

Si vous revenez les équations mathématiques dans Figure 2, vous remarquerez que le nombre d’actions en circulation pour chaque équipe/option (x, y), requise par toutes les équations.

Une fois que le nombre d’actions en attente a été mis à jour, elles sont utilisées pour estimer les probabilités de chaque équipe ou de gagnante d’option révisées :

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

Rappelez-vous que ces valeurs sont vraiment marginales prix, mais il est utile de les considérer comme des probabilités. Au final, l’objectif d’un marché de prédiction est de produire la probabilité que chaque équipe ou l’option gagnez, le jeu final de probabilités après que le marché se stabilise est ce que vous recherchez.

Le programme de démonstration se termine en répétant les trois fois plus de cinq opérations suivantes :

• Afficher le coût actuel pour un partage de chaque équipe
• Effectuer un achat ou de vente des transactions
• Afficher le coût de la transaction
• Mettre à jour le nombre total d’actions en circulation
• Mise à jour de la probabilité de gagner de chaque équipe

Notez que le programme de démonstration commence par les probabilités des deux équipes égales. Ce n’est pas réaliste dans de nombreux scénarios réels prédiction mise sur le marché. Il est possible d’initialiser un marché de prédiction avec des probabilités inégales en résolution de problèmes de x et y dans les équations 3 et 4.

Synthèse

Les informations contenues dans cet article sont basés sur le livre « Logarithmique marché score règles pour modulaire COMBINATOIRE informations d’agrégation, » 2002 recherche par Robin Hanson. Vous trouverez une version PDF du papier à plusieurs emplacements sur Internet à l’aide de n’importe quel outil de recherche.

Les marchés de prédiction ne sont pas simplement une idée théorique abstraite. Dans ces dernières années, plusieurs entreprises ont été créés est mise en œuvre de marchés de prédiction de l’argent.

Une zone de recherche active est ce que sont appelées sur les marchés combinatoire de prédiction. Au lieu de choisir une des deux options de gagner, experts peuvent acheter des actions dans les événements de combinaison comme équipe un sera battre équipe B et l’équipe J sera temps prédiction k COMBINATOIRE équipe marchés sont beaucoup plus complexes que les marchés simples.

---

Récupération d'urgence. James McCaffreytravaille pour Microsoft Research à Redmond, Wash. Il a travaillé sur plusieurs produits Microsoft, notamment Internet Explorer et Bing. Dr. Vous pouvez contacter James McCaffrey àjammc@microsoft.com.

Je remercie les experts techniques Microsoft suivants qui cet article : Pallavi Choudhury, Iqbal de Gaz, Umesh Madan et Tien Suwandy