Bitcoin Forum
June 19, 2021, 10:29:03 AM
 Welcome, Guest. Please login or register.
 News: Latest Bitcoin Core release: 0.21.1 [Torrent]
 Home Help Search Login Register More
 Pages: [1]
 Author Topic: request for a barter algorithm  (Read 2088 times)
grondilu
Legendary

Offline

Activity: 1218
Merit: 1005

 February 26, 2011, 01:04:13 PMLast edit: February 26, 2011, 04:34:55 PM by grondilu

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.

At the end of the day, the debate between communism and capitalism is not an economic one, because economics is not a reliable science.  It's a moral one.  It's whether or not people should be allowed to not care about other people's problems. I, for one, am not enthused by the idea of a world where everyone would be enslaved in order to avoid that anyone is miserable.
1624098543
Hero Member

Offline

Posts: 1624098543

Ignore
 1624098543

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

Offline

Posts: 1624098543

Ignore
 1624098543

1624098543
 Report to moderator
1624098543
Hero Member

Offline

Posts: 1624098543

Ignore
 1624098543

1624098543
 Report to moderator
ribuck
Donator
Hero Member

Offline

Activity: 826
Merit: 1008

 February 26, 2011, 02:06:30 PM

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

Offline

Activity: 1218
Merit: 1005

 February 26, 2011, 02:28:52 PM

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.

At the end of the day, the debate between communism and capitalism is not an economic one, because economics is not a reliable science.  It's a moral one.  It's whether or not people should be allowed to not care about other people's problems. I, for one, am not enthused by the idea of a world where everyone would be enslaved in order to avoid that anyone is miserable.
markm
Legendary

Offline

Activity: 2702
Merit: 1041

 February 26, 2011, 02:59:44 PM

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
Hero Member

Offline

Activity: 826
Merit: 1008

 February 26, 2011, 03:04:11 PM

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

Activity: 1218
Merit: 1005

 February 26, 2011, 03:08:04 PM

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.

At the end of the day, the debate between communism and capitalism is not an economic one, because economics is not a reliable science.  It's a moral one.  It's whether or not people should be allowed to not care about other people's problems. I, for one, am not enthused by the idea of a world where everyone would be enslaved in order to avoid that anyone is miserable.
markm
Legendary

Offline

Activity: 2702
Merit: 1041

 February 26, 2011, 03:19:05 PM

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

Activity: 870
Merit: 1015

 February 26, 2011, 03:45:22 PM

(-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
grondilu
Legendary

Offline

Activity: 1218
Merit: 1005

 February 26, 2011, 04:25:21 PM

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.

At the end of the day, the debate between communism and capitalism is not an economic one, because economics is not a reliable science.  It's a moral one.  It's whether or not people should be allowed to not care about other people's problems. I, for one, am not enthused by the idea of a world where everyone would be enslaved in order to avoid that anyone is miserable.
SmokeTooMuch
Legendary

Offline

Activity: 870
Merit: 1015

 February 26, 2011, 05:15:55 PM

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
grondilu
Legendary

Offline

Activity: 1218
Merit: 1005

 February 26, 2011, 05:18:51 PM

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.

At the end of the day, the debate between communism and capitalism is not an economic one, because economics is not a reliable science.  It's a moral one.  It's whether or not people should be allowed to not care about other people's problems. I, for one, am not enthused by the idea of a world where everyone would be enslaved in order to avoid that anyone is miserable.
 Pages: [1]
Jump to: