computational-equilibrium

Basic Idea

A very exciting use of smart contracts is to enable decentralized prediction markets

December 27th, 2024

An a particularly exciting perspective for using decentralized markets is that of decentralized computation

There is one specific type of smart contracts relying upon these ideas, which now comes under the name of optimistic roll-ups, or fraud proof systems: a result of a computation is posted, and there is a system which (in principle, at least) makes it possible to question the validity of that result, and in case of disagreement, to narrow it down to some computation that is simple enough to be checkable by the smart contract

This is a very nice idea, and it works quite well, but it is only applicable in the case where one instance performs a computation, and the others just verify it

It would be nice to have an architecture that would allow for more open-ended computational problems, in particular combinatorial problems (i.e. problems for which the solution is reasonably easy to check), where the role of the smart contract would be to elicit the best solution to a certain problem

What are Examples of Interesting Problems?

•

Hard inverse problems for LLMs: to me this is the most interesting class of problems... in particular:

•

Tasks that would revolve around some kind of clever synthesis or summarization

•

Tasks that have some adversarial component 'find some path that has the fewest weaknesses possible', i.e. games involving LLMs

While there is obviously something difficult about verifying LLM computations on the blockchain, it should still be feasible to do cool things... also, if the new result on the arrow of time for LLM-generated data holds true, this will be the sign that a fairly small model can (implicitly or explicitly) judge a much larger model with success

•

Some variants of some AI safety problems (prompt engineering, etc.): for instance, we could make a statement that a certain LLM is not known to be vulnerable to certain prompt engineering attacks

•

Some estimation problems related to computational physics or chemistry... a recurrent dream being to find the most consistent unified description of scales, and the most interesting and informative examples

•

Finding short proof arguments for theorems can probably ultimately be formulated as a game of this sort, as well

•

Some problems related to the discovery of interesting configurations in e.g. cellular automata

Usefulness aside, what are attractive problems?

Problems with a branching structure, where one is looking for a path in a space with certain properties that could be debated

For instance, if one claims that a certain solution will achieve a certain level of resistance of attacks, this should be up for debate; attacks should be proposed

What should we aim to achieve?

The idea would be to reach a state where a specific claim emerges as a consensus

The claim could e.g. be "a bounty of

x

was offered to find a better solution than

z

, no one could find a better solution for a period

y

This suggests that within the realm of various compute mechanisms of cost

\approx x

, the solution

z

cannot be distinguished from the optimal solution, and so could be treated as the optimal solution for specific needs

Interesting claims of this type would be of the form "this statement is evidently true, despite the fact that a full proof is not available, i.e. has never been computed by anyone

True provable statements without a full proof

If we consider a game like chess, there are positions that we will consider as being won by one side (black, say)... and this means that min-max of the game tree starting from that position yields the correct value

Typically, this game tree can be quite large, but the claim is (implicitly) that whatever move white makes, there will be a (reasonably obvious) black counter-move that will lead to a winning position for black again

Some positions are obviously winning by this definition, and some are not so obviously winning, and it is not completely clear how quickly the transition happens

December 30th, 2024

The notion of 'reasonably obvious' actually carries a notion of cost to compute that obvious move; and what will separate 'obvious situations' from 'non-obvious ones'

Open participation vs individual agency

There is a game-theoretic phenomenon about information asymmetry which is a bit puzzling to me, and I don't really know how to treat it

If there is a open challenge with a bounty in front of me, I will typically not want to invest time to participate (unless I have other forms of positive externalities), because the chance of winning is slim

As a result, I will tend to participate only to challenges where I know the number of eligible participants is relatively small (either because I have an edge, or because that number has been made artificially small)

So, if I create a challenge, it is not particularly clear that increasing the access pool will yield better submissions (there is the competition between 'more eligible people' vs 'each eligibile individual feels less agency')...

Does it make sense to restrict eligibility?

Conceivably, agents could have a good idea of what it would cost them to 'give a serious shot at finding a solution' without spending too much... and so there could be rounds where agents could make commitments about that

This is a set of relatively vague ideas about a general problem with open challenges (not very specific to this computational equilibrium framework, but still quite puzzling to me)... and at some point gaining clarity here seems very important

An essential property

Imagine that there is a prediction market (created according similar principles to the ones outlined above) as to whether a certain chess position is winning for black, and a certain consensus is reached

Now imagine that there is a separate universe where a prediction market about the same chess position has reached a different consensus

What happens when the two universes collide?

The idea is that there should be a quick convergence of the prediction markets (they should merge the relevant insights), i.e. we should learn that at least one of the consensus is wrong somewhere

A means to provide a proof would be to provide some chess engines with 'hints' for black, saying how to react to a certain white move ('hardcoded' as "this next black position is winning"), if that's not completely obvious

A challenge to the claim would take the form of a question "what do you do if I do this for white?"

Since all the chess engines with hints should provide some answers as to "how much is this black-winning" in various situations, we could start from the debated position, look at all the possible white moves from there, see if there is a discrepancy in the evaluation between the engines of both universes at the next move (there should be, otherwise one of the estimates was clearly inconsistent with respect to the min-max property), go to the next position of discrepancy, analyze where they differ, and so on... and this will lead to a quick identification of discrepancy (at the very least, one should end with a checkmate or draw position in a limited number of moves)

Obviously, the chess engine with hints should satisfy min-max consistency (it should still be the case that there is a winning black countermove to any white move, and this should hold true for anything labeled winning)

So, in some sense the claim will be "this hinted chess engine starting from this position that is being hinted as winning has the min-max consistency"

Chess position example

This is the kind of ideas that we introduced with Sprig, and that is a way in which research mathematics can be done, and that reasoning about games like chess works

Before discussing optimization in more detail, let us discuss a bit the concepts of

Unlike optimistic/fraud-proof systems, where someone has carried out the whole computation, here the different is that no one has done it (and likely no one will ever do it)... it is bit like a form of 'very lazy evaluation'

Let's discuss a bit how we would formalize things with chess

Computational Subjectivity

The key idea here is we can establish statements of the sort "this solution is a consensus solution, i.e. it can't be convincingly questioned within this computational envelope

Three Equivalences

A general framework which the above ideas could support is something linking (1) markets (2) information (3) computation

For 'math questions', i.e. questions whose answers can be (at least) completely verified by performing certain computations, the above three can be put in equivalence as follows:

Markets (i.e. "things with money") allow one to elicit information (and this is quite delicate in the case at hand, where the information pertains to certain computation results)