How to find opportunities for 3 + way trades (Like how sports teams do it)

Question

I'm trying to piece together an algorithm (preferably in ruby) that will analyze a database to find opportunities for 3+ way trades like how baseball teams typically do it.

For example:

Imagine there are 100s of teams, each having 20 or so players. Each player has some combination of possible attributes. (Things like "Fast running speed", "good defense", etc)

Each team has player needs (with specific attributes from the possible set mentioned above) as well as players to offer, (each with attributes that match the possible options mentioned above).

This theoretical algorithm could search all the needs and offers to find combinations of teams who 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 pitching Team Q has a player with good pitching and needs a player with good speed

So team A, F and Q could have a three-way trade where everyone wins.

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

Answer 1

You can model your needs and offers as a graph: Every team is a node and there is an edge from team A to team B of capacity x iif A could profit from x players that B has to offer. You can build up 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 in this graph that fulfills a certain property that you didn't state in your question (possibilities are: length > 3, maximum length, maximum capacity, ...). For each of those problems, you can use existing algorithms to solve them (maximum flow, shortest path, BFS, ...)