Project Incentivus is a new research initiative aiming to explore convex optimization applications to the incentive layer of blockchain protocols.
This interdisciplinary effort started from an earlier work on EIP 1559. In summary, this EIP suggests an alternative to the current first-price auction transaction fee market. In this scheme, all of the transactions in a block share a universal fee; however, this fee is dynamically updated across different blocks according to a predetermined in-protocol formula. We started to look at a question relevant to all users: what is the optimal policy to pay the minimum fee for executing a set of transactions? Such problems have long been investigated in economics and are frequently solved by convex optimization. In this case, the optimal policy turned out to be too optimal and could be considered an attack in the sense that controlling the allocation of a small fraction of the total volume of transactions is enough to manipulate the price and make it zero in a short time.
Moreover, instead of searching for the optimal behavior given a specific protocol design, we can turn such arguments around to engineer user behaviors by setting the right incentives. A simple observation is that the transaction fee pricing problem is similar in many aspects to the liquidation strategies in economics. In the former case, we want to execute many transactions, but each time we do so, the price of executing the next transaction goes up. In the latter case, we want to sell our assets, but each time we do so, the trading price goes down. An established model for the second problem is the Almgren–Chriss framework, which guarantees that the optimal execution of transaction strategy is to spread the transactions across time which in turn helps to avoid network congestion for blockchains. Overall, we believe that although such use cases of convex optimization are exploited extensively in game theory, they have not transitioned to the blockchain ecosystem yet.
A simple observation is that the problem of specifying the right equilibrium price (EP) for transaction fees is a particular instance of the more general problem of determining the EP in a DEX match engine. In this analogy, a single seller, which is the group of validators, is selling the block size amount of space to a large number of buyers, which are the user transactions. A continuous match engine results in the first-price auction and a discrete one gives the second-price auction for the fee market.
In order to show this, consider the steps in this article. Step 0 corresponds to the case of mining an empty block. Step 1 corresponds to choosing a price which fills up the block. Step 2 corresponds to choosing the EP in a way that if the transactions associated to the n highest bids fill up the block, then EP must be chosen between the n and n+1 bids. If we assume that the number of bids is large enough such that the n and n+1 bids are close enough, this already gives the second-price auction, and the steps 3 and 4 are irrelevant.
The Binance DEX has given numerous warnings regarding the aggressive orders in very volatile or illiquid markets. The problem is that it might be the case that one can even profit from selling less amount. This problem is precisely the same as when in second-price auctions a miner may profit from forging fake transactions in order to shrink the available block size. In both cases, the significant change in the final price makes up for the lesser quantity that one sells.
To show this problem by an example, consider an order book with one sell bid for 20 units at price 5, one buy bid for 10 units at price 11, and another buy bid for 10 units at price 5. According to the Binance DEX logic, in this scenario the seller earns 100. However, if the last buy bid did not exist, the seller would earn 110 while retaining half of his assets. Another way to see this point is that selling only 10 units instead of 20 units is in seller's favor because the money he earns is not an increasing function of the amount he sells.
Note that, this problem exists in any periodic auction with a single universal price in each period, where EP is set to be the price at which the maximum volume can be traded. In other words, to solve this problem, one should either match at multiple different prices like in the first-price auction or waive maximizing the execution quantity like in a recent proposal to redesign Bitcoin's fee market. In that article, the authors propose a monopolistic price mechanism in which the miners choose the optimal block size for maximizing their profit. This mechanism corresponds to the seller in our example, choosing to sell only ten units, which is the analog of reducing the block size.
The incentive incompatibility discussed in the previous section can be solved by increasing the market thickness. As a result, clearing the not-so-liquid markets at a lower frequency solves this problem at the expense of delay. The tradeoff between immediacy and batching in frequent call markets has been studied for a long time. It is well-known that higher frequencies reduce market liquidity and allocative efficiency and also suffer from the adverse effects of high-frequency traders exploiting latency arbitrage. We refer the interested reader to here for more details.
On the other hand, blockchains also have a limited block size, which can be either fixed or adaptive. Dividing this block size between the different trading pairs is a crucial design choice if the sum of the required spaces exceeds the block size. Together with the clearing frequency, both the clearing interval and volume which are a multiple of block time and a fraction of block size are adjustable. Note that, by volume, in here we mean the number of trades (or bytes to be more accurate) instead of the more conventional trading volume.
Depending on the relative adoption and scalability, clearing all the markets at every single block will eventually become infeasible for any DEX. Here we propose that in such inevitable situations, the available time and space should be divided proportionately to the liquidity of each market. Furthermore, this limitation of blockchains increases the efficiency of illiquid markets compared to the continuous matching or more frequent repeated auctions as suggested by many studies. Also, it increases the transparency of how the validators handpick trades from the mempool by reducing the degree of freedom in this framework compared to the arbitrary selection or fee arms race.
The problem of allocating block space as a resource to different trading pairs is comparable to scheduling in many respects. One of these aspects is the liveness property which can be defined in analogy to computer science by stating that a match engine provides a weak or strong liveness guarantee if all markets are guaranteed to be cleared in a finite or bounded number of blocks respectively. As an immediate result, these properties provide upper bounds on the wait time a user may experience. We can apply any of the priority inversion methods such as random boosting to achieve such guarantees.
To sum up, we have proposed to prioritize the trading pairs according to the liquidity of each market as a natural solution to the limitation of block space and the inevitability of choosing between trading transactions. Moreover, we have proposed augmenting this idea with priority inversion techniques to minimize the maximum wait time of clearing markets. For the future works, one can study the effect of different liquidity measures and priority inversion methods in a specific implementation of this proposal.
There are three important indicators that can help determine if a market is liquid or illiquid: 24-hour trading volume, order book depth, and the bid-ask spread. The bid-ask spread is the difference between the lowest ask price and the highest bid price. However, the order book might not always be an accurate representation due to factors like stop-limit orders and iceberg orders, which are not always visible in the order book.
Furthermore, variable block sizes can be implemented in order to adapt to the overall liquidity of all markets. One way of applying this idea is to define an increasing function for the probability of a market being cleared in the current block, given its market size. Then each market is selected according to this Bernoulli probability distribution independent of the other markets.