I have N big gold bars and 1 small gold bar equivalent in weight to some fraction x of a large bar. E.g N = 10 and x = 0.5 then I have 10.5 large bars worth of gold, in 10 large bars and 1 small bar
I want to distribute this between a gang of T thieves there thief i (T_i) has a share (s_i) of gold he or she should be entitled to. E.g. for T = 3 then Thief 1 has 40% share, Thief 2 has 50% share and Thief 3 has 10% share
What algorithm can I run to allocate the gold bars to the thieves so that the final share of the total gold (by weight) is closest to their desired shares? The gold bars cannot be cut or divided they must remain whole.
Example of how I thought about it, each thief gets NearestInteger((Tot Gold) * s_i) gold where Tot Gold = N + x = 10.5
Doing this approach with the numbers above
| Thief | share s_i | 10.5 * share | Rounded |
|---|---|---|---|
| 1 | 40% | 4.2 | 4 |
| 2 | 50% | 5.25 | 5 |
| 3 | 10% | 1.05 | 1 |
There are several issues
- The total allocation is 4+5+1 = 10 not 10.5, since everyone's gold is rounded down. But it could also end up overshooting if everyone happens to get rounded up.
- This algorithm will never allocate the small fractional bar of gold since it works in whole numbers.
- I don't know if it's provably the closest final ratio
An extension would be to allocate Thief N - the final person any remainder of the gold, however this would bias them to always get the leftovers.
Update
For "best" I want the Pythagorean distance of the shares (s_1, s_2, ... s_n) and the result fractions (r_1, r_2 ... r_n) to be minimised. If there are ties for best possible then the thieves are sensible and equally happy with any of the best allocations.
This is known as an "apportionment problem".
See Mathematics of apportionment of representation in a legislative body, How to round numbers fairly, https://stackoverflow.com/q/35931885/781723 for some resources.
In your case, the small bar complicates things. But you can always exhaustively search over all $T$ possibilities for which thief receives the gold bar; and for each, reduce that thief's share, then use an apportionment algorithm to split the big bars; and then compare all $T$ of those candidate solutions to see which is best.