Saturday, March 1, 2008

What the heck is a math trade?

Many sites exist for trading objects or services of various kinds—my favorite example is a site for trading right or left shoes. Over on BoardGameGeek, there is a very active community of users who trade board games. The site lets you list games that you are offering and games that you want, and then automatically finds possible matches. Even with this support, however, finding and negotiating individual trades can be tedious. Enter Math Trades, which have been running regularly on BoardGameGeek for several years.

One frequent difficulty with individual trades is that, although you have something I want, I might not have what you want. What if we were able to get a third person involved? Suppose you have what I want, Tina has what you want, and I have what Tina wants. Then we can arrange a three-person swap. SwapTree is a site that will find such three-way and even four-way trades for you automatically.

But why stop there? Why not look for five-way loops, or even hundred-way loops? That's what happens in a Math Trade.

How a math trade works

First, a moderator announces the opening of the trade and lays down trade-specific ground rules. Everybody who is interested in participating lists the items they choose to offer in the trade. At a pre-determined time, the list closes to new entries.

Next, the participants review all the offers and decide which ones they want. For each item you are offering, you create a wantlist that says, in essence, “I would be willing to trade item 57 (my item), for item 22 or item 34 or item 119 or item 576.” Everybody sends their wantlists to the moderator by the announced deadline.

After a brief period for finding and correcting errors, the moderator runs special math trade software to find the most trades possible. The moderator then publishes the results, the participants exchange addresses, and drop their items in the mail.

A lot of trades

Note that the “most trades possible” can be quite a lot. The largest math trade to date involved 2320 items, of which 994 traded. These 994 items were broken into 7 trade loops, including one monstrous loop of 920 items. Just imagine standing in a circle with 919 of your closest friends and everyone handing their game to the person on their right!

