Research map / Multi-agent systems and games / Games and equilibria
Selfish Knapsack
Itai Feigenbaum, Matthew Johnson
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 HALF-GREEDY in the overstating model | Knapsack mechanism with fake-item reports allowed · Overstating model | worst-case approximation ratio: 2 | Improved |
| Require strategyproofness for randomized mechanisms in the overstating model | Knapsack mechanisms · Overstating model | worst-case approximation ratio: 2 | Hurt |
| Require deterministic strategyproofness in the overstating model | Knapsack mechanisms · Overstating model | worst-case approximation ratio | Hurt |
| Use HALF-GREEDY at equilibrium | Knapsack mechanism with hiding-only reports · Understating model | correlated price of anarchy: 2 | Improved |
| Use HALF-GREEDY when agents do not use malicious strategies | Knapsack mechanism with hiding and fake-item reports · Full model | approximation ratio at BNE: 2 | Improved |
| Constrain the solution to equal expected utilities when single-agent optima are not sufficient | EQUAL-UTILITY · Understating model, 2 agents | approximation ratio: \frac{5+4\sqrt{2}}{7} \approx 1.522 | Improved |
| Use EQUAL-UTILITY rather than a deterministic strategyproof mechanism | Knapsack mechanism · Understating model, 2 agents | approximation ratio: \frac{5+4\sqrt{2}}{7} \approx 1.522 versus \phi=\frac{1+\sqrt{5}}{2} \approx 1.618 | Improved |
| Use PACIFY-THE-LIAR to select the manipulator's favorite qualifying solution | Knapsack mechanism with all but one agent honest · Understating model, n-1 agents honest | approximation ratio: \phi=\frac{1+\sqrt{5}}{2} \approx 1.618 | Improved |
| Adapt HALF-GREEDY by replacing MAXIMUM-VALUE with NEXT | Knapsack with known item quality and private size · KQUS | approximation ratio: 2 | Improved |
| Require randomized strategyproofness in KQUS | Knapsack mechanisms · KQUS | worst-case approximation ratio: 2 | Hurt |
| Require deterministic strategyproofness in KQUS | Knapsack mechanisms · KQUS | worst-case approximation ratio | Hurt |
Closest papers by meaning
- Plant-and-Steal: Truthful Fair Allocations via Predictions (NeurIPS 2024 · similarity 0.87)
- Optimal Mechanism in a Dynamic Stochastic Knapsack Environment (AAAI 2024 · similarity 0.86)
- On the Power of Randomization for Obviously Strategy-Proof Mechanisms (AAAI 2025 · similarity 0.86)
- A Unified Framework for Uniform-Price Resource Allocation Mechanisms (NeurIPS 2026 · similarity 0.85)
- Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting (NeurIPS 2024 · similarity 0.85)
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.85)
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.
