Recommend
6 
 Thumb up
 Hide
45 Posts
1 , 2  Next »   | 

BoardGameGeek» Forums » Gaming Related » Trades

Subject: Math Trade Theory: Maximizing number of users trading rss

Your Tags: Add tags
Popular Tags: Math-Trade-Info [+] [View All]
Jeff Michaud
United States
Longwood
Florida
flag msg tools
On-Line Want List Generator - Hopefully Making Math Trades a Little Bit Easier
badge
Captain Kirk, Captain Picard, Captain Sisko, Captain Janeway, Captain Archer
Avatar
mbmbmbmbmb
As some of you know I added to Chris Okasaki's TradeMaximizer some additional "metrics" for when using his support for ITERATIONS (the original/default metric is sum of squares of the chain lengths). One of those metrics is "Users-Trading" which is the number of unique users in the results that are trading "at least one" item. I felt is was a good goal, after maximizing the number of trades (which thanks to Chris is "solved"), to "spread the happiness around"... the idea being that the more folks who don't feel a math trade was a complete waste of their time (because they didn't get any trades) will make the experience better overall... and those that got at least one trade are more likely to participate again, which is good for everyone.

The problem however is that my current approach, using ITERATIONS and the new metric, is that:

1. like when using older trade resolvers in trying to reach the number one goal of max trades possible, it's a brute force type approach, trying lots of iterations and using one of the best we got... even though there are probably other trade sets (results) that may have even more.

2. it's slow (with large math trades even though trademax may fine a result set in a minute, with 100 iterations, that's 100 minutes.... still fast by previous standards, is now slow).

3. Users-Trading metric is essentially incompatible with any use of priorities (there's very little variability in the various iterations). While I have mixed thoughts on priorities (I love the higher level of determinism they provide but most folks misunderstand priorities and are lead to a false sense of security), I don't want have Users-Trading not be usable when the organizer wants priorities.

So what I'd like is a TradeMax, with a single iteration of the algorithm... have these goals, in order:

1. max number of items trading
2. max number of users trading at least one item
3. priorities
....

I do have one idea.... one that actaully uses goal #1.... I'm not sure if it works and if it has side-effects (I'll list at least one I'm concerned about)

The Idea
1. create all the current edges TradeMax already creates

2. For each unique user found in the math trade create a node for that user (or two nodes using the "S(end)" and "R(eceive)" model Chris describes, such as UserA-S and UserA-R).

3. For each user, create an edge from each of the nodes represending each of that user's items to the node represending that user (for exaple if UserA had items "1" and "2" then that would be two edges... 1-S to UserA-R and 2-S to UserA-R. For this step I believe we don't want though to creae edges from teh dummy item to the user's own node.

4. From each user node (the "S" one) create an edge to each item node that wants at least one of that user's items. This should actually be the same number of edges created in step 1 and could be created at the same time... for example if userA's item "1" wants userB's item "3" you'd not only create the edge from 3-S to 1-R, but also the edge from UserB-S to 1-R. For this step we still create the edge even if that R node is a dummy item.

The idea is that since the algorithm is finding a result set with the max number of (non-dummy) nodes included, that a path/chain that traverses a "user" node that isn't already in the results will be favored, thus also maximizing the number of user's with at least one trade.

For example with the input:

(A) 1 : 3
(A) 2 : 4
(B) 3 : 1
(C) 4 : 2 5
(D) 5 : 4

there are two possible result sets:

1-3
2-4

or

1-3
4-5

the first set has only 3 users with at least one trade (user A has 2 items trading). The second has all 4 users with at least one trade (in this case all have exactly 1).

With this idea of a node for each user and associated edges the above result sets are:

1-A-3-B
2-4-C

or

1-A-3-B
4-C-5-D

The latter will be the one actually found by TradeMax because 8 nodes are visited instead of just 7.

Potential Problems
1. unlike for dummy item's, we are actually counting the extra (user) nodes (though obviously we wouldn't display then in the output and subject it from the count displayed in the output)...

... does this lead to the possibility that a trade set can be found where the actual number of real items trading is less because it's inflated by the user nodes (items)?

I admit I haven't fully thought this out but I'm "guessing" that it won't because unlike with dummy items there are actually two possible between a real item and an item that wants it (one direct and one going through the offering user's node, where as with dummy items the path is normallly only through the wanting users dummy item).

