Robertson–Webb query model

Since the agents' valuations can be very complex, they cannot - in general - be given as inputs to a fair division algorithm.

The RW model specifies two kinds of queries that a fair division algorithm may ask the agents: Eval and Cut.

On the other hand, there are fair cake-cutting problems that provably cannot be solved in the RW model using finitely many queries.

In parallel, there are many hardness results, proving that certain fair division problems require many RW queries to complete.

Moreover, for any ε > 0: Maximin share cake-cutting, when the pieces must be separated by a positive distance, cannot be done using finitely-many RW queries.

In this model, there are knives moving continuously along the cake (see moving-knife procedures).

This model is related to the RW model as follows: any moving-knife procedure with a fixed number of agents and a fixed number of knives can be simulated using O(log ε−1) RW queries.

This allows to compute a proportional cake-cutting in time O(n) by simultaneously asking each agent for a discretization with n intervals (of equal value).

On the other hand, in the simultaneous model, it is impossible to compute an envy-free cake-cutting using a finite discretization for 3 or more agents; but for every e>0, there exists a simultaneous protocol with complexity O(n/e2), that attains an e-approximate envy-free division.