Your half is bigger than mine...... NOT! -- On fair division

The problem of fair division can be traced back a full 3000 years in history. Stated in simple terms, the problem is:

How do you divide a cake between n people such that each person gets a fair share of the cake? An additional clause is that if someone thinks they got lesser than someone else, then it should be such that, that person alone is to bear the blame.

Lets first consider the case of n=2. If there are two people involved, say Alice and Bob, the solution is simple -- "Alice cuts, Bob chooses". So the best solution for Alice in this scenario is to cut such that she feels both shares are equal halves, so that no matter which piece Bob chooses, she's happy with the other one. Best solution for Bob is that he chooses the piece he thinks is bigger. Now, if Alice didnt cut it into equal halves, and Bob chooses the bigger one, she has only herself to blame for being left with the smaller piece.

If you now extend this to n=3, the problem becomes extemely complicated. You can imagine how the above solution can be extended. Say Tom, Dick, and Harry are trying to divide the cake equally between themselves. You can imagine a solution where Tom cuts the cake into what he thinks are 1/3rd and 2/3rds. Then Dick cuts the 2/3rd piece into two halves. Harry picks one of the three pieces. Tom picks next, and the left over piece goes to Dick.

Some elementary analysis will reveal that this is fair to Tom and Harry, and not fair to Dick. Now, clearly, Harry is satisfied. There are three pieces and he picks the biggest of the three. Tom comes next. If Harry picked one of the pieces that Dick cut, then Tom can take the piece that he cut (as 1/3rd) and be satisfied. If Harry picks the 1/3rd piece that Tom cut, then Tom can take whichever of the other two he thinks is bigger -- at this stage it is a two-person problem betwen Tom and Dick, since he thinks the 2/3rd really was a 2/3rds.

The story for Dick though is very different. If Dick initially thought Tom's cut was fair, then he has no issues, and the solution works for all. However, if Dick thinks Tom's cut was unfair and the 2/3rd was smaller than actual 2/3rd, then no matter what, he will end up with an unfair deal.

The way to fix the solution is to not let Dick think Tom's cut was unfair. This is achieved by allowing Dick to "trim" Tom's 1/3rd version and adding that into the 2/3rd share before making the second cut. Now if Harry thought Tom's cut was fair, then he will pick from Dick's cut since he thinks that is bigger. Tom will also pick from Dick's cut. And Dick can take the "trimmed" 1/3rd since he thought that was a fair 1/3rd. The deal with this solution is it will take 3 cuts (one by Tom, one "trim" by Dick, and another by Dick). If you generalize this to the n player version, then this algorithm will take n*(n-1)/2 cuts.

This problem has been addressed by a lot of mathematicians in history. The first (erroneous) solution for the 3 person problem was provided by Robertson and Webb. The corrected n*(n-1)/2 cuts solution was provided in 1944 by Hugo Steinhaus. Since then advanced concepts in mathematics have chosen this problem to purvey their theories. We'll see a non-envy version of this problem later in this post. Fair division is a very practical problem in the real world. Be it geek-ish like bandwidth sharing, or esoteric like dividing Jerusalem and West Bank. As a twist, the problem gets very intricate and interesting when different parties believe different parts of the cake are better than other parts.

We extend the original problem to fair division without envy. In the earlier case, everyone got a fair deal, but we potentially still had people imagining that others got more than them. In fact, that was the case in all solutions except the 2 person scenario. The two person "I cut, you choose" scenario is guaranteed to be envy-free.

Lets define a cake-division as envy-free if no one thinks that someone else got a larger piece than they did. An envy-free division is always guaranteed to be fair. However a fair division need not be envy-free at all.

Lets look at a solution for the 3-person case envy-free fair division -- same drill: Tom, Dick, and Harry want to divide a cake fairly between them in an envy-free fashion -

• First, Tom divides the cake into three parts which he thinks are equal 1/3rds.
• Next, (a) if Dick thinks the two largest pieces are equal, he does nothing, otherwise (b) Dick trims one piece to achieve two equal largest pieces.
• Now, Harry, Dick, and Tom in that order pick. If Dick trimmed a piece earlier, then he has to pick the trimmed piece unless Harry has already picked it.

At this stage, you have an envy-free fair division of three pieces. What is leftover is the problem of dividing the "trimming".

• Now, if Dick didnt trim, then there is nothing to do. If he did trim, then either Dick or Harry took the trimmed piece. We'll assume Dick took the trimmed piece. (Substitute Harry for Dick in the rest of the solution if Harry took the trimmed piece.) Dick now divides the "trimming" into three equal parts.
  
• Harry, Tom, and Dick in that order now pick. Harry picks first, so he's not envious at all. Tom picks next, but he's absolutely not envious since this trimming is already a bonus for him -- he thought his first three way cut was already equal 1/3rds. Dick picks the last one, but he isnt envious either since he divided the "trimmings" 3-ways.
  

When you extend this to a n-person scenario, the problem becomes extremely complicated. Found a wikipedia link on Fair Division. Wikipedia talks about many versions of the problem and how after a century of solutions Steven Brams and Alan Taylor finally solved it in 1995. That was the solution for the general n-person envy-free fair division. That came 30 years after the first 3-person envy-free fair division solution. The first I came across this problem was when I heard Alan Taylor give a rather animated talk on this at Yale back in 1998.

A Psalm of Life

Henry Wadsworth Longfellow, was easily one of the most popular and prolific American poets of the 19th century. As always the Wikipedia has a detailed page on the life and times of Longfellow.

The Encyclopaedia Britannica has this to say of Longfellow --

During his lifetime Longfellow was loved and admired both at home and abroad. In 1884 he was honoured by the placing of a memorial bust in Poets' Corner of Westminster Abbey in London, the first American to be so recognized. Sweetness, gentleness, simplicity, and a romantic vision shaded by melancholy are the characteristic features of Longfellow's poetry. He possessed great metrical skill, but he failed to capture the American spirit like his great contemporary Walt Whitman, and his work generally lacks emotional depth and imaginative power. Some years after Longfellow's death a violent reaction set in against his verse as critics dismissed his conventional high-minded sentiments and the gentle strain of Romanticism that he had made so popular. This harsh critical assessment, which tried to reduce him to the status of a mere hearthside rhymer, was perhaps as unbalanced as the adulation he had received during his lifetime. Some of Longfellow's sonnets and other lyrics are still among the finest in American poetry, and Hiawatha, "The Wreck of the Hesperus," Evangeline, and "Paul Revere's Ride" have become inseparable parts of the American heritage. Longfellow's immense popularity helped raise the status of poetry in his country, and he played an important part in bringing European cultural traditions to American audiences.

Today's poem titled A Psalm of Life was interestingly also titled (by Longfellow himself) A Psalm of Death, before Longfellow decidedly changed the title to meet the optimistic sentiment he gushes forth in the poem.

A Psalm of Life

What the heart of the young man said to the psalmist

Tell me not, in mournful numbers,
Life is but an empty dream! --
For the soul is dead that slumbers,
And things are not what they seem.

Life is real! Life is earnest!
And the grave is not its goal;
Dust thou art, to dust returnest,
Was not spoken of the soul.

Not enjoyment, and not sorrow,
Is our destined end or way;
But to act, that each to-morrow
Find us farther than to-day.

Art is long, and Time is fleeting,
And our hearts, though stout and brave,
Still, like muffled drums, are beating
Funeral marches to the grave.

In the world's broad field of battle,
In the bivouac of Life,
Be not like dumb, driven cattle!
Be a hero in the strife!

Trust no Future, howe'er pleasant!
Let the dead Past bury its dead!
Act, -- act in the living Present!
Heart within, and God o'erhead!

Lives of great men all remind us
We can make our lives sublime,
And, departing, leave behind us
Footprints on the sands of time;

Footprints, that perhaps another,
Sailing o'er life's solemn main,
A forlorn and shipwrecked brother,
Seeing, shall take heart again.

Let us, then, be up and doing,
With a heart for any fate;
Still achieving, still pursuing,
Learn to labor and to wait.

-- Henry Wadsworth Longfellow

In one of the early stanzas Longfellow urges the reader to "Be not like dumb driven cattle, Be a hero in the strife". I think, and history stands in evidence and judgement, that any mass or gathering of people collectively does not think. Only individuals think. Masses have strength and can execute extraordinary tasks. But thinking stays the prerogative of the individual. Situation not withstanding. One can conceive extreme examples in Hitler or Advani as the individual and the Gestapo or Kar-Sevaks and other following as the masses; to a handful of researchers as the individual, and a large company as the mass, which can execute and build real products like computers, space ships, etc. I think Longfellow understood this and therefore exhorts his fellowmen to be thinking individuals, to be heroes in strife and not be like dumb driven cattle.

Of course, some memorable phrases like Footprints on the sands of Time and entire stanzas on Trust no future, Dead past bury its dead, Heart for any strife, Learn to labor and to wait -- the simple elegance with which Longfellow puts forth fairly well thought out concepts with astonishing ease, make this a much loved poem.

