Bitcoin Forum

I want to implement a generic barter plateform, but the algorithm is a bit tricky to write.


Here is the idea: we have a bunch of exchange orders between assets called asset1, asset2, etc.

An order looks like that:

#n  -q1 assetA q2 assetB


#n is the reference of the order
q1 is the quantity of assetA that is given
q2 is the quantity of assetB that is desired in exchange for assetA


I've made a simple bash function that generates random orders:



The goal is to create a function that takes the output of randtrades as input, and returns list of possible trade cycles:

exemples:

#1 -2 assetA 4 assetB
#2 -1 assetB 2 assetC
#3 -4 assetB 1 assetA

returns:

#1 #3

because obviously orders #1 and #3 match one another (they make a 2-lenghted cycle).


An other exemple:

#1 -2 assetA 4 assetB
#2 -1 assetB 5 assetD
#3 -2 assetC 1 assetA
#4 -5 assetB 2 assetC

returns:

#1 #3 #4

because #1 gives the required asset to #3 which gives the required asset to #4 which finally gives the required asset back to #1.  They make a 3-lenghted cycle.  Hope it's clear.

Don't worry too much about quantities.  The only important thing is that an order is capable of giving at least what is required.

Of course if there are muliple possibilities, all of them should be displayed, one per line.

It's for situations like this that "prices" were invented.

I disagree.   A price emerge when one particular asset acquires a currency status.

In a situation where almost all assets are currencies themselves, then the barter model makes sense.

I agree. Just because some forex sites only offer some currency pairs ought not prevent people from looking into how one might look at all known currencies stocks commodities goods services magic swords or whatever with an eye to whether maybe the shoelace the soldier needs to avoid tripping on way to keep the bull from killing the farmer who makes the cheese the lacemaker likes might be obtainable by some sequence of trades...

-MarkM- (Oh wait was it something other than a shoelace for want of which the rest of the old chestnut...?)

OK, that's fine. The word "currency" wasn't explicit in your first post, and I assumed the "assets" could be totally arbitrary, in which case it's impractical to solve complex multi-exchange trades without introducing prices.

I'm going to write the problem in an even more generic way.

An order will be a list of signed integers:

(-40, 0, 6, 12, 0, 0, 1, 0, 0, 0)

This example shows an order that says that the issuer is ready to give 40 units of asset 1 if this can give him 6 units of asset 3, 12 units of asset 4 and 1 unit of asset 7.

The order book is a list of such lists.

The requested algorithm should return a list of cycled orders lists.


I suspect it is possible to solve the problem elegantly with a recursive function.

Take a look at FellowTraveller's OpenTransaction.

You seem to have proposed a use-case for his "basket currency" feature maybe.

-MarkM-

Somehow this doesn't fit, does it ?

Why do you say this?  It all depends of the relative value of the assets.  I could have replaced 40 by 0.001 if asset 1 was extremely valuable compared to other assets.

Oh, sorry for being an idiot, I thought the integer tuple was structed like this:
(amount, index, amount, index, amount, index, ...)

Anyways, maybe this helps you a bit:
https://secure.wikimedia.org/wikipedia/en/wiki/Banker%27s_algorithm (https://secure.wikimedia.org/wikipedia/en/wiki/Banker%27s_algorithm)
It's not exactly what you are looking for, but I think it can help with getting the right idea.

Indeed it's rather structured like:

(amount, amount, amount, ....)


By the way, on second thought I wonder why I said that amounts should be integers.  Floating point values are necessary I guess.  But anyway one of the thing that bitcoin inspired me is that floating point values are nothing but very big integers.

But for the theoretical study it might be easier to consider real values.