To revive an old subject, Math Trade Theory & Algorithms.

First, if you don't know what a math trade is go here:
Math Trade Guide: http://www.boardgamegeek.com/thread/93555

Here are a few more reference threads:

Original Math Trade Algoriths: http://www.boardgamegeek.com/thread/88807/page/1
Math Trade Guide Discussion: http://www.boardgamegeek.com/article/756050
TradeGenie Q&A: http://www.boardgamegeek.com/article/802289#802289

One thing, I want to make clear before we start: I LOVE TRADEGENIE! However, I would like to find out if it is the best solution, and it may very well be the best.


Now to the Math behind a math trade.

A math trade problem is a problem in Graph Theory. To put it in Math speak, what we are looking for is:



And if you want to factor in a satisfaction type protocol, then the problem would be phrased:



I summize that the problem is NP-hard, but it has been suggested by a mathmatician I've been in contact with that the problem is intractable (that is no algorithm can exist which can compute the answer in polynomial time) so brute force is, in his opinion the only way to solve the problem. The brute force method can be either Breadth First (BF) or Depth First (DF).

Here is the problem, with a brute force technique it will take approximately O(2^n ln 2) to complete. For those of you playing the home game, for a Math Trade with 150 entries that is more than 2.85 quattuordecillion (thats 2.85 * 10^45) loops through the data, to put it differently it would take over 121 years on my 3GHz machine with 1GB RAM to go through ALL of the data, but a set of 50 games only takes slightly more than 2.25 * 10^15 loops (on the same machine takes about 1 to 2 seconds). For this reason, I believe smaller caps on the number of games are better, but only if the games involved in the Math trade of a quality that a majority would want.

So realistically we want the algorithm that gives us the best possible answer in a reasonable amount of time.

The program I wrote approched this problem from the Breadth-First (BF) angle, where as I believe TradeGenie approaches it from the Depth-First (DF) angle.

Both programs go through a weeding process were all games that cannot result in a trade are removed from the set of vertices. This reduces the scope of the problem significantly (by a factor of ~2 per game weeded out).

The BF method will find short cycle solutions quickly (first it finds all the direct trades, then all the 3 person cycles, 4 person, etc). The problem here is that it grows each cycle and therefor would take exponentially longer and longer time to find the longer cycles. In the 150 game example, a depth of 2 takes under 1 second, a depth of 3 takes 5 seconds, a depth of 5 takes five minutes, a depth of 7 take several hours.

The DF method will find some long cycle solutions quickly, but the starting point will not vary between runs until ALL cycles for that starting point have been exhausted.

The typical result here is that the game that is choosen to start will almost always get its first or second choice (and depending on the set of wants several games down stream may have the same results). It is impossible to predict how long it would take for the starting point to change since the only way to know that is to know all of the cycles.

After running my program against several data sets and comparing the results to TradeGenie, I find that my program will find better solutions in about one third of the sample data sets. When a better solution is found by my program, the processing time is often the same for both programs. Though the BF method has found a more optimum solution in a significantly shorter period (5 minutes versus 6 hours).

Given that both my program and TradeGenie generate the same answer set for small sets of data (70 or fewer games) and that in larger datasets TradeGenie appears to out perform my BF approach, I am willing to concede that for math trades that the DF approach may be the best approach.

TradeGenie selects the MOST Desired game as the starting point. This is a good start, and may well lead to the best approximation of the answer. The most wanted item, is the item that will be included in the highest number of cycles, and so forth for the second most desired game. Though I can derive a set of data that would prove this assumption false, I have no problem with the most desired game getting his top choice.

If TradeGenie does not already take into account games that have been weeded out for determined desire ability, it should. (For example, if Bob wants Advanced Civ for his Monopoly, but no one wants his Monopoly, then his trade should not be counted for the desirability for Advanced Civ for the purposes of the Math Trade algorithm).

Adding weight to the cycles will increase the processing time, but can result in better trades. Given two sets of cycles with equal number of vertice the one with the lowest weight would give us the best set of trades (highest total desirability).

I propose a simple integer weight scheme: 1 for the first game in the want list, 2 for the next, etc.

