Abstrakt. I maskinschemaläggningen måste en uppsättning n-jobb schemaläggas på en uppsättning m-maskiner. Varje jobb i har en processtid av pij på maskin j och målet är att schemalägga jobb för att minimera någon global objektiv funktion, såsom den maximala makespan av schemat som beaktas i detta papper. Ofta i praktiken styrs varje arbete av en oberoende självisk agent som väljer att schemalägga sitt arbete på maskin vilket minimerar (förväntade) slutförandet av sitt arbete. Detta scenario kan formaliseras som ett spel där spelarna är jobbägare; strategierna är maskiner; och disutility till varje spelare i en strategi profil är slutförandet av sitt jobb i motsvarande schema (en spelares mål är att minimera hans disutility). Likvilibria av dessa spel kan resultera i större än optimal övergripande makespan. Förhållandet av det värsta fallet jämvikt görpan till den optimala makepan kallas priset på anarki i spelet. I detta papper, vi utforma och analysera schemaläggning politik, eller samordningsmekanismer, för maskiner som syftar till att minimera priset på anarki (begränsat till ren Nash equilibria) i motsvarande spel. Vi studerar samordningsmekanismer för fyra klasser av flerprocessor maskin schemaläggning problem och härleda övre och nedre gränser för priset på anarki av dessa mekanismer. För flera av de föreslagna mekanismerna kan vi också bevisa att systemet konvergerar till en ren Nash-jämvikt i ett linjärt antal rundor. Slutligen noterar vi att våra resultat är tillämpliga på flera praktiska problem som uppstår i nätverk.
Immorlica m.fl. REF studerar fyra samordningsmekanismer för olika maskinschemaläggningsproblem och kartlägger resultaten för dessa problem.
Coordination mechanisms for selfish scheduling
{'venue': 'IN PROCEEDINGS OF THE FIRST ANNUAL INTERNATIONAL WORKSHOP ON INTERNET AND NETWORK ECONOMICS (WINE), VOLUME 3828 OF LECTURE NOTES IN COMPUTER SCIENCE', 'journal': None, 'mag_field_of_study': ['Computer Science']}