We study weighted, capacitated cost-sharing games on parallel-link networks, also known as bin packing games. We focus on an integer-splittable variant in which items of varying sizes can be divided into integer units and assigned to bins with heterogeneous capacities and costs. Although this setting has practical relevance, it remains largely unexplored in the context of cost-sharing games. We prove that, even in the most restrictive regular instances, where items and bins are all identical, a pure Nash equilibrium (PNE) might not exist. This is in contrast with the classic unsplittable variant of the game, where a PNE is guaranteed to exist even with non-identical items and in more general series-parallel networks. On the positive side, we present two simple polynomial-time algorithms that, when combined, compute a \(\frac{1}{3} (2 + \sqrt{7})\) -approximate PNE for regular instances. For general (non-regular) instances with arbitrary item sizes, bin capacities, and non-increasing unit cost functions, we provide a polynomial-time algorithm that guarantees a \(H_\beta \) -approximate PNE, where \(\beta \) is the minimum between the largest item size and largest bin capacity, and \(H_\beta \) denotes \(\beta \) -th harmonic number. Moreover, if the largest item size does not exceed the smallest bin capacity, or if all bins have identical unit cost at saturation, the same algorithm yields a 2-approximate PNE.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Integer-Splittable Bin Packing Games

  • Bainian Hao,
  • Carla Michini

摘要

We study weighted, capacitated cost-sharing games on parallel-link networks, also known as bin packing games. We focus on an integer-splittable variant in which items of varying sizes can be divided into integer units and assigned to bins with heterogeneous capacities and costs. Although this setting has practical relevance, it remains largely unexplored in the context of cost-sharing games. We prove that, even in the most restrictive regular instances, where items and bins are all identical, a pure Nash equilibrium (PNE) might not exist. This is in contrast with the classic unsplittable variant of the game, where a PNE is guaranteed to exist even with non-identical items and in more general series-parallel networks. On the positive side, we present two simple polynomial-time algorithms that, when combined, compute a \(\frac{1}{3} (2 + \sqrt{7})\) -approximate PNE for regular instances. For general (non-regular) instances with arbitrary item sizes, bin capacities, and non-increasing unit cost functions, we provide a polynomial-time algorithm that guarantees a \(H_\beta \) -approximate PNE, where \(\beta \) is the minimum between the largest item size and largest bin capacity, and \(H_\beta \) denotes \(\beta \) -th harmonic number. Moreover, if the largest item size does not exceed the smallest bin capacity, or if all bins have identical unit cost at saturation, the same algorithm yields a 2-approximate PNE.