Query Complexity Analysis
Comparing fair division algorithms through the Robertson-Webb lens
Complexity Comparison Table
| Algorithm | Players | Cut Queries | Eval Queries | Total |
|---|---|---|---|---|
| Divide-and-Choose | 2 | 1 | 1 | 2 |
| Austin's Moving Knife* | 2 | - | - | ∞ |
| Steinhaus Lone-Divider | 3 | 2-3 | 6-7 | 8-10 |
| Selfridge-Conway | 3 | 2-5 | 5-12 | 7-17 |
| Stromquist Moving Knife* | 3 | - | - | ∞ |
| Banach-Knaster Last-Diminisher | N | - | - | O(N²) |
| Brams-Taylor | N | - | - | $\Omega$(N) |
*Continuous algorithms require infinitesimal queries
Key Insights
Discrete vs. Continuous Procedures
The Robertson-Webb model reveals a fundamental trade-off between query efficiency and algorithmic properties:
- Discrete algorithms (like Divide-and-Choose) use finite queries but may sacrifice exactness
- Continuous algorithms (like Austin's Moving Knife) achieve stronger properties but require infinite query complexity
Lower Bounds
Theoretical results from the Robertson-Webb framework:
- Any proportional 2-player algorithm requires ≥ 2 queries
- Any envy-free n-player algorithm requires ≥ n queries
- Exact division generally requires continuous procedures