Professor @Columbia. Theoretical computer scientist. Educator. Wrote Algorithms Illuminated, 20 Lectures on Algorithmic Game Theory, etc. Favorite number: 4/3.

NYC
Joined March 2012
Teaching my @Columbia course "Foundations of Blockchains" this semester. Follow along as I haphazardly post lecture notes while trying to survive, or wait til early 2022 for more complete and polished learning materials. timroughgarden.github.io/fob…
49
158
17
1,021
Show this thread
All the content from the #AFT2021 conference is now up on YouTube: youtube.com/playlist?list=PL… Thanks to @4SarahAllen for making it happen! (cc @FBaldimtsi @ittayeyal)
0
11
0
34
Learn. Document. Repeat. (A good algorithm for both research and teaching. Don't forget the second step!)
3
16
1
203
Most DEXes are CFMMs and differ only in the choice of the trading function f. E.g., for two-token pools, Balancer (v1) corresponds to f(x,y)=(x**w)*(y**(1-w)) for a parameter w in [0,1], and Curve (v1) corresponds to a weighted average of f(x,y)=x+y and f(x,y)=xy. 15/30
1
0
0
8
Let's try to apply the 3-step optimization approach to the space of CFMMs (for two-token pools, say). What's the design space? Following @GuilleAngeris @tarunchitra @alexhevans, let's focus on trading functions f that have qualitatively similar geometry to the x*y=k curve. 16/30
1
0
0
11
Formally, for every k, the quantity pairs (x,y) satisfying f(x,y)>=k form a convex set (if two points lie in the set, so does the line segment between them). All the AMMs above satisfy this property, and for good reason (e.g., computational efficiency of optimal arbitrage). 17/30
1
0
0
8
For an alternative parameterization of the CFMM design space, define V_f(x,y,p,q) as the post-arbitrage USD value of a portfolio (x,y) deposited in a CFMM with trading function f when token prices (in USD) on the open market are p (for A) and q (for B). 18/30
1
0
0
9
Note that V_f(x,y,p,q) depends on the trading function f (in addition to the token quantities and market prices); different choices of f define different strategy spaces for arbitrageurs, and hence different post-arbitrage portfolio values. 19/30
1
0
0
7
Every f gives rise to a V_f that is nonnegative (obvious), nondecreasing in (p,q) (obvious), 1-homogeneous in (p,q) (e.g., doubling prices doubles the value), and concave in (p,q) (related to the inevitability of LP divergence loss). 20/30
1
0
0
7
A very cool "easy theorem" of @GuilleAngeris @tarunchitra @alexhevans (see "Replicating Market Makers") states that every function V with these properties can in fact be represented as a portfolio value function V_f for some trading function f. 21/30
1
0
0
12
Multiple representations of objects is a signature of a good theory. The most useful representation will depend on what you're trying to accomplish. Working with CFMMs, you can now go back and forth between trading functions and portfolio value functions, as is convenient. 22/30
1
1
0
6
.@jason_of_cs and I have been exploring yet another representation of CFMMs, in terms of the implied spot price function. E.g., we think Curve (v1) is easiest to understand (and perhaps improve upon) from this perspective. 23/30
1
0
0
8
Can we apply this theory to formally justify existing CFMM designs (e.g., if Uniswap is the answer, what is the question?) or even guide us to new and better designs? These questions are almost entirely open. 24/30
2
0
0
10
One can characterize the x*y=k curve in terms of an "equal cash split" property. A calculation shows that whatever the current market prices, at equilibrium (post-arbitrage), the USD values of the two sides of such a pool are equal. Do any other CFMMs have this property? 25/30
3
1
0
10
In fact, one can show that the only trading functions with the equal cash split property have the form f(x,y)=g(x*y) for some invertible function g. Balancer pools can be similarly characterized as those with a "fixed cash split" property. 26/30
1
0
0
9
Tons of opportunities for further theoretical work in DeFi. What objective functions should we focus on? Are any of the popular CFMMs (Uniswap, Curve, etc.) optimal for some natural optimization problem, or can they be improved upon in a precise sense? 27/30
1
1
0
8
Perhaps the ultimate CFMM result would be a general compiler (in the spirit of Myerson's optimal auction theory) that takes as input a model of price movement and outputs a corresponding "optimal" CFMM with respect to that model. 28/30
1
2
1
13
Summary: we don't have a theory of DeFi just yet, but I'm very optimistic that we'll see a lot of interesting work over the next couple of years. Let me know if you make any progress! 29/30
3
0
0
22
Thanks to @jason_of_cs for ongoing collaborations, and @HatforceSec @Daeinar @dawnsongtweets and Roger Wattenhofer for the invitation! 30/30
2
0
0
19
Show this thread