Research map / Learning theory and algorithms / Submodular and game algorithms
Fair and Efficient Online Allocations with Normalized Valuations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use guarded poly-proportional with p=2.7 instead of non-adaptive quadratic-proportional | Two-agent online allocation · Two agents, normalized valuations | optimal social welfare approximation: 0.894 -> 0.916 | Helped |
| Use quadratic-proportional (p=2) instead of proportional (p=1) | Non-adaptive online allocation · Two agents, normalized valuations | optimal social welfare approximation: 0.828 -> 0.894 | Helped |
| Use proportional allocation instead of equal-split | Non-adaptive online allocation · Two agents, normalized valuations | optimal social welfare approximation: 50% -> 82.8% | Helped |
| Add the guarded critical-point rule to poly-proportional allocation | Poly-proportional online allocation · Two agents, normalized valuations | fair-share | Helped |
| Raise p above 2 without the guard | Non-adaptive poly-proportional allocation · Two agents, normalized valuations | fair-share | Hurt |
| Set guarded poly-proportional p=2.1 rather than p=2.7 (ablation) | Guarded poly-proportional · Two agents, normalized valuations | optimal social welfare approximation: 0.898 -> 0.916 | Hurt |
| Set guarded poly-proportional p=2.2 rather than p=2.7 (ablation) | Guarded poly-proportional · Two agents, normalized valuations | optimal social welfare approximation: 0.902 -> 0.916 | Hurt |
| Set guarded poly-proportional p=2.3 rather than p=2.7 (ablation) | Guarded poly-proportional · Two agents, normalized valuations | optimal social welfare approximation: 0.905 -> 0.916 | Hurt |
| Set guarded poly-proportional p=2.4 rather than p=2.7 (ablation) | Guarded poly-proportional · Two agents, normalized valuations | optimal social welfare approximation: 0.908 -> 0.916 | Hurt |
| Set guarded poly-proportional p=2.5 rather than p=2.7 (ablation) | Guarded poly-proportional · Two agents, normalized valuations | optimal social welfare approximation: 0.911 -> 0.916 | Hurt |
| Set guarded poly-proportional p=2.6 rather than p=2.7 (ablation) | Guarded poly-proportional · Two agents, normalized valuations | optimal social welfare approximation: 0.914 -> 0.916 | Hurt |
| Set guarded poly-proportional p=2.8 rather than p=2.7 (ablation) | Guarded poly-proportional · Two agents, normalized valuations | optimal social welfare approximation: 0.912 -> 0.916 | Hurt |
Closest papers by meaning
- Online Fair Division with Additional Information (ICML 2026 · similarity 0.91)
- Greedy-Based Online Fair Allocation with Adversarial Input: Enabling Best-of-Many-Worlds Guarantees (AAAI 2024 · similarity 0.91)
- Online Fair Division Meets Reordering Buffers (NeurIPS 2026 · similarity 0.89)
- The Price of Opportunity Fairness in Matroid Allocation Problems (NeurIPS 2025 · similarity 0.88)
- Honor Among Bandits: No-Regret Learning for Online Fair Division (NeurIPS 2024 · similarity 0.88)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.88)
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.