Problem 18 Answer: "Rating Trading"

Problem 18A. Create a graph in which each node represents a player, and there is an edge from A to B if and only if B wants the game A has. Each edge has capacity 1 and cost -1, and each node has node capacity 1. If the edge from A to B has flow, then that means A gives his game to B. The conservation-of-flow constraints ensure that each person ends up with the same number of games he started out with (exactly one), the node capacity constraints ensure that a player isn't trying to give his game to two or more people at the same time, and "minimizing the cost" means to maximize the number of trades.

Problem 18B. Split each node into two nodes: an "in" node and an "out" node. All the incoming edges go into the "in" node, and all the outgoing edges come out of the "out" node. Add a "synthetic edge" going from the "in" node to the "out" node with cost equal to 0 and capacity equal to the node capacity. This guarantees that the amount flowing through that node is not greater than the node capacity.

Problem 18C. Suppose that I am person A and the people B1 ... Bn all have the same game that I want. What I do is create a "fake" person B that wants each of B1 ... Bn's games, and I say that I want B's game. Then the "person B" will win at most one of the games (and then pass it on to me, since I am the only one who wants B's game).

---

The current "gold standard" for software to do the Math Trades is TradeMaximizer, developed in 2008. The algorithm used is described at the bottom of that page, and as far as I can tell, the graph TradeMaximizer generates is exactly the same as the graph described above - the only difference is that TradeMaximizer formulates it as a bipartite graph matching problem while I formulated it as a network flow problem; the main difference between the formulations is that whether or not there is flow on each "synthetic edge" is inverted. I just hadn't noticed that the graph was bipartite so you can use the special "bipartite graph matching" algorithms, but even normal network flow algorithms are polynomial time (in the case where all the costs are 1), which is much better than the exponential time algorithms they were using for years before TradeMaximizer. Oh, well, if only I had found out about the math trades a few years earlier I could have been famous on BoardGameGeek.