Estimating clearing prices is important for market makers. Specifically, there might be an incoming market order on the token A->B. A marker maker/ trader now might be interested in calculating what is the worst price they can bid to still trade against the market order given the current state of the system.
A simple strategy might be:
Take all orders on A>B and B<A;
- Sort them in a way to get the order that is requesting the lowest price first;
- Adjust the order to a volume that is actually backed by user balance;
- Reduce the user balance by the sell amount (simulate that this order will be filled)
- Repeat 2. and 3. for all orders that involve token A or B
- Create synthetic orders via “transitive hull” (e.g. A>C; C>B)
- Calculate clearing price on A-B with the aggregate of volume adjusted order and synthetic volume adjusted orders.
If step 5 is used in combination with step 2 the order matters. Tokens A might for example already be virtually spent on a path A->C->B but it turns out the path A->D->B would result in a better A->B rate. To address this it might make sense to think of the problem as a pathfinding problem with tokens as nodes and the order prices are the travel costs of those routes. It might be best to load the problem as a graph problem and use a pathfinding library. In this case step, 1 and 4 can be done simultaneously. The direct path can be the cheapest but does not have to be.