Fair Division 101

George Rebane

It’s usually tough to divide up a set of assets when a partnership breaks up, spouses get divorced, or any set of in/divisible assets or resources must be allocated between multiple parties.  The study of fair division algorithms has seen a considerable amount of research and it isn’t over yet.  A good fair division algo that is adopted by negotiating parties will go a long way toward achieving a mutually acceptable outcome.  I have found Fair Division: from cake-cutting to dispute resolution (1996) by Brams and Taylor to be an excellent survey of such algos.

We all know how two people should divide a cake into equal pieces so that neither would have a reasonable complaint – the algo prescribes that one cuts the cake, the other chooses his piece.  But what happens when there are three or more people who want to divide the cake equally, or even to divide the cake into agreed upon portions?  You can see how things can get complicated very quickly.

In this edition we will consider a simple yet powerful algo – let’s call it FD01 (developed by Bronislaw Knaster) – that allows two parties to divide up a disparate set of indivisible assets, one of which consists of cash.  The entire schema for FD01 is shown in the spreadsheet figure below.


The left column lists the six assets (the cash asset is not required).  Parties A and B agree that their split is 40-60 respectively as shown.  Each party has the assets appraised.  This step is not required, and may be completed mutually if desired, or the two appraisals may even be shared.

Both parties, using all the information available to each that may include tax considerations, future plans, and knowledge of the other’s propensities, will now place a ‘bid value’ by each asset that represents his own assessment of what he considers to be the dollar value of the asset to be used in the subsequent calculations.  Each party submits a sealed bid list for all assets to be divided.  The bid values for each are listed in their respective columns.

As agreed before hand, the bids may be submitted to a mutually agreed upon agent who applies the FD01 algo, or the parties may just work the shown spreadsheet by themselves.  The next step is to assign each asset to its highest bidder.  Each party then receives the assets at their own bid values as shown in the Receive column.  In the example, Party A received assets #2,3,4 for a self-assessed total of $5,700.   Pary B received assets #1,5,6 for a self-assessed total of $5,730.

Party A’s value for all the assets totaled $11,100 of which he would expect to receive a fair share of at least 40% or $4,440 as indicated.  Party B’s commensurate total value turned out to be $11,050 of which he would expect to receive a fair share of at least 60% or $6,650 as indicated.

Returning to the self-assessed total values that each received in the division of listed assets, it is clear that Party A received $1,260 in excess of his $4,440 fair share.  At the same time Party B’s self-assessed value of received assets falls short of his expected fair share of $6,630.  The algo concludes with each party writing a check to the amount of their self-assessed excess to the other party.  In the example Party A, after writing Party B a $1,260 check, winds up with $4,440, his exact self-assessed fair share.   Party B receives a total of $6,990 which is nominally $360 in excess of his $6,630 self-assessed fair share.  Neither party has grounds for complaint since each received at least as much as they each expected from the fair division.

Finally, from Party A’s perspective the bid total for Party B was $5,400 and his fair share should have been 60% of $11,100 or $6,660.  Therefore, from Party A’s perspective the assets received by Party B gave him a $1,260 shortfall.  Party A is then satisfied that the $1,260 check he gave to Party B brought him up to his fair share as assessed by Party A.  Both parties have therefore done well in their own and in each other’s eyes.

Multi-party use of the FD01 algo

If three or more parties wish to use FD01 in fairly dividing a list of assets according to agreed on proportions, then the algo can be applied sequentially.  If three parties are involved, then two parties working together will bid against the third party.  After that the two remaining parties will divide their mutual assets from the first division as described above.  It should be clear that this same divide-and-conquer approach can be used with any number of parties.

There are more complex fair division algos that can be used in a one-shot fashion for multiple parties.

I leave you with an exit exercise – try to game FD01 with some bidding strategy that would benefit one side against the other.  If you succeed, tell us about it – or not ;-)

Comments

[Douglas Keachie]

I wonder how a certain party's version of "dividing by 1/2" would play out here?

[Account Deleted]

Here's an article that reflects on what's "fair".
http://www.calwatchdog.com/2012/05/04/affirmative-action-attacks-gate-school-program/
Once again, we see that albino children are discriminated against. Is that fair?

[Douglas Keachie]

Life is never fair, it's always cloudy with mild to midd'lin tornadoes.

[George Rebane]

ScottO 623pm - Sadly I have to report that in my many decades I have yet to find a progressive who is even capable of reasoned discussing about the notion of 'fair'.

In your GATE example the Democrats behave like dummies, and just equate 'fair' with proportional representation that translates to state set quotas. Meritocracy is the last attribute they will promote in any public policy for the simple reason that their political well-being requires catering to the intellectually challenged constituencies. That is why we must understand that their apparent dummy-like behavior is actually a self-serving political ruse - in short, they promote perfidy under the banner of fairness which their constituents swallow hook, line, and sinker. What makes it all sad is that their voters aren't smart enough to realize how such policies keep them as perennial wards of the state. But it's a politically dynamite strategy for the moral relativists.

[Douglas Keachie]

I agree that GATES standards should not be changed, but also note that: 'The American Indian Public Charter School serves 200 inner-city students in fifth through eighth grade, and has an average API of 988" achieved this with 58% Asian and steady increases in performance, just enough to boost the API ticker up an achievable notch each year. An API index like this does NOT mean that this is the top elementary school in the state, and indeed it is not, but rather that it has made the next Mario jump each time correctly.

