Apportioning refunds and discounts

This is a recounting of one of the more diabolical problems I’ve worked on over the years - apportioning discounts and refunds against orders.

Let’s assume for the sake of this discussion we have two tables in a relational database, orders and order_products. To understand unit economics, every business I can imagine would want to view net revenue, which is to say price - discounts, at a line level. Line-level financials allow analyses like “how do discounts compare across different cohorts of customers?” or “what is our per item net on products in this price band?”.

Our order products will have just two pieces of data we are concerned with - price and discount. Both are integers, with a unit of “cents”. A real order product model will also have tax, surcharges, item price, and possibly duty, but we will ingore these here - the same principles we are about to discuss apply across line-level order data.

We have six order products in our order, with prices of [1000, 1200, 2000, 2400, 1300, 900], for a total of 8800 ($88.00). We want to apportion a $10 (1000 cent), order-level discount against the items in this order.

Let’s start with a requirement - for any given order product, neither the sum of refunds nor discounts can exceed the price paid. This requirement suggests we weight discount and refund allocations using the prices of our order products.

discount = 1000

prices = [1000, 1200, 2000, 2400, 1300, 900]

total = prices.sum # 8800

Integer division cannot work here - we may end up a few pennies short depending on the amount of the discount and the prices.

prices.map { |price| price * discount / total }.sum
# => 997 😱

Rounding won’t work either, and is worse in the sense that the total might come out high or low depending on our prices and discount!

prices = [1000, 1000, 1000, 1000]
total = prices.sum

discount = 1001

prices.map { |price| (price.to_f * discount / total).round }.sum
# => 1000; 250.25 cents discounts rounded down to 250

discount = 1002
prices.map { |price| (price.to_f * discount / total).round }.sum
# => 1004; 250.5 cent discounts rounded up to 251

I settled on using integer division - this approach is easier than rounding because it always gives a total discount less than or equal to our desired total.

discount = 1000

prices = [1000, 1200, 2000, 2400, 1300, 900]

op_discounts = prices.map { |price| price * discount / total }

op_discounts.sum # => 997

op_discounts.map.each_with_index do |_, i|
  break if op_discounts.sum == discount
  op_discounts[i] += 1
end

op_discounts.sum # => 1000

Problem solved? Not quite. What happens when we issue multiple discounts or refunds against the same order?

refund_1 = 1000
refund_2 = 1000
refund_3 = 1000

prices = [1000, 1000, 1000]
total = prices.sum

ref1, ref2, ref3 = [refund_1, refund_2, refund_3].map do |refund|
  line_level_refunds = prices.map { |price| price * refund / total }
  line_level_refunds.map.each_with_index do |_, i|
    break if line_level_refunds.sum == refund
    line_level_refunds[i] += 1
  end
  line_level_refunds
end

[ref1, ref2, ref3].map(&:sum)
# => [1000, 1000, 1000]
# Looks great, I thought you said there was a problem?

ref1.zip(ref2, ref3).map(&:sum)
# => [1002, 999, 999] 😭

We’ve issued a total of $10.02 in refunds to a product that cost $10. As noted in our first requirement, refunds should never exceed the amount paid. The sum across all order products is correct, but I promise your finance team isn’t going to like it.

The missing piece here is that we need to know how much is left to refund for each order product. This ensures we always apportion missing pennies to order products with at least one penny left to refund.

# Once more, with feeling...

class Refunder
  attr_reader :total_refunded

  def initialize(payments, refund_amount, existing_refunds)
    @paid = payments
    @refund_amount = refund_amount
    @total_refunded = existing_refunds
  end

  def invoke!
    line_level_refunds = @paid.map.with_index do  |_, i|
      amount_left_to_refund(i) * @refund_amount / total_left_to_refund
    end

    line_level_refunds.map.each_with_index do |_, i|
      break if line_level_refunds.sum == @refund_amount
      line_level_refunds[i] += 1
    end

    line_level_refunds.each_with_index do |llr, i|
      @total_refunded[i] << llr
    end
  end

  private
  def total_left_to_refund
    @paid.map.with_index { |_, i| amount_left_to_refund(i) }.sum
  end

  def amount_left_to_refund(i)
    @paid[i] - @total_refunded[i].sum
  end
end

order_products = [1000, 1000, 1000]
refund_amount = 1000
all_refunds = [[], [], []]

3.times do 
  refunder = Refunder.new(order_products, refund_amount, all_refunds)
  refunder.invoke!
  all_refunds = refunder.total_refunded
end

all_refunds.map(&:sum)
# => [1000, 1000, 1000]

all_refunds 
# => [[334, 334, 332], [333, 333, 334], [333, 333, 334]]

all_refunds.map(&:sum)
# => [1000, 1000, 1000]

This is an imperfect solution. All three order products have the same price, but their combinations of refunds are not identical - the ideal solution would be a different permutation of [333, 333, 334] for each order product. One could accomplish this by assigning the penny to the order product with the greatest percentage left to refund. I’ve left this as an exercise for the reader.