Graph explorer

Selfish Knapsack

We consider a selfish variant of the knapsack problem. In our version, the items are owned by agents, and each agent can misrepresent the set of items she owns---either by avoiding reporting some of them (understating), or by reporting additional ones that do not exist (overstating). Each agent's objective is to maximize, within the items chosen for inclusion in the knapsack, the total valuation of her own chosen items. The knapsack problem, in this context, seeks to minimize the worst-case approximation ratio for social welfare at equilibrium. We show that a randomized greedy mechanism has attractive strategic properties: in general, it has a correlated price of anarchy of $2$ (subject to a mild assumption). For overstating-only agents, it becomes strategyproof; we also provide a matching lower bound of $2$ on the (worst-case) approximation ratio attainable by randomized strategyproof mechanisms, and show that no deterministic strategyproof mechanism can provide any constant approximation ratio. We also deal with more specialized environments. For the case of $2$ understating-only agents, we provide a randomized strategyproof $\frac{5+4\sqrt{2}}{7} \approx 1.522$-approximate m