Robertson–Webb query model
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. The name "Robertson–Webb model" was coined and formalized by Woeginger and Sgall.
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 vi on the cake. The algorithm does not know vi, 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., vi ([*x*,*y*]).
- A mark query (also called a cut query): given two real numbers x and r, Mark*i*(*x*,*r*) asks agent i to report some value y such that vi([*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 V1 be the answer (this is Alice's value of the entire cake).
- Ask Alice a Mark(0, V1 / 2) query; let x1 be the answer (this is Alice's mark which yields two pieces equal in her eyes).
- Ask George an Eval(0, x1) and an Eval(x1, 1) queries.
- If the former value is larger, give (0,x1) to George and (x1,1) to Alice; else, give (0,x1) to Alice and (x1,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(n2) RW queries and even–paz-protocol can be done by O(n log n) RW queries. In parallel, there are many hardness results, proving that certain fair division problems require many RW queries to complete. Some such hardness results are shown below.
- proportional-cake-cutting** requires Ω(*n* log *n*) RW queries when either
- the pieces must be connected, or
- the precision of cutting the cake is finite.
- envy-free-cake-cutting** requires
- Ω(n2) RW queries when the pieces may be disconnected,
- Infintiely many queries when the pieces must be connected and there are at least 3 agents. In other words, there is no algorithm that always finds an envy-free allocation among 3 or more agents using finitely-many RW queries.
- For any ε > 0, an ε-envy-free connected cake-cutting requires at least Ω(log ε−1) queries. For 3 agents, an O(log ε−1) protocol exists. For 4 agents, an O(poly(log ε−1)) protocol exists. For 5 or more agents, the best known protocol requires O(n ε−1), which shows an exponential gap in the query complexity.
- equitable-cake-cutting** cannot be done using finitely-many RW queries even for 2 agents. For 3 or more agents, the best known protocol requires O(*n* (log *n* + log ε−1)) queries.
- Even without connectivity, ε-equitable cake-cutting requires at least Ω(log ε−1 / log log ε−1 ) RW queries.
- Exact cake-cutting (also known as perfect cake-cutting**) cannot be done using finitely-many RW queries even for 2 agents. Moreover, for any ε > 0:
- An ε-perfect cake-cutting with the minimum possible number of cuts requires at least Ω(log ε−1) queries. For 2 agents, an O(log ε−1) protocol exists.
- maximin-share cake-cutting**, when the pieces must be separated by a positive distance, cannot be done using finitely-many RW queries. Moreover, even for *a single* agent, there is no algorithm that computes the agent's maximin-share using finitely-many RW queries. However:
- For any ε > 0, it is possible to compute a value between the MMS and the MMS-ε using O(n log ε−1) RW queries.
- When the cake is circular (i.e., in fair-pie-cutting), it is possible to compute a value between the MMS and the MMS-ε using O(n ε−1) RW queries. It is open whether O(n log ε−1) RW queries suffice.
- Average-proportional cake-cutting** (i.e., an allocation between *n* *families*, such that for each family, the average value is at least 1/*n* of the total) cannot be computed using finitely-many RW queries, even when there are 2 families with 2 members in each family. The proof is by reduction from equitable cake-cutting.
Variants ### Left-mark and right-mark When the value measure of an agent is not strictly positive (i.e., there are parts that the agent values at 0), a mark query can, in principle, return infinitely many values. For example, if an agent values [0,0.9] at 1 and [0.9,1] at 0, then the query Mark(0,1) can return any value between 0.9 and 1. Some algorithms require a more specific value:
- The left-mark query, LeftMark(x,r), returns the leftmost (smallest) y such that vi ([*x*,*y*]) = r;
- The right-mark query, RightMark(x,r), returns the rightmost (largest) y such that vi ([*x*,*y*]) = r;
If only one of these two variants is given (in addition to the Eval query), the other variant cannot be computed in finite time. and multi-dimensional cakes.