P is for Practical  
PerlMonks 
Re: Average Price Algorithmby blokhead (Monsignor) 
on Jan 29, 2009 at 17:47 UTC ( #739977=note: print w/replies, xml )  Need Help?? 
I agree with the hunches of my esteemed colleagues  this problem certainly smells NPcomplete. Of course, the details depend on the generalization of the problem, the range of values, and how the objective function is defined (how do you measure "closeness" of a set of numbers to the average?)
But since it's probably NPcomplete, one would imagine looking for some reasonable heuristics / approximations.
I propose the following mindnumbingly simple algorithm: 1. If a person wants N items, then just allocate a random N items to the person.Sounds like a joke, but think about it. From each person's point of view, they get a random sample of the available items. That person's "score" is the mean of their sample. But the expected value of a sample mean is the overall mean. So at least in expectation, each person's allocation tends to the overall mean. Next, the standard approach for "refining" an algorithm that only has good expected performance is: 2. Run many trials of #1 and take the best oneTo formally analyze the behavior of the repeatedtrials approach, you'd have to do some more statistical analysis that incorporates variances as well (to know how likely each trial is to get close to the objective). I can't make that backoftheenvelope statistical calculation now, but at least in the sample you gave, the variance among the items seems very small. Thus the variances of the sample means are also small. So I would expect this algorithm to do fairly well. This makes sense, because the difficulty of the problem seems related to how varied the individual items' scores are  the distribution of the sample mean is greatly influenced by outliers, for example. blokhead
In Section
Seekers of Perl Wisdom

