1

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?

Self-teaching worker
  • 5,058
ithisa
  • 2,763
  • Perhaps calculate the mean without moving anything around, and then start with those closest to it and equalize them first, moving outwards? – A. Thomas Yerger May 31 '14 at 01: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... – ithisa May 31 '14 at 02: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

0 Answers0