We study mechanism design problems in the ordinal setting wherein the preferences of agents are described by orderings over outcomes, as opposed to specific numerical values associated with them. This setting is relevant when agents can compare outcomes, but aren't able to evaluate precise utilities for them. Such a situation arises in diverse contexts including voting and matching markets. Our paper addresses two issues that arise in ordinal mechanism design. To design social welfare maximizing mechanisms, one needs to be able to quantitatively measure the welfare of an outcome which is not clear in the ordinal setting. Second, since the impossibility results of Gibbard and Satterthwaite Gibbard73,Satterthwaite75 force one to move to randomized mechanisms, one needs a more nuanced notion of truthfulness. We propose rank approximation as a metric for measuring the quality of an outcome, which allows us to evaluate mechanisms based on worst-case performance, and lex-truthfulness as a notion of truthfulness for randomized ordinal mechanisms. Lex-truthfulness is stronger than notions studied in the literature, and yet flexible enough to admit a rich class of mechanisms circumventing classical impossibility results . We demonstrate the usefulness of the above notions by devising lex-truthful mechanisms achieving good rank-approximation factors, both in the general ordinal setting, as well as structured settings such as (one-sided) matching markets , and its generalizations, matroid and scheduling markets.
Subsequent to the Gibbard-Satterthwaite result, researchers focused on design of randomized mechanisms. As mentioned above, this led to differing notions of truthfulness. Strong truthfulness was proposed by Gibbard @cite_26 . Postlewaite and Schmeidler @cite_30 proposed weak truthfulness and proved that no weakly truthful mechanism on @math or more outcomes, can be (ex ante) Pareto optimal if agents are allowed to have priors on their (own) preferences. Subsequently, @cite_18 removed the prior condition, but prove impossibility of only certain kinds of mechanism. We remark that our lex-truthful mechanisms, which are also weakly truthful, do not contradict these results, since our mechanisms are not Pareto optimal. However, our mechanisms are @math -implementations of Pareto-optimal SCFs, so they satisfy Pareto optimality with probability at least @math . Thus, we bypass the above impossibility results while sacrificing a modicum of Pareto-optimality.
@cite_30 @cite_18 @cite_26
2052444997 28510486 1977126954
A person is said to prefer in the stochastic dominance sense one lottery-over-outcomes over another lottery-over-outcomes if the probability of his (at least) first choice being selected in the first lottery is greater than or equal to the analogous probability in the second lottery, the probability of his at least second choice being selected in the first lottery is greater than or equal to the analogous probability in the second lottery, and so on, with at least one strict inequality. This (partial) preference relation is used to define straightforwardness of a social choice function that maps profiles of ordinal preferences into lotteries over outcomes. Given a prior probability distribution on profiles this partial preference ordering (taking into account the additional randomness) is used to induce a partial preference ordering over social choice functions for each individual. These are used in turn to define ex ante Pareto undominated (efficient) social choice functions. The main result is that it is impossible for a social choice function to be both ex ante efficient and straightforward. We also extend the result to cardinal preferences and expected utility evaluations. Two fundamental notions in microeconomic theory are efficiency---no agent can be made better off without making another one worse off---and strategyproofness---no agent can obtain a more preferred outcome by misrepresenting his preferences. When social outcomes are probability distributions (or lotteries) over alternatives, there are varying degrees of these notions depending on how preferences over alternatives are extended to preference over lotteries. We show that efficiency and strategyproofness are incompatible to some extent when preferences are defined using stochastic dominance (SD) and therefore introduce a natural weakening of SD based on Savage's sure-thing principle (ST). While random serial dictatorship is SD-strategyproof, it only satisfies ST-efficiency. Our main result is that strict maximal lotteries---an appealing class of social decision schemes due to Kreweras and Fishburn---satisfy SD-efficiency and ST-strategyproofness.