• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Gai, Ling (Gai, Ling.) | Wu, Chenchen (Wu, Chenchen.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Zhang, Weiwei (Zhang, Weiwei.)

Indexed by:

EI Scopus SCIE

Abstract:

In this paper, we introduce the selfish bin packing problem under a new version of cost sharing mechanism based on harmonic mean. The items (as agents) are selfish and intelligent to minimize the cost they have to pay, by selecting a proper bin to fit in. The tricky part is that the one with bigger size pays less and vice versa. We present the motivations and prove the existence of pure Nash Equilibrium under this new defined cost sharing mechanism. Then we study the Price of Anarchy, which is the ratio between the objective value of worst Nash Equilibrium and that of the optimum in the case with central decision maker. We prove the upper bound to be approximately 1.722 and show a 5/3 lower bound for this problem. We then include punishment into the model and prove that in this new model, the Price of Anarchy could be decreased to 3/2.

Keyword:

Selfish bin packing Harmonic mean Price of Anarchy Punishment Nash Equilibrium

Author Community:

  • [ 1 ] [Gai, Ling]Donghua Univ, Glorious Sun Sch Business & Management, Shanghai 200051, Peoples R China
  • [ 2 ] [Wu, Chenchen]Tianjin Univ Technol, Coll Sci, Tianjin 300384, Peoples R China
  • [ 3 ] [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 4 ] [Zhang, Weiwei]Shanghai Univ, Sch Management, Shanghai 201444, Peoples R China

Reprint Author's Address:

  • [Zhang, Weiwei]Shanghai Univ, Sch Management, Shanghai 201444, Peoples R China

Show more details

Related Keywords:

Related Article:

Source :

OPTIMIZATION LETTERS

ISSN: 1862-4472

Year: 2021

Issue: 5

Volume: 16

Page: 1445-1456

1 . 6 0 0

JCR@2022

ESI Discipline: MATHEMATICS;

ESI HC Threshold:31

JCR Journal Grade:2

Cited Count:

WoS CC Cited Count: 0

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:880/6451208
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.