Swaptree isn’t the first to try online bartering — Peerflix, Bookins, and La La help people trade movies, books, and CDs, respectively, while SwapThing lets users combine goods, cash, and services.
But it is, significantly, the first site to pull off direct trades between more than two people: Thanks to a nifty algorithm designed by Boesel, Swaptree can engineer three- and even four-way trades among users who want different things.
…For instance, one person sends a book to a second person, who sends a CD to a third, who sends a DVD to a fourth, who then sends the first person a videogame. Of course, ferreting out possible trades among tens of thousands of items requires intense computing. "The first four-way trade took 20 minutes to complete," Boesel says. His team has since squeezed the time down to one-fifth of a second.
Read more here. If this kind of procedure is generalizable, what does it imply for the path of future money demand and the price level? Of course it does require that everyone send what he or she promises to send…
If you generalize it very far, you get computationally intractable problems. I was dimly aware of this, and using Google to find the first hit on “combinatorial auction”
http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=10665
and reading the abstract, it looks as though a central problem is called the “winner determination problem” and a bit of search on that shows it’s an “NP complete” problem. One immediate consequence is that it’s straightforward for a computer scientist to generate a family of moderate-sized auction test cases which have good solutions which the program won’t be able to find in any reasonable time. (Solution time will grow faster than any polynomial function of the size of the test case.)
So “If this kind of procedure is generalizable” has an in-principle answer “no, it’s not [infinitely] generalizable.” But it is still an interesting question how much benefit we can get from the cases which are small or regular enough that we can solve them quickly. (And the “combinatorial auction” points into a vast literature on that question.)
I should note that the finding-trade algorithm is only efficient if you execute trades as you find them or if you cap the size of the trades you consider. The number of cycles can be exponential, which can indeed make the problem NP-complete, but that only matters if you are intentionally looking for the long, complex cycles. Presumably SwapTree prefers short cycles to Hamiltonian paths involving every member.
Using cutting-edge computer technology to go rocketing back to the early paloelithic. Amazing.
What does this imply about money demand? It implies that even in the post-dot-com era, anyone with an interesting idea and a website can demand a couple million from venture capitalists.
Peter Ash: alvin roth wrote some papers on kidney exchange for this kind of algorisms. thats things are part of marriage market theory courses
http://kuznets.fas.harvard.edu/~aroth/alroth.html#KidneyExchange
This post reminded me of the “red paper clip” guy that you posted about a while back:
http://www.marginalrevolution.com/marginalrevolution/2006/04/turn_the_intran.html
Although at present Swaptree is limited to books, CDs, DVDs, and videogames, perhaps in the future someone will be able to offer a paper clip in exchange for a fish pen, exchange the fish pen for a … (several steps omitted) … one year’s rent in downtown Phoenix … and eventually exchange for a house.
The world is filled with people with stuff that they are willing to trade, the hard part of barter is aligning the necessary double coincidence of wants. Swaptree’s trading algoriths can now manage — what would you call it — a triple- and quadruple coincidence of wants. The rest is mostly a question of computing power and building a database of offers.
Boardgame enthusiasts have been doing this on boardgamegeek.com for a while now. See here
http://www.boardgamegeek.com/thread/93555
for the guide, and here
http://www.boardgamegeek.com/article/892791
http://www.boardgamegeek.com/geeklist/14224
for an example.
asus z9100 battery
Comments on this entry are closed.