MaxMinFair Rewrite

I read Charles William’s MaxMinFair algorithm and I didn’t like his approach. That’s typical. I’ll read somebody’s code and think “They’re making that too hard”. Then I’ll set about rewriting it. In this case, as in most cases, it turns out that it is that hard, but I wasn’t going to convince myself until I tried it. I ended up with a different approach that’s not shorter, not easier to read, and not easier to follow. Oh well, here it is anyway.

In Charles’s implementation, he allocates an equal amount of the supply to each node, then takes back what that node didn’t need and puts it back in the available pool. When I was looking at the results, I was thinking that the smallest n nodes simply get their demand and only when there’s not enough to go around do we need to do something different than allocate the full demand.

In my implementation, I start by giving everyone what they demand. Then I start with the smallest demand, and if I can accommodate that amount for everyone, I just reduce the amount available and move to the second smallest demand. At some point (the sixth smallest demand in Charles’s data) I can’t meet that demand and still give everyone an equal share. At that point, I give anyone who hasn’t had their demand met an equal amount – the amount that’s already been distributed plus an equal share of what’s left.

Rank Demand Incremental Demand Allocated Remaining
        18.30
7 0.70 0.70 4.90 13.40
6 1.00 0.30 1.80 11.60
5 1.30 0.30 1.50 10.10
4 2.00 0.70 2.80 7.30
3 3.50 1.50 4.50 2.80
2 7.40 3.90 7.80 (5.00)
1 10.00 2.60 2.60 (7.60)

In the first iteration, I hand out 0.70 to everyone because I have enough supply to do that. In the second iteration, I had out the differential, 0.30, to everyone who’s left because I have enough supply remaining. When I get to #2, I can’t hand out 3.90 to the remaining two nodes because I don’t have enough supply. I’ve allocated up to 3.5 to anyone who’s demanded it, so the last two get the 3.5 plus half of the 2.8 that remains.

Although I didn’t accomplish anything, it was still a fun exercise.

8 thoughts on “MaxMinFair Rewrite

  1. snb writes:

  2. Quite right Charles. I never consider execution speed until it’s too late, but I should have guessed that you considered it. I started out sorting the list, but didn’t like it because the output array needs to match the input array. Still, it may have been the better way. It would get rid of the worksheet function part, which is always good because it make the code more portable.

  3. After sorting the task is much easier:

  4. I thought a sort based function might be faster with a long table, so I wrote one using my VBA sort routine, and another calling a Python sort.

    Here are results for 10,000 rows (times in seconds):

    CW UDF 0.014
    DK UDF 21.64
    SNB Sub1 163.8 for 1000 rows
    SNB Sub2 0.055
    DJ VBA UDF 0.051
    DJ Py UDF 0.025

    So some pretty dramatic differences there. Now I just need to have another look at Charles’ code and see how he gets it so fast on unsorted data.

  5. I am curious about the code to turn a range into an array

    If IsObject(Demands) Then Demands = Demands.Value2 ‘make range array

    Since Demands is a parameter passed into the function, and by default it is passed in ByRef, is it safe to just overwrite the parameter in that way – should the parameter be defined as ByVal just to be safe? If the calling function did something else with that parameter afterwards, then it might be expecting it to be pointing to a range object, not an array. Just curious …

  6. @Charlie
    The function is a worksheet User Defined Function and so can only return the result of the function for Excel( parameters are not passed back to Excel).
    If it was going to be called from code you would assign it to a variable local to the function and then coerce to values if required.

Leave a Reply

Your email address will not be published. Required fields are marked *