Abstract
We consider a game-theoretic bin packing problem with identical items, and we study the convergence time to a Nash equilibrium. In the model proposed, users choose their strategy simultaneously. We deal with two bins and multiple bins cases. We consider the case when users know the load of all bins and a case with less information. We consider two approaches, depending if the system can undo movements that lead to infeasible states. In the two bins case, we show an O (log log n) bound when undo movements are allowed. In multiple bins case, we show an O (log n) and an O (nm) bounds when undo movements are allowed and when they are not allowed, respectively. In the case with less information, we show an O (m log n) and an O (n^3 m) bounds when undo movements are allowed and when they are not allowed, respectively.
