Smart Contracts for Smart Markets
I’m Khan, and at Fetch.AI I’m leading a team focused on building amazing applications for our Virtual Machine. Some of these revolve around cutting edge machine learning, but today I want to share an innovation we’ve made on smart contracts around smart markets. We have named this technology Synergetic Contracts and will in the coming months release examples on how to build these on our new community site.
So what is a smart market?
From Wikipedia:
A smart market is a periodic auction which is cleared by the operations research technique of mathematical optimisation, such as linear programming…Trades are not bilateral, between pairs of people, but rather to or from a pool.
In other words a smart market is an auction where bids can be placed on combinations of items, rather than on individual items. Furthermore there may be special instructions or restrictions on those bids, such as ‘winning this bid requires invalidating my other bid’.
For example, maybe you want to go on holiday to Rome, and you’ve found two hotels you really like; you could place a combined bid on the taxi from Ciampino Airport to Palazzo Montemartini hotel, and the room booking therein, with a caveat that this bid explicitly excludes your other bid on the taxi from Leonardo da Vinci International Airport to Rome Cavalieri hotel, and the room booking there. Now the smart market runs an optimisation scheme to try to maximise the value in all bids proposed. Since many other people also bid on rooms at the Palazzo Montemartini, the bid wasn’t successful, but relatively few people attempted to book at Rome Cavalieri so that bid is won at a great price.
This is just a toy example, but hopefully you can see that this kind of process can release a lot of value to both buyers and sellers by automatically identifying the best combinations of transactions according to supply and demand.
In real life smart markets have already been used for managing transportation logistics and for selling radio wave bandwidth, but they come with a few complications. For example in our toy example you probably would want to be sure that you’ve booked a hotel room before boarding a plane; of course, you could bundle this into the auction too, but the point is the auction clearing schedule becomes quite important! Aspects of the market, such as the clearing schedule, or the handling of payment defaults, can be properly managed if there are different smart markets for different types of items, each with appropriate sets of rules.
Isn’t it hard to find the best combination of bids and items?
Ah, yes, it is! Specifically it’s an NP-hard problem, which means that as the number of items and bids (and their complexity) increases, the problem becomes extraordinarily hard to solve perfectly in most cases. Imagine millions of bids on millions of overlapping item sets; it would be pretty hard to manually identify which singular combination of bids would maximise value over all buyers and sellers. It turns out that it’s hard to do for computers too! This is because it’s difficult to write an algorithm that performs better than simply trying out lots of different combinations — hence why this is sometimes called a combinatorial auction.
However, the fact that optimising for a combinatorial auction takes a lot of work is actually an incredibly interesting property that makes it ideal for massively parallel search in a similar fashion to the proof-of-work hash puzzle in Bitcoin. Unlike PoW, this work is economically useful work as it optimises the ledger’s internal market. If the work is sold to those participating in the auction, the earnings can afterwards be used in a Proof-of-Stake consensus before being released to the miners to enable Useful Proof-of-Work (µPoW). We are currently studying different versions µPoW to understand under which conditions it would be secure before making our final decision on whether we want to include this in our final ledger. Regardless of whether µPoW makes it to the final system, Synergetic Contracts will and µPoW is a minor variation of this concept.
What makes combinatorial auctions an ideal candidate for Synergetic Contracts is that many problem miners can try to find the best combinations of bids in parallel, and we can reward the miner that finds the best combination (for example with tokens from transaction fees, or with a stake that comprises a probability to become the next block creator); other miners will be able to easily verify the total economic value of the winning miner’s solution.
So what algorithms can we use to solve this kind of optimisation problem?
To solve this type of problem our best approach is to use randomised heuristic algorithms. For example a random walk: we randomly pick a combination of bids to accept as winning bids, compute the economic value of that combination, randomly reject a few of those bids and accept a few different bids instead, then we compute the economic value again, and repeat over and over again, remembering whichever was the best combination we tried out. Thus it’s a random walk through the space of all possible combinations. There are various algorithms building on this principle, but the fundamental approach is really just this simple: try out some combinations at random, evaluate them, and then try out some more!
But wait, wouldn’t someone just train an AI or deep learning model to instantly find the best combination?
No! Cutting edge machine learning can do incredible things, but fundamentally what’s being achieved is an incredible capacity for perception and decision making. Perception means converting complicated inputs (e.g. millions of pixels) into meaningful conclusions (e.g. it’s a cat!), and decision making means deciding based on a complicated input (e.g. more pixels) which action to take next (e.g. which actuator in the robotic arm to activate). This kind of technology cannot instantly find the best combination of bids because, fundamentally, although millions of items and bids is complicated, it’s not rich data containing useful patterns (like eyes and ears) — in other words: machine learning can’t solve problems where there’s nothing for the machine to learn!
What cutting edge machine learning can do is provide a complement to smart markets. It might be hard to pick just two or three hotels you really like the look of from the thousands of hotels available in Rome; this is where modern machine learning approaches can excel! By combining all the rich details about the hotels with information about your past choices and preferences, a ‘recommender system’ can help you pick the hotel and taxi combinations worth bidding on in the smart market.
But wait, I don’t want to make a bid on a can of coke!
Fair enough, a smart market probably isn’t going to be the right environment for every transaction! In some market places we might really value immediacy, or we might want a lot of guidance about pricing. A smart market changes how we think about pricing: instead of paying a fixed price and knowing we’ll get the item, we have to think about what would be the maximum we would be willing to pay, commit to paying that price, and then wait for the auction to clear before finding out which bid was a winner and how much we in fact have to pay. That wait time will vary and, just like today, some transactions are concluded in seconds while others take months.
Okay, so why do smart markets need smart contracts?
The decentralised digital economy of the future needs protocols for running these smart markets, and that’s where Synergetic Contracts come into the picture. Existing smart contracts execute relatively trivial computations and are not much more complex than ordinary financial transactions. Truly smart contracts will need to be able to execute optimisation algorithms to run smart markets. This is what we’ve built and are developing on a daily basis at Fetch.AI. We are really excited about this as smart markets already have major applications in, for example, the energy sector.
Furthermore, these optimisation algorithms can be adjusted both in how long to run them for, as well as how many random parallel initialisations to begin. In general there are a some optimal combinations of these parameters that lead to finding better solutions more quickly. We can control these parameters if we embed the combinatorial auction in a smart contract; we simply control the number of miners, and the number of steps taken in a single call to the mining function.
On top of executing sophisticated optimisation algorithms, these Synergetic Contracts will need to be able to implement appropriate clearing schedules, methods for listing new items and bids, handling payment defaults, and much, much more. We are building smart contracts truly worthy of the moniker.
Smart contracts are going to play an increasing role in our lives over the coming years. To learn more about Fetch.AI’s unique take on another application of this technology, read our article about Synergetic Smart Contracts.
