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.
Dim dPrior As Double
Dim vaReturn As Variant
Dim dAvailable As Double
Dim i As Long, j As Long
Dim dTemp As Double
Dim wf As WorksheetFunction
On Error GoTo ErrHandler
Set wf = Application.WorksheetFunction
If IsObject(Demands) Then Demands = Demands.Value2 ‘make range array
dAvailable = Abs(Supply) ‘ignore negative supplies
If Not IsArray(Demands) Then
‘One demand = min of supply or demand
MaxMinFairDK = Array(dAvailable, Demands)(Abs(dAvailable > Demands))
Else
‘Excel returns NA when you use too many columns
If UBound(Demands, 2) > 1 Then Err.Raise xlErrNA
‘Assume everybody gets everything they want
ReDim vaReturn(LBound(Demands, 1) To UBound(Demands, 1), 1 To 1)
vaReturn = Demands
For i = UBound(Demands, 1) To LBound(Demands, 1) Step -1
‘If there’s enough, do nothing except reduce what’s available
If dAvailable / i > (wf.Large(Demands, i) – dPrior) Then
dAvailable = dAvailable – ((wf.Large(Demands, i) – dPrior) * i)
dPrior = wf.Large(Demands, i)
Else
‘Once there’s not enough, everyone splits what’s left
For j = LBound(Demands, 1) To UBound(Demands, 1)
If Demands(j, 1) > dPrior Then
vaReturn(j, 1) = dPrior + (dAvailable / i)
End If
Next j
Exit For
End If
Next i
MaxMinFairDK = vaReturn
End If
ErrExit:
Exit Function
ErrHandler:
MaxMinFairDK = CVErr(Err.Number)
Resume ErrExit
End Function
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.