Selfish Knapsack

Itai Feigenbaum, Matthew P. JohnsonAAAI 2017 · DOI

Introduction

The classic knapsack problem is a cornerstone of combinatorial optimization: given a set of items with specific values and weights, how can a central planner maximize the total value within a fixed capacity? While the algorithmic complexity of this problem is well-understood, its application in decentralized environments introduces a new layer of complexity: strategic behavior. In many real-world scenarios—such as allocating research grants, cloud computing resources, or advertising slots—the items are owned by self-interested agents who prioritize their own utility over the global social welfare.

This paper investigates the "Selfish Knapsack" problem, where agents may manipulate the information they provide to the planner. The authors propose and analyze mechanisms that remain robust even when agents act greedily, focusing on achieving high social welfare without the use of monetary transfers.

The Strategic Model: Understating and Overstating

In the selfish knapsack framework, agents can manipulate the system in two primary ways:

  1. Understating (UM): An agent hides some of the items they actually possess. This might be done to influence the algorithm to pick a specific high-value item that might otherwise be displaced by their other items.
  2. Overstating (OM): An agent reports "fake" items they do not actually own. This is often done to "crowd out" competitors or to trick the algorithm into a specific allocation.

The challenge is to design mechanisms that are strategyproof (where truth-telling is a dominant strategy) or have a low Price of Anarchy (where the social welfare at equilibrium is close to the optimum).

The HALF-GREEDY Mechanism

The central contribution of the paper is the HALF-GREEDY mechanism. This randomized approach balances two simple strategies:

  • GREEDY: Items are sorted by their value-to-size ratio and added until the next item does not fit. Crucially, the authors employ an "else break" rule—if an item fails to fit, the algorithm stops immediately rather than skipping to smaller items. This prevents certain types of strategic manipulation.
  • MAXIMUM-VALUE: The algorithm ignores ratios and simply selects the single most valuable item reported.

By flipping a fair coin and choosing one of these two strategies with 50% probability, the mechanism achieves a 2-approximation of the optimal social welfare.

Key Theoretical Results

Robustness to Overstating

In the Overstating Model (OM), the authors prove that HALF-GREEDY is strategyproof. Furthermore, they demonstrate that the 2-approximation ratio is tight; no randomized strategyproof mechanism can achieve a better constant ratio in this setting. This highlights the necessity of randomization, as no deterministic strategyproof mechanism can provide any constant approximation ratio for the overstating model.

Equilibrium in the Understating Model

While HALF-GREEDY is not strictly strategyproof in the Understating Model (UM), it exhibits a property the authors call "smoothness." If an agent successfully hides items to increase their own utility, the resulting change in the allocation often leads to an increase in total social welfare. Consequently, the authors prove that any Bayes-Nash Equilibrium (BNE) or Coarse Correlated Equilibrium (CCE) induced by the mechanism still maintains a 2-approximation of the optimal welfare.

Specialized Mechanisms

The paper also explores restricted scenarios with higher efficiency:

  • Two-Agent Understating: For exactly two agents, the authors introduce the EQUAL-UTILITY mechanism. By solving a mathematical program that ensures both agents receive identical expected utility, the incentive to hide items is removed. This mechanism is strategyproof and improves the approximation ratio to approximately 1.522.
  • The "One Bad Apple" Scenario: If only one agent is potentially dishonest among many honest participants, the PACIFY-THE-LIAR mechanism is used. It selects a solution that satisfies a specific welfare threshold while maximizing the utility of the potential liar. The authors prove this achieves an approximation ratio of ϕ ≈ 1.618 (the golden ratio), which is the theoretical limit for deterministic mechanisms in this context.

Conclusion and Future Directions

The "Selfish Knapsack" study provides a robust framework for resource allocation without money. By leveraging randomization and understanding the "smoothness" of agent selfishness, the authors provide mechanisms with provable performance guarantees.

However, several challenges remain. A strategyproof mechanism for the "Full Model"—where agents can both hide and fake items simultaneously—that achieves a constant approximation ratio is still an open problem. Additionally, while EQUAL-UTILITY works for two agents, scaling strategyproof mechanisms with low approximation ratios to $n$ agents in the understating model remains a significant hurdle for future research.

Summary updated

BibTeX
@inproceedings{feigenbaum2017selfish,
  author = {Itai Feigenbaum and Matthew P. Johnson},
  title = {{Selfish Knapsack}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10579},
}
Figure