Vi studerar onlineversionen av schemaläggningen problem med själviska agenter övervägas av Archer och Tardos [FOCS 2001]: jobb måste schemaläggas på m parallella relaterade maskiner, var och en av dem ägs av en annan självisk agent. Vår studie fokuserar på allmänna tekniker för att omvandla approximation/konkurrenskraftiga algoritmer till likvärdiga approximativa/konkurrenskraftiga sanningsenliga mekanismer. Våra resultat visar att denna översättning är mer problematisk i online-miljön än i offline. För m = 2, utvecklar vi en offline och en online "översättning" teknik som gör det möjligt att få f (ρ)-tillnärmning/konkurrenskraftig (polynom-tid) mekanism från alla ρ-tillnärmning/konkurrenskraftig (polynom-tid) algoritm, med f (ρ) = ρ (1 + ε) i offline fallet, för varje ε > 0. Däremot innebär en av våra lägre gränser att nätbaserade ρ-konkurrenskraftiga algoritmer i allmänhet inte kan omvandlas till ρ (1 + ε)-konkurrenskraftiga mekanismer, för vissa ε > 0 och varje m ≥ 2. Vi undersöker också frågan om att utforma nya online-algoritmer från grunden för att få effektiva konkurrensmekanismer, och bevisa några lägre gränser på en klass av "naturliga" algoritmer. Slutligen tar vi hänsyn till den variant som infördes av Nisan och Ronen [STOC 1999] där maskiner kan kontrolleras. För denna modell ger vi en O(1)-kompetitiv online-mekanism för alla typer av maskiner och bevisar att några av ovanstående nedre gränser kan brytas.
Auletta et al Ref fokuserar på allmänna tekniker för att omvandla approximation/konkurrenskraftiga algoritmer till likvärdiga approximativa/konkurrenskraftiga sanningsenliga mekanismer och tillämpa dessa på schemaläggning av relaterade maskiner.
On Designing Truthful Mechanisms for Online Scheduling
{'venue': 'In Proc. of the 12th International Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 3499 of Lecture Notes in Computer Science', 'journal': None, 'mag_field_of_study': ['Computer Science']}