logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-11062023-153211


Tipo di tesi
Tesi di laurea magistrale
Autore
IANNELLI, FRANCESCO
URN
etd-11062023-153211
Titolo
A smoothed dual approach for the optimal routing problem in blockchain trading
Dipartimento
INFORMATICA
Corso di studi
INFORMATICA
Relatori
relatore Prof. Frangioni, Antonio
Parole chiave
  • blockchain
  • cfmm
  • cryptocurrency
  • defi
  • optimization
  • routing
  • trading
Data inizio appello
01/12/2023
Consultabilità
Non consultabile
Data di rilascio
01/12/2093
Riassunto
This work addresses the practical application of optimal routing in blockchain trading, focusing on the challenge of dual decomposition when routing through Constant Function Market Makers (CFMMs) with linear trading functions. Those CFMMs, often called liquidity books, leverage concave but not strictly concave linear trading functions within each liquidity position. The study presents and evaluates two solutions suitable for the dual decomposition: sub-gradient methods and Nesterov's smoothing. We propose a Lagrangian heuristic for sub-gradient methods that provides a robust termination criterion in arbitrage instances. Furthermore, we demonstrate that Nesterov's smoothing generates strictly concave CFMMs capable of approximating linear ones, establishing sufficient conditions for valid approximations. New proximal functions specific to optimal routing are proposed, yielding better approximations compared to widely adopted proximal quadratic functions. Empirical evaluations on blockchain-derived data indicate the effectiveness of these approaches.
File