This post is part of my broader aim to try and formulate everything AI in terms of markets so that alignment becomes an antitrust problem. Comments appreciated. 


introduction: betting on what is neither verifiable nor falsifiable (non-VF)

Prediction markets are good at eliciting probabilities about events that will occur at a fixed, finite time. However, there are many questions we would like to bet on that cannot be resolved in finite time. For example:

  • () an asteroid impact will eventually occur; I am mortal; P halts
  • () an asteroid impact will never occur; I am immortal; P doesn't halt
  • () there will exist an immortal man; some P_n doesn't halt; this infinite checkerboard has a completely black horizontal row
  • () all men will be mortal; every P_n halts; there are infinitely many primes
  • () sentences about limits e.g. x_n diverges to +infinity

As a sigma-algebra, the  sentence  should be seen as the countable union  and so its probability should be the supremum of all the finite unions. Similarly, a  sentence should be seen as a countable intersection and its probability as an infimum. This is fine in probability theory, but I mean, "supremum" and "infimum" are not computable functions, you would need to elicit an infinite number of bets. 

Indeed, the desire to consider infinite events is basically the motivation for using sigma-algebras rather than set algebras in probability theories. Set algebras correspond to propositional logic; sigma-algebras to predicate logic (to be sure, to second-order logic rather than first, because you can take any countable unions and intersections, not necessarily even enumerable in a computable way, which would correspond to some hyperarithmetic theory).

Actually  (verifiable) and  (falsifiable) sentences are still OK: for verifiable sentences, just pay the trader if/when the sentence is verified; for falsifiable sentences, the trader is paid $1 upfront and returns it if the sentence is falsified. These are what we call "long" and "short" positions respectively.

So philosophers will tell you there is nothing beyond  and , but surely they must be wrong? Because we might actually care about sentences like "there are infinitely many primes" and "all men are mortal". We may care about them, means our utility functions may depend on them. We just need to construct a situation in which a utility function depends exactly on such a sentence and nothing else, i.e. devise a scoring rule to elicit probabilities on such sentences.

alternate introduction: theory-independent pricing of logical sentences

On the face of it, Garrabrant induction seems like the completely natural formalism for logical uncertainty, with no special tricks — of course markets are the correct way to handle algorithmic uncertainty (they're the natural way to "aggregate algorithmic information", because they aggregate all of the traders' information, including algorithmic information), of course you'd want an inexploitability/Dutch-book criterion.

But actually Garrabrant induction isn't just "markets" — it has several additional constructions:

  • You can't actually just have a prediction market for all logical sentences, because it's not like the ground truth for all mathematical claims is definitively revealed at some point. I'm not even talking about unprovable sentences — even the sentence "there are an infinite number of primes" is neither verifiable nor falsifiable! Peano Arithmetic believes it, and what Garrabrant induction does is to just pay off the sentence when PA proves it.
  • But Garrabrant induction isn't a prediction market for "" either — it actually does attempt to assign a price to undecidable sentences. This is because of the whole "propositionally consistent worlds" trick, specifically: the market maker is always willing to exchange  for , even when  is independent of .
  • Less important to this article but worth a mention: it only dominates continuous traders; it also has a weird way of computing equilibrium when something like LMSR would be nicer.

In general, I think it is unsatisfactory for a market to rely completely on a formal theory as a source of truth — it makes it hard to generalize beyond the realm of pure math, you can't design good agents with it, and I think the full theory of logical uncertainty should simultaneously address the question of Why even trust logic in the first place?, and the answer should look like "because logic makes a lot of money on the market".

the problem is not trivial

An obvious, immediate solution might look something like an inductive construction, where for  a  sentence, you can give a trader the asset  on day , taking it back the next day, ad infinitum, so the asset value approaches the  asset  over infinite time. 

