Welfare Maximization and Truthfulness in Mechanism Design with Ordinal Preferences
Pourquoi ce travail est-il dans la base ?
Une base qui oublie comment elle a trouvé un travail ne peut pas être vérifiée. Voici les voies qui ont admis celui-ci.
Le tri à trois modèles
les 1 000 travaux triés →Les trois modèles l'ont jugé hors champ.
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.
Résumé
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.
Conservé avec la notice de tri, où il sert de preuve aux étiquettes ci-dessus.
La notice
- Revue
- arXiv (Cornell University)
- Thématique
- Game Theory and Voting Systems
- Domaine
- Economics, Econometrics and Finance
- Établissements canadiens
- University of Waterloo
- Organismes subventionnaires
- —
- Mots-clés
- 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
- Résumé présent dans OpenAlex
- oui