Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This seems like a trivial problem, but dumb me thinked forever without proving any solution as the optimal.

So the problem is, given $n$ people, each with wealth $w_1,\dots ,w_n$, with $w_i$ being any real number, how to move money among the $n$ people so that everybody ends up being equally wealthy, and minimizes the the total transaction volume?

One trivial solution is to have everybody first pile up all the money on one person, then that one person divides the money equally and distributes it. (Side note: sounds very like a communist state...). However this can result in highly unoptimal transaction volumes: indeed it is almost never optimal and usually very unoptimal since everybody except the distributor needs to move all their money.

Is there a standard algorithm to solve this problem?

share|improve this question
    
Perhaps calculate the mean without moving anything around, and then start with those closest to it and equalize them first, moving outwards? –  Alfred Yerger May 31 at 1:58
    
I thought of something like that too, but it seems that I can't prove it is THE optimal way, and there certainly are pathological cases showing it is NOT the optimal way... –  user54609 May 31 at 2:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.