Vi bestämmer kvaliteten på randomiserade sociala valmekanismer i en miljö där agenterna har metriska preferenser: varje agent har en kostnad för varje alternativ, och dessa kostnader utgör ett mått. Vi utgår från att dessa kostnader är okända för mekanismerna (och möjligen även för agenterna själva), vilket innebär att vi inte bara kan välja det optimala alternativet, dvs. Alternativet som minimerar den totala agentkostnaden (eller medianagentkostnaden). Vi antar dock att agenterna känner till sina ordinära preferenser som framkallas av det metriska utrymmet. Vi undersöker randomiserade sociala valfunktioner som endast kräver denna ordinära information och väljer ett alternativ som är bra i förväntan med avseende på kostnaderna från metriska. För att kvantifiera hur bra en randomiserad social valfunktion är, band vi snedvridningen, vilket är det värsta fallet förhållandet mellan den förväntade kostnaden för det valda alternativet och kostnaden för det optimala alternativet. Vi tillhandahåller nya distorsionsgränser för en mängd olika randomiserade mekanismer, både för allmänna mätvärden och för viktiga specialfall. Våra resultat visar en betydande förbättring av förvrängningen över deterministiska mekanismer.
Anshelevich m.fl. REF undersöker kvaliteten på randomiserade sociala urvalsmekanismer när agenter har metriska preferenser, men endast ordinal information är tillgänglig för mekanismen.
Randomized Social Choice Functions Under Metric Preferences
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}