Research map / Learning theory and algorithms / Submodular and game algorithms
On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces CHB-k and CLB-k fairness hierarchies between proportionality and super envy-freeness, gives an O(n^4)-query protocol for CHB-n, and proves Omega(n^2) and unbounded-query lower bounds for CHB-2 and CLB-2 in the Robertson-Webb model.
Problem
Understanding the query complexity of fairness notions lying between proportionality and perfection/envy-freeness in cake cutting, where envy-free query complexity is huge (upper bound tower of exponents, lower bound Omega(n^2)).
Approach
Define two hierarchies of group-fairness notions (CHB-k with harmonic bound, CLB-k with linear bound) bounding the value a subset of agents collectively gets from others' pieces; show CHB-n is a superset of envy-free and computable in O(n^4) queries via phantom agents and a Last Diminisher-style residue allocation, while CLB-2 is impossible with bounded queries.
Key results
- CHB-n allocations computable with O(n^4) Cut and Eval queries in the Robertson-Webb model.
- Computing CHB-2 allocations requires Omega(n^2) queries.
- Computing CLB-2 allocations requires unboundedly many queries (reduction from exact division), so CLB-n = super envy-freeness is not bounded-query computable.
- delta-CLB-n allocations computable with O(n^6/delta * ln(n/delta)/ln(n)) queries (per the paper's stated bound).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Strengthen proportionality to CHB-n | Cake-cutting allocations in the Robertson–Webb model · Complete CHB-n | query complexity: O(n \log n) for proportional allocations; O(n^4) for CHB-n | Mixed |
| Strengthen proportionality to CLB-2 | Cake-cutting allocations in the Robertson–Webb model · CLB-2, n ≥ 3 | query complexity: an infinite number of queries | Hurt |
| Relax CLB-n to δ-CLB-n | Cake-cutting allocations in the Robertson–Webb model · δ-CLB-n | query complexity: O\left(\frac{n^6}{\delta} \, \frac{\ln(1/\delta)}{\ln(n)} \right) | Helped |
| Require complete, proportional, and ε-perfect allocations | Recursive ε-perfect and Last Diminisher protocol · Complete, proportional, and ε-perfect allocations | query complexity: O\left(\frac{n^5}{\epsilon} \, \frac{\ln(1/\epsilon)}{\ln(n)} \right) | Helped |
Limitations
- Results are about discrete protocols in the Robertson-Webb model; no empirical evaluation.
- Gap between Omega(n^2) lower bound and O(n^4) upper bound for CHB-2/CHB-n remains open.
- Some proofs are sketched (e.g. super-query and recursion details) and delta-CLB-n bound is loosely stated.
Experimental setup
Metrics: query complexity
Baselines: Procaccia Omega(n^2) envy-free lower bound Aziz-Mackenzie envy-free protocol Brânzei-Miltersen epsilon-perfect protocol
Builds on: Brânzei-Miltersen epsilon-perfect allocation Procaccia envy-free lower bound Dubins-Spanier last diminisher Aziz-Mackenzie envy-free protocol
Closest papers by meaning
- Contiguous Cake Cutting: Hardness Results and Approximation Algorithms (AAAI 2020 · similarity 0.93)
- Fair Division via the Cake-Cutting Share (AAAI 2025 · similarity 0.92)
- Fair Division with a Secretive Agent (AAAI 2019 · similarity 0.92)
- Fair Allocation of Items in Multiple Regions (AAAI 2024 · similarity 0.90)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.90)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.