Optimisation and game theory · Maths EE idea · Solid

Cutting a cake fairly

A research question to start from

How can a cake be divided among three people so that nobody envies another's piece, and what is the cost of envy-freeness?

A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.

Why it works as a maths EE

Algorithms whose fairness can be proved, with different fairness notions to compare.

Mathematics you would need

Proportional and envy-free division
Valuation functions
Proofs of algorithm properties
Counting cuts

Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.

One possible line of attack

Prove divide-and-choose is envy-free for two.
Analyse a proportional method for n people.
Work through and prove an envy-free method for three.

Scope and difficulty

Solid. Solid.

Pitfalls

Descriptive essay.
Proofs missing.

Where to start reading

Search a library catalogue or a university's open lecture notes for: Selfridge-Conway envy-free cake cutting proof; proportional division. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).

Make it your EE

Plan this EEOpens the free EE planner with this question as a starting point. Sharpen the questionSix quick checks for a focused research question. Self-check a draftCheck a section against each criterion, free.