Vi överväger mekanismer utan betalningar för problemet med schemaläggning av icke-relaterade maskiner. Specifikt anser vi sanningsenliga i förväntan randomiserade mekanismer under antagandet att en maskin (spelare) är bunden av sina rapporter: när en maskin ligger och rapporterar värderat i j för en uppgift istället för den faktiska en t i j, Det kommer att utföra för timet i j om det får uppgiften (om inte den deklarerade värdet i j är mindre än det faktiska värdet t i j, I vilket fall, Det kommer att köra för tid t i j ). Vårt huvudsakliga tekniska resultat är en optimal mekanism för en uppgift och n spelare som har approximation förhållande (n + 1)/2. Vi ger också en matchande lägre gräns, som visar att ingen annan sanningsenlig mekanism kan uppnå ett bättre approximationsförhållande. Detta ger omedelbart en approximationsgrad på (n + 1)/2 och n(n + 1)/2 för sociala kostnader och makepan minimization, respektive, för ett antal uppgifter. Vi studerar också priset på anarki av naturliga algoritmer.
Den mekanism som presenteras i Ref har ett snävt approximationsförhållande som är bundet till n+1 2 för inställningen av en enda uppgift.
Scheduling without payments
{'venue': 'SAGT', 'journal': None, 'mag_field_of_study': ['Computer Science']}