Math Trades 101: Hard how is it to setup an online clothing swap?
June 1, 2020 1:49 PM   Subscribe

A dear friend of mine runs an art and re-use community non-profit and the covid has hit its operations pretty hard. She's come to me asking about the difficulty level of hosting an online clothing swap event set up like a math trade as a possible means of recreating a common event that they used to hold in shop. This feels... hard?

I know BoardGameGeek has been running a Math Trade for seemingly forever, but I'm not super familiar with this outside of that context. I'm a front-end engineer, but I gather this seems rather difficult on the backend to match trades appropriately. Are there any other well known examples of this out in the wild that anyone can think of? Good related reading? Perhaps a better event-as-a-service stand-in that might be recommended instead?
posted by zsh2v1 to Computers & Internet (3 answers total) 1 user marked this as a favorite
 
> seems rather difficult on the backend to match trades appropriately.

If the goal is to have some automated decision system to spit out the best combination of matching trades, then this is will be an example of a combinatorial optimisation problem -- this is the kind of problem that techniques and algorithms from operations research & graph theory can often be fruitfully applied to.

There's a high level description of the BoardGameGeek math-trade algorithm here: https://boardgamegeek.com/wiki/page/TradeMaximizer#toc9 It reads as if the "TradeMaximizer" software models the board game swap problem as finding a maximum cardinality matching of a bipartite graph https://en.wikipedia.org/wiki/Maximum_cardinality_matching . Much of the writeup algorithm describes how the problem of maximising number of trades of board games can be modelled by defining a particular bipartite graph that encodes what items each person offers for trade, and what they are willing to receive in exchange, then running some kind of standard algorithm on it.

I'm not familiar with this problem, but the wiki page says it can be solved as a max flow problem: https://en.wikipedia.org/wiki/Maximum_flow_problem . The max flow problem is well known & encountered in industry, e.g. the wiki page lists a few applications around figuring out how to schedule things or route things: https://en.wikipedia.org/wiki/Maximum_flow_problem#Real_world_applications

A general approach to solving an applied combinatorial optimisation problem could be:

1. write down a precise definition of what decision problem you are trying to solve -- what are the decision variables, what are the constraints, is there some objective you are trying to minimise or maximise (e.g. maximise the number of trades)
2. try to identify the corresponding well-known general problem from computer science or operations research that your applied problem is an instance of. if you cannot find one, or the well-known problem is really hard to solve efficiently, go back to 1 and try to redefine your problem to make it simpler or easier to solve.
3. find a solver software library that implements an efficient way to solve that well-known, general class of problem
4. figure out how to pre-process, model or prepare the data from your applied problem to provide the input required to run the solver
5. figure out how to post-process whatever "solution" the solver spits out to recover the output decisions that make sense in the context of your applied problem

There's a bit of an art to figuring out how to model an actual real-life problem as a problem that can be solved effectively by algorithms from computer science (e.g. graph algorithms) or approaches from operations research (e.g. encoding the problem as a "mixed integer program" aka "MIP" that MIP solvers can be thrown at).

To give a concrete example of an unrelated combinatorial optimisation problem that can be solved with MIP techniques, using open source software, here's an example from the python "pulp" package documentation that declares a sudoku problem in the language of "mixed integer program" using the pulp library to model and solve it: https://coin-or.github.io/pulp/CaseStudies/a_sudoku_problem.html

> Are there any other well known examples of this out in the wild that anyone can think of?

There's the related problem of figuring out swaps for organ donation: suppose person A1 and person B1 need kidney transplants. Person A1 has a friend A2 who is willing to donate a kidney to A1, but they aren't a compatible donor for A1. Similarly, suppose B1 has a relative B2 who is willing to donate a kidney to B1, but again they aren't a compatible donor for B1. But if B2's kidney is compatible with A1, and A2's kidney is compatible with B1, then we can do: A2 -- donate kidney to -> B1 , B2 -- donate kidney to -> A1 . This is a simple example, what if B2's kidney is incompatible with A1, but there's another recipient-donor pair (C1, C2) where C1 is compatible to receive B2's kidney, and the donor C2's kidney is compatible with A1? Then all three transplants can be carried out provided we do three trades.

> In the United States, the National Kidney Registry organizes the majority of U.S. KPD transplants,[3][4][5] including the largest swaps. Swaps involving more than two recipients are termed a kidney chain. The first large swap was a 60 participant chain in 2012 that appeared on the front page of the New York Times[6] and the second, even larger swap, included 70 participants and was completed in 2014.

https://en.wikipedia.org/wiki/Kidney_Paired_Donation
posted by are-coral-made at 3:22 PM on June 1 [3 favorites]


This is why humans invented money.

Can you approximate it by having "credits" that people can use to buy and sell stuff?
posted by Jacqueline at 4:21 PM on June 1 [2 favorites]


How big is the event? In terms of both how many people will be involved and how many items will they potentially put on their list?

I used to study how to automate these kinds of problems. (The med school “matching” algorithm is another good example of this, if you’re looking for more key words.) However, in the real world, I would guess that this would actually be easier to do manually, like on a bunch of post-it’s, for the first round. Especially if there are less than say 20 participants, with 5 items or less. This is because I suspect:
- In pre-covid events, your friend probably used a bunch of “insider information” to figure out which items had similar value. (Like is it really okay to trade socks for a leather jacket, if that’s how people make their lists?)
- In doing this by hand once or twice, you’ll probably come up with some heuristics that will help you automate it in the future.
posted by tinymegalo at 4:39 PM on June 1


« Older Preview for Mac no longer copies and pastes pdf...   |   People with chronic illness - how do you push... Newer »

You are not logged in, either login or create an account to post comments