Welfare maximization and truthfulness in mechanism design with ordinal preferences
From MaRDI portal
Publication:2988871
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1559544 (Why is no real title available?)
- (Leveled) fully homomorphic encryption without bootstrapping
- A hierarchy of polynomial time lattice basis reduction algorithms
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Bounds for Width Two Branching Programs
- Efficient Fully Homomorphic Encryption from (Standard) LWE
- Evaluating Branching Programs on Encrypted Data
- Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
- Fully homomorphic encryption using ideal lattices
- Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based
- New lattice-based cryptographic constructions
- On lattices, learning with errors, random linear codes, and cryptography
- On lattices, learning with errors, random linear codes, and cryptography
- Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
- Public-key cryptosystems from the worst-case shortest vector problem
- Toward basing fully homomorphic encryption on worst-case hardness
- Trapdoors for hard lattices and new cryptographic constructions
- Trapdoors for lattices: simpler, tighter, faster, smaller
Cited in
(9)- Social welfare in one-sided matchings: random priority and beyond
- Truthful approximations to range voting
- Improved truthful rank approximation for rank-maximal matchings
- Truthful Mechanisms for Matching and Clustering in an Ordinal World
- Tight social welfare approximation of probabilistic serial
- Efficiency of truthful and symmetric mechanisms in one-sided matching
- Size versus truthfulness in the house allocation problem
- Approximating optimal social choice under metric preferences
- On mechanisms eliciting ordinal preferences
This page was built for publication: Welfare maximization and truthfulness in mechanism design with ordinal preferences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988871)