But that doesn't actually work. We can illustrate this with this simple pictorial description of arithmetical sentences — e.g. a  sentence can be formulated as: Consider an infinite grid of white and black squares. Does it have a row comprised entirely of black squares?

Then the described scoring mechanism is equivalent to looking at a finite chunk of the board each day, and give him $1 if it has a fully black row; the next day, you expand the chunk, take back any rewards from the previous day and repeat the exercise. Essentially, we are approximating  with the sequence . This has an intuitive appeal, because it mirrors what we do with  and  sentences: you give out $1 free to  sentences holders, then they must pay it back when falsified. 

Picture-proof to see this doesn't work:

In fact at least for  in the Arithmetic Hierarchy, we have an impossibility theorem for any such scoring mechanism:

Theorem 1 (the problem is hard). Let  be an -ary primitive relation (denote its  and  quantifications as  and  respectively), let  be some fixed  "enumerator" of  (i.e. ), and allow vectorizing  on , i.e. . A "mechanism" for  (respectively ) can be either:

  • [asset] a computable sequence of computable functions  such that  (respectively ).
  • [score] a computable sequence of computable functions  such that  (respectively ).

Then for , there is no computable procedure that, given some -ary , gives a mechanism for  (respectively ).

Proof. Suppose such a computable procedure existed, denote it by . Then for all -ary primitive relations , the sentence  would be equivalent to either  or , depending on the type of mechanism. However, both of these sentences are , and for every  sentence were equivalent to a  one would contradict Tarski's theorem.

options and game semantics

But here's what you could do: at each step in time, let the asset-holder choose the height of the finite window, then the asset-issuer choose the width of the finite window (do you see why the order is important?). Then you ask if there is a winning strategy for the asset-holder, i.e. to make the asset value sequence "converge" to $1, $1, $1 ... and if there's a winning strategy for the asset-issuer, i.e. to make the asset value sequence "converge" to $0, $0, $0 ... (I put "converge" in quotes because that's probably not actually what we care about) This approach is closely analogous to game semantics.

More generally:

Every asset has a "holder" and an "issuer".

 asset  entails a counter , chosen by the holder at every point in time, and an underlying  asset  with the same holder and issuer.

 asset  entails a counter , chosen by the issuer at every point in time, and an underlying  asset  with the same holder and issuer.

If the underlying asset is ever sold off or given away, it must be re-bought before the next time it is updated.

In other words: the asset-holder and issuer repeatedly play the verification-falsification game against each other; if the asset-holder can "consistently" win, the asset is worth $1, if the asset-issuer can "consistently" win, the asset is worth $0. In fact, I think this simpler formulation is enough:

 asset  entails a counter , chosen by the holder at every point in time, and an underlying  asset  with the same holder and issuer (if no counter is chosen, the underlying asset is ).

 asset  entails a counter , chosen by the issuer at every point in time, and an underlying  asset  with the same holder and issuer (if no counter is chosen, the underlying asset is ).

If the underlying asset is ever sold off or given away, it must be re-bought before the next time it is updated.

There are several obvious problems with this (either) formulation, which really boil down to two things:

  • Cost of construction — You want to bet on the existence of a winning strategy, but you're really betting on whether you (or really anyone ever in the market) will find a winning strategy. In particular, this means the "cost of finding a winning strategy" sounds like something that may matter to the price of the asset, and also that the task of holding and issuing assets is itself strategic, so it is perhaps not straightforward to design an inventory-based market-maker (e.g. LMSR).
  • Solvency/strategic bankruptcy — Traders no longer have limited liability, they don't really own the cash they claim to have (they might have to pay it back at any point if they lose the game again). Given an agent whose asset's underlying value goes as $1, $0, $1, $1, $0, $1, ... how do you even determine what the "true" value of this asset is? In markets, the thing that really enforces the assumed incentive (i.e. that agents actually care about money) is the budgeting mechanism, aka capitalism[2], which lets agents that have proved themselves to be good at profit-maximizing gain more influence, as measured by a variable called "wealth". This "capitalism" thing is really what allows us to bring markets over to settings where traders are not assumed to be perfect profit-maximizing agents, but simply some programs. Now when traders had limited liability like in the traditional prediction markets (i.e. they actually hold the asset they do, and will never be asked to return it), checking if they are in-budget was easy: just check the value of their current cash reserves. Besides, you could still have just focused on profit-maximizing agents and still studied interesting things: not so anymore, when there is no way to define even how much an agent values a particular value sequence without resorting to "what kind of agent does capitalism select for?".


The latter problem can be cast aside for the time-being by making the games one-shot, i.e. having the agents pick their set of choices at one go rather than letting them add to it indefinitely (explicit construction [3])

The first problem, I believe, implies a somewhat radical rethinking of the probabilities we give sentences. Much like logical uncertainty requires us to accept giving a probability that isn't 0 or 1 to  — by relativizing knowledge to a class of programs — constructivism demands that we accept the probability of non-VF sentences to be read as:

the probability that WE WILL CONSTRUCT an  such that for all  WE WILL CONSTRUCT

Constructivism, as I would put it, is the position that the only information that counts towards a non-VF sentence is one that helps you win a VF game for it. If it is very difficult for you to construct an  to play, that should count against the probability of the sentence. This is not as damning as one might think, though, because you do have the whole market's abilities at your disposal.

I will now present some results to persuade you that this approach is fine. It might be easier, for this purpose, to focus on statistical rather than algorithmic uncertainty. To be concrete, what I'm talking about is some sequence of random variables indexed as ; then  is a  sentence;  is , etc. Note that if the s were independent, then the probability of any  or  or higher sentence would have to be 0 or 1 by Kolmogorov's 0-1 law; so you have to introduce dependencies between them. E.g. 

Generate each  unconditionally and  conditionally on  (the number of 1s so far for the same ). One can show that the probability of  is .

(for those who want to play with such propositions, here's a Colab notebook with a class RandomProp.)

The limitation of sticking to statistical uncertainty is that you no longer have a notion of non-constructive evidence. Well, actually you do have the weak kind of non-constructive evidence: 

an event  that gives no information on  or  but gives information on 

e.g. I have two children;  is "my eldest is a boy";  is "my youngest is a boy";  is "I have a boy and a girl". 

But this is not really non-constructive for us, because we are allowed to submit bets on any finite set of options (so, for e.g. the  proof is OK). What we do not have with statistical uncertainty is the strong kind of non-constructive evidence:

an event  that is independent of every finite union  but gives information on the countable union :

This is impossible, as you can prove by applying continuity from below to the sequence .

So we will need some cleverer way to formalize the idea that our scheme incentivizes "constructive evidence" only. But at least we can prove some results in the logical case. In the long run, all possible constructors will be born. So in the long run, the probabilities must approach the ones predicted by probability theory. For example, in the "infinite black row" example, once  is added to the market, where  buys  indefinitely and  is a constructor such that , the price of  will approach $1 and the price of  ("there is an infinite black row") will approach $0.

(In fact, you don't even need to wait for that constructor to get the right probability: agents can also learn to wait for constructors to be born to; think e.g. the market for bonsai trees.)

Notation. Let  be a sentence and  be a constructor, i.e. a map . Write  for  and  for the replacement of the leading bounded variable in  by the outputs of , i.e.  if  is  and  if  is . Note that  is always lower on the (hyper-)arithmetical hierarchy than . Thus for two constructors , the alternating sequence  must eventually terminate at an atomic proposition. Denote this atomic proposition by . E.g. for First-Order-Logic sentences (specifically the example of  for even ):

For sentences beyond FOL, the expression is much the same except that  cannot be determined easily (but the fact that the sequence terminates is equivalent to the well-foundedness of its ordinal rank).

We are ready to formulate our main theorem: that equilibrium prices for constructively true sentences (i.e. sentences for which there is a computable winning strategy to the Verification-Falsification game) approach $1. The sketch of the proof is as follows: 

  • [a complete class theorem] if a sequence of prices (paired with a constructor) is exploitable (you can generate infinite profits by trading on it, which means it never "learns" to beat your strategy) by some (trader, constructor) pair, it is exploitable by "the market" (i.e. by the firm that hires each enumerated (trader, constructor) pair with smaller and smaller portions of the budget)
  • [market cannot exploit its own equilibrium prices] let the sequence of prices simply be the market equilibrium prices; then there are constructors you can pair them with so that "the market" cannot exploit them. 
  • [nobody can exploit market equilibrium prices] therefore for market equilibrium prices, there are constructors you can pair them with to make them inexploitable.
  • [this implies everything] if market prices of constructively true sentences did not tend towards $1, there would be a strategy to exploit them. Thus they do. 

Definition 1 (Being very precise about the market construction). Define:

  • A price setter is composed of:
    • a price sequence 
    • a constructor 
    • a labeller  (where  is the symbol for a piecewise-constant function over a finite number of pieces, i.e. a labelled finite-interval partition) such that  has length  (defined via mutual recursion as follows)
  • An agent  is composed of:
    • an endowment  and a birthday 
    • a trader  such that  is decreasing in price
    • a constructor 
    • a labeller  such that  has length  (defined via mutual recursion as follows).
    • an inventory  defined by initial conditions  for  and for all other propositions ;  and recursion where:
      • orders placed:  where  indicates that for all  (you're not selling what you don't have) AND  (you can afford all your purchases)
      • cost of orders placed: 
      • the moves played (if  is ):  and .
      • the opponent's moves (if  is ):  and 
      • the payout from empirical truth (if  is ): if  supports , then  and 
  • The empirical reality is a process  such that , and .
  • A father of agents is an injective  with a finite total endowment i.e.  and correct birthdays i.e. . It is associated with an aggregate agent as follows:
    •   where  indicates that for all  and .
    •  where  is the smallest  such that  if such a  exists, otherwise .
  • An agent  is said to exploit a price-setter  if  is bounded below but not above.
  • A special price sequence  called equilibrium, computed as follows. For each  is the solution  to 


Theorem 2a [market dominance/CCT]. Suppose some agent  exploits a price setter . Then so does any aggregate agent  that fathers . (Proof: immediate.)

Lemma 2b [market cannot exploit its own equilibrium]. There exists constructors and labellers  such that  cannot exploit .

Proof. At equilibrium price,  buys equal amounts of  and , however it may use different constructors for different portions of each. So we will have  use 's constructors for  against 's constructors for  and vice versa so that it wins exactly the same number of games as it loses.

We construct as follows: 

The result is immediate.

Corollary 2c [thus no one can]. Thus no one can exploit . (Proof: immediate.)

Theorem 2d [thus our result, pt 1].  exists for all ; denote this as .

Proof. Suppose it didn't; then there is some  and  such that  infinitely often and  infinitely often. Then consider the agent given by a trader that sells at  and buys at , and a trivial constructor (doesn't play the game at all, returns  every turn). This agent exploits the market.  

Theorem 2e [thus our result, pt 2]. If  is a constructively true sentence, i.e. such that  (where quantifications are over constructors enumerated by the father), then .

Proof. Suppose it wasn't; then there is some  such that  is below  infinitely many times. Then consider the agent given by trader that buys at  and the constructor  from the hypothesis. This agent exploits the market. 

Corollary 2f. If  is a constructively false sentence, i.e. such that , then .

Proof. Just apply 2e to .

This is not nearly as strong a result as I would like. I don't know what happens with sentences that are neither constructively true nor constructively false (perhaps it depends on the exact enumeration order ... ?), I don't have any nice results relating to the behaviour of prices "in approach" (stuff like  having price  for a long time).

Perhaps something like this captures part of what I want:

Definition 2 (Constructible sigma algebras). Define , i.e. the set of binary sequences, to be our "sample space". We define our "constructible algebra"  on this space as the smallest set such that:

  • every subset  and  is in .
  • The finite unions and intersections of  are in ; these are called its "propositional sets"
  •  is closed under unions and intersections over the its computably enumerable subsets, i.e. for  computable,  and  are in .

(Does this differ from "monadic algebras", "quantifier algebras" and "polyadic algebras"?)

How would we actually define probability assignments on this? I would think something like , but that's not right. Seems like it should be something bounded between .

Perhaps it relates to Japaridze's "Computability Logic". Or to Vladimir Vovk's reformulation of probability theory.

betting on the latent space

So the real reason this matters, and what I'm more interested in working on hereon:

If a tree falls in the forest, and no one's there to bet on it, does it make a sound?

There is a whole class of sentences which apparently have no grounding in empirical verification or falsification. Unlike our examples, they can't even be expressed as arithmetical sentences in verifiable or falsifiable things. Yet we see them as meaningful; they are part of our world-model. 

How could you possibly bet on something like "Is Bob responsible for the murder?" It's not good enough to resolve according to the outcome of an investigation, it certainly feels as though this sentence has some meaning outside of the outcome of an investigation, that there is some noumenal reality

Perhaps it is instructive to ask: why do we care about "Is Bob responsible for the murder?" Because it correlates with other questions, that are rooted in empirical reality, like "Will the murder rate be lower if we jail Bob?". This is why we care about, say, history, or heck, much of real science too.

More importantly, such statements about this mentally-constructed world model — about the past, about the faraway and invisible, about the imagined — are pieces of information that we regard as likely to be useful for multiple downstream tasks. They are good abstractions, good compressed representations capturing correlations between things.

Related: Latent variables for prediction markets: motivation, technical guide, and design considerations by tailcalled

The noumenal reality is a mentally-constructed world model. It exists in the latent space of an intelligent agent. Intelligence is about creating good abstractions in this sense. So if we develop a model of markets that automatically compute likely useful abstractions, i.e. a framework of prediction markets for subjective questions, that will dual as an alternate framework for designing AI agents.

  1. ^

    If you are unfamiliar with logic you should read my previous post Meaningful things are those the universe possesses a semantics for

    If you're unfamiliar with markets and scoring rules read Robin Hanson's Logarithmic Market Scoring.  

    If you're unfamiliar with logical uncertainty and specifically Garrabrant induction read Scott Garrabrant's Logical Induction.

    If you are unfamiliar with ordinals, it's OK, so am I.

    (But you can read my blog post so you're at least not any more unfamiliar with them than I am.)

  2. ^

    Markets are intelligence; capitalism is learning.

  3. ^

    A trader is a function  where  is the information in the environment (e.g. information from the order book) and  is time, returning limit orders for each sentence ().

    A constructor is a function  (where  is some  sentence) which returns a finite set of naturals (or "skip") to substitute for the leading bound variable.

    An agent is a (trader, constructor) pair, and acts in the obvious way, i.e. for each :

    1. Submit an order  to the exchange and receive assets to inventory.

    2. For each  sentence  in inventory, generate  and submit them, replace  with  and reduce to prenex normal form.

    3. For each  sentence  in inventory, receive the finite set  chosen by the opponent, replace  with  and reduce to prenex normal form.

    4. For each  sentence  in inventory, receive its computation and cash out.

    The details of the exchange are not important, it could be a continuous double auction, what's crucial is that orders are only filled if within budget, and that  and  orders are matched to each other: an order for a  asset at price  allows the exchange to sell its negative  asset at price , and vice versa. (Essentially: each trade is a  bettor and a  bettor coming together to pool  and  and the winner gets the total amount.)

New to LessWrong?

New Comment