Exact Envy-Free Cake Cutting with Polynomial Expected Queries

Simon Mackenzie and Mashbat Suzuki investigate a longstanding question in fair division: how much preference information is needed to divide an entire cake so that no agent prefers another agent’s share? The cake represents a divisible resource, and agents have nonnegative, additive, nonatomic valuations, meaning that individual points have zero value. Each share may consist of several disconnected intervals. Previous deterministic protocols established finite query bounds depending only on the number of agents, but those bounds remained enormous. According to the paper, the best previous upper bound was a polynomial factor times \(2^n\), whereas the general lower bound is quadratic. The paper’s central contribution is a randomized protocol that achieves complete, exact envy-freeness with polynomial expected query complexity for every fixed valuation profile, without assuming that preferences are randomly distributed. The protocol operates in the Robertson–Webb model. Evaluation queries ask an agent to value an interval, while cut queries locate a point that yields a specified value. All answers are exact, and randomness comes exclusively from independent uniform draws from the unit interval. The main theorem guarantees almost-sure termination and a complete, exactly envy-free allocation, with expected query complexity \(O(n^{30})\). The expected number of uniform draws is also polynomial. The method combines three local procedures: Repair, Shrink, and Snapshot. Repair begins with existing bundles and an additional buffer of cake, assuming that initial envy is sufficiently small relative to each agent’s value of the buffer. It reassigns the existing bundles without splitting them and adds small cake payments to eliminate envy. These additions consume at most one-quarter of the buffer according to every participating agent, and each agent receives an allocation she values at least as highly as every original bundle. Each repair trial succeeds with probability greater than \(63/64\). The main technical innovation is the conversion of numerical compensation into physical cake payments without introducing new envy. After normalizing each agent’s reserve value to one, the protocol computes credits using a maximum-value bundle assignment and longest-path compensation constraints. Small random additions separate competing assignments enough to accommodate payment errors. A fractional payment plan is then simplified until at most \(k^2\) cells remain split, where \(k\) is the current number of agents. Whole cells provide most of the payments, and randomized correction pieces fill recipients’ deficits exactly. A sampling argument controls discrepancies even when later cuts depend on previously observed values. Every accepted output undergoes exact verification. Shrink repeatedly constructs envy-free partial allocations that reduce every participant’s value of the remainder. Snapshot either completes the division or establishes an advantage worth an inverse-polynomial fraction of the remaining cake. The completion procedure saves \(k^2\) snapshots at each stage, shrinks the residue, and uses directed graphs to reassign saved bundles. A final repair preserves enough advantage for a nonempty group to stop participating safely while the remaining agents divide the residue. The analysis bounds the expected number of attempts by \(O(n^5)\), with each attempt requiring \(O(n^{25})\) queries. A capped variant uses \(O(n^{30}(1+\log(1/\delta)))\) queries on every run and succeeds with probability at least \(1-\delta\). Otherwise, it reports failure; it never returns an incorrect allocation. The computation is polynomial in expectation under unit-cost exact real arithmetic, though not necessarily in binary running time. The presentation assumes hungry agents, but the authors state that the results extend beyond this assumption. Whether deterministic polynomial query complexity is possible, and whether uniform-real randomness can be replaced by polynomially many fair-coin bits, remain open questions.

A Randomized Breakthrough in Envy-Free Cake Cutting

How much do we need to know about people’s preferences to divide a resource fairly? In “Exact Envy-Free Cake Cutting with Polynomial Expected Queries,” Simon Mackenzie and Mashbat Suzuki tackle a longstanding version of this question: dividing an entire cake so that nobody prefers someone else’s share. Their central result shows that randomness can dramatically reduce the expected amount of preference information needed, while preserving exact fairness.

What Makes a Division Envy-Free?

The “cake” is a mathematical stand-in for a divisible resource. Different agents may value different parts, and each person’s share can contain several disconnected intervals. Valuations are nonnegative and additive, so the value of separate pieces adds up. They are also nonatomic: individual points have zero value.

