Hacker News Reader

Comment by vintermann | Hacker News Reader

Many years ago, on Boardgamegeek, there was a game trading system called "Math Trades", where participants would list a number of trades they were willing to make, and they ran some complicated calculations to figure out how to let as many as possible trade.

CS professor Chris Okasaki, known for his book on purely functional data structures, also played board games and he came across this phenomenon. He realized that it could be modelled as a bipartite matching problem, and wrote a MUCH faster program to manage math trades.

https://okasaki.blogspot.com/2008/03/what-heck-is-math-trade...

I guess it can be made even faster now in theory.

View on HN

I don't think this new result is supposed to be a speedup. It might even be slower than the existing method. Rather, it's a way to get rid of the random number generator that the old algorithm relied on, so it's deterministic unlike the old way. I'm not even sure that it's guaranteed to find the answer, as opposed to finding it with high probability.

It's mostly of theoretical interest except for some possible niche applications, I'd say. For a math trade type of problem, you'd just go ahead and use the old algorithm with an RNG.

Another famous result of this type was AKS primality testing. Randomized algorithms like Miller-Rabin were known for a long time, very reliable, and quite simple to implement, but AKS was an important theoretical advance because it didn't use random inputs. I think everyone still uses Miller-Rabin in practice.

The kidney exchange problem isn't bipartite matching but a cycle packing problem (or disjoint cycle cover).

The math trades still happen regularly at cons, e.g. Origins had one just last week.

Of course the easiest solution to the problem is money. You sell the games you don't want for money. You buy the games you want with money.

Much simpler than algorithms for bartering.

Chris okasaki! Was into functional data structures in college, great book and great dude

Reply on news.ycombinator.com