How to find opportunities for 3+ ways to trade (How, how sports teams do it)

Question

I am trying to combine an algorithm (preferably in ruby) that will analyze the database to find opportunities for 3+ ways to trade, for example, how baseball teams do it.

For example:

Imagine there are 100 teams, each of which has about 20 players. Each player has some combination of possible attributes. (Things like Fast Speed, Good Defense, etc.)

Each team has a needs player (with certain attributes from a possible set mentioned above), and players also offer (each with attributes that correspond to possible options above).

This theoretical algorithm can search for all needs and offers in order to find combinations of teams that could trade with each other.

In a theoretical scenario, imagine three teams:

Team A has a player with speed and needs a player with good defense. Team F has a player with good defense and needs a player with good serve. Team Q has a player with good serve and needs a player with good speed.

Thus, teams A, F, and Q can have a three-way deal in which everyone wins.

My question is about an algorithm that could identify this feature. Is this a problem that has been solved by the algorithm before? If so, I would appreciate any direction in where to look. I have several different ideas on how to structure this in a database with clever use of caching and crons. Build it in Rails. Just a little stuck in finding algo.

Answer 1

You can simulate your needs and proposals in the form of a graph: each team is a node, and there is a team from team A to team B from capacity x iif A can profit from x players that B can offer. You can build this graph in O(o + n) , where o is the number of offers, and n is the number of needs by categorizing the offers by their attributes.

Now you need to find a cycle on this graph that satisfies a certain property that you did not specify in your question (features: length> 3, maximum length, maximum capacity, ...). For each of these problems, you can use existing algorithms to solve them (maximum flow, shortest path, BFS, ...)