Bitcoin Forum
December 11, 2016, 10:19:28 AM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Trading/order fulfilling algorithms  (Read 982 times)
genjix
Legendary
*
Offline Offline

Activity: 1232


View Profile
March 14, 2011, 09:16:47 PM
 #1

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.
1481451568
Hero Member
*
Offline Offline

Posts: 1481451568

View Profile Personal Message (Offline)

Ignore
1481451568
Reply with quote  #2

1481451568
Report to moderator
1481451568
Hero Member
*
Offline Offline

Posts: 1481451568

View Profile Personal Message (Offline)

Ignore
1481451568
Reply with quote  #2

1481451568
Report to moderator
1481451568
Hero Member
*
Offline Offline

Posts: 1481451568

View Profile Personal Message (Offline)

Ignore
1481451568
Reply with quote  #2

1481451568
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481451568
Hero Member
*
Offline Offline

Posts: 1481451568

View Profile Personal Message (Offline)

Ignore
1481451568
Reply with quote  #2

1481451568
Report to moderator
1481451568
Hero Member
*
Offline Offline

Posts: 1481451568

View Profile Personal Message (Offline)

Ignore
1481451568
Reply with quote  #2

1481451568
Report to moderator
1481451568
Hero Member
*
Offline Offline

Posts: 1481451568

View Profile Personal Message (Offline)

Ignore
1481451568
Reply with quote  #2

1481451568
Report to moderator
grondilu
Legendary
*
Offline Offline

Activity: 1134


View Profile
March 14, 2011, 09:24:48 PM
 #2


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.
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!