Ett av de mest grundläggande resultaten på området för mekanismutformning säger att varje utilitarisk social valfunktion medger en mekanism som sanningsenligt genomför den. I skarp kontrast till detta konstaterande visar det sig, när man betraktar en icke-utilitär social valfunktion, att det inte går att ge några garantier, d.v.s. Det finns icke-användande funktioner som inte kan genomföras på ett sanningsenligt sätt. Mot bakgrund av detta är ett av forskningens mest naturliga och spännande mål att förstå de inneboende begränsningarna i infrastrukturen för sanningsenliga mekanismer för icke-användande sociala val funktioner. I denna uppsats fokuserar vi vår uppmärksamhet på att studera de gränser som är påtvingade av sannfärdighet för två icke-användande multiparameteroptimeringsproblem. Den första är arbetsbördan minimering i inter-domain routing problem, som modellerar ett av de mest principiella problem i utformningen av routing protokoll, och den andra är de orelaterade maskiner schemaläggning problem, som är en av de mest klassiska och allmänna varianter inom schemaläggning. Våra viktigaste resultat kan sammanfattas kortfattat enligt följande: 1. Vi bevisar att alla sanningsenliga deterministiska mekanismer, och alla universella sanningsenliga randomiserade mekanismer för arbetsbördan minimering i inter-domain routing problem inte kan uppnå en approximation garanti som är bättre än 2. Dessa resultat förbättrar de nuvarande lägre gränserna (1 + 5)/2 och 1 618 och (3 + 5)/4, som beror på Mu'alem och Schapira [SODA '07]. 2. Utgångspunkten är följande: Vi etablerar en lägre gräns på 1 + 2  och 2.414 om det uppnåeliga approximationsförhållandet för någon sanningsenlig deterministisk mekanism för de icke-relaterade maskinerna schemaläggning problem när antalet maskiner är minst 3. Denna lägre gräns är jämförbar med ett resultat som nyligen uppnåtts av Christodoulou, Koutsoupias och Vidali [SODA '07]. Ändå är vårt tillvägagångssätt betydligt enklare och kan därmed kasta lite nytt ljus över grunden för detta problem. * En utdragen abstrakt av denna uppsats framträdde i
Gamzu Ref visade sig ha en lägre gräns på 2, vilket är den mest kända nedre gränsen för detta problem och det gäller även randomiserade mekanismer.
Improved Lower Bounds for Non-Utilitarian Truthfulness ∗
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Computer Science']}