Abstract Bin packing is one of the most fundamental problems in resource allocation. Most research on the classical bin packing problem has focused on the design and analysis of centralized packing rules. However, such rules are often infeasible to implement in distributed and decentralized environments, for the sake of both unavailability of global information and incentive compatibility. In this paper, we revisit the cost-sharing mechanisms for selfish bin packing (SBP) in decentralized environments. We first propose a simple and intuitive mechanism with PoA=1.5documentclass12pt{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$PoA=1.5$$end{document}. We then show that for a large class of mechanisms for the SBP, 1.5 is actually a lower bound of PoA. Based on this, we propose new rules for the SBP and design a new mechanism with PoA≤22/15≈1.467documentclass12pt{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$PoA le 22/15approx 1.467$$end{document}.
展开▼
