2013/12/06 by Deeparnab Chakrabarty, Chakrabarty, Deeparnab, Chaitanya Swamy +1 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Experimental Behavioral Economics Studies #F.2.2 #FOS: Computer and information sciences #G.2 #Game Theory and Voting Systems #J.4
paper · pdf · doi:10.48550/arxiv.1312.1831
openalex publication_date 2013/12/06 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
We study mechanism design problems in the em ordinal setting wherein the\npreferences of agents are described by orderings over outcomes, as opposed to\nspecific numerical values associated with them. This setting is relevant when\nagents can compare outcomes, but aren't able to evaluate precise utilities for\nthem. Such a situation arises in diverse contexts including voting and matching\nmarkets.\n Our paper addresses two issues that arise in ordinal mechanism design. To\ndesign social welfare maximizing mechanisms, one needs to be able to\nquantitatively measure the welfare of an outcome which is not clear in the\nordinal setting. Second, since the impossibility results of Gibbard and\nSatterthwaite~ citeGibbard73,Satterthwaite75 force one to move to randomized\nmechanisms, one needs a more nuanced notion of truthfulness.\n We propose em rank approximation as a metric for measuring the quality of\nan outcome, which allows us to evaluate mechanisms based on worst-case\nperformance, and em lex-truthfulness as a notion of truthfulness for\nrandomized ordinal mechanisms. Lex-truthfulness is stronger than notions\nstudied in the literature, and yet flexible enough to admit a rich class of\nmechanisms em circumventing classical impossibility results. We demonstrate\nthe usefulness of the above notions by devising lex-truthful mechanisms\nachieving good rank-approximation factors, both in the general ordinal setting,\nas well as structured settings such as em (one-sided) matching markets, and\nits generalizations, em matroid and em scheduling markets.\n