Coordination mechanisms for selfish scheduling
In machine scheduling, a set of jobs must be scheduled on a set of machines so as to minimize some global objective function, such as the makespan, which we consider in this paper. In practice, jobs are often controlled by independent, selfishly acting agents, which each select a machine for process...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2010
|
| Online Access: | http://hdl.handle.net/1721.1/52521 https://orcid.org/0000-0002-9595-459X |
| _version_ | 1826204864136347648 |
|---|---|
| author | Mirrokni, Vahab Li, Li (Erran) Immorlica, Nicole Schulz, Andreas S. |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Mirrokni, Vahab Li, Li (Erran) Immorlica, Nicole Schulz, Andreas S. |
| author_sort | Mirrokni, Vahab |
| collection | MIT |
| description | In machine scheduling, a set of jobs must be scheduled on a set of machines so as to minimize some global objective function, such as the makespan, which we consider in this paper. In practice, jobs are often controlled by independent, selfishly acting agents, which each select a machine for processing that minimizes the (expected) completion time. This scenario can be formalized as a game in which the players are job owners, the strategies are machines, and a player’s disutility is the completion time of its jobs in the corresponding schedule. The equilibria of these games may result in larger-than-optimal overall makespan. The price of anarchy is the ratio of the worst-case equilibrium makespan to the optimal makespan. In this paper, we design and analyze scheduling policies, or coordination mechanisms, for machines which aim to minimize the price of anarchy of the corresponding game. We study coordination mechanisms for four classes of multiprocessor machine scheduling problems and derive upper and lower bounds on the price of anarchy of these mechanisms. For several of the proposed mechanisms, we also prove that the system converges to a pure-strategy Nash equilibrium in a linear number of rounds. Finally, we note that our results are applicable to several practical problems arising in communication networks. |
| first_indexed | 2024-09-23T13:02:34Z |
| format | Article |
| id | mit-1721.1/52521 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:02:34Z |
| publishDate | 2010 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/525212022-09-28T11:40:34Z Coordination mechanisms for selfish scheduling Mirrokni, Vahab Li, Li (Erran) Immorlica, Nicole Schulz, Andreas S. Sloan School of Management Schulz, Andreas S. Schulz, Andreas S. In machine scheduling, a set of jobs must be scheduled on a set of machines so as to minimize some global objective function, such as the makespan, which we consider in this paper. In practice, jobs are often controlled by independent, selfishly acting agents, which each select a machine for processing that minimizes the (expected) completion time. This scenario can be formalized as a game in which the players are job owners, the strategies are machines, and a player’s disutility is the completion time of its jobs in the corresponding schedule. The equilibria of these games may result in larger-than-optimal overall makespan. The price of anarchy is the ratio of the worst-case equilibrium makespan to the optimal makespan. In this paper, we design and analyze scheduling policies, or coordination mechanisms, for machines which aim to minimize the price of anarchy of the corresponding game. We study coordination mechanisms for four classes of multiprocessor machine scheduling problems and derive upper and lower bounds on the price of anarchy of these mechanisms. For several of the proposed mechanisms, we also prove that the system converges to a pure-strategy Nash equilibrium in a linear number of rounds. Finally, we note that our results are applicable to several practical problems arising in communication networks. 2010-03-11T19:49:19Z 2010-03-11T19:49:19Z 2008-12 Article http://purl.org/eprint/type/SubmittedJournalArticle 0304-3975 http://hdl.handle.net/1721.1/52521 Immorlica, Nicole et al. “Coordination mechanisms for selfish scheduling.” Theoretical Computer Science 410.17 (2009): 1589-1598. © 2008 Elsevier B.V. https://orcid.org/0000-0002-9595-459X en_US http://dx.doi.org/10.1016/j.tcs.2008.12.032 Theoretical Computer Science Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Elsevier Andreas Schulz |
| spellingShingle | Mirrokni, Vahab Li, Li (Erran) Immorlica, Nicole Schulz, Andreas S. Coordination mechanisms for selfish scheduling |
| title | Coordination mechanisms for selfish scheduling |
| title_full | Coordination mechanisms for selfish scheduling |
| title_fullStr | Coordination mechanisms for selfish scheduling |
| title_full_unstemmed | Coordination mechanisms for selfish scheduling |
| title_short | Coordination mechanisms for selfish scheduling |
| title_sort | coordination mechanisms for selfish scheduling |
| url | http://hdl.handle.net/1721.1/52521 https://orcid.org/0000-0002-9595-459X |
| work_keys_str_mv | AT mirroknivahab coordinationmechanismsforselfishscheduling AT lilierran coordinationmechanismsforselfishscheduling AT immorlicanicole coordinationmechanismsforselfishscheduling AT schulzandreass coordinationmechanismsforselfishscheduling |