Trading/order fulfilling algorithms

[genjix]

Hey,

I've tried google but it's not turning up much. I'm looking for algorithms to match up and fulfill an orderbook.

A offers 20 GBP for 10 BTC
B offers 5 BTC for 9 GBP
C offers 2 BTC for 6 GBP

Looking above we can see that to fulfill A's order, we can use B but not C's order:

BTC per GBP for A = A_want / A_amount = 10 / 20 = 0.5
BTC per GBP for B = B_amount / B_want = 5 / 9 = 0.56

if B_amount / B_want >= A_want / A_amount
(rephrased to avoid float rounding errors)
if B_amount * A_amount >= B_want * A_want
then order is OK

So using B's rate to fulfill A's order gives A more BTC for his GBP's worth:

=> take B's order from A leaves:
A offers 11 GBP for 5.5 BTC at the original rate of 0.5  (A got a better deal than he was asking for but the rate he has chosen remains fixed).

Do the comparison for C we see that (2 * 11 = 22) < 6 * 5.5... Ergo C's order is invalid for A.

HOWEVER

This isn't optimal at all. It has two problems:
- The rate is fixed at what A has chosen.
- Doesn't find the best all round solution to fulfill an order for everybody.
I tried rephrasing it as a linear programming problem,

A offers 20 GBP for 10 BTC
B offers 5 BTC for 9 GBP

x = X / GBP
y = Y / BTC

Constraints:
x <= 20
y <= 5

y >= x * 10 / 20  (from A's order)
or y >= 0.5 x

x >= y * 9 / 5     (from B's order)
or y >= 0.56 x

I have to maximise x + y in the space between those 2 lines and the box from the first 2 constraints... However the problem becomes error prone fast- I can easily do bounds detection but am worried about bugs.

Implementation MUST be perfect. Therefore I'm asking if anybody knows any pre-existing systems, algorithms or code I can read.

[grondilu]

You might have a look at davout's website code, if you like ruby.

I have also been thinking about that for a few weeks now.  I'm working on yet-another implementation in bash.

The problem with this kind of stuff is, as you pointed out, it's easy to make a simple implementation but much more complex if you want to make it optimal.

I can't believe there is not more public documentation about these kinds of algorithms.

[odolvlobo]

Keep in mind that these orders don't all appear at once. They happen sequentially and are generally resolved according to the terms of the earlier order.


On the other hand, the Gemini exchange has a particular kind of auction in which all orders are resolved simultaneously. Here is how it works according to them:

Market participants can place an auction-only market order (which will execute at the final auction price) or a limit order indicating the maximum buy price they are willing to pay, or minimum sell price they are willing to receive. The Gemini Auction will match the aggregate buy and sell demands from all participating orders and determine the price (“cross-price”) at which the largest quantity can be filled.

This page goes into a little more detail: https://gemini.com/marketplace/#gemini-auction-example