Kelly betting in LMSR

In general the "scoring problem" can be formulated as follows.

There are miners m ∈ M , questions q ∈ 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 ∈ T_m, q some list of time points of its choice < t_q), where each p_m, q, t is a vector of dimension N_q (the number of exclusive outcomes for q). At t_q or later, v_q (a one-hot vector representing the resolved outcome of q) is revealed.

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}$.

Given such predictions, we want to compute:

A sequence p̄_q, t, still an N_q vector, that "aggregates" the predictions of all miners p_m, q, s for s ≤ t.
A sequence w_m, t that maintains scores or "cash wealths" for each miner.

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 p̄_q, t from ∑_mx_m, q, t — this corresponds to a particular scoring rule. For example, the following supply curve for each outcome stock i ∈ 1, …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_qlog (p⋅v_q).

To see why they're equivalent, see Logarithmic market scoring
To understand the parameter b_q, see LMSR subsidy parameter is the price of information

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 p̄_q, 0 = (1/N_q,…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 p̄_q, t, we determine the Kelly-optimal price vector 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.: p̄_q ← p̃.

We can calculate a new vector of outstanding stocks (x′₁,…x′_{N_q}) that is compatible with the new price vector p̃ — for the LMSR case, this is a rank N − 1 linear system in e^x′₁/b, …e^x′_N/b, equivalent to e^x′₁/b/p₁ = e^x′₂/b/p₂ = …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) = bln ∑exp (x_i/b)

In general it is related to the supply curve by a simple line integral:

C(x′) − C(x) = ∫_x^x′p(x) ⋅ 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 p̄ = (p̄₁,…p̄_N) and your subjective belief is p — then what price 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:

We're dealing with a market-scoring rule, which means p^* continuously changes in response to our bets. The naive Kelly formula should appear in the limit of b → ∞ (where our bets are a drop in the ocean), or we could apply it for infinitesimal bets and do an integral.
The naive formula is generally only given for binary questions — for multiple outcomes, life is a bit more complicated.

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 p̃ from first principles, as the p̃ that maximizes the expected logarithm of wealth, i.e.

arg max_p̃∑_ip_ilog (w+s(p̃,i)−s(p̄,i)) For example for LMSR:

arg max_p̃∑_ip_ilog (w+blog(p̃_i)−blog(p̄_i))

One worry I have is that simply optimizing against p̃ will cause numerical issues in highly liquid markets (i.e. high values of b) in which p̃ barely budges from p̄. That's fine, we can just reparameterize this expression in terms of the stocks purchased and optimize that instead.

Example implementation

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).

# !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)