Algorithm for Trading Resources

Question

I'm trying to find the best algorithmic solution to the following problem. It's a real-world problem, but I'm going to present it in an abstract manner.

There is a community of 1000 people. Each user is provided with a set number of tickets. There are four types of tickets (each one corresponds to a different event). However, some people are willing to make trades (for example, I want one A-ticket and am willing to give up two B-tickets). Moreover, some people have extra tickets that they are willing to give away for nothing (for example, I'll give away two C-tickets to whoever wants them). Assuming that I know what each person is willing to give away / trade, how do I satisfy the most number of people?

I tried Googling, but I don't know how to word this problem to avoid getting results related to algorithmic trading of financial instruments.

Thanks.

Answer 1

Given that it has multiple dimensions, it is likely an NP-complete problem. It has parallels to a multi-dimensional knapsack problem.

Therefore, I recommend trying a backtracking approach.

Start with everybody involved in the trade.

Sort the people who cause the most deficit descending (here you can weight the deficit caused by each ticket type by the shortfall in each ticket).

Then in a backtracking manner, kick the person causing the next highest deficit person out of the trade.

Repeat until you either have no more deficit in any ticket (record as possible answer), or you have kicked everybody out.

When that happens, backtrack 1 step and continue (if you already tried kicking the highest deficit, kick the next highest deficit causing person).

Repeat until end or you run out of time. Get the optimal answer out of the possible answers you found.

If the problem is too hard, it will probably run out of time. Otherwise, this algorithm should give you a reasonable answer (perhaps near to optimal).

How well this method works depends on how generous/greedy the people are, how many people there are, and how fast your computer is.

Answer 2

Look for a bipartite minimum weigth matching problem. The idea is to find the shortest distance from i to j using vertices 1 .. k only.