Algorithm for fair distribution of revenue

Question

I am after an algorithm (preferably abstract or in very clear Python or PHP code) that allows for a fair distribution of revenue both in the short and in the long term, based on the following constraints:

1. Each incoming amount will be an integer.
2. Each distribution will be also an integer amount.
3. Each person in the distribution is set to receive a cut of the revenue expressed as a fixed fraction. These fractions can of course be put under a common denominator (think integer percentages with a denominator of 100). The sum of all numerators equals the denominator (100 in the case of percentages)
4. To make it fair in the short term, person i must be receiving either floor(revenue*cut[i]) or ceil(revenue*cut[i]). EDIT: Let me emphasize that ceil(revenue*cut[i]) is not necessarily equal to 1+floor(revenue*cut[i]), which is where some algorithms fail including one presented (see my comment on the answer by Andrey).
5. To make it fair in the long term, as payments accumulate, the actual cuts received must be as close to the theoretical cuts as possible, preferably always under 1 unit. In particular, if the total revenue is a multiple of the denominator of the common fraction, every person should have received the corresponding multiple of their numerator.
6. [Edit] Forgot to add that the total amount distributed every time must of course add up to the incoming amount received.

Here's an example for clarity. Say there are three people among which to distribute revenue, and one has to get 31%, another has to get 21%, and the third has to get 100-31-21=48%.

Now imagine that there's an income of 80 coins. The first person should receive either floor(80*31/100) or ceil(80*31/100) coins, the second person should receive either floor(80*21/100) or ceil(80*21/100) and the third person, either floor(80*48/100) or ceil(80*48/100).

And now imagine that there's a new income of 120 coins. Each person should again receive either the floor or the ceiling of their corresponding cuts, but since the total revenue (200) is a multiple of the denominator (100), each person should have now their exact cuts: the first person should have 62 coins, the second person should have 42 coins, and the third person should have 96 coins.

I think I have an algorithm figured out for the case of two people to distribute the revenue among. It goes like this (for 35% and 65%):

set TotalRevenue to 0
set TotalPaid[0] to 0
{ TotalPaid[1] is implied and not necessary for the algorithm }
set Cut[0] to 35
{ Cut[1] is implied and not necessary for the algorithm }
set Denominator to 100
each time a payment is received:
   let Revenue be the amount received this time
   set TotalRevenue = TotalRevenue + Revenue
   set tmp = floor(TotalRevenue*Cut[0]/Denominator)
   pay person 0 the amount of tmp - TotalPaid[0]
   set TotalPaid[0] = tmp
   pay person 1 the amount of TotalRevenue - TotalPaid[0]

I think that this simple algorithm meets all of my constraints, but I have not found the way to extend it to more than two people without violating at least one. Can anyone figure out an extension to multiple people (or perhaps prove its impossibility)?

Answer 1

To accomodate constraint 4, the current payment must be used as the basis for distribution. After distributing the rounded dividends to the investors, the leftover dollars may be awarded, one each, to any eligible investors. An investor is eligible if he is due a fractional share, that is, ceil(revenuecut[i]) > floor(revenuecut[i]).

Constraint 5 may be addressed by deciding who, among the eligible investors, should get the leftover dollars. Maximum long-term fairness will be most closely approached by always awarding the leftover dollars to the eligible investors who have accumulated the most total (long-term) distribution error.

The following is derived from the algorithm I used for my fund manager clients. (I always used Pascal for financial applications for forensic reasons.) I have transposed the code fragments from a database application to an array-based method in an attempt to improve the clarity.

Included in the accounting data structures is a table of investors. Included in the information about each investor is his share fraction (investor share count divided by fund total shares), amount earned to date, and amount distributed (actually paid to investor) to date.

Investors : array [0..InvestorCount-1] of record
        // ... lots of information about this investor
        ShareFraction       : float; // >0 and <1
        EarnedToDate        : currency; // rounded to dollars
        DistributedToDate   : currency; // rounded to dollars
    end;
// The sum of all the .ShareFraction in the table is exactly 1.

Some temporary data is created for these calculations and freed afterwards.