If there is a problem and we still want the #1 goal to be the max (real) items trading, we may be able to solve it using different costs for the edges going to and/or from the user nodes....

... however personally I think it may still be preferable to have an option where the #1 goal is to max out the number of users trading at least one item, even if fewer items overall are trading.

2. since we are creating about twice as many more edges than we are with TradeMax today, this is going to impact the speed (and memory usage) of TradeMax. I forget if the speed is linear or not with the number of edges, if it is then it's going to take twice as long.

Lastly I think this is compatible with priorities. If priorities are used then the additional edge from the user node to the item wanting it could get the same priority as the normal edge, and the edges from a user's own items to his own node would be 0 (or higher than any other priority if the above is a problem).

Big Brain Fart?
Did I completely under think this and this just plain can't work? Even if I didn't, are there other ways to do this?

I obviously haven't hacked TradeMax to try this out as otherwise I'd have answers to some of the questions above (and instead of this being a post about theory ....). Want to see if this looks promising or not before I spend time coding (though I don't mind if someone else codes it either) to try it out.

Jeff
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Eric Flood
United States
San Francisco
California
flag msg tools
badge
Avatar
mbmbmbmbmb
I haven't looked at the source code at all, but it should be possible to find all the ties from maximizing-items, then add in an attribute of userid between each item (ignoring if previously seen), then maximize that, before going to the priorities for a further tie-breaker. I guess it depends how the code handles the objects, though.

BTW, how many ties are typical of a math trade, on only the "maximize trades" list? Is there any way to see this output from the current release?

I've often done some retroactive fiddling to see what I (and others) might've gotten/not gotten if I (or others) had changed my (or their) wantlist(s). I've noticed it to be a really unstable system, sometimes changing dramatically if I just add/remove one want for one item listed.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Flying Arrow
United States
Pennsylvania
flag msg tools
badge
Avatar
mbmbmbmbmb
The number of tied result-sets is typically too large to search exhaustively. It's can be in the millions or more.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Flying Arrow
United States
Pennsylvania
flag msg tools
badge
Avatar
mbmbmbmbmb
JeffyJeff wrote:


The Idea
1. create all the current edges TradeMax already creates

2. For each unique user found in the math trade create a node for that user (or two nodes using the "S(end)" and "R(eceive)" model Chris describes, such as UserA-S and UserA-R).

3. For each user, create an edge from each of the nodes represending each of that user's items to the node represending that user (for exaple if UserA had items "1" and "2" then that would be two edges... 1-S to UserA-R and 2-S to UserA-R. For this step I believe we don't want though to creae edges from teh dummy item to the user's own node.

4. From each user node (the "S" one) create an edge to each item node that wants at least one of that user's items. This should actually be the same number of edges created in step 1 and could be created at the same time... for example if userA's item "1" wants userB's item "3" you'd not only create the edge from 3-S to 1-R, but also the edge from UserB-S to 1-R. For this step we still create the edge even if that R node is a dummy item.



The problem is that when an item wants a "user", there is no indication which item of that user the person wants. So you could have the following:

(A) 1 :
(A) 2 : 3 4
(B) 3 : 1
(B) 4 : 1 2


2-A-3-B

Item 3 doesn't want item 2, but because item 3 wants the "user A" node, a cycle can be formed where item 3 gets item 2.
1 
 Thumb up
0.01
 tip
 Hide
  • [+] Dice rolls
Jeff Michaud
United States
Longwood
Florida
flag msg tools
On-Line Want List Generator - Hopefully Making Math Trades a Little Bit Easier
badge
Captain Kirk, Captain Picard, Captain Sisko, Captain Janeway, Captain Archer
Avatar
mbmbmbmbmb
blueatheart wrote:
I haven't looked at the source code at all, but it should be possible to find all the ties from maximizing-items, then add in an attribute of userid between each item (ignoring if previously seen), then maximize that, before going to the priorities for a further tie-breaker. I guess it depends how the code handles the objects, though.

Doesn't work that way... see http://www.boardgamegeek.com/wiki/page/TradeMaximizer#toc9 ... it only loops N times and it's done Why it's so fast!
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Michaud
United States
Longwood
Florida
flag msg tools
On-Line Want List Generator - Hopefully Making Math Trades a Little Bit Easier
badge
Captain Kirk, Captain Picard, Captain Sisko, Captain Janeway, Captain Archer
Avatar
mbmbmbmbmb
FlyingArrow wrote:
The problem is that when an item wants a "user", there is no indication which item of that user the person wants. So you could have the following:

(A) 1 :
(A) 2 : 3 4
(B) 3 : 1
(B) 4 : 1 2


2-A-3-B

Item 3 doesn't want item 2, but because item 3 wants the "user A" node, a cycle can be formed where item 3 gets item 2.

Thanks, yea, there's my brain fart Looked good on my paper/graph

Back to the drawing board
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Michaud
United States
Longwood
Florida
flag msg tools
On-Line Want List Generator - Hopefully Making Math Trades a Little Bit Easier
badge
Captain Kirk, Captain Picard, Captain Sisko, Captain Janeway, Captain Archer
Avatar
mbmbmbmbmb
FlyingArrow wrote:
there is no indication which item of that user the person wants

What I really need is a way to pair two edges going into and out of the same node such that if it takes one edge in it has to take the companion edge out (I'd also need a lot more edges than I planned) but I have a feeling it's not possible with the algorithm

I do remember that Chris said that we can't play with dynamic edge costs because the algorithm requires them to be fixed in a run of the algorithm Probably can't also create edges dynamically either as I was thinking maybe the "user" nodes don't have any edges going in or out and are "inserted" with just one edge in and one out between an edge being inserted into the results for the first edge using one of those user's items. But readying Chris's description of the algorithm I don't think that works either
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
David Spitzley
United States
Belleville
Michigan
flag msg tools
Avatar
mbmbmbmbmb
Well, this may be obvious, but I'll toss it out there: since every receiver is also a sender, you only need to count the number of distinct receivers or distinct senders. As such, you are essentially talking about adding one additional map, from (say) the send nodes to a set of user nodes, and after you've completed the send-receive map you just find the size of the inverse of the send-user map.

How are the nodes and mappings being stored, anyway? I'm thinking in array terms, but I realize there may be some other sort of structure involved. If this whole thing is implemented with pointers, then it might actually be easier to use the approach above than I'm thinking.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Michaud
United States
Longwood
Florida
flag msg tools
On-Line Want List Generator - Hopefully Making Math Trades a Little Bit Easier
badge
Captain Kirk, Captain Picard, Captain Sisko, Captain Janeway, Captain Archer
Avatar
mbmbmbmbmb
Dspitzle wrote:
Well, this may be obvious, but I'll toss it out there: since every receiver is also a sender, you only need to count the number of distinct receivers or distinct senders. As such, you are essentially talking about adding one additional map, from (say) the send nodes to a set of user nodes, and after you've completed the send-receive map you just find the size of the inverse of the send-user map.

Yes, only need to "count" number of receivers *or* senders, and my (brain fart) proposal was to count senders (it could count receivers instead but it's the same problem FA pointed out).

However I'm not following your proposal about creating an additional (distinct?) map and how to integrate that into the existing graph that Dijkstra's algorithm is run on so that it maximizes the number of user's trading at lest one item. The algorithm doesn't look at counts. We need to "guide" the algorithm which is finding the "minimum-cost perfect matching" so that to meet the minimum-cost requirement means the resulting items (nodes) belong to more unique users (trading at least one item).

Dspitzle wrote:
How are the nodes and mappings being stored, anyway? I'm thinking in array terms, but I realize there may be some other sort of structure involved. If this whole thing is implemented with pointers, then it might actually be easier to use the approach above than I'm thinking.

Chris has documented it at http://www.boardgamegeek.com/wiki/page/TradeMaximizer#toc9
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Michaud
United States
Longwood
Florida
flag msg tools
On-Line Want List Generator - Hopefully Making Math Trades a Little Bit Easier
badge
Captain Kirk, Captain Picard, Captain Sisko, Captain Janeway, Captain Archer
Avatar
mbmbmbmbmb
JeffyJeff wrote:
We need to "guide" the algorithm which is finding the "minimum-cost perfect matching" so that to meet the minimum-cost requirement means the resulting items (nodes) belong to more unique users (trading at least one item).

What I'm considering now, after reading Chris's description of how TradeMax works a few times, is that maybe it can be done without creating any new pseudo nodes and corresponding edges...

... instead maybe we can play with "prices" on the either the sending or receiving nodes... when the price is recalculated based on whether or not the owning user of the node (item) has any edges in the current matching (if we add to the cost for user's with nodes in the matching, maybe we can not only max the number of users trading at least one item, but spread out the items trading more evenly... ie. lowest sum of squares of number of items trading by each user).

Requires more thought unless someone tells me it's another brain fart on my part
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Okasaki
United States
White Plains
New York
flag msg tools
badge
Avatar
mbmbmbmbmb
JeffyJeff wrote:

... instead maybe we can play with "prices" on the either the sending or receiving nodes... when the price is recalculated based on whether or not the owning user of the node (item) has any edges in the current matching (if we add to the cost for user's with nodes in the matching, maybe we can not only max the number of users trading at least one item, but spread out the items trading more evenly... ie. lowest sum of squares of number of items trading by each user).


That's what I've referred to in the past as having the edge costs change dynamically. That is, the cost of an edge changes during the execution of the algorithm. I don't think that will work, but it's not impossible.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
I believe that the way the algorithm works that dynamically changing the cost of each edge is the only way to accomplish the goal.

However, it could lead to a few problems.

1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Michaud
United States
Longwood
Florida
flag msg tools
On-Line Want List Generator - Hopefully Making Math Trades a Little Bit Easier
badge
Captain Kirk, Captain Picard, Captain Sisko, Captain Janeway, Captain Archer
Avatar
mbmbmbmbmb
cokasaki wrote:
JeffyJeff wrote:

... instead maybe we can play with "prices" on the either the sending or receiving nodes... when the price is recalculated based on whether or not the owning user of the node (item) has any edges in the current matching (if we add to the cost for user's with nodes in the matching, maybe we can not only max the number of users trading at least one item, but spread out the items trading more evenly... ie. lowest sum of squares of number of items trading by each user).
That's what I've referred to in the past as having the edge costs change dynamically. That is, the cost of an edge changes during the execution of the algorithm. I don't think that will work, but it's not impossible.

I definitely remember that you said "edges" can't have dynamic costs, and that's why I'm looking at node "prices" instead which actually are already updated/changed on each pass of the algorithm (though this may be a subtle point?)

Actually I was hoping for clarification on that too about the edges... when you say the edges can't (or shouldn't) change costs while running the algorithm... do you mean dijkstra's algorithm or the "minimum-cost perfect matching" finding (augmenting paths) algorithm (aka findCycle's) which runs dijkstra's algorithm once for each pass of in findCycle's?

I also saw the assertion in Heap.Entry.decreaseCost that the new node cost must be less than the previous cost?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Okasaki
United States
White Plains
New York
flag msg tools
badge
Avatar
mbmbmbmbmb
JeffyJeff wrote:
I definitely remember that you said "edges" can't have dynamic costs, and that's why I'm looking at node "prices" instead which actually are already updated/changed on each pass of the algorithm (though this may be a subtle point?)

Actually I was hoping for clarification on that too about the edges... when you say the edges can't (or shouldn't) change costs while running the algorithm... do you mean dijkstra's algorithm or the "minimum-cost perfect matching" finding (augmenting paths) algorithm (aka findCycle's) which runs dijkstra's algorithm once for each pass of in findCycle's?

I also saw the assertion in Heap.Entry.decreaseCost that the new node cost must be less than the previous cost?


In terms of "minimum-cost perfect matching", nodes do not have costs or prices. Only edges have costs. The algorithm maintains prices internally, but those prices have no external meaning.

Similarly, in Dijkstra's algorithm, nodes do not have costs or prices, but the algorithm internally maintains information about the best path found so far to each node.

I think the comment in the heap code is talking about nodes in the skew heap (the data structure representing the priority queue) rather than nodes in the graph.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
David Spitzley
United States
Belleville
Michigan
flag msg tools
Avatar
mbmbmbmbmb
JeffyJeff wrote:
Dspitzle wrote:
How are the nodes and mappings being stored, anyway? I'm thinking in array terms, but I realize there may be some other sort of structure involved. If this whole thing is implemented with pointers, then it might actually be easier to use the approach above than I'm thinking.

Chris has documented it at http://www.boardgamegeek.com/wiki/page/TradeMaximizer#toc9


What I meant is how are they stored in software?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Michaud
United States
Longwood
Florida
flag msg tools
On-Line Want List Generator - Hopefully Making Math Trades a Little Bit Easier
badge
Captain Kirk, Captain Picard, Captain Sisko, Captain Janeway, Captain Archer
Avatar
mbmbmbmbmb
Dspitzle wrote:
What I meant is how are they stored in software?

Vertex's and Edge's are classes... Vertex's contain an array of Edges, and Vertex's are kept in two different List objects (one for receivers one for senders) and then turned into arrays after they've all been created. Vertex's also go into the priority queue.

I still don't understand how adding another map will help implement this?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
David Spitzley
United States
Belleville
Michigan
flag msg tools
Avatar
mbmbmbmbmb
JeffyJeff wrote:
Dspitzle wrote:
What I meant is how are they stored in software?

Vertex's and Edge's are classes... Vertex's contain an array of Edges, and Vertex's are kept in two different List objects (one for receivers one for senders) and then turned into arrays after they've all been created. Vertex's also go into the priority queue.

I still don't understand how adding another map will help implement this?


I'm not sure either, I'm just trying to figure out how things are organized. Ultimately I may not be able to offer much help, but I'm still thinking.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
Okay, a thought...

I wrote a c# program a while back that found all feasible trades. It did a whole lot of processing of the data. Here is the link to the old thread for reference: http://www.boardgamegeek.com/thread/319975

What about using part of that idea here?

Basically, using "strict" priorities I first set all edges to a value of 2 and ran trademax. This gave me the trade value (which was 2x the number of games trading). Then I ran iterative passes to figure out which games could feasibly trade, by decreasing the values of edges to 1 and re running the trade. If the trade value decreased then the edge was feasible, the the trade value remained constant then that edge was not feasible. Depending on the size of the trade this process took a while (but for Carls springtime trade with over 2000 items, the whole feasibility tool ran in a little more than a half hour).

Now, if we track the out while finding the feasibility we know the largest number of users trading. If that number equals the number of feasible traders we can quit right there. We found a max user result. If the number of feasible users is greater than the max user result from the preliminary runs we can make a few more passes.

We would know which games MUST trade from the preliminary runs, so we can set ALL games from that user to a strict priority of 2. All games from users that may not trade can be set to a strict priority of 1. Then run trademax again. This run will favor the users who do not have a mandatory trade (but those that have a mandatory trade still get that mandatory trade). If the metric "users trading" is compatible with "strict priorities" and the iterations, we may be able to find the max user trading result set quickly.

This can be taken a few steps further and we could find the users that must be included in a trade even if they do not have a mandatory trade.

Removing all the processing for the various priority scales and I think this whole thing could probably run in less than half an hour.

If I get a chance, I'll try to put this together this week.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeff Michaud
United States
Longwood
Florida
flag msg tools
On-Line Want List Generator - Hopefully Making Math Trades a Little Bit Easier
badge
Captain Kirk, Captain Picard, Captain Sisko, Captain Janeway, Captain Archer
Avatar
mbmbmbmbmb
Hi James,

It sounds interesting... not the ideal I had originally hoped for (single iteration/run), but it sounds like it could improve on the current USERS-TRADING iterations metric... or in the least will at least let us know how close the number coming out of the USERS-TRADING metric is to the max.

I assume when you say "strict" you mean EXPLICIT priorities, and "trade value" you mean "total cost".

Explicit priorities should be compatible with METRIC=USERS-TRADING in this case (I may have TM set to split out a warning if any priority is in use but it can be ignored).... doesn't work with the other priorities because there is very little variability in the number of users trading when they are in use.

You do have me thinking also if changing costs which sounds like could be a problem especially trying to increase the costs for users with already one trade.. but decreasing costs instead... for other users. Ie. set all edge costs (except the self edges and the ones for dummies that are already set to 0 I think) to the same value (at least 1 more than the number of items)... then each time we add an edge decrease the cost of all other edges by 1 except for those edges belonging to the same user. But decreasing edge costs may break the algorithm like increasing. May just have to code it sometime (don't have time right now) and watch it blow up
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Okasaki
United States
White Plains
New York
flag msg tools
badge
Avatar
mbmbmbmbmb
grimstuff wrote:
This is why I'm scared of math trades. Yeah, I've read the math trade guide someone posted, but it scared me away also. I must be rather dumb.


Don't be scared by this. This is talking about stuff that only a few people need to understand. Here's an analogy. You can drive your car quite well without understanding anything that happens under the hood. Having that understanding might allow you to be a slightly better driver, but the vast majority of drivers get by just fine without it.

Similarly, the kind of stuff being talked about here is stuff that your mechanic might need to know about, but you don't.
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Okasaki
United States
White Plains
New York
flag msg tools
badge
Avatar
mbmbmbmbmb
Regai wrote:

This can be taken a few steps further and we could find the users that must be included in a trade even if they do not have a mandatory trade.


I wonder if it might be quicker just to work with feasible/mandatory users from the beginning, and skip tracking whether individual items are feasible/mandatory.

It would work in a very similar way as for items, but by decreasing (for feasible)/increasing (for mandatory) all the wants of a particular user.

The hope is that there are a lot fewer users than items, often by a factor of 5 or more.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
James Perry
United States
Spring Hill
Tennessee
flag msg tools
badge
Ex-Term-In-Ate
Avatar
mbmbmbmbmb
cokasaki wrote:

The hope is that there are a lot fewer users than items, often by a factor of 5 or more.


We can certainly explore that, however, my fear is that some users will have say 10 or more items, but only one feasible trade.

Though, we could definitely do feasible items and not feasible wants. That would reduce the number of checks.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sparr Risher
United States
San Francisco
California
flag msg tools
designer
Avatar
mbmbmbmbmb
Reviving this thread, 5 years later. I have an idea:

First, to make sure I understand part of the algorithm correctly:

While assembling the minimum-cost perfect matching, the important step that gets repeated is to take a partial matching and find a minimum-cost augmenting path to add one edge (or more?) to the matching. If there are two or more possible such paths tied for the minimum cost, then there are [possibly] multiple possible minimum-cost perfect matchings to be reached. To get different results from different iterations, the tied path options are chosen between randomly, based on a seed.

This is where my idea branches off. What if that decision, between two tied augmenting paths, was [optionally] made in favor of the path with the highest net change to the number of users participating in the trade?

Would this produce the max-users result? It would definitely produce a result involving more users than most other potential results. I'm not very strong with graph theory, and I'm rusty on algorithms in general. My first and biggest fear in suggesting this is that this approach may be subject to a local maximum problem.

If local maxima are not a problem (someone might be smart enough to simply tell me that they aren't) then this is a solution, right?



If local maxima ARE a problem then I have a further idea, but it's more complicated, and closely mirrors another implementation that has probably already occurred to you folks and been discarded:

Instead of re-running the algorithm with different random seeds, it would be possible to create a tree structure of every possible path decision at each step of the process, and populate the entire tree with every possible result. I suspect this is not done because of the staggering number of possible results in a large trade. (If I'm wrong about that, I'd like to know why this isn't done.)

However, reducing the number of branches from every possible path decision to only the max-users possible path decisions would make the tree significantly smaller. If that tree is small enough to fully calculate, would it contain the desired solution? Or might there still be a maximum solution that requires at least one "downward step" to reach?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sparr Risher
United States
San Francisco
California
flag msg tools
designer
Avatar
mbmbmbmbmb
My Java is really rusty, and it's late, so I'm currently failing to get started on testing my idea. I've gotten this far:

In Graph.java, in dijkstra(), I think this line is responsible for keeping only the first-found lowest-cost edge in the current augmenting path:

if (cost + c < other.heapEntry.cost()) {

What needs to happen here, instead, might be something like the following:

if (
cost + c < other.heapEntry.cost() ||
(
cost + c == other.heapEntry.cost() &&
other.user is not in the current matching
)
)

This might require keeping track of, or immediately counting, which users are trading in the current matching up to this point.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sparr Risher
United States
San Francisco
California
flag msg tools
designer
Avatar
mbmbmbmbmb
I'm moving this idea to http://boardgamegeek.com/article/15083487#15083487 so it's easier to find in the future.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
1 , 2  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.