Thursday, December 12, 2013

Fair Slice

It seems impossible to teach math without toothpicks and pizzas but in computer science it's all about cake*. Specifically when addressing fair division the analogy used is Cake Cutting. The goal is equitable (fair?) division of oft indivisible assets and has found utility in asset allocation in divorce settlements. The research goals are systems that are Pareto-optimal**, envy-free, and maximal. Algorithms include Cut and Choose, Last Diminisher, Divide and Conquer, and Adjusted Winner.

For this discussion "maximal" is not a consideration but Pareto-optimal and envy-free are and since we are concerned with a 2-person problem we'll start off simple with Cut and Choose.

As an overview let's cut the cake.

In the good old days Mum cut the cake and choose who got each piece--you and your self-centered older Sis. This resulted in you and Sis examining the other's plate and concluding that plate held the larger piece thereby failing on our two important criteria. It was neither an equitable allocation nor was it envy-free. In fact one has to wonder how so many have concluded "Mum always liked me best."

When Mum's not around and Dad's watching football then Sis generally wields the knife dividing the cake into a two thirds piece and a one thirds piece then declares these "halves". You get the "smaller half." This is arguable less equitable in distribution but disregarding intensity cuts the envy in half.

Cut and Choose is simply this: Sis cuts the cake and you choose who gets which piece. Sis can cut where ever she likes but will cut as closely as she possibly can to equalize the pieces lest you give her the short piece. Consequently she will be equally pleased with either piece as it is she who ensured they were equal sized. You will be at least as pleased as you choose the one you feel is best. Equal division and envy-free.

A hybrid approach is to allow Sis to cut and cut wherever she likes and then let you cut the larger piece to a size you deem equal to the smaller. Then you subdivide the remainder in a similar fashion with you cutting first. Rinse...Repeat...Until only a small crumb remains. This is laborious and time consuming and is often expedited by having an objective third party (Mum) equalize the pieces reserving the excess for other purposes. Like herself.

Dunwoody has become quite accustomed to playing the role of big Sis when Mum's not around cutting and taking the choice bits for herself. With cityhood there were inherent limits to selfish behaviour in that Dunwoody is not the exclusive taxing authority but shares that with DeKalb County. Not so with the proposed Dunwoody Independent School District since DeKalb County Schools will no longer receive any tax revenue from properties within Dunwoody.

Like big Sis, Dunwoody will make the cut and would like to be the sole unfettered Chooser guaranteeing an inequitable distribution. But in seceding Dunwoody will also point towards a solution. In fact they already have. In Representative Taylor's Report it is disclosed that Dunwoody will leave $8600 per student for DeKalb County Schools to educate children in DeKalb. This is a clear statement that Dunwoody believes that a child in DeKalb (which also means in Dunwoody) can be properly educated for $8600  per year. Now they are quick to point out that with the same millage rate Dunwoody would take in over $12,600 per student per year but it bears restating: Dunwoody claims that a student can be properly educated for $8600 per year. In fact Dunwoody claims they can do even better as they tout anticipated fiscal efficiencies due to their smaller system with lowered administrative overhead.

Given approval by the Legislature and voters across Georgia it appears that Dunwoody will be granted the option to unilaterally choose whether or not to "Cut the Cake" with an a priori assignment of the pieces. Any hope of equitable envy-free distribution rests on use of the hybrid approach with the State Legislature playing the role of Mum. This is easily done and need not be post facto. The legislature simply needs to ensure that the applicable law requires that new schools operate with per student expenditures equal to or less than that of the system they leave behind:
"To ensure efficacy of newly created City Schools these schools will operate on a budget not to exceed the per FTE budget of the existing System after the City Schools separate. This budget limitation will be in effect for ten years after which the budget can only be raised with approval of voters in the City."

* Food seems to be the Computer Scientists' friend beginning with the analogy of the dining philosophers.
** This is a ten dollar word for "fair" but anyone, especially computer scientists who've grappled with "fair" allocation of resources know there is no such thing. Consequently the ten dollar word is preferred.