CODEWITHSUNDEEP
algorithm
Kurisu
Kurisu

Reputation: 852

Resource Sharing/Trading algorithm

Lets say we have 3 people, Alice, Bob, and Charlie.

Lets say each of them have a resource, Aplles, Bannanas, and Coconuts.

Each of them have 3 of this resource.

The goal of the algorithm is to make 1-1 trades such that each of them end up with 1 of each of our 3 resources. A list of those trades is what I want to obtain.

Ideally I would like to know how to solve this. But I'm willing to settle for the name of this kind of problem, or a problem similar to it that I can research and get ideas from.

The problem I'm working on will have around 600 objects, with ~1000 people each with a random amount/type of starting resources, (with the assumption that there are enough resources to satisfy our end result) so Ideally any solution provided would be feasible for such a scale. But I'll take whatever I can get, I just need some kind of starting point.

Upvotes: 1

Views: 746

Answers (3)

SáT
SáT

Reputation: 3692

The answers of ElKamina and Tyler Durden are decent, but they don't seem to take into account that Kuriso would like to perform 1-1 trades, that people may have multiple commodities, and multiple units of commodities. I have a naive solution that does.

I think the original example was a bit oversimplified, so let's take another one:

  c1 c2 c3 c4
A 5  0  1  0
B 0  1  0  1
C 0  6  2  0

Where A,B,C are people and c1,c2,c3,c4 are the commodities.

First, let's calculate the ideal distribution, which is easily done: for each commodity, divide the sum of stuff by the number of people, rounded down, and everybody gets that:

  c1 c2 c3 c4
A 1  2  1  0
B 1  2  1  0
C 1  2  1  0

Now let's define a WANT function denoting how much of a stuff c would person X need to get into the ideal position: WANT(X,c) = IDEAL(c) - Xc.

  c1  c2  c3  c4 sum
A -4  2   0   0  -2
B  1  1   1   0   3
C  1 -4  -1   0  -4

Let's make a list of people ordered by the sum of their wants. Let's take the richest guy, the one with the lowest want, in this case C, and let's try to satisfy his wants by matching him up with people who has the most to offer of the commodity he wants most. If they can make a trade, great, if not, continue until we find a match (a match is guaranteed, eventually). In this example, C needs c1; the one offering the most c1 is A, iterating over the commodities, we find that A needs c2 and C does have surplus c2, so they exchange them. Update their position in the list, or remove them if they no longer have any needs. Iterate this until nobody has any wants. This won't produce properly equal distribution, but as equal as they can get to by 1 for 1 trading.

This is indeed a naive solution, with the heuristics that the richest guy has the most chance to offer stuff in return for the commodity he needs. The complexity is high, but with ordered lists it should be managable for the numbers you specified.

Upvotes: 1

ElKamina
ElKamina

Reputation: 7817

Assume you have a total number of x1 resources of kind 1,..., xn resources of kind n.

Assume you have k people and each of them have (or need to end up with y1, y2,..., yk resources respectively.

Now, pick a person i and assign him resources that are most prevalent. Once assignment is done, decrement the corresponding xj s (i.e. if resource j is assigned to i, decrement xj).

Keep repeating until all resources are assigned.

This is the way to assign stuff most evenly. It assumes that you dont care about sequences of trades, but the end result itself.

Upvotes: 1

Tyler Durden
Tyler Durden

Reputation: 11562

To restate this, let's say you have set of lists like this:

{ 1, 1, 1 }
{ 2, 2, 2 }
{ 3, 3, 3 }

and you want to swap elements from different sets until you have the sets like this:

{ 1, 2, 3 }
{ 1, 2, 3 }
{ 1, 2, 3 }

Now, you might notice that if we regard these lists as a single matrix then one matrix is the inverse of the other. You can perform this inversion by swapping across the 1-2-3 diagonal.

So item 2 in list 1 is swapped with item 2 in row 2, item 3 in list 1 is swapped with item 1 in list 3, and finally item 3 in list 2 is swapped with item 2 in list 3.

To sum up: do a matrix inversion by swapping across the diagonal.

Upvotes: 0

Related Questions