Algo. Discussion

[WillRuddick]

Specification for Developing Optimization Algorithms for Networks of SwapPools:

Use Case #1: Optimal Pathfinding

• Objective: Develop an algorithm to find the most efficient path for exchanging Asset A for Asset C through intermediary pools (e.g., A->B, B->C).
• Optimization Criteria:
  • Minimize Costs: Calculate the total fees for different paths and choose the one with the lowest cost.
  • Pool Balancing: Prefer paths that help maintain or achieve balance in the pools' liquidity.
  • Speed and Efficiency: Prioritize paths that require the fewest number of swaps to complete the exchange.
• Data Inputs:
  • Pool Metadata: Information on each pool’s supported swaps, liquidity, and fee structure.
  • Market Data: Current valuation of assets across pools for accurate cost assessment.
• Algorithm Design:
  • Graph Theory Application: Model the network of pools as a graph, with pools as nodes and swaps as edges.
  • Cost Function Definition: A cost function that accounts for fees, pool liquidity impact, and asset valuation.

Use Case #2: Pool Balancing (Obligation Clearing)

• Objective: Create an algorithm that identifies and executes rebalancing opportunities among a network of pools to maintain desired liquidity ratios.
• Optimization Criteria:
  • Liquidity Distribution: Aim for a target distribution of assets across pools.
  • Trade Efficiency: Minimize the number of transactions required to achieve balance.
  • Equitable Exchange: Ensure that the value exchanged between pools is equitable and fair.
• Data Inputs:
  • Liquidity Levels: Current levels of each asset in all pools.
  • Target Ratios: Desired liquidity ratios for each asset in each pool.
• Algorithm Design:
  • Cycle Detection: Identify cycles that allow for multi-pool balancing without redundant swaps.
  • Transaction Sequencing: Order transactions in a way that maximizes rebalancing while minimizing impact on any single pool.

For both use cases, the algorithms should be designed to run at specified intervals or triggered by certain thresholds being met (e.g., liquidity imbalance). They should also be robust enough to handle the dynamic nature of the pools, where liquidity and valuations can change frequently. The algorithms must be transparent and verifiable to maintain trust among participants in the network. Additionally, the implementation should prioritize security and auditability, especially when integrating with blockchain-based SwapPools.

Use Case #3: Multi-Asset Exchange Maximization

• Objective: Formulate an algorithm akin to Math Trades that handles a multitude of individual "want" lists across the network of SwapPools, optimizing for the maximum number of completed trades.

• Optimization Criteria:

  • Trade Maximization: Maximize the total number of assets successfully exchanged.
  • User Satisfaction: Prioritize trades that fulfill the highest number of users’ want lists.
  • Fairness: Ensure that trades are conducted equitably, with users receiving fair value.

• Data Inputs:

  • User "Want" Lists: Comprehensive lists of assets that users are willing to trade and assets they desire in return.
  • Pool Inventories: Current asset holdings in each SwapPool, available for trade.

• Algorithm Design:

  • Order Matching: Implement order book matching to pair users' offers with their wants, utilizing assets from relevant pools.
  • Graph Cycles: Detect cycles within the graph where a series of trades can satisfy multiple wants, similar to finding cycles that maximize vertex coverage in Math Trades.
  • Iterative Improvement: Utilize an iterative approach to refine solutions, ensuring an increasing number of wants are satisfied in each iteration.

For this use case, the algorithm should consider the liquidity in each SwapPool to fulfill orders without causing significant imbalance. It must also be capable of handling complex multi-party trades that could involve more than two participants to find the optimal trade cycles. This optimization task will likely be computationally intensive and require sophisticated mathematical models to execute effectively.

[michielbdejong]

Yes, well described! Use case 1 is basically https://interledger.org - multi-hop payments. See also an old blog post of mine about Ripple Classic, Interledger, and multihop with hashlocks.

Use case 2 is different from that because the user is not synchronously waiting for a payment to complete; the rebalancing can happen asynchronously, so the time constraints are much less strict. And indeed instead of path finding we then call it cycle detection, like in https://ledgerloops.com.

And use case 3 is maybe the combination of the two, but taking into account how one trade can sometimes block the possibility of a different trade? As in "find an optimal set of trades". A trade might be beneficial in itself, but in the bigger picture it can lead to a suboptimal end result for the network as a whole.

Do read https://www.mdpi.com/1911-8074/13/12/295 if you haven't yet.

This optimization task will likely be computationally intensive and require sophisticated mathematical models to execute effectively.

Not if you start with a complete bird's eye view of the market. You could use the algorithm that Slovenia uses (I can't find the link right now, I think there is a 4-letter acronym for it but I forgot, so quoting from memory):

• create a graph where nodes are companies and weighted directed edges are what they owe each other
• add two imaginary nodes to the graph: source and drain
• For every node, calculate the balance of incoming - outgoing weights. If it's positive, add an edge with that weight from the source to that node. If the balance is negative, add an edge with the absolute value of that balance as its weight from that node to the drain.
• Now, for each node, the sum of weights of incoming edges is equal to the sum of weights of outgoing edges.
• Use a Max Flow algorithm to find the set of weighted paths that make up the maximum flow from source to drain. There are algorithms that do this in time that in basically linear time (see that Wikipedia link).
• Substract these flows from the graph. All edges that are left will be part of a cycle. So then you can know you have a maximum set of cycles you can remove from the graph.
• There will still be multiple options though, because some cycles will overlap, and removing one cycle will break another one.

My research interest is also in solving this without a bird's eye view of the network, so by only sending signalling messages through the network. One way of doing that is using market forces, to get netting at equilibrium although we had a discussion about this at CoFi'24, since it may be optimal for individual agents to incentivise market makers, but of course society as a whole is better off without brokers who just exploit their network position to charge a toll.