blog.questright.com

Tue, 30 Jun 2009

RFC: Math::Round::Fair

I’ve developed a small module, Math::Round::Fair, which currently resides on github. If the name is suitable and nothing like it already exists on CPAN, I’ll upload it after some time for comment.

I blogged about this a few years ago, but until I needed the algorithm again, recently, I didn’t attempt to create a CPAN module for it.

From the POD:

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.

The code is small enough to include here as well:

sub round_fair {
    my $value = shift;

    croak "Value to be allocated must be an integer" unless int($value) == $value;

    my $basis = 0;
    for my $w ( @_ ) {
        croak "Weights must be > 0" unless $w > 0;
        $basis += $w;
    }

    return ($value) if @_ == 1;

    map {
        my $allocation = $value * $_ / $basis;
        my $allocated  = int $allocation;
        my $remainder  = $allocation - $allocated;
        ++$allocated if rand() < $remainder;
        $basis -= $_;
        $value -= $allocated;
        $allocated
    } @_;
}

Send comments to Marc Mims or post them on github.

[/perl] [link]

About this weblog

This site is the personal weblog of Marc Mims. You can contact Marc by sending e-mail to:
[email protected].

Marc writes here about cycling, programming, Linux, and other items of personal interest.

This site is syndicated with RSS.

Archives