I detta dokument studerar vi problem med mekanismens utformning i den ordinära miljön där agenters preferenser beskrivs genom beställningar över utfall, i motsats till specifika numeriska värden som förknippas med dem. Denna inställning är relevant när agenter kan jämföra resultat, men inte kan utvärdera exakta verktyg för dem. En sådan situation uppstår i olika sammanhang, inklusive röstnings- och matchningsmarknader. Vårt papper tar upp två frågor som uppstår i ordinal mekanism design. För att kunna utforma mekanismer för maximering av social välfärd måste man kvantitativt kunna mäta välfärden för ett resultat som inte är tydligt i ordinära sammanhang. För det andra, eftersom det omöjliga resultatet av Gibbard och Setterthwaite [14, 25] tvingar en att gå över till slumpmässiga mekanismer, behöver man en mer nyanserad uppfattning om sannfärdighet. Vi föreslår rangen approximation som ett mått för att mäta kvaliteten på ett resultat, vilket gör att vi kan utvärdera mekanismer baserade på värsta fall prestanda, och lextruthfulness som en uppfattning om sannfärdighet för randomiserade ordinala mekanismer. Lex-sanning är starkare än föreställningar som studeras i litteraturen, men ändå tillräckligt flexibel för att erkänna en rik klass av mekanismer som kringgår klassiska omöjlighetsresultat. Vi visar nyttan av ovanstående begrepp genom att utforma lex-truthful mekanismer för att uppnå goda rank-tillnärmningsfaktorer, både i den allmänna ordinära inställningen, samt strukturerade inställningar såsom (ensidiga) matchande marknader, och dess generaliseringar, matriser och schemaläggning marknader.
Chakrabarty och Swamy REF införde begreppet rankning approximation för att mäta den sociala välfärden enligt ordinära preferenser.
Welfare maximization and truthfulness in mechanism design with ordinal preferences
{'venue': "ITCS '14", 'journal': None, 'mag_field_of_study': ['Economics', 'Computer Science', 'Mathematics']}