Bitcoin Forum
December 10, 2016, 08:57:41 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: request for a barter algorithm  (Read 1864 times)
grondilu
Legendary
*
Offline Offline

Activity: 1134


View Profile
February 26, 2011, 01:04:13 PM
 #1

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:

Code:
randtrades() {
    for a in asset{1..10}
    do for b in asset{1..10}
    do
        if [[ "$a" != "$b" ]]
        then echo -$((RANDOM%10)) $a $((RANDOM%10)) $b
        fi
    done
    done |
    grep -v -e '^-0' -e ' 0' |
    sort -r |
    cat -n |
    sed -r 's/^\s+/#/'
}


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.

1481360261
Hero Member
*
Offline Offline

Posts: 1481360261

View Profile Personal Message (Offline)

Ignore
1481360261
Reply with quote  #2

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

Posts: 1481360261

View Profile Personal Message (Offline)

Ignore
1481360261
Reply with quote  #2

1481360261
Report to moderator
1481360261
Hero Member
*
Offline Offline

Posts: 1481360261

View Profile Personal Message (Offline)

Ignore
1481360261
Reply with quote  #2

1481360261
Report to moderator
1481360261
Hero Member
*
Offline Offline

Posts: 1481360261

View Profile Personal Message (Offline)

Ignore
1481360261
Reply with quote  #2

1481360261
Report to moderator
ribuck
Donator
Legendary
*
Offline Offline

Activity: 826


View Profile
February 26, 2011, 02:06:30 PM
 #2

It's for situations like this that "prices" were invented.
grondilu
Legendary
*
Offline Offline

Activity: 1134


View Profile
February 26, 2011, 02:28:52 PM
 #3

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.
markm
Legendary
*
Offline Offline

Activity: 1792



View Profile WWW
February 26, 2011, 02:59:44 PM
 #4

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...?)

Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
ribuck
Donator
Legendary
*
Offline Offline

Activity: 826


View Profile
February 26, 2011, 03:04:11 PM
 #5

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

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.
grondilu
Legendary
*
Offline Offline

Activity: 1134


View Profile
February 26, 2011, 03:08:04 PM
 #6

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.
markm
Legendary
*
Offline Offline

Activity: 1792



View Profile WWW
February 26, 2011, 03:19:05 PM
 #7

Take a look at FellowTraveller's OpenTransaction.

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

-MarkM-

Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
SmokeTooMuch
Legendary
*
Offline Offline

Activity: 873


View Profile
February 26, 2011, 03:45:22 PM
 #8

(-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.


Somehow this doesn't fit, does it ?

Date Registered: 2009-12-10 | I'm using GPG, pm me for my public key. | Bitcoin on Reddit: https://www.reddit.com/r/btc
You like what I'm doing? Why don't you send me a coin: 17Pj8jpUgY6qTaKgiopL5U48zxU4rTrkuB
grondilu
Legendary
*
Offline Offline

Activity: 1134


View Profile
February 26, 2011, 04:25:21 PM
 #9

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.
SmokeTooMuch
Legendary
*
Offline Offline

Activity: 873


View Profile
February 26, 2011, 05:15:55 PM
 #10

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
It's not exactly what you are looking for, but I think it can help with getting the right idea.

Date Registered: 2009-12-10 | I'm using GPG, pm me for my public key. | Bitcoin on Reddit: https://www.reddit.com/r/btc
You like what I'm doing? Why don't you send me a coin: 17Pj8jpUgY6qTaKgiopL5U48zxU4rTrkuB
grondilu
Legendary
*
Offline Offline

Activity: 1134


View Profile
February 26, 2011, 05:18:51 PM
 #11

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

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.
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!