Abstract
We consider complexity issues for a special type of combinatorial auctions, the single-minded auction, where every agent is interested in only one subset of the commodities. First, we present a matching bound on the communication complexity for the single-minded auction under a general communication model. Next, we prove that it is NP-hard to decide whether Walrasian equilibrium exists in a single-minded auction. Finally, we establish a polynomial size duality theorem for the existence of Walrasian equilibrium for the single-minded auction. © 2004 Elsevier Inc. All rights reserved.
| Original language | English |
|---|---|
| Pages (from-to) | 675-687 |
| Journal | Journal of Computer and System Sciences |
| Volume | 69 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - Dec 2004 |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Funding
This research is fully supported by a research grant (CityU1081/02E) from Research Grants Council of Hong Kong SAR, China, and research grants (60223004, 60321002, 60273045) from Natural Science Foundation of China. We thank the anonymous reviewers for their suggestions for improving this work. We especially thank Andrew C. Yao for his helpful discussions and comments on this work.
Research Keywords
- Combinatorial auctions
- Communication complexity
- Single-minded auction
- Time complexity
RGC Funding Information
- RGC-funded
Fingerprint
Dive into the research topics of 'On complexity of single-minded auction'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver