All › Fair division › Query complexity of envy-free cake-cutting

More in “Query complexity of envy-free cake-cutting”

• Lower bound
• For n=3, there is an algorithm with 54 queries.
• For n\geq 4, no finite algorithm is currently known.
• For n=3, there is an algorithm that attains 1/3, which is optimal.
• For n=4 (the smallest open case), there is an algorithm that attains 1/7.
• For any n, there is an algorithm that attains 1/(3n).
• For n\geq 3, a finite algorithm does not exist for n-1 cuts (1 piece per agent).
• For n=3, Selfridge–Conway procedure solves the problem in finite time with 5 cuts (and at most 2 pieces per agent).

Another random fair division problem →