Lower Bounds on the Convergence to Nash Equilibrium in the Bin Packing Game

• Flávio K. Miyazawa UNICAMP
• André L. Vignatti UFPR

DOI: https://doi.org/10.5753/etc.2026.23180

Resumo

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.

Referências

Bilò, V. (2006). On the packing of selfish items. In 20th Internacional Parallel and Distributed Processing Symposium - IPDPS, pages 9–18. IEEE.

Dósa, G. and Epstein, L. (2018). The convergence time for selfish bin packing. Acta Cybernetica, 23(3):853–865.

Epstein, L. and Kleiman, E. (2008). Selfish bin packing. In ESA ’08: Proceedings of the sixteenth annual European Symposium on Algorithms.

Even-Dar, E., Kesselman, A., and Mansour, Y. (2007). Convergence time to Nash equilibrium in load balancing. ACM Transactions on Algorithms, 3(3):Article 32.

Ma, R., Dósa, G., Han, X., Ting, H.-F., Ye, D., and Zhang, Y. (2013). A note on a selfish bin packing problem. Journal of Global Optimization, 56:1457–1462.

Miyazawa, F. K. and Vignatti, A. L. (2009). Distributed selfish bin packing. In Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on, pages 1–8.

Miyazawa, F. K. and Vignatti, A. L. (2011). Bounds on the convergence time of distributed selfish bin packing. International Journal of Foundations of Computer Science, 22(03):565–582.

Yu, G. and Zhang, G. (2008). Bin packing of selfish items. In 4th International Workshop on Internet and Network Economics, WINE, pages 446–453.