Lower Bounds on the Convergence to Nash Equilibrium in the Bin Packing Game - Miyazawa, Flávio K.; Vignatti, André L. (Anais do Encontro de Teoria da Computação (ETC), 2026)
This paper analyzes the convergence time to Nash equilibrium in the selfish bin packing game under the elementary stepwise system (ESS). By using structural dualities between bin packing and load balancing games, we establish the first non-trivial lower bounds for this problem. We demonstrate that convergence can require exponential time in the general case, while proving a tight bound of Θ(n2) steps for instances with uncapacitated bins under the best-response strategy. Our results introduce proof techniques that depart from traditional potential functions.