From packing rules to cost-sharing mechanisms

Chenhao Zhang () and Guochuan Zhang ()
Additional contact information
Chenhao Zhang: Northwestern University
Guochuan Zhang: Zhejiang University

Journal of Combinatorial Optimization, No 0, 16 pages

Abstract: 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.5$$PoA=1.5. 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 \le 22/15\approx 1.467$$PoA≤22/15≈1.467.

Keywords: Bin packing; Cost-sharing mechanism; PoA (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00519-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v::y::i::d:10.1007_s10878-019-00519-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00519-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().