Jump to content

Robertson–Webb query model

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Erel Segal (talk | contribs) at 18:04, 17 February 2021 (→Results). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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 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, Evali(x,y) asks agent i to report the value of the interval [x,y], i.e., vi ([x,y]).
  • A cut query: given two real numbers x and r, Cuti(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 Cut(0, V1 / 2) query; let x1 be the answer (this is Alice's cut which yields to 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 of these problems are:

  • Proportional cake-cutting requires Ω(n log n) RW queries when either (a) the pieces must be connected,[2] or (b) the protocol is deterministic[3], or (c) the precision of cutting the cake is finite.[3] The only protocol which uses O(n) RW queries is a randomized protocol, which can return disconnected pieces, and the allocation can be only fractionally-proportional.
  • Envy-free cake-cutting requires Ω(n2) RW queries when the pieces may be disconnected,[4] and might return infintiely many queries when the pieces must be connected and there are at least 3 agents.[5] In other words, there is no algorithm that always finds an envy-free allocation among 3 or more agents using finitely-many queries.

References

  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.
  2. ^ a b 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.
  3. ^ a b Edmonds, Jeff (2006). Cake cutting really is not a piece of cake. pp. 271–278. CiteSeerX 10.1.1.412.7166. doi:10.1145/1109557.1109588. ISBN 978-0898716054. {{cite book}}: |journal= ignored (help), Edmonds, Jeff (2011). "Cake cutting really is not a piece of cake". ACM Transactions on Algorithms. 7 (4): 1–12. CiteSeerX 10.1.1.146.1536. doi:10.1145/2000807.2000819. S2CID 2440968.
  4. ^ Procaccia, Ariel (2009). "Thou Shalt Covet Thy Neighbor's Cake". IJCAI'09 Proceedings of the 21st International Joint Conference on Artificial Intelligence: 239–244.
  5. ^ Stromquist, Walter (2008). "Envy-free cake divisions cannot be found by finite protocols" (PDF). Electronic Journal of Combinatorics.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Robertson–Webb_query_model&oldid=1007351573"