Research map / Learning theory and algorithms / Submodular and game algorithms
Fair Division via the Cake-Cutting Share
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.
Defines cake-cutting and envy-free fair shares that account for other agents' utilities via envy constraints, and proves tight Θ(√n) worst-case approximation bounds (plus O(m^{2/3}) for CCS in terms of items) for allocating divisible items with linear valuations.
Problem
Fair division of divisible items with linear valuations: proportionality ignores other agents' utilities and can be far too small, so the paper asks whether more informative fair shares (cake-cutting and envy-free shares) can be approximated simultaneously for all agents.
Approach
Fair shares are defined as max-min values in a cake-cutting game where agent i knows other agents' utilities and constrains its bundle so each other agent weakly prefers the proportional split (CCS) or does not envy the agent's bundle (EFS); the worst-case approximation is bounded via a dual-fitting argument on an LP reduced to binary valuations.
Key results
- For CCS and EFS, the worst-case approximation is Theta(sqrt(n)), via a dual-fitting upper bound and a projective-plane lower bound.
- CCS achieves O(m^{2/3}) approximation in terms of number of items, with an Omega(sqrt(m)) lower bound.
- Empirically, CCS approximation ratio is close to 1 while PROP is much higher than 1 and EFS much lower than 1 on simulated and Yahoo data (n=20-25).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CCS instead of PROP | Fair-share targeting on simulated uniform-value instances · Simulated uniform-value instances | approximation ratio θ | Mixed |
| Use CCS instead of EFS | Fair-share targeting on simulated uniform-value instances · Simulated uniform-value instances | simultaneous achievability of shares | Helped |
| Use CCS rather than EFS | Fair-share targeting on Yahoo A1 instances · Yahoo A1 | feasibility of shares | Helped |
| Use CCS rather than PROP or EFS | Fair-share targeting under Bernoulli and intrinsic-value utility models · Bernoulli and Intrinsic Value models | approximation ratio θ closeness to 1 | Helped |
| Increase Δ | EFS^Δ · Simulated and Yahoo datasets | approximation ratio θ | Helped |
Surprising findings
- The envy-free share can be unachievable simultaneously for all agents in practice (EFS approximation ratio well below 1), while CCS is nearly achievable.
Limitations
- Results restricted to divisible items with additive linear valuations
- Worst-case bounds are Theta(sqrt(n)) which is non-trivial only asymptotically; O(m^{2/3}) bound has a factor 3 in the algorithm
Experimental setup
Datasets: Yahoo A1 advertiser bid data
Benchmarks: Yahoo A1 advertiser bid data (simulated and real instances)
Metrics: approximation ratio theta
Baselines: proportional share envy-free share (EFS) maximin share
Builds on: proportionality envy-freeness maximin share
Closest papers by meaning
- Mind the Gap: Cake Cutting With Separation (AAAI 2021 · similarity 0.93)
- On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness (NeurIPS 2025 · similarity 0.92)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.90)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.90)
- Fair Division with Market Values (AAAI 2025 · similarity 0.90)
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.89)
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.