Since this is already a lengthy post, I'm going to stop here and open it up to discussion about the theory & assumptions, before getting to deep into finding a solution.

Hmmm... in reviewing the above post, I have come to the realization, that the most wanted game may not be the best start point. While it is in the maximum number of PATHS that is not the same as the maximum number of cycles. [edit] Heck, even that isn't true.... hmmm. [/edit]

A game wanted by 50 people but has no wants is not a cycle. Similary if the game only wants one or two games that in turn want it only, means that it is only part of one or two cycles.

The best game to start with should be the game that is in the highest number of cycles. But how to determine that without find all of the cycles first?

Maybe you can approximate it by assigning each game a Tradeability Score, which could be something as simple as adding the number of want lists that include a particular game, plus the number of wants in that game's want list.

This could be done after all the non-tradeable games have been filtered out.

Just a thought.

You broke my brain!
I'm going to assume I don't need to understand all that to moderate a math trade, otherwise I'm in trouble!

You don't have to understand it, but it may help you explain why a certain trade happened when there was an equal or better trade available.

I think you want weights on the edges, not the vertices. Weights on the vertices would mean everybody agrees on the value on a game; weights on the edges mean each person can have a different value for each game.



A better form of weeding is to break the original graph into its strongly connected components. Games in different strongly connected components cannot interact in any way, so each strongly connected component can be solved separately. With luck, a big graph might decompose into a couple of big components of maybe a third or half the size, plus a number of small components. Games that cannot be traded form singleton components, which can be deleted. Components with two or three vertices are also low-hanging fruit: there's exactly one possible trade for a size-2 component, and either one or two 3-way trades in a size-3 component.

You can also get a huge payoff from the big components. For an exponential problem like this, solving two problems of size N/2 instead of one big problem of size N takes about the square root of the original time. Of course it may turn out that most of the vertices end up in one great big component, but that's ok -- SCC algorithms are cheap enough that you haven't wasted much.

The first two steps are to first remove any user from want lists who themselves want nothing (since they will never be a part of a cycle), and then to count up how many wants there are for each offer, and if any are unwanted, then deep-six them too for the same reason.

Then is the time to worry about ordering and weighting, once the set is reduced to those that can actually be in trades.

Although the possible paths does increase with the number of offers, the size of the want lists is a huge factor in how long the processing takes. Your original estimate of total cycles is high, every combination of offers doesn't actually exist, only some fraction of them. (Which is why I too have been tinkering with a depth-first approach, a lot of branches don't lead anywhere useful.) But that fraction is then effectively multiplied by the length of every want list.

And you are of course right, there is no way to know how many cycles a user is in without checking them all, the very definition of NP-hard. (or close to it. )

But a user who has a popular offer is more likely to be in any result set, simply because so many other offers lead to it. Therefor it is a reasonable assumption that there is a greater chance that it is a member of the greatest result set as well. The results of the last 15 or so trades have bourn this out.

I think the only real improvements anyone can make at this point is in coming up with a better way to short-circuit dead-ends while the graph is being walked, or throwing a lot more CPU cycles at it.

Right. If you do the strongly connected component trick, then you'll end up picking a different starting point for each component, presumably the game that is considered most desirable only counting "votes" from other games in the same component.



I really don't think assigning a single weight (overall desirability) to each node is a good idea. The weights that arise from individual lists are weights on the edges, not the vertices. I do admit, however, that dealing with weighted edges is probably slower than dealing with weighted vertices.



Ok, this does sound like weights on edges, rather than on vertices, unless you are summing all these points to come up with the desirability of a vertex? But summing these points would be a really bad way to get a single number for desirability.

If they are weights on edges, then I'm not sure a 1,2,3,... distribution makes sense. For example, consider two 9-game cycles. Which would be better, eight 1's and one 9, or nine 2's? That's a philosophical question about which we can easily disagree, but I lean toward thinking the nine 2's is better. A squared distribution might be better (1,4,9,16,...) or maybe triangle numbers (1,3,6,10,...)?

In any case, when people have, say, 10 games in a want list, I don't think they can usually rank-order them precisely. Something I tried in a math trade I ran a few months ago was to have only two levels of priorities: for each game, you listed your high-prioritiy wants and your low-priority wants, and the order in which games of the same priority were listed was irrelevant.

