Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.05740 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911754859053056 |
|---|---|
| author | Berger, Andre Rouhani, Arman Schröder, Marc |
| author_facet | Berger, Andre Rouhani, Arman Schröder, Marc |
| contents | In this paper, we introduce an improved upper bound for the efficiency of Nash equilibria in utilitarian scheduling games on related machines. The machines have varying speeds and adhere to the Shortest Processing Time (SPT) policy as the global order for job processing. The goal of each job is to minimize its completion time, while the social objective is to minimize the sum of completion times. Our main result provides an upper bound of $2-\frac{1}{2\cdot(2m-1)}$ on the price of anarchy for the general case of $m$ machines. We improve this bound to 3/2 for the case of two machines, and to $2-\frac{1}{2\cdot m}$ for the general case of $m$ machines when the machines have divisible speeds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_05740 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An improved bound for the price of anarchy for related machine scheduling Berger, Andre Rouhani, Arman Schröder, Marc Computer Science and Game Theory In this paper, we introduce an improved upper bound for the efficiency of Nash equilibria in utilitarian scheduling games on related machines. The machines have varying speeds and adhere to the Shortest Processing Time (SPT) policy as the global order for job processing. The goal of each job is to minimize its completion time, while the social objective is to minimize the sum of completion times. Our main result provides an upper bound of $2-\frac{1}{2\cdot(2m-1)}$ on the price of anarchy for the general case of $m$ machines. We improve this bound to 3/2 for the case of two machines, and to $2-\frac{1}{2\cdot m}$ for the general case of $m$ machines when the machines have divisible speeds. |
| title | An improved bound for the price of anarchy for related machine scheduling |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2401.05740 |