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:
(Σ1) an asteroid impact will eventually occur; I am mortal; P halts
(Π1) an asteroid impact will never occur; I am immortal; P doesn’t halt
(Σ2) there will exist an immortal man; some P_n doesn’t halt; this infinite checkerboard has a completely black horizontal row
(Π2) all men will be mortal; every P_n halts; there are infinitely many primes
(Π3) sentences about limits e.g. x_n diverges to +infinity
As a sigma-algebra, the Σn+1 sentence ∃x,P(x) should be seen as the countable union ⋃∞x=1P(x) 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 Σ1 (verifiable) and Π1 (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 Σ1 and Π1, 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 “PA⊢ϕ” 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 $1, even when ϕ is independent of PA.
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 P a Πn sentence, you can give a trader the asset ⋁x≤nP(x) on day n, taking it back the next day, ad infinitum, so the asset value approaches the Σn+1 asset ∃x,P(x) over infinite time.
But that doesn’t actually work. We can illustrate this with this simple pictorial description of arithmetical sentences — e.g. a Π2 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 ∃x,∀y,P(x,y) with the sequence ⋁x≤n⋀y≤nP(x,y). This has an intuitive appeal, because it mirrors what we do with Σ1 and Π1 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 n>3 in the Arithmetic Hierarchy, we have an impossibility theorem for any such scoring mechanism:
Theorem 1 (the problem is hard). Let P(x1,…xn) be an n-ary primitive relation (denote its Σn and Πn quantifications as ΣP and ΠP respectively), let D:N→listNn be some fixed “enumerator” of Nn (i.e. set(Dt+1)⊇set(Dt), ⋃t∈Nset(Dt)=Nn), and allow vectorizing P on finsetNn, i.e. P(⟨x1,…xn⟩)=⟨P(x1),…P(xn)⟩. A “mechanism” for ΣP (respectively ΠP) can be either:
[asset] a computable sequence of computable functions vt:BoolDt→R such that limt→∞vt(P(Dt))={$1if ΣP$0if ¬ΣP (respectively ΠP).
[score] a computable sequence of computable functions st:(0,1)→BoolDt→R such that limt→∞st(p,P(Dt))={log(p)if ΣPlog(1−p)if ¬ΣP (respectively ΠP).
Then for n>3, there is no computable procedure that, given some n-ary P, gives a mechanism for ΣP (respectively ΠP).
Proof. Suppose such a computable procedure existed, denote it by ϕ. Then for all n-ary primitive relations P, the sentence ΣP would be equivalent to either limt→∞ϕ(P)t(P(Dt))=1 or limt→∞ϕ(P)t(0.3,P(Dt))=log(0.3), depending on the type of mechanism. However, both of these sentences are Π3, and for every Σn sentence were equivalent to a Π3 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”.
A Σn+1 asset ∃x,P(x) entails a counter S⊆N, chosen by the holder at every point in time, and an underlying Πn asset ⋁x∈SP(x) with the same holder and issuer.
A Πn+1 asset ∀x,P(x) entails a counter S⊆N, chosen by the issuer at every point in time, and an underlying Σn asset ⋀x∈SP(x) 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:
A Σn+1 asset ∃x,P(x) entails a counter x∈N, chosen by the holder at every point in time, and an underlying Πn asset P(x) with the same holder and issuer (if no counter is chosen, the underlying asset is ⊥).
A Πn+1 asset ∀x,P(x) entails a counter x∈N, chosen by the issuer at every point in time, and an underlying Σn asset P(x) 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?”.
constructivism
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 π1099=6 — 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 x such that for all yWE WILL CONSTRUCT, P(x,y)
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 x 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 P(x,y); then ⋃xP(x,5) is a Σ1 sentence; ⋃x⋂yP(x,y) is Σ2, etc. Note that if the P(x,y)s were independent, then the probability of any Σ2 or Π2 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 P(x,0)∼Bernoulli(1(x+1)2) unconditionally and P(x,y+1)∼Bernoulli(e−1#[P(x,≤y)]2) conditionally on #[P(x,≤y)] (the number of 1s so far for the same x). One can show that the probability of ∃x,∀y,P(x,y) is 1−sinc(πe−π2/12)≈0.288.
(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 I that gives no information on A or B but gives information on A∪B:
e.g. I have two children; A is “my eldest is a boy”; B is “my youngest is a boy”; I 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 √2√2 proof is OK). What we do not have with statistical uncertainty is the strong kind of non-constructive evidence:
an event I that is independent of every finite union ⋃i∈SAi but gives information on the countable union ⋃i∈NAi:
This is impossible, as you can prove by applying continuity from below to the sequence Ai∩I.
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 ∀x,∃y,x≤y indefinitely and ℵ is a constructor such that ℵ(∀y,x≥y)∋x+1, the price of ∀x,∃y,x≤ywill approach $1 and the price of ∃x,∀y,x≥y (“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 P be a sentence and ~α be a constructor, i.e. a map Prop→finsetN. Write P,~α for ~α(P) and P.~α for the replacement of the leading bounded variable in P by the outputs of ~α, i.e.⋁x∈~α(P)P[x] if P is Σ and ⋀x∈~α(P)P[x] if P is Π. Note that P.~α is always lower on the (hyper-)arithmetical hierarchy than P. Thus for two constructors ~α, ~β, the alternating sequence P.~α.~β.~α.~β.~α… must eventually terminate at an atomic proposition. Denote this atomic proposition by Game(P,~α,~β). E.g. for First-Order-Logic sentences (specifically the example of Σn for even n):
For sentences beyond FOL, the expression is much the same except that n 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 π∗:t↦Prop→[0,1]
a constructor ~π:t↦Prop→label→finsetN∪{pass}
a labeller π#:t↦Prop→Q→_label∪{pass} (where →_ is the symbol for a piecewise-constant function over a finite number of pieces, i.e. a labelled finite-interval partition) such that suppπ#(t,P) has length μ$(t,P) (defined via mutual recursion as follows)
An agentα is composed of:
an endowment αb∈Q and a birthday αt∈N
a trader ^α:t↦Prop→∘[0,1]→Q such that ^α(t,P) is decreasing in price
a constructor ~α:t↦Prop→label→finsetN∪{pass}
a labeller α#:t↦Prop→Q→_label∪{pass} such that suppα#(t,P) has length α$(t,P) (defined via mutual recursion as follows).
an inventory α$:t↦Prop→∘Q defined by initial conditions α$(s,⊤)=0 for s<αt, α$(αt,⊤)=αb and for all other propositions α$(0,P)=0; and recursion α$(t+1)=α$(t)+∑P,iδP,iα$(t)where:
orders placed: δP,1α$(t,P)=λ^α(t,P,π∗(t,P)) where λ indicates that for all P, maxp−^α(t,P,p)≤α$(t,P) (you’re not selling what you don’t have) AND ∑Pmaxpp^α(t,P,p)≤α$(t,⊤) (you can afford all your purchases)
cost of orders placed: δP,2α$(t,⊤)=−π∗(t,P)δP,1α$(t,P)
the moves played (if P is Σ): δP,3α$(t,P)=−∑l∈supp~α(t,P)|α#(t,P)−1(l)| and δP,4α$(t,P[~α(t,P,l)])=|α#(t,P)−1(l)|.
the opponent’s moves (if P is Π): δP,5α$(t,P)=−∑l∈supp~π(t,P)|π#(t,P)−1(l)| and δP,6α$(t,P[~π(t,P,l)])=|π#(t,P)−1(l)|
the payout from empirical truth (if P is Δ0): if ξ(t) supports P, then δP,7α$(t,P)=−α$(t,P) and δP,8α$(t,ξ(t,P))=α$(t,P)
The empirical reality is a process ξ:t↦Δ0→∘{⊤,⊥,pass} such that s≤t⟹ξ(t)|suppξ(s)=ξ(s), ⋃tsuppξ(t)=Δ0, and ξ(t,¬P)=¬ξ(t,P).
A father of agents is an injective μbh:t↦α with a finite total endowment i.e.∑tμbh(t)b<∞ and correct birthdays i.e. μbh(t)t=t. It is associated with an aggregate agent as follows:
μb=∑tμbh(t)b
^μ(t)=∑αλα^α(t) where λα indicates that for all P, maxp−^α(t,P,p)≤α$(t,P) and ∑Pmaxpp^α(t,P,p)≤α$(t,⊤).
~μ(t,P,‘‘α":l)=~α(t,P,l)
μ#(t,P,q)=‘‘μbh(tq)":μbh(tq)#(t,P) where tq is the smallest t such that ∑s≤tμbh(s)$(t,P)≥q if such a tq≤t exists, otherwise pass.
An agent α is said to exploit a price-setter π if {α$(t,⊤):t∈N} is bounded below but not above.
A special price sequence ϖ∗ called equilibrium, computed as follows. For each P, ϖ∗(t,P) is the solution p to ^μ(t,P,p)−^μ(t,¬P,1−p)=0.
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 P and ¬P, however it may use different constructors for different portions of each. So we will have ϖ use μ‘s constructors for ¬P against μ’s constructors for P and vice versa so that it wins exactly the same number of games as it loses.
We construct as follows:
~ϖ(t,P)=~μ(t,¬P)
ϖ#(t,P)=μ#(t,¬P)
The result is immediate.
Corollary 2c [thus no one can]. Thus no one can exploit ϖ. (Proof: immediate.)
Theorem 2d [thus our result, pt 1].limt→∞ϖ∗(t,P) exists for all P; denote this as ϖ∞(P).
Proof. Suppose it didn’t; then there is some p′∈(0,1) and ε>0 such that ϖ∗(t,P)>p′+ε infinitely often and ϖ∗(t,P)<p′−ε infinitely often. Then consider the agent given by a trader that sells at p>p′+ε and buys at p<p′−ε, and a trivial constructor (doesn’t play the game at all, returns pass every turn). This agent exploits the market.
Theorem 2e [thus our result, pt 2]. If P is a constructively true sentence, i.e. such that ∃~α,∀~β,Game(P,~α,~β) (where quantifications are over constructors enumerated by the father), then ϖ∞(P)=1.
Proof. Suppose it wasn’t; then there is some ε such that ϖ∗(t,P) is below 1−ε infinitely many times. Then consider the agent given by trader that buys at p<1−ε and the constructor ~α from the hypothesis. This agent exploits the market.
Corollary 2f. If P is a constructively false sentence, i.e. such that ∃~β,∀~α,¬Game(P,~α,~β), then ϖ∞(P)=0.
Proof. Just apply 2e to ¬P.
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 π101000=3 having price 0.1 for a long time).
Perhaps something like this captures part of what I want:
Definition 2 (Constructible sigma algebras). Define Ω={0,1}N, 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 ¯¯¯πi={w∈Ω∣wi=0} and πi={w∈Ω∣wi=1} is in Ψ.
The finite unions and intersections of πi,¯¯¯πi are in Ψ; these are called its “propositional sets”
Ψ is closed under unions and intersections over the its computably enumerable subsets, i.e. for p:N→Ψ computable, ⋃x∈Np(x) and ⋂x∈Np(x) 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 sup~αinf~βGame(P,~α,β), but that’s not right. Seems like it should be something bounded between sup~αinf~βGame(P,~α,β)≤Pr(P)≤inf~βsup~αGame(P,~α,β).
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.
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.
A trader is a function Q(i,t) where i is the information in the environment (e.g. information from the order book) and t is time, returning limit orders for each sentence (Prop→∘([0,1]→┘Q)).
A constructor is a function ℵ(t,P) (where P is some Σn 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 t:
1. Submit an order Q(i,t) to the exchange and receive assets to inventory.
2. For each Σ sentence P in inventory, generate X=ℵ(t,P) and submit them, replace P with ⋁x∈XP(x) and reduce to prenex normal form.
3. For each Π sentence P in inventory, receive the finite set X chosen by the opponent, replace P with ⋀x∈XP(x) and reduce to prenex normal form.
4. For each Δ0 sentence P 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 p allows the exchange to sell its negative Σ asset at price 1−p, and vice versa. (Essentially: each trade is a Σ bettor and a Π bettor coming together to pool $p and $(1−p) and the winner gets the total amount.)
Betting on what is un-falsifiable and un-verifiable
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.
Prerequisites[1].
This post is also available as an arXiv paper.
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:
(Σ1) an asteroid impact will eventually occur; I am mortal; P halts
(Π1) an asteroid impact will never occur; I am immortal; P doesn’t halt
(Σ2) there will exist an immortal man; some P_n doesn’t halt; this infinite checkerboard has a completely black horizontal row
(Π2) all men will be mortal; every P_n halts; there are infinitely many primes
(Π3) sentences about limits e.g. x_n diverges to +infinity
As a sigma-algebra, the Σn+1 sentence ∃x,P(x) should be seen as the countable union ⋃∞x=1P(x) 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.
Actually Σ1 (verifiable) and Π1 (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 Σ1 and Π1, 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 “PA⊢ϕ” 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 $1, even when ϕ is independent of PA.
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 P a Πn sentence, you can give a trader the asset ⋁x≤nP(x) on day n, taking it back the next day, ad infinitum, so the asset value approaches the Σn+1 asset ∃x,P(x) over infinite time.
But that doesn’t actually work. We can illustrate this with this simple pictorial description of arithmetical sentences — e.g. a Π2 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 ∃x,∀y,P(x,y) with the sequence ⋁x≤n⋀y≤nP(x,y). This has an intuitive appeal, because it mirrors what we do with Σ1 and Π1 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 n>3 in the Arithmetic Hierarchy, we have an impossibility theorem for any such scoring mechanism:
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:
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:
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?”.
constructivism
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 π1099=6 — by relativizing knowledge to a class of programs — constructivism demands that we accept the probability of non-VF sentences to be read as:
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 x 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 P(x,y); then ⋃xP(x,5) is a Σ1 sentence; ⋃x⋂yP(x,y) is Σ2, etc. Note that if the P(x,y)s were independent, then the probability of any Σ2 or Π2 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.
(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:
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 √2√2 proof is OK). What we do not have with statistical uncertainty is the strong kind of non-constructive evidence:
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 ∀x,∃y,x≤y indefinitely and ℵ is a constructor such that ℵ(∀y,x≥y)∋x+1, the price of ∀x,∃y,x≤y will approach $1 and the price of ∃x,∀y,x≥y (“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.)
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.
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 π101000=3 having price 0.1 for a long time).
Perhaps something like this captures part of what I want:
How would we actually define probability assignments on this? I would think something like sup~αinf~βGame(P,~α,β), but that’s not right. Seems like it should be something bounded between sup~αinf~βGame(P,~α,β)≤Pr(P)≤inf~βsup~αGame(P,~α,β).
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:
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.
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.
^
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.)
^
Markets are intelligence; capitalism is learning.
^
A trader is a function Q(i,t) where i is the information in the environment (e.g. information from the order book) and t is time, returning limit orders for each sentence (Prop→∘([0,1]→┘Q)).
A constructor is a function ℵ(t,P) (where P is some Σn 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 t:
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 p allows the exchange to sell its negative Σ asset at price 1−p, and vice versa. (Essentially: each trade is a Σ bettor and a Π bettor coming together to pool $p and $(1−p) and the winner gets the total amount.)