This scheme is easy to generalize to as many levels as you want, without significantly complicating the want lists. Here are two easy schemes.

First, you can put semicolons between groups of equal priority. For example, if you said "1 2 3 4; 5 6; 7 8 9" this would mean you were trading 1, and you had three high-priority wants (2,3,4), two medium-priority wants (5,6), and three low-priority wants (7,8,9). This works best if you expect each group to typically have more than one game.

If you expect many groups to contain only a single game, then another format is "1 2 (3 4) (5 6 7) 8" where you are trading game 1 and have four levels of priority 2 by itself, 3/4, 5/6/7, and 8 by itself. This can degenerate into lists of exactly the same format as today's lists (eg, "1 2 3 4 5") with exactly the same meaning as today's lists (I want 2 more than 3, 3 more than 4, etc.).

For what it's worth, the strongly connected component trick will do this automatically, plus quite a bit more.

Probably most people who have bothered to read this far already know what a strongly connected component is, but just in case... A strongly-connected component is a set of nodes such that every pair of nodes in the component is connected by some "cycle" (but not necessarily all by the same cycle). If two nodes are in different components, then there is no cycle that contains both. (I put "cycle" in quotes above because it's not quite the truth, but it's close enough for now.)

There is a blindingly fast algorithm for breaking a graph into its strongly connected components, discussed in just about any algorithms textbook.

Strongly connected components naturally take care of special cases such as games with empty want lists, as well as games that nobody wants. Plus, for example, games that are only wanted by games that nobody wants.

It can also easily happen in real math trades that you can get several big components. For example, you might have a bunch of people trading low-valued games and a bunch of people trading high-valued games. Usually, the people with the low-value games want the high-valued games, but not vice versa, so the two groups naturally separate out into two (or more) components. The same kind of thing can happen with, say, wargames vs Euros.

And getting those big components is a HUGE win. Dealing with two groups of, say, size 75 instead of one group of 150 gives you a ridiculous speedup.

That may well sum everything up.

The theory behind math trades is interesting to many, but not necessary to run the trade. If you can use the program, you can run the trade. (If you can't, you need to PM me so I can explain it better.) If/when people complain that they weren't included in a trade, send them to a thread like this where we can explain it mathematically.



Thank you very much. It's not the best solution possible, but it's definitely the best available (for now). A lot of thought went into making it more effecient. You've reproduced much of what went through my head when I was first creating it.

When I first wrote TradeGenie, I thought a computer could easily breeze through all possible compinations in a matter of seconds. It took me all morning to write (initially) and when I ran it I thought it was stuck. I soon realized the vast complexity of the problems at hand and spent the next several months making improvements to the TradeGenie engine. Since then, TradeGenie has increased its speed several thousand-fold. I'm still working to make it faster, but that's harder and harder to do.



I'd like to see the math on that. There is, of course, no entirely accurate equation as the want lists can vary in size and complexity.



What if we incorporated something like that into TradeGenie? It could time-share its first few minutes by doing a BF search at the same time. Is that feasible?



I'm working on an algorithm that more acurately predicts the best starting point. There's an overhead to it, but it should pay for itself.

I've been working on it for 3 months now. Incidentally, I started my new career 3 months ago. That's where most of my time has gone. Sadly, TradeGenie took a back seat.



That's a good idea. I played around with that early on, hoping that trade lists could be broken apart and solved as pieces. I quickly found that the trade lists are sufficiently intertwined as to prevent this from being a viable option.

I'm also very reluctant to force major "nodes" (or high-popularity entries) apart from each other because of the whole idea behind TradeGenie. TradeGenie was created to search every possibility and find the "best" solution. In making it run faster, I have merely eliminated redundant checks (e.g. checking entries that have no wants).


Before it slips my mind, I want to thank James Perry not just for starting this thread, but also for finding a very obscure bug in TradeGenie earlier today. It'd be very hard to reproduce, but I always feel better having one fewer bug in TradeGenie. (In particular, I don't want to be accused of ruining someone's chances in a math trade because I didn't program TradeGenie well enough.) Also, I have a brother named James Perry, which only