Truthfulness via Proxies

2010/11/14 by Shahar Dobzinski, Dobzinski, Shahar, Hu Fu +3
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #cs.GT

paper · pdf · doi:10.48550/arxiv.1011.3232

arxiv created 2010/12/13 · arxiv updated 2015/03/17

Abstract

This short note exhibits a truthful-in-expectation O(\frac log m log log m)-approximation mechanism for combinatorial auctions with subadditive bidders that uses polynomial communication.

Related

• Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
• Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions
• Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier
• Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
• Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier