Welfare maximization and truthfulness in mechanism design with ordinal preferences

DOI10.1145/2554797.2554810zbMath1366.91091arXiv1312.1831OpenAlexW2097613630MaRDI QIDQ2988871

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)

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

zbMATH Keywords

linear programmingmatroidsordinal preferencesmechanism designalgorithmic game theorycomputational social choice theorysocial welfare and rank approximationtruthfulness for randomized mechanisms

Mathematics Subject Classification ID

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

Related Items (4)

Tradeoffs between information and ordinal approximation for bipartite matching ⋮ Approximating optimal social choice under metric preferences ⋮ Size versus truthfulness in the house allocation problem ⋮ Tight social welfare approximation of probabilistic serial

Cites Work

• Unnamed Item
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• (Leveled) fully homomorphic encryption without bootstrapping
• Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
• Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Trapdoors for hard lattices and new cryptographic constructions
• Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness
• Evaluating Branching Programs on Encrypted Data
• Bounds for Width Two Branching Programs
• Fully homomorphic encryption using ideal lattices
• Public-key cryptosystems from the worst-case shortest vector problem
• Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
• New lattice-based cryptographic constructions
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: Welfare maximization and truthfulness in mechanism design with ordinal preferences