On complexity of single-minded auction

DOI10.1016/j.jcss.2004.04.012zbMath1076.68046OpenAlexW2056772150WikidataQ106376688 ScholiaQ106376688MaRDI QIDQ1765304

Xiaoming Sun, Xiaotie Deng, Ning Chen

Publication date: 23 February 2005

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.04.012

zbMATH Keywords

Time complexityCombinatorial auctionsSingle-minded auctionCommunication complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Special types of economic equilibria (91B52) Combinatorics in computer science (68R05) Auctions, bargaining, bidding and selling, and other market models (91B26)

Related Items

Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs ⋮ Decentralized subcontractor scheduling with divisible jobs ⋮ Walrasian equilibrium: Hardness, approximations and tractable instances ⋮ Approximation of Walrasian equilibrium in single-minded auctions ⋮ On social envy-freeness in multi-unit markets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Walrasian equilibrium with gross substitutes
• Competitive equilibrium in an exchange economy with indivisibilities
• Combinatorial auctions with decreasing marginal utilities
• The assignment game. I: The core
• Combinatorial Auctions: A Survey
• Truth revelation in approximately efficient combinatorial auctions
• On the complexity of equilibria
• Job Matching, Coalition Formation, and Gross Substitutes
• Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree
• On the Complexity of Cooperative Solution Concepts
• Communication Complexity
• Algorithmic Aspects of the Core of Combinatorial Optimization Games
• Existence of an Equilibrium for a Competitive Economy
• On rational computability and communication complexity