On First Looking into Chapman's Homer

John Keats was exemplar of the turn of the 18th century romantic poets who had far reaching influence on poets to come long after his short 25 year lifespan. The ever-reliable Wikipedia has a well documented page on Keats. We'll, here, instead focus on today's poem, On First Looking into Chapman's Homer.

Keats was so moved by the power and aliveness of Chapman's (George Chapman, 1559 - 1634) translation of Homer that he wrote this sonnet--after spending all night reading Homer with a friend. The poem expresses the intensity of Keats' experience; it also reveals how passionately he cared about poetry. To communicate how profoundly the revelation of Homer's genius affected him, Keats uses imagery of exploration and discovery. In a sense, the reading experience itself becomes a Homeric voyage, both for the poet and the reader.

First, the poem itself, before we start analyzing the sonnet:

On First Looking Into Chapman's Homer

Much have I travell'd in the realms of gold,
And many goodly states and kingdoms seen;
Round many western islands have I been
Which bards in fealty to Apollo hold.
Oft of one wide expanse had I been told
That deep-brow'd Homer ruled as his demesne;
Yet never did I breathe its pure serene
Till I heard Chapman speak out loud and bold.
Then felt I like some watcher of the skies
When a new planet swims into his ken;
Or like stout Cortez, when with eagle eyes
He star'd at the Pacific - and all his men
Look'd at each other with a wild surmise -
Silent, upon a peak in Darien.

-- John Keats

As any Petrarchan sonnet, "On First Looking into Chapman's Homer" falls into two parts--an octet (eight lines) and a sestet (six lines). The octet describes Keats' reading experience before reading Chapman's translation and the sestet contrasts his experience of reading it. Keats builds up the scenario in the octet, with phrases like "Much have I travell'd" -- indicating the vastness of his reading, before talking about the triumphant entry Chapman's Homer makes in his literary universe in the sestet. Quite aptly, Keats chooses the metaphors of discovery in vast spaces, like a planet in the universe, or discovering the vast Pacific.

One, much-oft criticized point in the sonnet is that in reality it was Balboa the sailor who discovered the Pacific and not Cortez. An interesting theory proposed to reason this is that just as it was Homer who described the voyages of Odysseus and it was Chapman whose subsequent translation was what had caught Keats' heart and soul; the metaphor links to Cortez who repeated Balboa's original feat of viewing and describing the vastness of the Pacific.

I'll just end with what an anonymous writer has to say of Keats --

... more than any other writer before or since Shakespeare, he (Keats) had the ability to distil in its purest form that quality called 'poetry' in his verse. He doesn't use ornate or flowery language; his rhymes and rhythms are often less than perfect; his themes can be ordinary. And yet his words are just magical - pure music.

Ithaka

"The means are everything, the end matters not, ever." My grandfather never tired of telling me that when we were growing up. I would come back from school and tell him all that we learnt that day. He would nod indulgently, and unfailingly ask, "So you learnt all that today, what did you understand?". In keeping with what he preached, Constantine Cavafy's Ithaka was one of his favorite poems.

Cavafy's Ithaka is exactly just that. Ithaka is your goal, and the road to Ithaka is the fulfillment of that goal. Once you reach Ithaka, Ithaka has nothing left to give you any more.

Ithaka

As you set out for Ithaka
hope the journey is a long one,
full of adventure, full of discovery.
Laistrygonians and Cyclops,
angry Poseidon - don't be afraid of them:
you'll never find things like that on your way
as long as you keep your thoughts raised high,
as long as a rare excitement
stirs your spirit and your body.
Laistrygonians and Cyclops,
wild Poseidon - you won't encounter them
unless you bring them along inside your soul,
unless your soul sets them up in front of you.

Hope the voyage is a long one.
may there be many a summer morning when,
with what pleasure, what joy,
you come into harbours seen for the first time;
may you stop at Phoenician trading stations
to buy fine things,
mother of pearl and coral, amber and ebony,
sensual perfume of every kind -
as many sensual perfumes as you can;
and may you visit many Egyptian cities
to gather stores of knowledge from their scholars.

Keep Ithaka always in your mind.
Arriving there is what you are destined for.
But do not hurry the journey at all.
Better if it lasts for years,
so you are old by the time you reach the island,
wealthy with all you have gained on the way,
not expecting Ithaka to make you rich.

Ithaka gave you the marvellous journey.
without her you would not have set out.
She has nothing left to give you now.

And if you find her poor, Ithaka won't have fooled you.
Wise as you will have become, so full of experience,
you will have understood by then what these Ithakas mean.

-- Constantine Cavafy