Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.20711 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915084829196288 |
|---|---|
| author | Wang, Wenqian Xu, Chenyang Zhang, Yuhao |
| author_facet | Wang, Wenqian Xu, Chenyang Zhang, Yuhao |
| contents | In this paper, we study the classic optimization problem of Related Machine Online Load Balancing under the conditions of selfish machines and selfish jobs. We have $m$ related machines with varying speeds and $n$ jobs arriving online with different sizes. Our objective is to design an online truthful algorithm that minimizes the makespan while ensuring that jobs and machines report their true sizes and speeds.
Previous studies in the online scenario have primarily focused on selfish jobs, beginning with the work of Aspnes et al. (JACM 1997). An $O(1)$-competitive online mechanism for selfish jobs was discovered by Feldman, Fiat, and Roytman (EC 2017). For selfish machines, truthful mechanisms have only been explored in offline settings, starting with Archer and Tardos (FOCS 2001). The best-known results are two PTAS mechanisms by Christodoulou and Kovács (SICOMP 2013) and Epstein et al. (MOR 2016).
We design an online mechanism that is truthful for both machines and jobs, achieving a competitive ratio of $O(\log m)$. This is the first non-trivial two-sided truthful mechanism for online load balancing and also the first non-trivial machine-side truthful mechanism. Furthermore, we extend our mechanism to the $\ell_q$ norm variant of load balancing, maintaining two-sided truthfulness with a competitive ratio of $\tilde{O}(m^{\frac{1}{q}(1-\frac{1}{q})})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_20711 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | How to Balance the Load Online When Jobs and Machines Are Both Selfish? Wang, Wenqian Xu, Chenyang Zhang, Yuhao Data Structures and Algorithms Computer Science and Game Theory In this paper, we study the classic optimization problem of Related Machine Online Load Balancing under the conditions of selfish machines and selfish jobs. We have $m$ related machines with varying speeds and $n$ jobs arriving online with different sizes. Our objective is to design an online truthful algorithm that minimizes the makespan while ensuring that jobs and machines report their true sizes and speeds. Previous studies in the online scenario have primarily focused on selfish jobs, beginning with the work of Aspnes et al. (JACM 1997). An $O(1)$-competitive online mechanism for selfish jobs was discovered by Feldman, Fiat, and Roytman (EC 2017). For selfish machines, truthful mechanisms have only been explored in offline settings, starting with Archer and Tardos (FOCS 2001). The best-known results are two PTAS mechanisms by Christodoulou and Kovács (SICOMP 2013) and Epstein et al. (MOR 2016). We design an online mechanism that is truthful for both machines and jobs, achieving a competitive ratio of $O(\log m)$. This is the first non-trivial two-sided truthful mechanism for online load balancing and also the first non-trivial machine-side truthful mechanism. Furthermore, we extend our mechanism to the $\ell_q$ norm variant of load balancing, maintaining two-sided truthfulness with a competitive ratio of $\tilde{O}(m^{\frac{1}{q}(1-\frac{1}{q})})$. |
| title | How to Balance the Load Online When Jobs and Machines Are Both Selfish? |
| topic | Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2412.20711 |