(Actually, this trade involved 316 users, many of whom were trading multiple items. So that loop of 920 items wasn't really 920 people.)

Although math trades have been run regularly on BoardGameGeek for almost three years, it is only recently that trades of this size have become possible. About six months ago, I wrote TradeMaximizer, which has become the de facto standard software for math trades. TradeMaximizer improves on previous software by guaranteeing to find the maximum number of trades possible, and by doing so quickly, in under a minute for the large trade above and in just a few seconds for most trades. Previous software ran in hours or days, and even then might not find all the trades possible. I'll describe TradeMaximizer in detail in an upcoming post.

Beyond games

There's nothing specific to games in the idea of math trades or in TradeMaximizer. I know of math trades run for metal CDs (using earlier software) and for geocoins (using TradeMaximizer). If you have run a math trade in another community, or think you might like to, please post a comment here and let us know. Don't be afraid! They're easy to run if you keep it relatively small, and a lot of fun.

Probably the coolest application of math trades is for trading...kidneys!

No, this isn't some urban legend about waking up in an ice-filled bathtub. This is serious, life-or-death stuff.

When somebody needs a kidney transplant, they can often find a family member or friend who is willing to donate one. But what happens if the donor's kidney is biochemically incompatible with the intended recipient? Well, sometimes you can find two such donor-recipient pairs where each donor is compatible with the other recipient. By donating to the other recipient, each donor ensures that their intended recipient gets a compatible kidney. Three-way trades and four-way trades are also possible. Unlike ordinary math trades, however, larger loops are not supported. Oh, you can find the loops, but doctors won't perform the surgeries because the risks of something going wrong (such as somebody backing out at the last minute) are just too great.

A trio at CMU implemented a system that is now being used to find matches in a national list of donors every two weeks by the Alliance for Paired Donation. Their system differs from an ordinary BoardGameGeek-style math trade in two fundamental ways. One is the deliberate limit on the sizes of trade loops (which actually makes the problem harder, not easier). The other is the presence of altruistic donors—donors who give their kidneys to strangers without asking for a kidney for a friend or loved one in return.

16 comments:

Unknown said...

This reminded me of the Three Ballot voting scheme, at en.wikipedia.org/wiki/Three_Ballot_Voting

If you read the paper, at the end they talk about a possible way to simplify it further, which would involve trading voting ballots between other people before leaving the polling station. It sounds like there is some overlap here with Math Trades.

lofigeek said...

is this the stable marriage problem?

Unknown said...

Yes, this is the marriage problem; more formally, the maximum matching in a bipartite graph problem. And it's been solved for ages. Don't understand why anybody's algorithm would take more than a second or two to run because it's polynomial in time, order O(pq^2).

rgrig said...

What is the reason for ITERATIONS?

rgrig said...

I mean, I saw what it does, but I don't see why shorter cycles would be preferred.

Isamoor said...

Great software by the way. I'm running a local no-shipping math trade for our gaming group. I've allowed an "anything goes" policy and it's fun to see what the relative worth of a microwave is going to be :)

Chris Okasaki said...

rgrig,

The main algorithm optimizes the the number of trades and the cost of those trades. Iterating this algorithm to find multiple solutions that are tied according to those two criteria, lets you try to improve some third criterion that is not directly optimized by the main algorithm.

Right now, that's used to try to get shorter cycles. The benefit of shorter cycles is in case something goes wrong, and the affected cycle needs to be cancelled.

Chris Okasaki said...

lofigeek: It's not directly the stable marriage problem, although it's similar in some ways. The goal here is to optimize a global notion of happiness that is different from stability.

vanekl: Maximum matching in a bipartite graph doesn't necessarily produce trade loops. Instead, this uses minimum-cost perfect bipartite matching. And, yes, it's polynomial, but the graphs can be pretty darn big. (Also, the code hasn't been particularly optimized, because that wasn't necessary when trades had fewer than 1000 entries.)

Unknown said...

Chris: you are correct. But if a few preconditions are met, one is guaranteed a maximal matching that also creates a cycle:
1. the relation is not reflexive (the "seller" doesn't want his own product back).
2. the bipartite graph is connected.
3. the degree for each vertex in the bipartite graph is > 1. In other words, every "buyer" would be willing to trade for at least two products, and every product had at least two interested parties.

lawnun said...

I should preface with an explanation that while I think the concept is intriguing from a mathematical perspective, my inner sociologist is skeptical.

From an individual trader standpoint, I can see why the large-scale trades-within-trades (919 of your closest friends standing around in a circle) might not be a good idea. The math is great, but how do you ensure that A and B actually get to the follow-through once a match has been made?

For example, when I (briefly) looked over the game link example you provided, I wasn't able to find out how many actual trades were successfully completed. Although there was substantial data on how many trades had been arranged by the algorithm (which the site reported as received), it wasn't at all clear whether those trades actually took place.

Of course, the problems I'm curious about (laziness/forgetfulness/greed/shipping /cost differentials between distant trading partners) are of a human, and not really a mathematical variety. Still, I'd love to see if math could somehow overcome these issues.

Chris Okasaki said...

LegalGeek: I completely understand your skepticism. Still, the community on BoardGameGeek has thus far made it work.

Although there are occasional bad traders, they are quite rare. The vast majority of trades go through without a hitch. I don't have hard numbers available, but most math trades go through without any significant problems of the kind you're talking about. And by "most math trades", I mean the entire set of trades, not the individual trades within the math trade!

Part of this is due to the BoardGameGeek community, which is remarkably close knit and friendly (as internet communities go). The community is also self-policing; it keeps an eye out for bad traders, and actively shuns those it finds.

I'm sure another part of the success so far is the relatively low value of the items being traded, usually less that $100 worth.

I'm sure there would be more problems if this model were applied to a more anonymous community, or to items with higher values. One approach in such cases might be to require users to set up an escrow account before being allowed to participate.

ChuckT said...

I am currently running a Math Trade with TradeMaximizer for geocoins. We have 58 participants with 1437 total coins in the trade.

I ran the program with the completed want lists for the first time tonight and came up with less than 50% of the coins changing.


Num trades = 673 of 1437 items (46.8%)
Total cost = 673 (avg 1.00)
Num groups = 4
Group sizes = 501 142 17 13
Sum squares = 271623

From reading your blog I see that this is not an unexpected result, but I'm still rather disappointed that so few coins traded. I suppose the culprit is likely participants submitting short want lists for their coins.

At least it should cut down on shipping though -- I participated myself, and 23 of my 48 coins need to be shipped now :)

Thanks for the software!

rgrig said...

"I'll describe TradeMaximizer in detail in an upcoming post."

I didn't find the upcoming post so I tried to briefly describe the algorithm here: http://goo.gl/pi9XO

I hope I didn't misrepresent your program.

Chris Okasaki said...

@Radu: Yep, that's a good description.

Welton Rodrigo Torres Nascimento said...

Hi,

on your description of trademaximizer[1]:

> Although it is relatively straightforward to understand how prices work, it is extremely difficult to understand why they work to produce the desired result. I take no credit for inventing this part of the algorithm, which is a standard--albeit fairly obscure--algorithm in the computer science toolkit. My Eureka moment was in figuring out how to model the problem as a bipartite graph in such a way that the standard algorithm could be applied.

Would you mind explaining better? And which algorithm is this?

I solved a problem[2] using your software, but didn't understood very well how prices work.

1 - http://boardgamegeek.com/wiki/page/TradeMaximizer
2 - http://cstheory.stackexchange.com/q/11093/9090

Welton Rodrigo Torres Nascimento said...
This comment has been removed by the author.