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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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. 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|cite|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 '14 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 '14 at 2:00
    
Can you share the pathological example? It seems intuitively obvious to me that any system where the people of excess wealth give it away in a reasonable manner, I.e., nobody receiving money ever has to give any away, that the total transferred will not depend on any of the choices made. Just add up the excesses above the mean that the richer people have. One of us is mistaken, and if you have a possible counter example, that is the best place to start. – Aaron Dec 30 '15 at 13:13

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.