Robertson–Webb query model

In computer science, the Robertson–Webb (RW) query model is a model of computation used by algorithms for the problem of fair cake-cutting. In this problem, there is a resource called a "cake", and several agents with different value measures on the cake. The goal is to divide the cake among the agents such that each agent will consider his/her piece as "fair" by his/her personal value measure. 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. Informally, an Eval query asks an agent to specify his/her value to a given piece of the cake, and a Cut query (also called a Mark query) asks an agent to specify a piece of cake with a given value.

Despite the simplicity of the model, many classic cake-cutting algorithms can be described only by these two queries. On the other hand, there are fair cake-cutting problems that provably cannot be solved in the RW model using finitely many queries.

The Eval and Cut queries were first described in the book of Jack M. Robertson and William A. Webb.^[1] The name "Robertson–Webb model" was coined and fofmalized by Woeginger and Sgall.^[2]

Definitions

The standard RW model assumes that the cake is an interval, usually the interval [0,1]. There are n agents, and each agent i has a value measure v_i on the cake. The algorithm does not know v_i, but can access it using two kinds of queries:

An eval query: given two real numbers x and y, Eval_i(x,y) asks agent i to report the value of the interval [x,y], i.e., v_i ([x,y]).
A cut query: given two real numbers x and r, Cut_i(x,r) asks agent i to report some value y such that v_i ([x,y]) = r.

Example

The classic Divide and choose algorithm, for cutting a cake between two children, can be done using four queries.

Ask Alice an Eval(0,1) query; let V₁ be the answer (this is Alice's value of the entire cake).
Ask Alice a Cut(0, V₁ / 2) query; let x₁ be the answer (this is Alice's cut which yields to pieces equal in her eyes).
Ask George an Eval(0, x₁) and an Eval(x₁, 1) queries.
If the former value is larger, give (0,x₁) to George and (x₁,1) to Alice; else, give (0,x₁) to Alice and (x₁,1) to George.

Results

Besides divide-and-choose, many cake-cutting algorithms can be performed using RW queries whose number is polynomial in n (the number of agents). For example: Last diminisher can be done by O(n²) RW queries and Even–Paz protocol can be done by O(n log n) RW queries.

References

^ Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. ISBN 978-1-56881-076-8. LCCN 97041258. OL 2730675W.
^ Gerhard J. Woeginger and Jiri Sgall (2007). "On the complexity of cake cutting". Discrete Optimization. 4 (2): 213–220. doi:10.1016/j.disopt.2006.07.003.

[book-1] Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. ISBN 978-1-56881-076-8. LCCN 97041258. OL 2730675W.

[ws07-2] Gerhard J. Woeginger and Jiri Sgall (2007). "On the complexity of cake cutting". Discrete Optimization. 4 (2): 213–220. doi:10.1016/j.disopt.2006.07.003.

[1]

[2]