Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions

DOI10.1137/20M1370021zbMath1485.91105OpenAlexW4225941144MaRDI QIDQ5071085

Raghuvansh R. Saxena, Sepehr Assadi, S. Matthew Weinberg, Hrishikesh Khandeparkar

Publication date: 20 April 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1370021

zbMATH Keywords

communication complexitycombinatorial auctionsfractionally subadditivesimultaneous communication

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Algorithmic game theory and complexity (91A68) Mechanism design theory (91B03)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on communication complexity
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Multi-unit auctions: beyond Roberts
• Limitations of VCG-based mechanisms
• The communication requirements of efficient allocations and supporting prices
• Limitations of randomized mechanisms for combinatorial auctions
• Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
• Online Mechanism Design (Randomized Rounding on the Fly)
• Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders
• Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations
• Truth revelation in approximately efficient combinatorial auctions
• An improved approximation algorithm for combinatorial auctions with submodular bidders
• Two Randomized Mechanisms for Combinatorial Auctions
• Rounds in Communication Complexity Revisited
• Incentives in Teams
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Communication Complexity of Simultaneous Messages
• Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
• On Maximizing Welfare When Utility Functions Are Subadditive
• Economic efficiency requires interaction
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• From query complexity to computational complexity
• An impossibility result for truthful combinatorial auctions with submodular valuations
• Elements of Information Theory
• Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms when Demand Queries are NP-hard

This page was built for publication: Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions