James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
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. devil

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

Quote:
The set of disjointed directed cycles within a set of vertices that contains the maximum number of vertices.


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

Quote:
The set of disjointed directed cycles within a set of vertices that contains the maximum number of vertices with the lowest weight.


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.
5 
 Thumb up
0.01
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
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?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Matt Cobb
United States
Cortland
New York
flag msg tools
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Quote:
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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Matt Pritchard
United Kingdom
Nottingham
flag msg tools
Avatar
mbmbmbmbmb
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!
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
Kanedacorp wrote:
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.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Okasaki
United States
White Plains
New York
flag msg tools
badge
Avatar
mbmbmbmbmb
Quote:
The set of disjointed directed cycles within a set of vertices that contains the maximum number of vertices with the lowest weight.


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.

Quote:
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).


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.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
George Kinney
United States
Bellefontaine
Ohio
flag msg tools
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Regai wrote:
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 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.





 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Okasaki
United States
White Plains
New York
flag msg tools
badge
Avatar
mbmbmbmbmb
Quote:
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).


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.

Quote:
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 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.

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


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.).
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Okasaki
United States
White Plains
New York
flag msg tools
badge
Avatar
mbmbmbmbmb
Quote:
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.


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.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
B. Perry
United States
Colorado Springs
Colorado
flag msg tools
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Kanedacorp wrote:
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!


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.

Quote:
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.


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.

Quote:
with a brute force technique it will take approximately O(2^n ln 2) to complete.


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.

Quote:
Though the BF method has found a more optimum solution in a significantly shorter period (5 minutes versus 6 hours).


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?

Quote:
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.


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.

Quote:
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.


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 makes this cooler.

I've rambled long enough. I will have to come back and read over everyone's comments again. They're all well thought out and there are some very good points made.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
Hmm... I'll definitely look into the connected components. You are correct when you state that two groups of n/2 is MUCH faster than one group of size n.

I fear, however, that a math trade may be a case where there is one group of tradeables and one or more groups of untradeables. That is to say, it may be that using this approach would net the same results as the current weeding process that is used.

Since I have no algorithm book, perhaps a link to a web resource can be provided, or the algorithm posted here?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Okasaki
United States
White Plains
New York
flag msg tools
badge
Avatar
mbmbmbmbmb
Kayvon wrote:
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.


It can definitely happen that strongly connected components won't help for a particularly trade list, because everything (except the nodes that are weeded out) ends up in the same component. In that case, you haven't really lost anything because SCC algorithms are so fast. Plus SCC will take automatically care of any possible "weeding" strategy you could think of.

Kayvon wrote:
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).


Breaking things into strongly connected components will *never* eliminate a possible solution. If two games are "forced apart" into different components, it can only be because it was impossible for them to be involved in the same chain anyway.

Regai wrote:
I fear, however, that a math trade may be a case where there is one group of tradeables and one or more groups of untradeables. That is to say, it may be that using this approach would net the same results as the current weeding process that is used.


Sure that can definitely happen. SCC isn't guaranteed to help in all cases, but it is guaranteed never to hurt. Plus, to do a good job "weeding" using special cases, you pretty much have to iterate them (that is, keep re-running the special cases until they don't get any hits), and SCC will probably run faster than that *and* is guaranteed not to miss any special cases that you just didn't think of.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Okasaki
United States
White Plains
New York
flag msg tools
badge
Avatar
mbmbmbmbmb
Regai wrote:
Since I have no algorithm book, perhaps a link to a web resource can be provided, or the algorithm posted here?


The most common algorithm involves doing two depth-first searches, one on the original graph and one on the transpose of the graph, where the second DFS is performed in a certain order based on the results of the first DFS.

I've just done some poking around using Google and haven't found any good stand-alone descriptions of the algorithm. The good news is that SCC is already included in a bunch of libraries like Boost and LEDA. PM me with what programming language you're using, and I'll see if I can find a library for you.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
For the geeks who are playing the home game, we are currently talking about this: http://en.wikipedia.org/wiki/Strongly_connected_component

According to the wiki article, this would take V+E time to complete.... interesting, on a worst case scenario for 150 trades that would be only 22,650 loops.

Here is a link to Kosaraju's algorithm which should find all the Strongly Connected Components: http://lcm.csa.iisc.ernet.in/dsa/node171.html

It's late here and I really cannot think of how to translate that into computer speak, so I'll offer it up to everyone to chew on.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Roderick Schertler
United States
Charlottesville
Virginia
flag msg tools
badge
Avatar
mbmbmbmbmb
looking for the want lists from old math trades
I was going to go through the old math trades looking for the ones which posted the want lists, so I could have some real-life data with which to play around. If anybody has done this already, could you provide the lists so as to save others the trouble?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Okasaki
United States
White Plains
New York
flag msg tools
badge
Avatar
mbmbmbmbmb
Ok, here's a description of the strongly connected components algorithm.


visit(x):
mark game x
for each game y that x wants
if y is unmarked then
visit(y)
add x to beginning of FINISHED list

revisit(x):
mark game x
for each game y that wants x
if y is unmarked then
revisit(y)
add x to current component

scc:
clear all marks
clear the FINISHED list
for each game x in any order (such as numerical)
if x is unmarked then
visit(x)
clear all marks
for each game x in the order of the FINISHED list
if x is unmarked then
start a new component
revisit(x)
output the current component

Notice how the first pass (visit) looks at which games x wants, and the second pass (revisit) looks at which games x is wanted by.

And here's an example. Given the trade data

1 2 6
2 6 4
3 7 5
4 2 8
5
6 3 4
7 3
8 5 4

The first pass (the visit pass) will go

visit 1
visit 2 (from 1)
visit 6 (from 2)
visit 3 (from 6)
visit 7 (from 3)
done visiting 7, FINISHED = 7
visit 5 (from 3)
done visiting 5, FINISHED = 5 7
done visiting 3, FINISHED = 3 5 7
visit 4 (from 6)
visit 8 (from 4)
done visiting 8, FINISHED = 8 3 5 7
done visiting 4, FINISHED = 4 8 3 5 7
done visiting 6, FINISHED = 6 4 8 3 5 7
done visiting 2, FINISHED = 2 6 4 8 3 5 7
done visiting 1, FINISHED = 1 2 6 4 8 3 5 7


The second pass (the revisit pass) will then go

revisit 1
done with 1, component = (1)
output component (1)
revisit 2
revisit 4 (from 2)
revisit 6 (from 4)
done with 6, component = (6)
revisit 8 (from 4)
done with 8, component = (8 6)
done with 4, component = (4 8 6)
done with 2, component = (2 4 8 6)
output component (2 4 8 6)
revisit 3
revisit 7 (from 3)
done with 7, component = (7)
done with 3, component = (3 7)
output component (3 7)
revisit 5
done with 5, component = (5)
output component (5)

which leaves us with the components (1), (2 4 8 6), (3 7), and (5). The two singleton components, (1) and (5), can be discarded. The doubleton component (3 7) means that 3 and 7 should immediately trade with each other. That leaves only the component (2 4 8 6) for the rest of your algorithm to figure out what to do with.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
George Kinney
United States
Bellefontaine
Ohio
flag msg tools
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
BTW - the above post gives a good description, these links go into it a bit more:
http://www.ics.uci.edu/~eppstein/161/960220.html
and here's a python implementation (missing a lot of '_' chars) of the algorithm:
http://www.ics.uci.edu/~eppstein/161/python/SCC.py

Since I already have a DFS based trade finder I wrote in python, I quickly hacked it to take advantage of the SCC object from the link above.

A pass over the initial list does remove unwanted offers, and emtpy lists, but since that was a very trivial thing to do to begin with, it isn't a useful change.

In fact, running the SCC finder over the want lists of 15 past trades didn't produce a single one that didn't consist of a single large block and a bunch of singletons. No quick finds of 2 member lists.

But, it does turn out to provide a useful optimization within the DFS.

My program follows the simple algorithm :
1 for each offer->want pair :
2 do DFS to find complete cycle
3 remove cycle's members from graph
4 repeat until no more cycles found or graph empty
5 cache the result set if larger than last one cached

Step 3 is where the SCC search becomes useful. Originally, I would end up with a list of unused names, but any fraction of them were ones that weren't part of a cycle. And I had no way to know. But now I run the SCC finder, and then start a new cycle search on each SCC set with 2 or more components.

The end result is a massive speedup. One search that used to complete in 2 hours finished in 96 seconds just moments ago. WooHoo!

As I mentioned, my program is written in Python (+ psyco), and although it has its advantages, raw processing speed just isn't one of them. In this case its roughly 45x slower than TradeGenie over the same dataset, but that's not bad IMO, TradeGenie being compiled (C++?) and all.

So thanks for the pointer cokasaki, it proved most useful.

I also use a weighting scheme both for ordering the initial list, and for choosing which complete sets to keep.

The want lists are loaded into a dictionary, keyed by offer, with each entry being a list of wants. (keys = nodes, key+want = edge)

For each want list, I assign decending fractions to the items in the list. First is 1/1, then 1/2, then 1/4, etc. For a completed cycle, the weights of each trade (ie. edge) are looked up, and averaged. This final value is used as the 'satisfaction' of the trade. Essentially, it is just a measure of how close all the member trades were to the front of the individual want lists, thus hopefully more satisfying.

For the initial sorting, an 'overall satisfaction' rating is calculated which is the number of users wanting the offer plus the average satisfaction weight for all of those users wanting the offer. I added the second bit so that it becomes extremely unlikely that two offers can have the same final number, and thus won't be ordered arbitrarily.

Recently I've also been tinkering with subtracting the length of the users want list from this value as well, since very long want lists are real processing killers, and the more of the graph that's been culled before they are seen the better. (The SCC culling helps a lot with these, since they are usually found attached to less desirable offers, so they rarely survive very far into the DFS.)

Anyways, there are occassionally a set of maximum sized sets of cycles, so there is a need to determine which of them to keep. TradeGenie just keeps the first one it sees, while I've opted to also compare the 'satisfaction' ratings as well in an effort to keep as close the front of the want lists as possible. Whether the extra effort is worth it is debatable.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
B. Perry
United States
Colorado Springs
Colorado
flag msg tools
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
humeral wrote:
I was going to go through the old math trades looking for the ones which posted the want lists, so I could have some real-life data with which to play around. If anybody has done this already, could you provide the lists so as to save others the trouble?


I've done it to some extent. I posted a few of them on www.kayvon.org under "Examples" on the right-hand side.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
Gecko23 wrote:
In fact, running the SCC finder over the want lists of 15 past trades didn't produce a single one that didn't consist of a single large block and a bunch of singletons. No quick finds of 2 member lists.


I found the above to be true as well, with the single exception of my April Fools Math trade, which did find two SCC sets. One that was 3 in size and one that was 79 in size. This eliminated 10 more games than TradeGenie did.

At first I was excited about this, until I reviewed the data. It eliminated 8 games that successfully traded in the AprilFools list.....

I'm going to assume that my implimentation is flawed, but I would like other people to double check this result.


I'm and idiot.... I ran this on the list I have at work, which is missing the last minute additions/changes. I'll check it again at home.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
George Kinney
United States
Bellefontaine
Ohio
flag msg tools
badge
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Regai wrote:
I'm going to assume that my implimentation is flawed, but I would like other people to double check this result.


That'd be a lot easier if the want lists were posted with the geeklist or the forum entry...
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
Responding to this thread is like an excercise in Graph Theory.... surprise

cokasaki wrote:
Quote:
The set of disjointed directed cycles within a set of vertices that contains the maximum number of vertices with the lowest weight.


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.


Right, weights on the edges is what I was refering to.

cokasaki wrote:
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.


Currently, it looks like the graph itself is to strongly connected to break apart into components. I have a theory that it has to do with a few people with to many wants. I'll have to check into that.

cokasaki wrote:
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.


But eight people would disagree with you.

cokasaki wrote:
A squared distribution might be better (1,4,9,16,...) or maybe triangle numbers (1,3,6,10,...)?


