Recommend
6 
 Thumb up
 Hide
5 Posts

BoardGameGeek» Forums » Gaming Related » Trades

Subject: Idea for a more flexable Math trade algorithm rss

Your Tags: Add tags
Popular Tags: [View All]
Nathan Triplett
United States
Portland
Unspecified
flag msg tools
mbmbmbmbmb
tldr version: I propose a more flexable math trade algorithm. If it would be sufficently useful, I would consider trying to write the code for it. Please let me know your thoughts.

General Idea:
I have been thinking about math trades lately, and that they are often very inefficent. Especially in the case where I have 3 or 4 lower valued items I'd like to trade for 1 higher valued item. Or in most any case where you want to trade several items at once.

This is because while several people might want the first game I am offering, and several other might want the second game I am offering, no one wants both very badly. So my trade fails. Looking around I found this thread which attempts a clever solution:
http://www.boardgamegeek.com/article/1173108

In this method, each person values their own games they have for trade and values every game they want. Then the algorithm finds loops such that everyone makes trades which increase their personal value.

Unfortunatly, it doesn't seem to be active anymore. I've been considering, therefore, to start work on a standalone piece of code that will do something similar. Ideally, this will take a text file (full of everyone's wants and owned games) as input, run, and output the set of trades such that everyone is better off than before and has the most games being traded.

Example wrote:

3 people, A, B, and C. They decide to put the following games up for trade:
A puts up A1, A2, and A3.
B puts up B1, and B2.
C puts up C1, C2, and C3.

Now this list is made public to all three traders and they value all of the games. They are required to value all of their own games, and any of the others they want.
A values: A1=10, A2=15, A3=30 : B1=12, B2=6, C1=8, C2=5
B values: B1=60, B2=75 : A1=40, A2=35, A3=60, C1=65, C3=25
C values: C1=7, C2=9 C3=11 : A1=8, A3=10, B1=4, B2=5

Note that they all used different scales for valuing their games. That is just fine, all that matters is how a given trader values games in relation to each other.

The list of values is put into an algorithm which returns a set of trades such that all players come out as good or better than the left off. For example, it would discover the trade that A1, B1, and C1 should all be passed around. Leaving the end result like this:
A: A2, A3, B1. Total value of 57, up from 55.
B: B2, C1. Total value of 140, up from 135.
C: C2, C3, A1. Total value of 28, up from 27.



The Algorithm
Step 1:
Input all of the data of trades and values.

Step 2:
For each trader, create the list of what they would minimally accept in exchange for each item they are offering for trade. Minimally meaning that if they would accept items 1, 2 and 3 in exchange but also accept items 1 and 2. Then only include the latter.
Example wrote:

A's Valuations from previous example:
A values: A1=10, A2=15, A3=30 : B1=12, B2=6, C1=8, C2=5


So the list would look like this:
A will trade: A1->B1 A1->B2+C1 A1->B2+C2 A1->C1+C2 A2->B1+B2 A2->B1+C1 A2->B1+C2 A2->B2+C1+C2 A3->B1+B2+C1+C2 A1+A2->B1+B2+C1

Make a similar list for trader B and C.


Step 3a:
Pick the first trade out of the list. In our example that is A1->B1. This means you add a copy of A1 into the vacuume** and take a copy of B1 out of it (minus 1 copy of B1 in the vacuume).
Step 3b:
For each game with a negitive copy in the vacuume, pick the first trade from the list that provides that game. Add and remove appropreate games from the vacuume. Repeat until the vacuume is empty or no valid trades can be found to empty it.

In our example. We need to add a copy of B1 into the vacuume. B1->C1 is a valid trade on B's list. So use that. Now we have 1 copy of A1, and -1 copy of C1 in the vacuume. Look for a trade giving C1. C1->A1 is a valid trade in C's list. And makes the vaccume empty.
Step 3c:
If the vacuume is not empty go to Step 3d. Otherwise, record the number of trades made (1 in our example) and with the remaining games that have not been traded, repeat steps 3a and 3b.
Step 3d:
Since the vacuume is not empty, undo last trade and try another one. If no other trades, undo last two trades and try another. Repeat recursively until all options have been exhausted. Be clever about removing items from the list that have been used to avoid double counting.

**by vacuume, I mean a space where we can keep track of how many games are needed to be given up and how many are in need of someone to take them. The algorithm finishes when the vacuume is empty again. And yes, I am a physicist.

Step 4: Of all of the recorded successful trades, choose the one with the most games traded. That is the one to use.

Conclusion
There you have it. Hopefully the idea and the algorithm make sense. If not, please let me know and I'll try to clarify. So is it worth my time to try and impliment this in C++? It will be very complex in time, so will only work for relatively small numbers of people I imagine. Lists of 100 people will almost certainly be impractical. Especially as I am not promising highly optimized code. But it could be fun to try.

Let me know what you think, or if you have a better algorithm to do the same thing.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
David Thompson
United States
Portland
Oregon
flag msg tools
Avatar
mb
I ran a similar trade in February, and agree that a system like you describe would be ideal. The thread details some of the ideas, successes and obstacles encountered. Chris Okasaki and Ryan Gatti worked from different angles to solve the problem, and I think both would have good insight to some of the challenges of writing efficient code to solve the problem.
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Nathan Triplett
United States
Portland
Unspecified
flag msg tools
mbmbmbmbmb
Oooh good thread, thank you. I was searching for something like that but I never seemed to find your thread. And better still, it has a good data set to compare against if I do get the code written.
 
 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
themilkcrate wrote:
I ran a similar trade in February, and agree that a system like you describe would be ideal. The thread details some of the ideas, successes and obstacles encountered. Chris Okasaki and Ryan Gatti worked from different angles to solve the problem, and I think both would have good insight to some of the challenges of writing efficient code to solve the problem.

Thanks Dave, didn't realize (or remembered if I did know) you guys had run one, very interesting... I only remember the other thread that was just a proposal/discussion at

http://www.boardgamegeek.com/thread/296868

trip11 wrote:
I have been thinking about math trades lately, and that they are often very inefficent. Especially in the case where I have 3 or 4 lower valued items I'd like to trade for 1 higher valued item. Or in most any case where you want to trade several items at once.


The biggest problem is that it doesn't work well for "shipping" math trades because even though you may only have to pay to ship one item so it's no more cost to you... those 3 or 4 lower valued items may very well come from different individuals and hence it becomes very inefficient fast An algorithm that factors in shipping may be possible though (so for example you don't end up shipping 5 low valued items to 5 different folks to get one comparable or higher valued item but that the 5 different packages you have to ship cost more to ship than what you receive, but factoring in that if 2+ items are going from one user to another user that the shipping cost is only incremental instead of multiplied).

The other problem whether shipping or no shipping is to make sure there is some form of duplicate protection, I remember trades where I've seen folks receive 4 copies of the same game.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Ryan Gatti
United States
Portland
Oregon
flag msg tools
badge
Avatar
mbmbmbmbmb
First, the trade we ran (local, limited to ~100 items and 9 people) worked well as a proof-of-concept. It also provided a good set of data if someone wanted to test out an algorithm. The data is here: http://www.boardgamegeek.com/thread/377422#3075151 (Note: If you look at the data, you'll notice that most participants used the same weighting scale, but that wasn't required.)

Second, even after lengthy discussions, this sort of trade didn't have an easily identifiable goal. Most items trading definitely isn't right. Highest average utility gain is closer, but still isn't perfect. Something aimed at making everyone trading "happiest" is the goal, but the proper metric to measure that isn't clear. Maybe trying to maximize the minimum (non-zero) user utility. This sort of trade sounds fairly simple/clear, but it is extremely complex (at least, to do it in a way that really is clearly better than traditional math trades).

Third, as others have said, this really only works for no-shipping Math Trades. Though, if you were able to add a shipping "cost" for each trade involving a new trading partner (and if everyone factored in shipping costs in their valuations, like a normal math trade), you might be able to do a shipping variant of this, Then, trades involving people you are already trading with would be favored since they wouldn't incur a new shipping cost (decrease in value/utility) for each item. This might work, but it complicates an already complex system.

Fourth, people seem to understand the general math trade concept pretty quickly. There was surprising opposition/reluctance to getting people to try out this sort of trade. Just explaining valuations lead to some unexpected debates. Some people were hesitant to trade rare/out-of-print items for many more common items, even though the values added up. Admittedly, it was also more work to assign accurate values to both trade and want items, so there was more overhead than a traditional math trade (granted, it removed the large matrix in Step 4 of the OLWLG).

Fifth, having experienced this sort of math trade, I have the following unexpected conclusions:
1) This sort of trade works best for items with fuzzy values (ie. items that different people have considerable differences in valuation. OOP games, thrifted items, used games, and things that couldn't be easily looked up at an online retailer.).
2) Participants willing to list the items they are trading for more than average/retail value and overvaluing items they are wanting for more than average/retail is necessary to create the value necessary for exchanges. This seems obvious, but it is harder to do in practice.
3) This sort of trade works best when participants have larger want lists. Again, this seems obvious, but this trade relies on having sufficient flexibility to create value consumed by other trades.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
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.