Welfare Maximization and Truthfulness in Mechanism Design with Ordinal Preferences
Why is this work in the frame?
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
The three-model screen
all 1,000 screened works →All three models called this out of scope.
Theoretical paper on welfare maximization and truthfulness in ordinal mechanism design.
It develops mathematical mechanisms for voting and matching markets, not methods of research.
Theoretical mechanism design and voting/matching markets; computational social choice, not research practice.
Abstract
We study mechanism design problems in the {\em 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~\cite{Gibbard73,Satterthwaite75} force one to move to randomized mechanisms, one needs a more nuanced notion of truthfulness. We propose {\em rank approximation} as a metric for measuring the quality of an outcome, which allows us to evaluate mechanisms based on worst-case performance, and {\em 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 {\em 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 {\em (one-sided) matching markets}, and its generalizations, {\em matroid} and {\em scheduling} markets.
Stored with the screening record, where it is evidence for the labels above.
The record
- Venue
- arXiv (Cornell University)
- Topic
- Game Theory and Voting Systems
- Field
- Economics, Econometrics and Finance
- Canadian institutions
- University of Waterloo
- Funders
- —
- Keywords
- ImpossibilityMechanism designOutcome (game theory)Social choice theoryArrow's impossibility theoremMatching (statistics)Mathematical economicsMaximizationComputer scienceMechanism (biology)Rank (graph theory)Metric (unit)VotingMatroidSocial WelfarePairwise comparisonMicroeconomicsEconomicsMathematicsArtificial intelligenceStatisticsDiscrete mathematicsEpistemologyCombinatorics
- Has abstract in OpenAlex
- yes