Table of Contents
In general the “scoring problem” can be formulated as follows.
There are miners \(m\in M\) , questions \(q\in Q\) with respective resolution times \(t_q\). For any \((m,q)\), the miner \(m\) submits a time series \(p_{m,q,t}\) of forecasts (ranging over \(t\in T_{m,q}\) some list of time points of its choice \(
E.g. \((p_{m,q,t})_t\) may look like
\[t=0:\begin{bmatrix}0.7\\0.3\end{bmatrix},t=3.6:\begin{bmatrix}0.5\\0.5\end{bmatrix}, t=10:\begin{bmatrix}0.99\\0.01\end{bmatrix}\]
(so \(N_q=2\)) And after \(t_q=15\), it may be revealed that \(v_q=\begin{bmatrix}1\\0\end{bmatrix}\).
<!—A market scoring rule \(s\) is a map that takes the entire matrix of time series \((p_{m,q,t})\) and the vector of resolutions \((v_q)\) , and spits out a score vector in \(\mathbb{R}^M\). In general we will have some basic properties like “finite budget” \(\sum_m s_m(p_{m,q,t}, v_q)
Given such predictions, we want to compute:
We will additionally maintain sequences \(x_{m,q,t}\) that tracks the “stock” of miner \(m\) in question \(q\) at time \(t\). Each \(x_{m,q,t}\) will be an \(N_q\) vector (e.g. for a binary question, we will track YES and NO stocks).
Our wealth-based scoring mechanism can then be described as follows.
First for each \(q\) its validator needs to decide and publish (or it can be done in a default way for all questions) its supply curve for stocks, i.e. the rule it will use to compute \(\bar{p}_{q,t}\) from \(\sum_m{x_{m,q,t}}\) — this corresponds to a particular scoring rule. For example, the following supply curve for each outcome stock \(i\in{1,\dots N_q}\):
\[
\bar{p}_{q,t}^i=\frac{\exp{\sum_mx^i_{m,q,t}/b_q}}{\sum_i{\left[\exp{\sum_mx^i_{m,q,t}/b_q}\right]}}
\] (an easier way to see what’s going on: \(\bar{p}_{YES} = \frac{\exp{(x_{YES}/b)}}{\exp{(x_{YES}/b)}+\exp{(x_{NO}/b)}}\)) parameterized by \(b_q\), the “subsidy parameter for question \(q\)” , is equivalent to a simple logarithmic market scoring rule \(s(p)=b_q\log(p\cdot v_q)\).
We could start with this as the scoring rule and then think about how to explicitly introduce decreasing subsidy with time (this is not strictly necessary, as market scoring already solves for the problem of rewarding agents only for the new information they add — but it is definitely possible, since market scoring can just be implemented as having the market-maker participate as an agent in an unsubsidized continuous double auction, see e.g. obsidian/_private/infinite_games/2011)).
For each miner we initialize some cash wealths \(w_{m,0}\) (e.g. to their initial TAO holdings), and stocks \(x_{m,q,0}=0\). We initialize the probabilities of each question as uniform \(\bar{p}_{q,0}=(1/N_q,\dots 1/N_q)\).
Then, ordering all the \(p_{m,q,t}\) (over all miners \(m\) and all questions \(q\) — yes, even questions, this is a form of “transfer learning”) by \(t\), we perform for each \(t\), for each \(m\), for each \(q\):
1) get \(p_{m,q,t}\) e.g. \((0.2, 0.6, 0.2)\).
2) comparing \(p_{m,q,t}\) to \(\bar{p}_{q,t}\), we determine the Kelly-optimal price vector \(\tilde{p}\) that the miner should bring the prices to — see “Kelly betting in LMSR” below for how to do this.
3) We update the market price of \(q\), and the wealth and stocks of \(m\), as follows:
The new market price of \(q\) is simply the Kelly compromise price.: \(\bar{p}_{q}\gets \tilde{p}\).
We can calculate a new vector of outstanding stocks \((x'_1,\dots x'_{N_q})\) that is compatible with the new price vector \(\tilde{p}\) — for the LMSR case, this is a rank \(N-1\) linear system in \(e^{x'_1/b},\dots e^{x'_N/b}\), equivalent to \(e^{x'_1/b}/p_1=e^{x'_2/b}/p_2=\dots e^{x'_N/b}/p_N\). The overdetermination is equivalent to adding a constant amount to each \(x'_i\) (scaling each \(e^{x'_i/b}\) by the same factor), i.e. differences in cash reserves.
We calculate this \(x'-x\) and add it to \(x_{m,q}\). Any multiples of \(\vec{1}\) can immediately be exchanged for cash (this is a generalized form of “selling stock” — to sell YES, just buy NO then exchange YES+NO for cash).
Finally, we calculate \(C(x')-C(x)\) where \(C\) is the “costing function” i.e. the integral of the supply curve — and deduct it from \(w_m\). For the LMSR case this is:
\[C(x)=b\ln\sum\exp{(x_i/b)}\]
In general it is related to the supply curve by a simple line integral:
\[C(x')-C(x)=\int_x^{x'} p(x)\cdot dx\]
4) Repeat for all \(m\) and all \(q\).
5) When any question \(q\) is resolved, increment \(w_{m,q}+=x_{m,q,t}\) for all miners and set the latter to 0.
The key question is then: if the market price for some question \(q\) is \(\bar{p}=(\bar{p}_1,\dots \bar{p}_N)\) and your subjective belief is \(p\) — then what price \(\tilde{p}\) should you bring the market price to?
If you wanted to maximize your expected score, you would simply bring it to \(p\) — this is what a proper scoring rule entails, after all. But this is not great — if every miner just brought the market price to their subjective probability, it would simply oscillate between each miner’s subjective price, rather than finding any “aggregate” or “consensus” estimate. We would be dealing with a setting where every miner can go into indefinite amounts of debt, so their wealth has no meaning. Whereas we would like a “wealth-weighted” average of their forecasts.
The way to achieve this is via Kelly betting, as proven in obsidian/_private/infinite_games/2012). The naive formula for calculating Kelly fractions (the fraction of your wealth you should bet) doesn’t work for our purposes, because:
Fortunately there is a rather easy way to derive the Kelly compromise price for market scoring rules — instead of starting with calculating the “wealth fraction”, we can just compute \(\tilde{p}\) from first principles, as the \(\tilde{p}\) that maximizes the expected logarithm of wealth, i.e.
\[\arg\max_{\tilde{p}}\sum_i{p_i \log\left(w + s(\tilde{p},i)-s(\bar{p},i)\right)}\] For example for LMSR:
\[\arg\max_{\tilde{p}}\sum_i{p_i \log\left(w + b\log(\tilde{p}_i)-b\log(\bar{p}_i)\right)}\]
One worry I have is that simply optimizing against \(\tilde{p}\) will cause numerical issues in highly liquid markets (i.e. high values of \(b\)) in which \(\tilde{p}\) barely budges from \(\bar{p}\). That’s fine, we can just reparameterize this expression in terms of the stocks purchased and optimize that instead.
A basic implementation to make the above precise. The main point is to show that “selling stock” is possible (you will see “net SALE” printed here and there).
1. Kelly betting in LMSR
2. Example implementation
# !pip install numpy matplotlib scipy
from os import makedirs
from math import log, exp
from random import random, randint
from numpy import array
from numpy.typing import NDArray
import matplotlib.pyplot as plt
from scipy.optimize import minimize
from scipy.stats import beta
class Miner:
def __init__(self, id: str, cash: float = 1.0):
self.id = id
self._cash = cash
self._stocks: dict["Question", NDArray] = {}
self.cash_history: NDArray = [cash]
@property
def cash(self):
return self._cash
@cash.setter
def cash(self, value):
print(f"Updating Miner {self.id} cash from {self._cash} to {value}")
self._cash = value
self.cash_history.append(value)
@property
def stocks(self):
return self._stocks
@stocks.setter
def stocks(self, value):
self._stocks = value
def set_stock(self, question: "Question", stock: NDArray):
print(
f"Updating Miner {self.id} stock for Question {question.id}"
f" from {self._stocks.get(question, 0)} to {stock}"
)
self._stocks[question] = stock
def prediction(self, question: "Question", time: int) -> NDArray | None: ...
def plot_cash(self):
fig = plt.figure()
fig.suptitle(f"Miner {self.id} Cash over time")
plt.plot(self.cash_history)
return fig
class Question:
def __init__(
self,
id: str,
text: str,
n: int,
resolution_time: int,
scoring: "Scoring",
resolution: int,
):
self.id = id
self.text = text
self.n = n
self.resolution_time = resolution_time
self.scoring = scoring
self.resolution: int = resolution
self._price: NDArray = array([1 / n] * n)
self.price_history: list[NDArray] = [self._price]
@property
def price(self):
return self._price
@price.setter
def price(self, value):
print(f"Updating Question {self.id} price from {self._price} to {value}")
self._price = value
self.price_history.append(value)
def __hash__(self):
return hash(self.id)
def plot_price(self):
fig = plt.figure()
fig.suptitle(f"Question {self.id} Price over time")
plt.plot(self.price_history)
return fig
class Scoring:
"""Abstract class for scoring functions."""
def score(self, probs: NDArray, resolution: int) -> float:
"""equivalent to specifying the cost/price function, as per Hanson 2002"""
...
def cost_function(self, outstanding_stocks: NDArray) -> float:
"""the line integral of the price_function"""
...
def price_function(self, outstanding_stocks: NDArray) -> NDArray:
"""the gradient of the cost_function"""
...
def invert_price(self, probs: NDArray) -> NDArray:
"""an inverse of the price_function -- get some outstanding_stocks that
lead to the given probs"""
...
class LMSR(Scoring):
def __init__(self, b: float):
self.b = b
def score(self, probs: NDArray, resolution: int) -> float:
return self.b * log(probs[resolution])
def cost_function(self, outstanding_stocks: NDArray) -> float:
v = array([exp(x / self.b) for x in outstanding_stocks])
return self.b * log(sum(v))
def price_function(self, outstanding_stocks: NDArray) -> NDArray:
v = array([exp(x / self.b) for x in outstanding_stocks])
return v / sum(v)
def invert_price(self, probs: NDArray) -> NDArray:
"""*A* possible inverse of the price_function, i.e. an outstanding_stocks
that lead to the given probs"""
return array([self.b * log(p) for p in probs])
def market(questions: list[Question], miners: list[Miner]):
time_range = max([q.resolution_time for q in questions])
# all_market_probs: dict[Question, list[float]] = {
# q: [1 / q.n] * q.n for q in questions
# }
all_outstanding_stocks: dict[Question, NDArray] = {
q: array([0] * q.n) for q in questions
}
for t in range(time_range + 1):
for q in questions:
for m in miners:
if t >= q.resolution_time:
m.cash += m.stocks.get(q, array([0] * q.n))[q.resolution]
m.set_stock(q, array([0] * q.n))
continue
subjective_probs: NDArray | None = m.prediction(q, t)
if subjective_probs is None:
continue
kelly_probs: NDArray = get_kelly_probs(
market_probs=q.price, # all_market_probs[q],
subjective_probs=subjective_probs,
scoring=q.scoring,
wealth=m.cash,
)
print(
f"## Question {q.id}\n"
f"Outstanding stocks: {all_outstanding_stocks[q]}\n"
f"Miner {m.id} stocks in {q.id}: {m.stocks.get(q, array([0] * q.n))}\n"
f"Miner {m.id} cash: {m.cash}\n"
f"Market price: {q.price}\n"
f"Miner {m.id} belief: {subjective_probs}\n"
f"Kelly probs: {kelly_probs}\n"
)
q.price = kelly_probs # update market probs # all_market_probs[q] = kelly_probs
# get a possible outstanding stocks for q that lead to its new price
compatible_new_outstanding_stocks: NDArray = q.scoring.invert_price(
kelly_probs
)
# the miner would get this difference
compatible_delta_miner_stocks: NDArray = (
compatible_new_outstanding_stocks - all_outstanding_stocks[q]
)
compatible_new_miner_stocks: NDArray = (
m.stocks.get(q, array([0] * q.n)) + compatible_delta_miner_stocks
)
# we want to keep things so that the lowest stock the miner owns on any outcome is 0
# (if it's positive this means the miner holds YES+NO that can instantly be traded for cash)
# (if it's negative well I don't believe in loans)
# so we take min(compatible_new_miner_stocks) and:
# - subtract it from all elements of compatible_new_miner_stocks
# - subtract it from all elements of compatible_new_outstanding_stocks
cash_equivalent = min(compatible_new_miner_stocks)
new_miner_stocks = compatible_new_miner_stocks - cash_equivalent
new_outstanding_stocks = (
compatible_new_outstanding_stocks - cash_equivalent
)
# cost miner for stocks purchased (or reward for sale)
cost = q.scoring.cost_function(
new_outstanding_stocks
) - q.scoring.cost_function(all_outstanding_stocks[q])
print(
f"Miner {m.id} updates stocks in {q.id}"
f" from {m.stocks.get(q, array([0] * q.n))} to {new_miner_stocks} stocks"
f" for a cost of {cost}.\n"
f"It is a net {"SALE" if cost < 0 else "BUY"}.\n"
)
m.cash -= cost
m.set_stock(q, new_miner_stocks)
all_outstanding_stocks[q] = new_outstanding_stocks
# plot 5 miners and 5 questions
makedirs("figs", exist_ok=True)
for m in miners[:6]:
m.plot_cash().savefig(f"figs/miner_{m.id}.png")
for q in questions[:6]:
q.plot_price().savefig(f"figs/question_{q.id}.png")
def expected_log_return(
compromise_probs: NDArray,
market_probs: NDArray,
subjective_probs: NDArray,
scoring: Scoring,
wealth: float,
) -> float:
"""Expected log return of bringing market_probs to compromise_probs given subjective_probs"""
n = len(market_probs)
return sum(
[
subjective_probs[i]
* log(
wealth
+ scoring.score(compromise_probs, i)
- scoring.score(market_probs, i)
)
for i in range(n)
]
)
def get_kelly_probs(
market_probs: NDArray,
subjective_probs: NDArray,
scoring: Scoring,
wealth: float,
) -> NDArray:
"""Get Kelly criterion probabilities given subjective probabilities
Example:
x = get_kelly_probs([0.5, 0.5], [0.6, 0.4], LMSR(1000.0), 1.0)
print(x)
"""
def f(x):
try:
return -expected_log_return(
compromise_probs=x,
market_probs=market_probs,
subjective_probs=subjective_probs,
scoring=scoring,
wealth=wealth,
)
except ValueError:
return float("inf") # Return infinity for invalid solutions
constraints = [
{"type": "eq", "fun": lambda x: sum(x) - 1}, # Probabilities sum to 1
{"type": "ineq", "fun": lambda x: x}, # Probabilities are non-negative
]
return minimize(
f,
market_probs,
bounds=[(0, 1)] * len(market_probs),
constraints=constraints,
# method='SLSQP',
).x
##### Example implementation #####
class BetaMiner(Miner):
def __init__(
self, id: str, cash: float = 1.0, alpha: float = 2.0, beta: float = 2.0
):
super().__init__(id=id, cash=cash)
self.alpha = alpha
self.beta = beta
def prediction(self, question: Question, time: int) -> NDArray | None:
return list(beta.rvs(self.alpha, self.beta, size=question.n))
def ConstantMiner(Miner):
def __init__(self, cash: float = 1.0, probs: NDArray = None):
super().__init__(cash)
if probs is None:
probs = array([0.5, 0.5])
self.probs = probs
miners = [
BetaMiner(id=1, alpha=1.0, beta=1.0),
BetaMiner(id=2, alpha=1.0, beta=1.0),
BetaMiner(id=3, alpha=2.0, beta=2.0),
BetaMiner(id=4, alpha=2.0, beta=2.0),
BetaMiner(id=5, alpha=2.0, beta=5.0),
BetaMiner(id=6, alpha=5.0, beta=2.0),
BetaMiner(id=7, alpha=5.0, beta=5.0),
]
questions = [
Question(
id=i,
text=f"Question {i}",
n=2,
resolution_time=randint(1, 25),
scoring=LMSR(1 + 1 * random()),
resolution=randint(0, 1),
)
for i in range(100)
]
if __name__ == "__main__":
market(questions, miners)