Robertson-Webb Query Model

A computational framework for analyzing fair division algorithm complexity

Overview

The Robertson-Webb query model provides a theoretical framework for measuring the computational complexity of fair division algorithms. Rather than counting traditional operations, this model measures complexity in terms of queries to players about their preferences.

Query Types

Cut Queries

Format: "Cut the cake at position $x$ such that the left piece has value $v$ to you."

Used when algorithms need players to make specific cuts based on their valuations.

Eval Queries

Format: "What is the value of this piece to you?"

Used when algorithms need to determine how players value given pieces.

Applications to Fair Division

Query Complexity Analysis

Different algorithms require different numbers of queries:

  • Divide-and-Choose: 1 cut query + 1 eval query = 2 total queries
  • Austin's Moving Knife: Continuous eval queries until stopping condition
  • Steinhaus Lone-Divider: 2 cut queries + multiple eval queries

Lower Bounds

The model helps establish theoretical limits on algorithm efficiency. For example, any proportional division algorithm for $n$ players requires at least $n-1$ queries.

We use an adversarial argument with a communication complexity reduction. Consider the following problem: given $n-1$ bits, $b_1, b_2, ..., b_{n-1}$, compute their OR. We can reduce this to a proportional division problem as follows:

  • Significance

    This framework is crucial because:

    • It provides a realistic model where players' preferences are private
    • It enables fair comparison between different algorithmic approaches
    • It bridges theoretical computer science and practical mechanism design