Implement DaoSwap optimization problem

[tamriq]

From whitepaper:

The general problem of determining the token equilibrium price and the allocation among the swap participants can be formulated in terms of the inequalities on quantities and prices corresponding to the orders and on the need that the total quantity exchanged of each token is preserved across the swaps, i.e., the quantity bought for each token is equal to the sold quantity.

The general solution of the DaoSwap problem is a set of non-linear equation with combinatorial constraints, which is of course NP-complete. It can still be solved in an effective way with solvers like ...

• Modeling languages https://coin-or.github.io/pulp/ https://pyomo.readthedocs.io/en/latest/index.html https://stackoverflow.com/questions/26305704/python-mixed-integer-linear-programming Questions: Do they support open-source backends?

• Use one of the solvers (open-source) https://www.gnu.org/software/glpk/ https://github.com/coin-or/Cbc https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.milp.html http://users.isy.liu.se/johanl/yalmip/ Closed-source: CPLEX and Mosek (used in the past, but too expensive)

• How to represent non-linear constraints https://math.stackexchange.com/questions/2117912/conditional-constraint-in-a-linear-program https://stackoverflow.com/questions/57949190/how-to-apply-conditional-constraints-to-python-pulp-function Lots of examples of how to map non-linear constraints onto CPLEX (probably possible to reformulate for other solvers) https://www.linkedin.com/pulse/making-optimization-simple-python-alex-fleischer/

• Interesting papers https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=c66efc96ff4099fa214dfef684cdddd30b0fc770

[gpsaggese]

I can work on this with @PomazkinG when he has bandwidth

[PomazkinG]

@gpsaggese I could use some help here

What I don't quite get is what do we want to maximize / minimize?

Typically the pulp solver accepts:

• The objective function (i.e. what we want to maximize / minimize)
  • e.g., z = f(x, y, z)
• Constraints on x, y, z
  • e.g., 10x + 20y = 50 and 5x - 2z <= 20

Now let's come back to our toy example:

• 2 limit orders
• opposite direction
• same base token = "BTC"
• prices are known

My understanding is that we need to match the orders below. In other words find q_base_asterisk_1 and q_base_asterisk_2 such that all constraints are satisfied. Maybe another detailed natural language description or a formula would help me.

# We use exchange_rate for the limit price constraint.
exchange_rate = p_base / p_quote = known const 
# Toy orders: holders want to buy / sell the same about of BTC.
o_1 = (action="buy", q_base=5, base_token="BTC", limit_price=4, quote_token="ETH")
o_2 = (action="sell", q_base=5, base_token="BTC", limit_price=5, quote_token="ETH")
# Constraints.
# TODO(Grisha): do we need a constraint saying that sum(q_base_asterisk * to_ineq(action))  = 0?
# i.e. the quantity of bought and sold token is equal? 
cond_1 = exchange_rate <= limit_price(o_1)
if cond:
   0 <= q_base_asterisk(o_1) <= q_base(o_1)
else:
   q_base_asterisk(o_1) = 0
#
cond_2 = exchange_rate => limit_price(o_2)
if cond:
   0 <= q_base_asterisk(o_2) <= q_base(o_2)
else:
   q_base_asterisk(o_2) = 0

[gpsaggese]

Good question. That part is not clear from the paper.

The maximization constraint can be 1) "maximize the volume exchanged"; or 2) "maximize the total welfare" (i.e., the sum of the differences between what people are paying for and their reservation price) 3) something else

I would pick the constraint that it's easier to specify and helps convergence -- so maybe 1)

[gpsaggese]

Also yes you need to impose a constraint saying that "the ETH tokens bought are == to the tokens ETH sold".

The maximization constraint is needed otherwise a valid solution is always "nothing gets exchanged".

I think both DaoSwap (where the prices need to be determined) and DaoCross benefit from the maximization constraint.

Another problem is once we have prices how you determine how to match buyers and sellers? We can either do another optimization (like "bin-packing") or the simple priority queue approach might be enough to compute the matches, with some extensions for the more complicated cases of more tokens.

[PomazkinG]

After https://github.com/sorrentum/sorrentum/pull/94 is merged the plan is:

• Move the code to a lib, add unit tests
• Extend the functionality to work with
  • N orders instead of 2
  • N base tokens instead of 1

[gpsaggese]

Good plan.

Of course let's do baby steps: PR1: N orders with one base token first PR2: N orders with base / quote token (e.g., buy ETH vs BTC, sell ETH, buy BTC vs ETH, sell BTC) PR3: N orders with N tokens mixing everything

[PomazkinG]

As a workaround I install the pulp package manually in a tmp docker container to run the tests but later we should consider adding it (or another package) to a docker image (amp / defi)

[PomazkinG]

Extended for N tokens (only the 2 token case is tested for now) in https://github.com/sorrentum/sorrentum/pull/108

The next steps are:

• Refactor the unit tests so that it is easy to delegate to students. Add 1 example unit test per test class and ask the students to finish.
• Create random orders and run the optimization for everything
  • E.g., 4 different base tokens, 4 orders for each token such that: 1 buy order with the limit price cond = True, 1 buy order with the limit price cond = False and 2 sell orders with the same logic

Current progress and the plans are reflected in https://docs.google.com/document/d/1Kxu6gfUTtfLKaw2O_SBn_iBfpORhlRFMB4uJ4RpA4Hs/edit#heading=h.hnjzvh3d7tw8

[gpsaggese]

Fantastic job and perfect organization. You guys are coding machines.

[PomazkinG]

Question to @gpsaggese and/or @gitpaulsmith:

When solving the DaoCross optimization problem: I am trying to maximize the volume exchanged.

Where the volume is: sum(clearing_price_base_token * executed_quantity_base_token) for each order

e.g,:

• BTC clearing price in terms of a reference currency (e.g., USDT) = 2
• order1(base_token="BTC", quote_token="ETH", action="buy", quantity=8)
• order2(base_token="BTC", quote_token="ETH", action="sell", quantity=8)
• assume a perfect match here 8 BTC to buy and 8 BTC to sell

The total exchanged volume is 32 = 8 2 (buy order) + 8 2 (sell order). Is it correct? It seems to me that I count the quantity of BTC twice, while the answer should be 16.

[gpsaggese]

We'll add a precise formula in the white paper, but you can double count things if it's simple, since maximizing is invariant by multiplying by a positive constant.

Not sure if we should use the $price quantity$ to maximize notional transacted or something like $max \sum_i q^(o_i)$ over the orders, where q^*(o_i) is the actual quantity exchanged for each order. The equation balancing between sell and buy will take care of making sure that the exchanged quantities are valid. Maybe we need to sum by different tokens accounting for the direction of buying and selling.

We can also try different approaches for the implementation to inform the theoretical part...

We'll think about it in any case.

[DanilYachmenev]

Seems to be implemented at defi/dao_cross/optimize.py Should we close?

[gitpaulsmith]

Done.