Selfish bin packing under Harmonic mean cost sharing mechanism
| Autor: | Ling Gai, Dachuan Xu, Chenchen Wu, Weiwei Zhang |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Computer Science::Computer Science and Game Theory
Mathematical optimization Control and Optimization Bin packing problem Harmonic mean TheoryofComputation_GENERAL Computational intelligence Upper and lower bounds Bin symbols.namesake Nash equilibrium Value (economics) symbols Price of anarchy Mathematics |
| Zdroj: | Optimization Letters. 16:1445-1456 |
| ISSN: | 1862-4480 1862-4472 |
| DOI: | 10.1007/s11590-021-01782-5 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink