Welfare maximization and truthfulness in mechanism design with ordinal preferences

DOI10.1145/2554797.2554810zbMATH Open1366.91091arXiv1312.1831OpenAlexW2097613630MaRDI QIDQ2988871FDOQ2988871

Authors: Deeparnab Chakrabarty, Chaitanya Swamy 

Publication date: 19 May 2017

Published in: Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1312.1831

Recommendations

• Truthful Mechanisms for Matching and Clustering in an Ordinal World
• Truthful approximations to range voting
• Social welfare in one-sided matchings: random priority and beyond
• Efficiency of truthful and symmetric mechanisms in one-sided matching
• On mechanisms eliciting ordinal preferences

zbMATH Keywords

linear programmingmatroidsmechanism designalgorithmic game theoryordinal preferencescomputational social choice theorysocial welfare and rank approximationtruthfulness for randomized mechanisms

Mathematics Subject Classification ID

Social choice (91B14) Randomized algorithms (68W20) Auctions, bargaining, bidding and selling, and other market models (91B26)

Cites Work

• A hierarchy of polynomial time lattice basis reduction algorithms
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Evaluating Branching Programs on Encrypted Data
• Fully homomorphic encryption using ideal lattices
• Public-key cryptosystems from the worst-case shortest vector problem
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• On lattices, learning with errors, random linear codes, and cryptography
• Trapdoors for hard lattices and new cryptographic constructions
• Title not available (Why is that?)
• (Leveled) fully homomorphic encryption without bootstrapping
• On lattices, learning with errors, random linear codes, and cryptography
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• Trapdoors for lattices: simpler, tighter, faster, smaller
• Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
• New lattice-based cryptographic constructions
• Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based
• Toward basing fully homomorphic encryption on worst-case hardness

Cited In (6)

• Truthful Mechanisms for Matching and Clustering in an Ordinal World
• Size versus truthfulness in the house allocation problem
• Improved truthful rank approximation for rank-maximal matchings
• Tight social welfare approximation of probabilistic serial
• Approximating optimal social choice under metric preferences
• Tradeoffs between information and ordinal approximation for bipartite matching

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)