On the Complexity of Envy-Free Cake Cutting

Details On the Complexity of Envy-Free Cake Cutting On the Complexity of Envy-Free Cake Cutting

2009-07-08

arxiv.org/abs/0907.1334v1

Computer Science

Computer Science and Game Theory

Scientific paper

We study the envy-free cake-cutting problem for $d+1$ players with $d$ cuts, for both the oracle function model and the polynomial time function model. For the former, we derive a $\theta(({1\over\epsilon})^{d-1})$ time matching bound for the query complexity of $d+1$ player cake cutting with Lipschitz utilities for any $d> 1$. When the utility functions are given by a polynomial time algorithm, we prove the problem to be PPAD-complete. For measurable utility functions, we find a fully polynomial-time algorithm for finding an approximate envy-free allocation of a cake among three people using two cuts.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of Envy-Free Cake Cutting does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Complexity of Envy-Free Cake Cutting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Envy-Free Cake Cutting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-319843