tag:blogger.com,1999:blog-2564777502681463717.post3638279325415766701..comments2023-12-31T10:17:57.560-05:00Comments on Teaching, Playing, and Programming: What the heck is a math trade?Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-2564777502681463717.post-62707855586367947742015-04-27T21:10:20.189-04:002015-04-27T21:10:20.189-04:00This comment has been removed by the author.Welton Rodrigo Torres Nascimentohttps://www.blogger.com/profile/04062742781277935680noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-73863889125169497542015-04-27T21:10:14.256-04:002015-04-27T21:10:14.256-04:00Hi,
on your description of trademaximizer[1]:
&g...Hi,<br /><br />on your description of trademaximizer[1]:<br /><br />> Although it is relatively straightforward to understand how prices work, it is extremely difficult to understand why they work to produce the desired result. I take no credit for inventing this part of the algorithm, <i>which is a standard--albeit fairly obscure--algorithm in the computer science toolkit</i>. My Eureka moment was in figuring out how to model the problem as a bipartite graph in such a way that the standard algorithm could be applied.<br /><br />Would you mind explaining better? And which algorithm is this?<br /><br />I solved a problem[2] using your software, but didn't understood very well how prices work.<br /><br />1 - http://boardgamegeek.com/wiki/page/TradeMaximizer<br />2 - http://cstheory.stackexchange.com/q/11093/9090Welton Rodrigo Torres Nascimentohttps://www.blogger.com/profile/04062742781277935680noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-75138950136297479842012-04-16T12:17:09.538-04:002012-04-16T12:17:09.538-04:00@Radu: Yep, that's a good description.@Radu: Yep, that's a good description.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-18986949049148985812012-04-16T12:06:35.412-04:002012-04-16T12:06:35.412-04:00"I'll describe TradeMaximizer in detail i..."I'll describe TradeMaximizer in detail in an upcoming post."<br /><br />I didn't find the upcoming post so I tried to briefly describe the algorithm here: http://goo.gl/pi9XO<br /><br />I hope I didn't misrepresent your program.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-57157068797601019152009-02-14T23:08:00.000-05:002009-02-14T23:08:00.000-05:00I am currently running a Math Trade with TradeMaxi...I am currently running a Math Trade with TradeMaximizer for geocoins. We have 58 participants with 1437 total coins in the trade.<BR/><BR/>I ran the program with the completed want lists for the first time tonight and came up with less than 50% of the coins changing.<BR/><BR/><BR/>Num trades = 673 of 1437 items (46.8%)<BR/>Total cost = 673 (avg 1.00)<BR/>Num groups = 4<BR/>Group sizes = 501 142 17 13<BR/>Sum squares = 271623<BR/><BR/>From reading your blog I see that this is not an unexpected result, but I'm still rather disappointed that so few coins traded. I suppose the culprit is likely participants submitting short want lists for their coins.<BR/><BR/>At least it should cut down on shipping though -- I participated myself, and 23 of my 48 coins need to be shipped now :)<BR/><BR/>Thanks for the software!ChuckThttps://www.blogger.com/profile/13662967829927795925noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-25044232752553251652008-04-07T13:34:00.000-04:002008-04-07T13:34:00.000-04:00LegalGeek: I completely understand your skepticism...LegalGeek: I completely understand your skepticism. Still, the community on BoardGameGeek has thus far made it work.<BR/><BR/>Although there are occasional bad traders, they are quite rare. The vast majority of trades go through without a hitch. I don't have hard numbers available, but most math trades go through without any significant problems of the kind you're talking about. And by "most math trades", I mean the entire set of trades, not the individual trades within the math trade!<BR/><BR/>Part of this is due to the BoardGameGeek community, which is remarkably close knit and friendly (as internet communities go). The community is also self-policing; it keeps an eye out for bad traders, and actively shuns those it finds.<BR/><BR/>I'm sure another part of the success so far is the relatively low value of the items being traded, usually less that $100 worth.<BR/><BR/>I'm sure there would be more problems if this model were applied to a more anonymous community, or to items with higher values. One approach in such cases might be to require users to set up an escrow account before being allowed to participate.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-27258227542781532452008-04-07T13:15:00.000-04:002008-04-07T13:15:00.000-04:00I should preface with an explanation that while I ...I should preface with an explanation that while I think the concept is intriguing from a mathematical perspective, my inner sociologist is skeptical. <BR/><BR/>From an individual trader standpoint, I can see why the large-scale trades-within-trades (919 of your closest friends standing around in a circle) might not be a good idea. The math is great, but how do you ensure that A and B actually get to the follow-through once a match has been made? <BR/><BR/>For example, when I (briefly) looked over the game link example you provided, I wasn't able to find out how many actual trades were successfully completed. Although there was substantial data on how many trades had been arranged by the algorithm (which the site reported as received), it wasn't at all clear whether those trades actually took place. <BR/> <BR/>Of course, the problems I'm curious about (laziness/forgetfulness/greed/shipping /cost differentials between distant trading partners) are of a human, and not really a mathematical variety. Still, I'd love to see if math could somehow overcome these issues.lawnunhttps://www.blogger.com/profile/05365067389794051802noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-78527359188539217502008-03-03T12:59:00.000-05:002008-03-03T12:59:00.000-05:00Chris: you are correct. But if a few preconditions...Chris: you are correct. But if a few preconditions are met, one is guaranteed a maximal matching that also creates a cycle:<BR/>1. the relation is not reflexive (the "seller" doesn't want his own product back).<BR/>2. the bipartite graph is connected.<BR/>3. the degree for each vertex in the bipartite graph is > 1. In other words, every "buyer" would be willing to trade for at least two products, and every product had at least two interested parties.vaneklhttps://www.blogger.com/profile/00728653010839416298noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-30362612934821611292008-03-02T13:29:00.000-05:002008-03-02T13:29:00.000-05:00lofigeek: It's not directly the stable marriage pr...lofigeek: It's not directly the stable marriage problem, although it's similar in some ways. The goal here is to optimize a global notion of happiness that is different from stability.<BR/><BR/>vanekl: Maximum matching in a bipartite graph doesn't necessarily produce trade loops. Instead, this uses minimum-cost perfect bipartite matching. And, yes, it's polynomial, but the graphs can be pretty darn big. (Also, the code hasn't been particularly optimized, because that wasn't necessary when trades had fewer than 1000 entries.)Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-40535783872550496012008-03-02T13:23:00.000-05:002008-03-02T13:23:00.000-05:00rgrig,The main algorithm optimizes the the number ...rgrig,<BR/><BR/>The main algorithm optimizes the the number of trades and the cost of those trades. Iterating this algorithm to find multiple solutions that are tied according to those two criteria, lets you try to improve some third criterion that is not directly optimized by the main algorithm. <BR/><BR/>Right now, that's used to try to get shorter cycles. The benefit of shorter cycles is in case something goes wrong, and the affected cycle needs to be cancelled.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-43619960233635844332008-03-02T11:37:00.000-05:002008-03-02T11:37:00.000-05:00Great software by the way. I'm running a local no...Great software by the way. I'm running a local no-shipping math trade for our gaming group. I've allowed an "anything goes" policy and it's fun to see what the relative worth of a microwave is going to be :)Isamoorhttps://www.blogger.com/profile/17246918125961752266noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-8481813734188346232008-03-02T10:31:00.000-05:002008-03-02T10:31:00.000-05:00I mean, I saw what it does, but I don't see why sh...I mean, I saw what it does, but I don't see why shorter cycles would be preferred.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-20068727073147220532008-03-02T10:29:00.000-05:002008-03-02T10:29:00.000-05:00What is the reason for ITERATIONS?What is the reason for ITERATIONS?rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-17032850946580466482008-03-02T10:00:00.000-05:002008-03-02T10:00:00.000-05:00Yes, this is the marriage problem; more formally, ...Yes, this is the marriage problem; more formally, the maximum matching in a bipartite graph problem. And it's been solved for ages. Don't understand why anybody's algorithm would take more than a second or two to run because it's polynomial in time, order O(pq^2).vaneklhttps://www.blogger.com/profile/00728653010839416298noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-63339545085970032992008-03-02T09:26:00.000-05:002008-03-02T09:26:00.000-05:00is this the stable marriage problem?is this the stable marriage problem?lofigeekhttps://www.blogger.com/profile/16015495842779233560noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-11571043016629791562008-03-02T05:14:00.000-05:002008-03-02T05:14:00.000-05:00This reminded me of the Three Ballot voting scheme...This reminded me of the Three Ballot voting scheme, at en.wikipedia.org/wiki/Three_Ballot_Voting<BR/><BR/>If you read the paper, at the end they talk about a possible way to simplify it further, which would involve trading voting ballots between other people before leaving the polling station. It sounds like there is some overlap here with Math Trades.Unknownhttps://www.blogger.com/profile/10908210050410667635noreply@blogger.com