Vi anser att problemet med makespan minimering på m orelaterade maskiner i samband med algoritmisk mekanism design, där maskinerna är de strategiska spelarna. Detta är en flerdimensionell schemaläggningsdomän, och de enda kända positiva resultaten för makespan minimization i en sådan domän är O(m)-uppskattning sanningsenliga mekanismer [22, 20]. Vi studerar ett välmotiverat specialfall av detta problem, där bearbetningstiden för ett arbete på varje maskin antingen kan vara "låg" eller "hög", och de låga och höga värdena är offentliga och jobbberoende. Detta bevarar multidimensionelliteten i domänen, och generaliserar de begränsade maskinerna (t.ex., {pj, ❌}) inställning i schemaläggning. Vi ger en allmän teknik för att konvertera alla c-tillnärmning algoritm till en 3c-tillnärmning sanningsenlig-in-förväntning mekanism. Detta är ett av de få kända resultat som visar hur man exporterar approximationsalgoritmer för ett flerdimensionellt problem till sanningsenliga mekanismer på ett svart-box-sätt. När de låga och höga värdena är desamma för alla jobb, vi utforma en deterministisk 2- approximation sanningsenlig mekanism. Dessa är de första sanningsenliga mekanismerna med icke-triviala prestandagarantier för en flerdimensionell schemaläggningsdomän. Våra konstruktioner är nya i två avseenden. För det första använder vi oss inte av eller förlitar oss på tydliga prisdefinitioner för att bevisa sannfärdighet; istället utformar vi algoritmer som uppfyller cykelmonotonicitet. Cykelmonotonicitet [23] är ett nödvändigt och tillräckligt villkor för sannfärdighet, är en generalisering av värdemonotonicitet för flerdimensionella domäner. Samtidigt som värdemonotonicitet har använts i stor utsträckning och framgångsrikt för att utforma sanningsenliga mekanismer inom endimensionella domäner, är vårt första arbete som utnyttjar cykelmonotonicitet i den multidimensionella inställningen. För det andra, våra randomiserade mekanismer erhålls genom att först konstruera en fraktionerad sanningsenlig mekanism för en fraktionerad avslappning av problemet, och sedan omvandla det till en sanningsenligin-expectation mekanism. Detta bygger på en teknik [16], och visar nyttan av fraktionerade mekanismer i sanningsenlig mekanism design.
Lavi och Swamy REF överväga ett specialfall av samma problem-namely när bearbetningstiderna har endast två möjliga värden låg eller hög-och utforma en deterministisk 2- approximation sanningsenlig mekanism.
Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity
{'venue': "EC '07", 'journal': None, 'mag_field_of_study': ['Computer Science']}