Leveraging Arrow-Debreu Exchange Mechanisms for On-Chain Asset Exchanges
Utilizing Arrow-Debreu exchange markets, this study explores scalable solutions for on-chain asset exchanges, focusing on replicability, market models, and parallelizing transaction processing. Key considerations include agent endowments, utility functions, and maximizing trade efficiency within markets.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Scaling On-Chain Asset Exchanges via Arrow-Debreu Exchange Markets Geoffrey Ramseyer, Ashish Goel, and David Mazi res, 2020
Scaling On-Chain Asset Exchanges Debreu Exchange Markets Asset Exchanges via Arrow- I d like to trade $1 for at least 100 I d like to trade $1 for at least 1 I d like to trade 1 for at least $1
Scaling On Debreu Exchange Markets On- -Chain Chain Asset Exchanges via Arrow- There can be many acceptable ways to match buyers with sellers SELL $1 for at least 1 BUY $1 for 1 SELL $1 for at least 1 BUY $1 for 1.01
Scaling On Debreu Exchange Markets On- -Chain Chain Asset Exchanges via Arrow- An On-Chain Exchange must be Replicable A A B B C D C D E
Scaling On Debreu Exchange Markets On- -Chain Chain Asset Exchanges via Arrow- An On-Chain Exchange must be Replicable A A A B E B B B C C D D C D C A E E
Scaling On Debreu Exchange Markets On- -Chain Chain Asset Exchanges via Arrow- An On-Chain Exchange must be Replicable A A A B A B B B C C D D C D C D E E
Scaling Scaling On-Chain Asset Exchanges via Arrow- Debreu Exchange Markets Existing on-chain exchanges or automated market-makers (e.g. Uniswap) achieve replicable operation by serializing transaction processing. Transaction rate inherently limited by CPU speed Can we parallelize transaction processing replicably?
Scaling On-Chain Asset Exchanges via Arrow Debreu Exchange Markets Debreu Exchange Markets Arrow- - My endowment is $3 and 2 Arrow-Debreu Exchange Market Model M agents trading N assets 1. Each agent starts with an endowment 2. Market produces a public set of prices Denominated in monopoly money (M) 3. Agents sell their endowment for M at these prices 4. Agents spend their M to buy whatever set of goods they desire most. Each agent has a utility function, which they maximize subject to their budget constraint. $1= 1M 1= 2M I sell my endowment for 7M I spend 7Mto buy $5 and 1
Arrow-Debreu Market Equilibria A set of prices is an equilibrium of an Arrow-Debreu exchange market if after all agents buy and sell goods at these prices, no goods are overbought or oversold.
Scaling On Debreu Exchange Markets Debreu Exchange Markets On- -Chain Chain Asset Exchanges via Arrow Asset Exchanges via Arrow- - Transactions Block Producer Every 5 seconds: 1. Gather a set of Sell Offers (100k? 500k?) 2. Compute (Approximately) Equilibrium Prices 3. Output Block (Offers, Prices) Prices ?1,?2,?3, Block Validator Given a new block (Offers, Prices): 1. Check Transaction Validity (Signatures, etc) 2. Check that Prices are (Approximately) Equilibrium
Scaling On Scaling On- -Chain Asset Exchanges via Arrow Chain Asset Exchanges via Arrow- - Debreu Exchange Markets Debreu Exchange Markets Suppose we have a reliable equilibrium price oracle: 1. Transactions can be processed in parallel while producing replicable results 2. Access to market is more equitable 3. No arbitrage within the system, better liquidity 4. Since the market clears, no monopoly money is left behind, i.e. there is no actual need for a reserve currency
N Assets M Sell Offers (M Agents in A-D Market) Theory to Practice: A Scaling Problem Suppose there are M Sell Offers trading N assets. Existing market clearing algorithms all run in time polynomial in market size, which means poly(M). However, there are far more people in the world than types of asset. Concretely: ? 20 to 100 (Coinbase lists 4000) ? 100,000 to 1,000,000 + ????(?) is feasible, ????(?) is not Goal: Reduce ????(?) to ????(?) or ???? ? log ?
Our results A prototype system (SPEEDEX) that 1. Incorporates algorithmic insights that give sub-second latency for computation of equilibrium prices for up to a million orders 2. Is robust in cases where the price computation does not converge to an optimum solution 3. Achieves less than 5s latency for processing an entire block of orders Also, we show that incorporating both Buy and Sell offers makes the price computation intractable (via PPAD completeness).
Ttonnement [CPV05, CMV05] 1. Pick a candidate set of prices 2. Compute excess supply and demand at these prices 3. Adjust prices, repeat
N Assets M Sell Offers (M Agents in A-D Market) Logarithmic Time Demand Oracle The utilities of agents in our Arrow-Debreu Markets are not arbitrary linear utilities. Agents only have valuations for two goods what they sell, and what they buy. Idea: Group agents by which goods they value, then sort these groups by minimum price. With some preprocessing, compute total demand for the group with one binary search. Compute demand in time ? ?2log ?
N Assets M Sell Offers (M Agents in A-D Market) Convex Optimization [DGV16] ????? ? ?? min ? ? ????? ???log ??log ?? such that: 0 ?? ????? ??? ?:???? ? =???= ?:??? ? =??? ?? ????? ? ???? ???? ? ? 0,? 1
N Assets M Sell Offers (M Agents in A-D Market) Empirical Results Points to Note: 1. Scaling Trends 2. T tonnement appears practical outside of sparse markets but appears unreliable in sparse markets. 3. Convex solvers work well in sparse markets 4. The ? ? to ?(log ? ) transformation is critical for real-world usability.
Buy Offers and PPAD-Completeness So far, all operations in the exchange were Sell Offers A natural extension is the Buy Offer : I d like to spend as few $$$ as necessary to acquire exactly 10 Theorem Computing (approximate) equilibrium prices in a system with Buy and Sell offers is PPAD-Complete Proof Follows directly from [CPY17]
Conclusion We can effectively parallelize the operation of a distributed asset exchange using the mathematical model known as the Arrow-Debreu Exchange Market This approach requires efficient computation of equilibrium prices. Efficient algorithms for price computation require combining theoretical literature with additional structure in the real-world problem.
