How can we coordinate on solving important computational problems? And how can we do this safely?

Computing Markets

We can think of computing power as a resource, and one way to get people to contribute their resources to a project you think is important is to pay them! The global computing power market is already a $45 billion industry, and this is expected to roughly double in the next decade. One popular model for cloud computing is to rent the services of someone else's computer, paying by the hour.

Another approach is to pay for results, using a bounty. A legible delegated software system, such as a smart contract, can act as an escrow service, which releases funds under two conditions: 

  • Someone has submitted a solution, which the delegated system can verify. In which case the contract pays out to the solver.
  • The bounty has expired, and only the principal that originally deposited the funds can reclaim them.

Optimization Markets

Optimization problems have a measure of "how good a solution is", in addition to criteria for what makes a solution valid. And we can use this additional structure to pay solvers more for better solutions. The creator of an optimization market likely has some sense of what they'd be willing to pay for solutions of varying quality. And they can use that information to structure a payout function.

One example architecture would be to allow anyone in a large pool of participants to submit solutions, with top solutions being published to the entire pool as they're submitted. The market creator seeds the market with an initial solution, a payout function, and funds to pay solvers. If a participant has a better solution than the current best, they can submit it and claim the corresponding marginal payout for their marginal improvement. If the optimization metric goes from 0 to 100, and the slope of the payout function is a constant $1/unit of improvement, then the optimization market pays out $5 for improving the top solution from a score of 45 to 50.

Another architecture would be to keep solutions private, and award prizes to the participants that submit the best solutions. Kaggle runs competitions where teams compete to submit the best machine learning models, with prizes in the tens of thousands of dollars for big competitions. To prevent overfitting, there is a public training data set, and a private validation data set. Teams have a limited number of submissions, and their model's performance on the validation data set determines their team's score.

Safety

An optimization market has all the dangers of optimization and markets. They should only be used in domains where both can be used safely. But I think there are times when running an optimization algorithm, or a market, or a market for good solutions to problems, can be done safely.

Up next: When Can Optimization Be Done Safely?

New Comment
2 comments, sorted by Click to highlight new comments since:

This gave me an idea: You could have a website where bidders upload a problem description, public and private data, an optimization goal (in the form of a solution-evaluation algorithm), and a bid like 'for a solution at least x good I pay y'. Takers can submit algorithms that produce solutions. They get run against the data with time and memory limit as specified by the bidder and if they match the solution quality the taker gets paid.

Is there something like this around?

It seems straightforward! Kaggle is the closest example I've been able to think of. But yes that's totally the sort of thing that I think would constitute an optimization market!