DistErrs : array [0..InvestorCount-1] of record
        TotalError      : float; // distribution rounding error
        CurrentError    : float; // distribution rounding error
        InvestorIndex   : integer; // link to Investors record
    end;
UNDISTRIBUTED_PAYMENTS  : currency;
CurrentFloat            : float;
CurrentInteger          : currency;
CurrentFraction         : float;
TotalFloat              : float;
TotalInteger            : currency;
TotalFraction           : float;
DD, II                  : integer; // array indices

FUND_PREVIOUS_PAYMENTS : currency; is a parameter, derived from the fund history. If it is not provided as a parameter it may be calculated as the sum over all Investors[].EarnedToDate.

FUND_CURRENT_PAYMENT : currency; is a parameter, derived from the current increase in fund value.

FUND_TOTAL_PAYMENTS : currency; is a parameter, derived from the current fund value. This is the fund total amount previously paid out plus the fund current payment.

These three values form a dependents system with two degrees of freedom. Any two may be provided and the third calculated from the others.

// Calculate how much each investor has earned after the fund current payment.
UNDISTRIBUTED_PAYMENTS := FUND_CURRENT_PAYMENT;
for II := 0 to InvestorCount-1 do begin

  // Calculate theoretical current dividend whole and fraction parts.
  CurrentFloat := FUND_CURRENT_PAYMENT * Investors[II].ShareFraction;
  CurrentInteger := floor(CurrentFloat);
  CurrentFraction := CurrentFloat - CurrentInteger;

  // Calculate theoretical total dividend whole and fraction parts.
  TotalFloat := FUND_TOTAL_PAYMENTS * Investors[II].ShareFraction;
  TotalInteger := floor(TotalFloat);
  TotalFraction := TotalFloat - TotalInteger;

  // Distribute the current whole dollars to the investor.
  Investors[II].EarnedToDate := Investors[II].EarnedToDate + CurrentInteger;
  // Track total whole dollars distributed.
  UNDISTRIBUTED_PAYMENTS := UNDISTRIBUTED_PAYMENTS - CurrentInteger;

  // Record the fractional dollars in the errors table and link to investor.
  DistErrs[II].CurrentError := CurrentFraction;
  DistErrs[II].TotalError := TotalFraction;
  DistErrs[II].InvestorIndex := II;

end;

At this point UNDISTRIBUTED_PAYMENTS is always less than InvestorCount.

// Sort DistErrs by .TotalError descending.

In the real world the data is kept in a database not in arrays, so sorting is done by creating an index on DistErrs using TotalError as a key.

// Distribute one dollar each to the first UNDISTRIBUTED_PAYMENTS eligible 
// investors (i.e. those whose current share ceilings are higher than their 
// current share floor), in order from greatest to least .TotalError.
for DD := 0 to InvestorCount-1 do begin
if UNDISTRIBUTED_PAYMENTS <= 0 then break;
  if DistErrs[DD].CurrentError <> 0 then begin
    II := DistErrs[DD].InvestorIndex;
    Investors[II].EarnedToDate := Investors[II].EarnedToDate + 1;
    UNDISTRIBUTED_PAYMENTS := UNDISTRIBUTED_PAYMENTS - 1;
  end;
end;

In a subsequent process, each investor is paid the difference between his .EarnedToDate and his .DistributedToDate, and his .DistributedToDate is adjusted to reflect that payment.

Answer 2

I think this works:

• Keep track of a totalReceived, the total amount of money that has entered the system.
• When money is added to the system, add it to totalReceived.
• Set person[i].newTotal = floor(totalReceived * cut[i]). Edit: had error here; thanks commenters. This distributes some of the money. Keep track of how much, to know how much "new money" is left over. To be clear, we are keeping track of how much of the total amount of money is left over, and intuitively we re-distribute the whole sum at every step, although actually nobody's fund ever goes down between one step and the next.
• You need to know how to distribute the left-over integer amount of money: there should be less than numPeople amount left over. For i ranging from 0 to leftOverMoney - 1, increment person[i].newTotal by 1. Effectively we give a dollar to each of the first leftOverMoney people.
• To compute how much a person "received" during this step, compute person[i].newTotal - person[i].total.
• To clean/finish up, set person[i].total = person[i].newTotal.