Hmm... these would produce different results (both favoring the #2's) as such:
(8 #1's, 1 #9) (9 #2's)
Integer 17 18
Squared 89 36
Triangle 53 27


I'm not sure which cycle I would prefer. I'll chew on that some more.

cokasaki wrote:
In any case, when people have, say, 10 games in a want list, I don't think they can usually rank-order them precisely.


This is probably true, but anything more complex could make submitting wants difficult for the participants.


Kayvon wrote:
Quote:
with a brute force technique it will take approximately O(2^n ln 2) to complete.


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.


That is an approximation I came across while researching the problem. It fits pretty well with my observed results. Of course, the real time formula would have to take into account both the vertices and the edges.

Kayvon wrote:
Quote:
Though the BF method has found a more optimum solution in a significantly shorter period (5 minutes versus 6 hours).


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?


It is feasible, and may be a good idea. Remember though that BFS only outperfoms DFS in a few instances.

Kayvon wrote:
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 makes this cooler.

I've rambled long enough. I will have to come back and read over everyone's comments again. They're all well thought out and there are some very good points made.


No problems. This is a problem that I've toyed with for a while.


Gecko23 wrote:
Regai wrote:
I'm going to assume that my implimentation is flawed, but I would like other people to double check this result.


That'd be a lot easier if the want lists were posted with the geeklist or the forum entry...


I'll have the list up later tonight, but as I stated above I don't have the correct list in front of me right now.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
B. Perry
United States
Colorado Springs
Colorado
flag msg tools
Avatar
mbmbmbmbmb
Re: Math Trade Theory & Algorithms (Warning: Can Hurt Brain
Here's a question for everyone:

There's been a lot of talk concerning "weeding" out non-viable entries. TradeGenie's algorithm for this is already on par with everything that's been said. What about weeding wants? TradeGenie only has a very simple system to weed out wants from an entry's want lists that it knows will not be useful in the final outcome. There's got to be a way to eliminate some of the wants from some of the entries ahead of time, right? Currently, very few such entries are eliminated. What are some ways to do this?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Okasaki
United States
White Plains
New York
flag msg tools
badge
Avatar
mbmbmbmbmb
Kayvon wrote:
What about weeding wants?


Here are two possible approaches. First, if you've done a strongly connected components analysis, then any want of a game in a different component can be deleted. (Yeah, yeah, I promise not to mention strongly connected components any more tonight unless someone specifically asks. )

Second, if you do a "reachability" analysis, then if game x wants game y, but x is not reachable from y, then that want can be eliminated. A reachability analysis is really easy.


Define a 2D array R[1..N,1..N]
Initialize R so that R[x,y]=true if and only if x wants y
for i in 1..N do
for x in 1..N do
for y in 1..N do
if R[x,i] and R[i,y] then set R[x,y] := true

At the end R[x,y] is true if y is reachable from x, meaning that x wants y or x wants some other game that wants some other game ... that wants y.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
Regai wrote:
Gecko23 wrote:
In fact, running the SCC finder over the want lists of 15 past trades didn't produce a single one that didn't consist of a single large block and a bunch of singletons. No quick finds of 2 member lists.


I found the above to be true as well, with the single exception of my April Fools Math trade, which did find two SCC sets. One that was 3 in size and one that was 79 in size. This eliminated 10 more games than TradeGenie did.

At first I was excited about this, until I reviewed the data. It eliminated 8 games that successfully traded in the AprilFools list.....

I'm going to assume that my implimentation is flawed, but I would like other people to double check this result.


I'm and idiot.... I ran this on the list I have at work, which is missing the last minute additions/changes. I'll check it again at home.


Ok, when run against the final April Fools data, the SCC algorithm eliminated two additional games, so that is good. It's not terrific, but it has the potential of being terrific. There still were only two components one size 3 and one size 93.


cokasaki wrote:
Kayvon wrote:
What about weeding wants?


Here are two possible approaches. First, if you've done a strongly connected components analysis, then any want of a game in a different component can be deleted. (Yeah, yeah, I promise not to mention strongly connected components any more tonight unless someone specifically asks. )

Second, if you do a "reachability" analysis, then if game x wants game y, but x is not reachable from y, then that want can be eliminated. A reachability analysis is really easy.


The reachability analysis is made moot by SCC, since for two items to be in the same component they MUST be reachable. And since SCC provides a better weeding algorithm then what I have seen so far, I suggest it is used at least for weeding. (and if the above post is correct, SCC can be used to trim the items remaining after the first DFS cycle when finding multiple cycles.)
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
For those of you still reading this thread, I set up a website with my take on whats going on here so far. When you get the chance, check it out and let me know what you think.

[edit]It helps if I provide the URL:

http://www.clanperry.net/mathtrades/

[/edit]
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
1 , 2 , 3  Next »   | 
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.