Abstrakt. Vi anser att K-Facility Location spel, där n strategiska agenter rapporterar sina platser i ett metriska utrymme, och en mekanism kartlägger dem till K anläggningar. Agenterna försöker minimera sina anslutningskostnader, nämligen avståndet från deras verkliga plats till närmaste anläggning, och kan felrapportera sin plats. Vi är intresserade av deterministiska mekanismer som är strategiskt säkra, dvs. se till att ingen agent kan dra nytta av att felrapportera sin plats, inte ta till penningöverföringar, och uppnå ett begränsat approximationsförhållande till den totala anslutningskostnaden för agenterna (eller till Lp-normen för anslutningskostnaderna, för vissa p  på [1, ∞] eller för p = ∞). Vårt huvudresultat är en elegant karakterisering av deterministiska strategisäkra mekanismer med ett begränsat approximationsförhållande för 2-Facility Placering på linjen. I synnerhet visar vi att för fall med n ≥ 5 agenter, varje sådan mekanism antingen erkänner en unik diktator, eller alltid placera faciliteterna på den vänstra och den högra platsen av instansen. Som en följd av detta uppnår vi att det bästa approximativa förhållande som kan uppnås genom deterministiska strategisäkra mekanismer för problemet att lokalisera 2 anläggningar på linjen för att minimera den totala anslutningskostnaden är exakt n − 2. En annan ganska överraskande konsekvens är att TWO-EXTREMES-mekanismen (Procaccia och Tennenholtz, EC 2009) är den enda deterministiska anonyma strategisäkra mekanismen med ett begränsat approximationsförhållande för 2-Facility Placering på linjen. Beviset på karakteriseringen använder flera nya idéer och tekniska verktyg, som ger nya insikter i beteendet hos deterministiska strategisäkra mekanismer för K-Facility Placering spel, och kan vara av oberoende intresse. Med hjälp av ett av dessa verktyg visar vi att det för varje K ≥ 3 inte finns några deterministiska anonyma strategisäkra mekanismer med ett begränsat approximationsförhållande för K-Facility Placering på linjen, även för enkla instanser med K + 1 agenter. Dessutom, bygger på karakteriseringen för linjen, visar vi att det inte finns några deterministiska strategisäkra mekanismer med ett begränsat approximationsförhållande för 2-Facility Placering på mer allmänna metriska utrymmen, vilket är sant även för enkla fall med 3 agenter belägna i en stjärna.
Fotakis m.fl. REF bevisar den förmodade nedre gränsen för (n) för deterministiska SP-algoritmer för anläggningens lokaliseringsproblem på linjen.
On the power of deterministic mechanisms for facility location games
{'venue': 'ICALP', 'journal': None, 'mag_field_of_study': ['Computer Science']}