Selfish Vector Packing

We study the multidimensional vector packing problem with selfish items. An item is a d-dimensional non-zero vector, whose rational components are in [0, 1]. A set of items can be packed into a bin if for every $$1 \le i \le d$$ , the sum of the ith components of all items of this set does not exceed 1. Items share costs of bins proportionally to the $$\ell _1$$ -norms of items, and each item corresponds to a selfish player in the sense that it prefers to be packed into a bin minimizing its resulting cost. This defines a class of games called vector packing games. We show that any game in this class has a packing that is a strong equilibrium, and that both the strong price of anarchy and the strong price of stability are logarithmic in d. We also provide an algorithm that constructs a packing that is a strong equilibrium. Furthermore, we show improved and nearly tight lower and upper bounds of $$d+0.657067$$ and $$d+0.657143$$ , respectively, for any $$d\ge 2$$ , on the price of anarchy. This exhibits a difference between the multidimensional problem and the one-dimensional problem, for which that price of anarchy is at most 1.6428.