The communication requirements of efficient allocations and supporting prices

DOI10.1016/j.jet.2004.10.007zbMath1132.91531OpenAlexW2161272173MaRDI QIDQ2496786

I. R. Segal', Noam Nisan

Publication date: 20 July 2006

Published in: Journal of Economic Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jet.2004.10.007

zbMATH Keywords

approximationcommunication complexitypreference elicitationcombinatorial auctionsdistributional complexitysubstitutable itemssubmodular valuationsmessage space dimensionhomogeneous itemsinformational efficiency of prices

Mathematics Subject Classification ID

Economics of information (91B44)

Related Items (48)

An efficient ascending auction for private valuations ⋮ An options-based solution to the sequential auction problem ⋮ The communication cost of selfishness ⋮ Ad Exchange: Envy-Free Auctions with Mediators ⋮ Combinatorial Auctions with Conflict-Based Externalities ⋮ Iterative Auction Design for Tree Valuations ⋮ Setting lower bounds on truthfulness ⋮ Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions ⋮ Ascending price Vickrey auctions for general valuations ⋮ Fraction auctions: the tradeoff between efficiency and running time ⋮ Efficient sets are small ⋮ Minimizing the total weighted completion time of fully parallel jobs with integer parallel units ⋮ Gross substitutability: an algorithmic survey ⋮ Mechanism design and communication networks ⋮ Comparing multiagent systems research in combinatorial auctions and voting ⋮ A Dual Approach for Dynamic Pricing in Multidemand Markets ⋮ Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices ⋮ Computational implementation ⋮ Unnamed Item ⋮ A characterization of the existence of succinct linear representation of subset-valuations ⋮ Inapproximability of Truthful Mechanisms via Generalizations of the Vapnik--Chervonenkis Dimension ⋮ Unnamed Item ⋮ Truthful randomized mechanisms for combinatorial auctions ⋮ Limitations of VCG-based mechanisms ⋮ The communication requirements of social choice rules and supporting budget sets ⋮ When Are Welfare Guarantees Robust ⋮ Composition of semi-LTCs by two-wise tensor products ⋮ Inapproximability results for combinatorial auctions with submodular utility functions ⋮ Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents ⋮ Truthfulness with value-maximizing bidders: on the limits of approximation in combinatorial markets ⋮ The communication complexity of private value single-item auctions ⋮ Introduction to computer science and economic theory ⋮ Multi-unit auctions: beyond Roberts ⋮ Combinatorial auctions ⋮ Informational limitations of ascending combinatorial auctions ⋮ On the existence of Pareto efficient and envy-free allocations ⋮ Economic efficiency requires interaction ⋮ Combinatorial auctions with decreasing marginal utilities ⋮ Computing Walrasian equilibria: fast algorithms and structural properties ⋮ On the Approximability of Combinatorial Exchange Problems ⋮ Truthful approximation mechanisms for restricted combinatorial auctions ⋮ Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions ⋮ A Simple and Approximately Optimal Mechanism for a Buyer with Complements ⋮ Market Pricing for Matroid Rank Valuations ⋮ Combinatorial auctions with endowment effect ⋮ Fair by design: multidimensional envy-free mechanisms ⋮ Optimally Deceiving a Learning Leader in Stackelberg Games ⋮ Auction design with costly preference elicitation

Uses Software

• CABOB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Incentive compatibility and informational requirements
• The competitive allocation process is informationally efficient uniquely
• Decentralized resource allocation and increasing returns
• On the informational size of message spaces
• The space complexity of approximating the frequency moments
• Walrasian equilibrium with gross substitutes
• Competitive equilibrium in an exchange economy with indivisibilities
• Hardness results for multicast cost sharing.
• Finite allocation mechanisms: approximate walrasian versus approximate direct revelation
• Comparing finite mechanisms
• The English auction with differentiated commodities
• The package assignment model.
• Bundling equilibrium in combinatorial auctions
• Combinatorial auctions with decreasing marginal utilities
• Computationally Manageable Combinational Auctions
• Combinatorial Auctions: A Survey
• CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions
• A New and Improved Design for Multiobject Iterative Auctions
• Truth revelation in approximately efficient combinatorial auctions
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Efficiency and Decentralization in the Pure Theory of Public Goods
• Lower Bounds on Information Transfer in Distributed Computations
• Job Matching, Coalition Formation, and Gross Substitutes
• Communication Complexity

This page was built for publication: The communication requirements of efficient allocations and supporting prices