## 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.