Vi studerar samordningsmekanismer som syftar till att minimera den viktade summan av slutförandetider för jobb i samband med själviska schemaläggningsproblem. Vårt mål är att utforma lokala policyer som uppnår ett bra pris på anarki i den resulterande jämvikt för orelaterade maskin schemaläggning. För att uppnå dessa approximativa gränser, introducerar vi en ny teknik som konceptuellt enkelt, verkar vara ganska kraftfull. Metoden innebär att kartlägga strategivektorer in i ett noga valt inre produktutrymme; kostnaderna visas motsvara normen i detta utrymme, och Nash tillstånd har också en enkel beskrivning. Med denna struktur på plats kan vi bevisa ett antal resultat, enligt följande. För det första anser vi att Smiths regel, som beställer jobben på en maskin i stigande bearbetning tid till vikt förhållande, och visar att det uppnår en approximation förhållande 4. Vi visar också att detta är bästa möjliga för deterministisk, icke-förebyggande, starkt lokal politik. Eftersom Smiths regel alltid är optimal för ett givet fast uppdrag, kan detta verka föga förvånande, men vi visar då att bättre approximativa proportioner kan uppnås om antingen företräde eller randomisering tillåts. Vi bevisar att ProportionalSharing, en förebyggande starkt lokal politik, uppnår en approximationsgrad på 2,618 för den viktade summan av slutförandetider och en approximationsgrad på 2,5 i det oviktade fallet. Vi noterar också att dessa gränser är snäva. Därefter betraktar vi Rand, en naturlig icke förebyggande men randomiserad politik. Vi visar att den uppnår en approximationsgrad på högst 2.13; dessutom, om summan av de viktade genomförandetiderna är försumbar jämfört med kostnaden för den optimala lösningen, förbättras detta till π/2. Slutligen visar vi att både ProportionalSharing och Rand framkallar potentiella spel, och därmed alltid har en ren Nash jämvikt (till skillnad från Smiths regel). Detta gör att vi kan utforma den första combinatorial konstant-faktor approximation algoritm minimera viktad slutförande tid för orelaterade maskin schemaläggning. Det uppnår en faktor på 2 + för alla > 0, och innebär att efterlikna bästa svar dynamik med hjälp av en variant av ProportionalSharing som policy.
Mycket nyligen betraktade REF som ett mål den viktade summan av genomförandetiderna.
Inner product spaces for MinSum coordination mechanisms
{'venue': "STOC '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}