Maybe we should write our senators and the governor. What are the odds of it making it all the way through?

[billy T]

It becomes dog eat dog when many people what a bigger piece of a single pie. It gets downright eating one's own children time when somebody wants the whole enchilada. The EPA is continuing to gobble up chunks of the shrinking pie. At work we are going through the anal exam by the EPA. Odd cause we manufacture nothing, handle no fluids, create nothing but a service. Even all company vehicles are serviced at auto shops. In fact, I am forbidden to even change a taillight or fix a flat. But, here comes the EPA. A single dumpster inspection can run as high as $1,500, or at least $600.00 if you use an EPA approved inspector. They found gold at our dumpster. Somebody tossed a broken remote control with 2 AA batteries (probably cleaning out a closet)and we were fined 200 clams for the "electronic waste" and 200 clams each for the batteries for a cool 600 bucks plus inspection plus plus plus. Good thing nobody tossed an empty can of wasp spray or else all hell would have broken loose. Fair or not, reasonable or extreme, the pie is not being divided fairly and somebody has one humungous appetite. I bet the UPS store is next. http://www.soundviewwindowanddoor.com/uncategorized/standing-water-in-your-birdbath-that-will-be-a-300-fine

[Douglas Keachie]

Well, I'd have more sympathy for WM if they'd have a more reasonable sized minimum load, and fees to match. 400 lbs costs $12 in Marysville, and that makes much better sense than what I think was last $30 for 2,000 lbs. Then EPA could go bust the homeowner as they threw the stuff into the general heap.

Also, why not have battery containers and e-waste containers out at the transfer stations like NSJ? You do get oil and tires, that's nice, why not complete the cycle? Also, can I put broken window glass and mirrors into the mixed recyclables bin?

Seems to me that posting your story on sites like the transfer stations might do some good, but then maybe some would deliberately go out of their way to get you fined. BTW, Carol Chadima does a most excellent job out at NSJ, and so does her substitute.

[billy T]

Concerning dividing up the cake, I will continue. Every little town and county and state is looking high and low for M O N E Y. Your money, my money, anyone's money. The EPA is just a small example. We played ball with them and proved we were going green. Started a big paper recycling drive and even cut out all Sytrofoam coffee cups and went paperless to win their favor. We passed out one green "coffee" cup with lid to all employees. But, unless you washed them out often, the bottom would literally fall out within 3 weeks. The lids would also break off after a couple of weeks. The big joke is the green coffee cups are job security for the carpet cleaners. We tried to look good and played ball. Even got kudos. All it really got us was an open door for them to fine, fine and inspect. It ain't about the environment anymore, its about funding the EPA. Same with cigs. Now that the Big Tobacco settlements are drying up, the states are taxing ciggies more and more with less PSAs about the dangers of smoking. Its now about money, not trying to get people to stop smoking. Sugar is deemed bad so they tax cookies and sodas even higher. Alcohol is bad, so tax beer more and more as revenues are declining. They want a piece of the pie, even though taxing cookies and milk (some states started taxing milk) hurts the poor working stiffs. Thought the California Lottery was going to fund our schools, but I digress. No, there ain't enough money in the world for these control freaks and when given more money they have a knack for throwing it up into the wind and come back and ask for even more of the pie. Our servants have become our slave masters. Of course the people will always find a way around it. When in Northeast WA State a couple of summers ago, the local TV station ran a good example. WA jacked up its cigs to about $7/pack, while Idaho was cheaper, a lot cheaper. A woman was pulled over for a traffic violation and they found she had bought a carton of smokes in Idaho without paying WA cig taxes. She was fined $200.00, the same fine as if she was carrying an ounce of pot while driving. Doug, the dumpster divers are picking on the deep pockets, i.e. businesses first. Wait till we all have trash can police like Frisco. Imagine paying a $200.00 fine for a near empty bottle of Windex or a AAA battery. Then, once they get your number, they never will let you go. Its all in the name of your health or the environment, but in reality its all about feeding the beast. Even as I type this Congress is considering taxing the 401Ks. They tax you on the money you earn, tax you on the money you put aside for retirement, then tax you when you pull it out. The pie is shrinking and the libbies are getting desperate.

[Douglas Keachie]

"Thought the California Lottery was going to fund our schools" not hardly. It was sold to the voters as a way of generating extra enrichments for schools. It hovers around 1% of the total funding for k-12:

"Lottery Payments Are a Small Part of Education Funding. In the 2008-09 fiscal year, the lottery sold about $3 billion of tickets, paid out $1.6 billion in prizes, and spent $396 million on operating expenses, most of which consist of sales commissions, bonuses, and other payments to the retailers that sell lottery tickets. This left just over $1 billion in lottery profits, which were distributed to public educational entities based on their number of students. This amount represents only a small part of the overall budget of California's public education institutions. For kindergarten through twelfth-grade schools, for example, lottery funds made up just over 1 percent of all revenues in 2008-09."

And it is now considered to be a line income item, for normal expenses. Those that operate it get 40% of the amount that the schools get.

My mistake, I thought you were part of WM. In San Francisco most businesses keep locks on their dumpsters all the time, too much illegal dumping. It;s a pain, but for $1200 I'd do it. Then have a $1 a day fund, and each year that goes by with no fines, four employees will get $100, $100, $100, and $65 by lottery. That should avoid internal mistakes.