Vi skulle alla vilja rösta på best man, men han är aldrig en kandidat" -Kin Hubbard Vi studerar mekanismer för kandidatur som försöker minimera den sociala kostnaden, där väljare och kandidater är förknippade med punkter i någon underliggande metriska utrymme. Den sociala kostnaden för en kandidat är summan av dess avstånd till varje väljare. En del av vårt arbete förutsätter att dessa punkter kan modelleras på den verkliga linjen, men andra resultat av vårt arbete är mer allmänna. En fråga som är nära relaterad till kandidaturvalet är att minimera summan av avstånden för anläggningens läge. Skillnaden är att det i vår miljö finns en fast uppsättning kandidater, medan det stora arbetet på anläggningen plats anser att varje punkt i det metriska utrymmet är en möjlig kandidat. Denna inställning ger upphov till tre typer av urvalsmekanismer för kandidater som skiljer sig åt i fråga om storleken på deras inmatningsutrymme (en enda kandidat, rangordnings- och lokaliseringsmekanismer). Vi studerar förhållandet mellan dessa tre kategorier av mekanismer. Även om det kan tyckas att Blacks 1948 medianalgoritm är optimal för kandidatval på linjen, är detta inte fallet. Vi ger matchande övre och nedre gränser för en mängd olika inställningar. Särskilt när kandidater och väljare står på spel ger vår universellt sanningsenliga spikmekanism en [tät] approximation av två. Vid bedömningen av urvalsmekanismer söker vi efter flera önskvärda egenskaper: (a) effektivitet (minimering av den sociala kostnaden) (b) sannfärdighet (dominant strategi incitament kompatibilitet) och (c) enkelhet (en mindre insatsutrymme). Vi kvantifierar den effekt som sannfärdighet och enkelhet medför på effektiviteten.
Feldman m.fl. Ref överväga scv-mekanismer och strategisäkerhet i den metriska inställningen, och föreslå en 2-snedvridningsmekanism på den verkliga linjen.
On Voting and Facility Location
{'venue': "EC '16", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}