Suggestion on algorithm to distribute objects of different value

Question

Hello,

I have the following problem:

Given N objects of different values (N < 30, and the values are multiple of a "k" constant, i.e. k, 2k, 3k, 4k, 6k, 8k, 12k, 16k, 24k and 32k), I need an algorithm that will distribute all items to M players (M <= 6) in such a way that the total value of the objects each player gets is as even as possible (in other words, I want to distribute all objects to all players in the fairest way possible).

EDIT: By fairest distribution I mean that the difference between the value of the objects any two player get is minimal. Another similar case would be: I have N coins of different values and I need to divide them equally among M players; sometimes they don't divide exactly and I need to find the next best case of distribution (where no player is angry because another one got too much money).

I don't need (pseudo)code to solve this (also, this is not a homework :) ), but I'll appreciate any ideas or links to algorithms that could solve this.

Thanks!

Answer 1

how about this:

order the k values. order the players.

loop over the k values giving the next one to the next player. when you get to the end of the players, turn around and continue giving the k values to the players in the opposite direction.

Answer 2

Repeatedly give the available object with the largest value to the player who has the least total value of objects assigned to him.

Answer 3

30 ^ 6 isn't that large (it's less than 1 billion). Go through every possible allocation, and pick the one that's the fairest by whatever measure you define.

Answer 4

The problem is strongly NP-complete. This means there is no way to ensure a correct solution in reasonable time. (See 3-partition-problem, thanks Paul).

Instead you'll wanna go for a good approximate solution generator. These can often get very close to the optimal answer in very short time. I can recommend the Simulated Annealing technique, which you will also be able to use for a ton of other NP-complete problems.

The idea is this:

1. Distribute the items randomly.
2. Continually make random swaps between two random players, as long as it makes the system more fair, or only a little less fair (see the wiki for details).
3. Stop when you have something fair enough, or you have run out of time.

This solution is much stronger than the 'greedy' algorithms many suggest. The greedy algorithm is the one where you continuously add the largest item to the 'poorest' player. An example of a testcase where greedy fails is [10,9,8,7,7,5,5].

---

I did an implementation of SA for you. It follows the wiki article strictly, for educational purposes. If you optimize it, I would say a 100x improvement wouldn't be unrealistic.

from __future__ import division
import random, math

values = [10,9,8,7,7,5,5]
M = 3
kmax = 1000
emax = 0

def s0():
    s = [[] for i in xrange(M)]
    for v in values:
        random.choice(s).append(v)
    return s

def E(s):
    avg = sum(values)/M
    return sum(abs(avg-sum(p))**2 for p in s)

def neighbour(s):
    snew = [p[:] for p in s]
    while True:
        p1, p2 = random.sample(xrange(M),2)
        if s[p1]: break
    item = random.randrange(len(s[p1]))
    snew[p2].append(snew[p1].pop(item))
    return snew

def P(e, enew, T):
    if enew < e: return 1
    return math.exp((e - enew) / T)

def temp(r):
    return (1-r)*100

s = s0()
e = E(s)
sbest = s
ebest = e
k = 0
while k < kmax and e > emax:
    snew = neighbour(s)
    enew = E(snew)
    if enew < ebest:
        sbest = snew; ebest = enew
    if P(e, enew, temp(k/kmax)) > random.random():
        s = snew; e = enew
    k += 1

print sbest

Update: After playing around with Branch'n'Bound, I now believe this method to be superior, as it gives perfect results for the N=30, M=6 case within a second. However I guess you could play around with the simulated annealing approach just as much.

Answer 5

This is a straight-forward implementation of Justin Peel's answer:

M = 3
players = [[] for i in xrange(M)]

values = [10,4,3,1,1,1]
values.sort()
values.reverse()
for v in values:
    lowest=sorted(players, key=lambda x: sum(x))[0]
    lowest.append(v)

print players
print [sum(p) for p in players]

I am a beginner with Python, but it seems to work okay. This example will print

[[10], [4, 1], [3, 1, 1]]
[10, 5, 5]

Answer 6

EDIT:

The purpose was to use the greedy solution with small improvement in the implementation, which is maybe transparent in C#:

static List<List<int>> Dist(int n, IList<int> values) 
{ 
    var result = new List<List<int>>(); 
    for (int i = 1; i <= n; i++) 
        result.Add(new List<int>()); 
    var sortedValues = values.OrderByDescending(val => val);//Assume the most efficient sorting algorithm - O(N log(N))
    foreach (int val in sortedValues) 
    { 
        var lowest = result.OrderBy(a => a.Sum()).First();//This can be done in O(M * log(n)) [M - size of sortedValues, n - size of result]
        lowest.Add(val); 
    } 
    return result; 
} 

Regarding this stage:

var lowest = result.OrderBy(a => a.Sum()).First();//This can be done in O(M * log(n)) [M - size of sortedValues, n - size of result]

The idea is that the list is always sorted (In this code it is done by OrderBy). Eventually, this sorting wont take more than O (log(n)) - because we just need to INSERT at most one item into a sorted list - that should take the same as a binary search. Because we need to repeat this phase for sortedValues.Length times, the whole algorithm runs in O(M * log(n)).

So, in words, it can be rephrased as: Repeat the steps below till you finish the Values values: 1. Add the biggest value to the smallest player 2. Check if this player still has the smallest sum 3. If yes, go to step 1. 4. Insert the last-that-was-got player to the sorted players list

Step 4 is the O (log(n)) step - as the list is always sorted.

Answer 7

The greedy solution suggested by a few people seems like the best option, I ran it a bunch of times with some random values, and it seems to get it right every time.
If it's not optimal, it's at the very least very close, and it runs in O(nm) or so (I can't be bothered to do the math right now)
C# Implementation:

static List<List<int>> Dist(int n, IList<int> values)
{
    var result = new List<List<int>>();
    for (int i = 1; i <= n; i++)
        result.Add(new List<int>());
    var sortedValues = values.OrderByDescending(val => val);
    foreach (int val in sortedValues)
    {
        var lowest = result.OrderBy(a => a.Sum()).First();
        lowest.Add(val);
    }
    return result;
}