I’ve been working with an interesting system called a prediction market. The goal of a prediction market is to predict an outcome such as the winner of a basketball tournament with 64 teams. You get a group of experts and let them buy and sell shares of teams in a way that’s similar to the way the stock market works. The number of shares held can be mapped to a probability of winning.

One of the key underlying math equations of a prediction market is a Cost function. Suppose you have three options (X, Y, Z). If (x, y, z) are the number of shares held by the experts, the Cost function is:

Here b is a scaling constant and doesn’t affect the main idea of this post. A straightforward calculation of the Cost function could blow up if x or y or z is very large because if some value v is large then exp(v) can be astronomically large and cause arithmetic overflow.

If you toss out the irrelevant b constant (irrelevant in terms of the overflow problem), the simplified Cost function with three input values is:

In order to have a prediction market that scales to thousands of users, I needed a way to safely calculate ln(exp(a) + exp(b) + exp(c)). It took me a couple of hours of fiddling with the equation using properties of the exp() and ln() functions to come up with a solution. It’s best illustrated by an example.

Suppose a = 5, b = 8, and c = 2. The Cost function (without the liquidity constant) is:

C = ln(exp(5) + exp(8) + exp(2)) = ln(148.41 + 2980.96 + 7.39) = ln(3136.76) = 8.05

The trick, which I’ll call softsum max trick because it resembles a similar idea when calculating something called the softmax function, is:

C = ln(exp(5-8) + exp(8-8) + exp(2-8)) + 8 = ln(exp(-3) + exp(0) + exp(-6)) + 8 = ln(0.05 + 1.00 + 0.01) + 8 = ln(1.06) + 8 = 0.05 + 8 = 8.05

In words, instead of using each raw input value, you use each value minus the max input value, which keeps the exp() of each small.

Here’s a C# demo:

using System; namespace SoftsumTrick { class Program { static void Main(string[] args) { Console.WriteLine("\nBegin softsum demo \n"); Console.WriteLine("Goal is to safely compute "); Console.WriteLine(" ln(exp(a) + exp(b) + . . )"); int[] vals = new int[] { 5, 8, 2 }; Console.Write("\nInputs values = "); for (int i = 0; i < vals.Length; ++i) Console.Write(vals[i] + " "); Console.WriteLine("\n"); Console.WriteLine("ln(sum(exp(x)) directly = "); double v1 = Crude(vals); Console.WriteLine(v1); Console.WriteLine("\nln(sum(exp(x)) safely = "); double v2 = Softsum(vals); Console.WriteLine(v2); Console.WriteLine("\nEnd softsum demo \n"); Console.ReadLine(); } // Main static double Crude(int[] vals) { // direct calculation (could overflow) double sum = 0.0; for (int i = 0; i < vals.Length; ++i) sum += Math.Exp(vals[i]); return Math.Log(sum); } static double Softsum(int[] vals) { // safe calculation int max = vals[0]; for (int i = 1; i < vals.Length; ++i) if (vals[i] > max) max = vals[i]; double sum = 0.0; for (int i = 0; i < vals.Length; ++i) sum += Math.Exp(vals[i] - max); return Math.Log(sum) + max; } } // Program } // ns

The softsum trick can then be applied to the actual Cost function, which I’ll describe in a future post.