An allocation is envy-free when every agent values her own share at least as highly as every other agent’s share. Completeness means that the entire cake is allocated. The challenge is to achieve both properties exactly, rather than leaving a remainder or tolerating a small amount of envy.

Earlier deterministic protocols established finite query bounds depending only on the number of agents, but those bounds remained enormous. According to the paper, the best previous upper bound was a polynomial factor times 2 to the power n, where n is the number of agents. The general lower bound, meanwhile, is quadratic. That gap leaves considerable room for improvement.

Randomness Without Random Preferences

Mackenzie and Suzuki give a randomized protocol with expected query complexity O(n^30). The exponent is large, but the qualitative change is significant: the expected bound is polynomial rather than exponential.

Crucially, the guarantee holds for every fixed valuation profile. The protocol does not assume that agents’ preferences come from a convenient random distribution. Instead, randomness belongs entirely to the procedure, through independent uniform draws from the unit interval.

The protocol operates in the Robertson–Webb model, which provides two ways to learn about preferences:

• Evaluation queries ask an agent how much she values a specified interval.
• Cut queries ask for a point that gives an interval a specified value.

All answers are exact. The main theorem guarantees almost-sure termination and a complete, exactly envy-free allocation. The expected number of uniform random draws is polynomial as well.

Repair: Turning Compensation into Cake

The method combines three local procedures: Repair, Shrink, and Snapshot. Repair addresses a delicate problem. Suppose agents already have bundles, plus access to an additional buffer of cake, and their initial envy is sufficiently small relative to how much each values that buffer. Can small additions eliminate envy without creating new envy elsewhere?

Repair reassigns the existing bundles without splitting them and adds cake payments. These additions consume at most one-quarter of the buffer according to every participating agent. Each agent ends up with an allocation she values at least as highly as every original bundle. Each repair trial succeeds with probability greater than 63/64.

The main technical innovation is converting numerical compensation into physical cake. A numerical credit is easy to describe; a piece of cake may have different values to different recipients and observers. Paying one agent can therefore disturb someone else’s fairness comparison.

After normalizing each agent’s reserve value to one, the protocol computes credits using a maximum-value bundle assignment and longest-path compensation constraints. Small random additions separate competing assignments enough to tolerate payment errors. A fractional payment plan is then simplified until at most k^2 cells remain split, where k is the current number of agents.

Whole cells supply most payments, while randomized correction pieces fill recipients’ deficits exactly. A sampling argument controls discrepancies even when later cuts depend on previously observed values. Importantly, every accepted output undergoes exact verification: randomness helps find a valid allocation, rather than weakening the fairness requirement.

Shrinking the Remainder and Saving Advantages

Shrink repeatedly constructs envy-free partial allocations that reduce every participant’s value of the remainder. Snapshot either completes the division or establishes an advantage worth an inverse-polynomial fraction of the remaining cake.

The completion procedure saves k^2 snapshots at each stage, shrinks the residue, and uses directed graphs to reassign saved bundles. A final repair preserves enough advantage for a nonempty group to stop participating safely while the remaining agents divide the residue. The analysis bounds the expected number of attempts by O(n^5), with O(n^25) queries per attempt.

What the Guarantee Does—and Does Not—Mean

A capped variant uses O(n^30(1 + log(1/δ))) queries on every run and succeeds with probability at least 1 − δ. Otherwise, it reports failure; it never returns an incorrect allocation.

The computational guarantee assumes unit-cost exact real arithmetic, so polynomial expected computation does not necessarily mean polynomial binary running time. The presentation assumes hungry agents, although the authors state that the results extend beyond that assumption.

Two major questions remain open: whether deterministic polynomial query complexity is possible, and whether polynomially many fair-coin bits can replace uniform-real randomness. For now, the result establishes that complete, exact envy-freeness can be achieved with polynomial expected queries without placing a probability distribution on people’s preferences.