semifor / math-round-fair

NAME
    Math::Round::Fair - distribute rounding errors fairly

SYNOPSIS
      use Math::Round::Fair 'round_fair';

      my $cents = 7;
      my @weights = (1, 2, 3, 2, 1);
      my @allocation = round_fair($cents, @weights);

DESCRIPTION
    This module provides a single, exportable function ("round_fair") which
    allocates an integer value, fairly distributing rounding errors.

    Consider the problem of distributing one indivisible item, for example a
    penny, across three evenly weighted accounts, A, B, and C.

    Using a naive approach, none of the accounts will receive an allocation
    since the allocated portion to each is 1/3 and 1/3 rounds to zero. We
    are left with 1 unallocated item.

    Another approach is to adjust the basis at each step. We start with 1
    item to allocate to 3 accounts. 1/3 rounds to 0, so account A receives
    no allocation, and we drop it from consideration. Now, we have 2
    accounts and one item to allocate. 1/2 rounds to 1, so we allocate 1
    item to the account B. Account C gets no allocation since there is
    nothing left to allocate.

    But what happens if we allocate one item to the same three accounts
    10,000 times? Ideally, two accounts should end up with 3,333 items and
    one should end up with 3,334 items.

    Using the naive approach, all three accounts receive no allocation since
    at each round the allocation is 1/3 which rounds to zero. Using the
    second method, account A and account C will received no allocation, and
    account B will receive a total allocation of 10,000 items. Account B
    always receives the benefit of the rounding errors.

    <round_fair> uses an algorithm with randomness to ensure a fair
    distribution of rounding errors. In our example problem, we start with 1
    item to allocate. We calculate account A's share, 1/3. Since it is less
    than one item, we give it a 1/3 chance of rounding up (and, therefore, a
    2/3 chance of rounding down). It wins the allocation 1/3 of the time.
    2/3 of the time we continue to B. We calculate B's allocation as 1/2
    (since there are only 2 accounts remaining and one item to allocate). B
    rounds up 1/2 of 2/3 (or 1/3) of the time and down 1/2 of 2/3 (or 1/3)
    of the time. If neither A nor B rounds up (which occurs 2/3 * 1/2, or
    1/3 of the time), C's allocation is calculated as 1/1 since we have one
    item to allocate and only one account to allocate it to. So, 1/3 of the
    time C receives the benefit of the rounding error. We never end up with
    any unallocated items.

    This algorithm works for any number of weighted allocations.

METHODS
    round_fair($value, @weights)
        Returns a list of integer values that sum to $value where each
        return value is a portion of $value allocated by the respective
        weights in @weights. The number of return values is equal to the
        number of elements in @weights

        $value must be an integer.

AUTHOR
    Marc Mims <marc@questright.com>

LICENSE
    Copyright (c) 2009 Marc Mims

    This is free software. You may use it, distributed it, and modify it
    under the same terms as Perl itself.